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: NeurIPS 2023 poster (2023)
Keywords: causal discovery
experimental design
active learning
neural networks
TL;DR: We propose GIT, a novel gradient-based intervention targeting method, which improves the performance of causal discovery, especially in the low data regime.

Abstract: Inferring causal structure from data is a challenging task of fundamental importance in science. Often, observational data alone is not enough to uniquely identify a system’s causal structure. The use of interventional data can address this issue, however, acquiring these samples typically demands a considerable investment of time and physical or financial resources. In this work, we are concerned with the acquisition of interventional data in a targeted manner to minimize the number of required experiments. 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 the intervention targeting 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.

Trust Your V: Gradient-based Intervention Targeting for Causal Discovery
Mateusz Olko 12+ Michal Z
Aleksandra Nowak 2,3,4
Nino Scherrer Yashas Annadani Stefan Bauer
Lukasz Kuciúskia.7 Piotr 2itos2.8.7
Warsaw University, 2IDEAS NCBR,
Jagiellonian Univeristy. Faculty of Mathematics and Computer Science, Jagiellonian University, Doctoral School of Exact and Natural Sciences,
'ETH Zurich, Helmholtz, TU Munich, ddepssesse.a
Institute of Mathematics, Polish Academy of Sciences
Abstract
Inferring causal structure from data is challenging task of fundamental importance in science. Often, observational data alone not enough to uniquely identify a system's causal structure. The of interventional data can address this issue, however, acquiring these samples typically demands a considerable investment of time and physical financial resources. In this work, acquisition of interventional data in targeted manner to minimize the number of required experiments. We propose a novel Gradient-based Intervention Targeting method, abbreviated GIT, that 'trusts' the gradient estimator of a gradient-basse causal discovery framework to provide signals for the intervention targeting fune- tion. 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.
concerned with the
1 Introduction
Estimating causal structure from data, commonly known as causal discovery, is central to the progress of science [Pearl, 2009]. Real-world systems often be explained as composition of smaller parts connected by causal relationships. Understanding this underlying structure essential for making accurate predictions about the system's behavior after perturbation treatment has been applied [Peters et al., 2016]. Causal discovery methods have been successfully deployed in various fields, such biology [Sachs al., 2005, Triantafillou al., 2017, Glymour al., 2019], medicine [Shen et al., 2020, Castro et al., 2020, Wu et al., 2022], earth system science [Ebert-Uphoff and Deng, 2012], neuroscience [Sanchez-Romer] decomposition has been shown to enable sample- -fffcceffficintt learning and fast adaptation to distribution shifts by only updating subset of parameters [Bengio al., 2020, Scherrer al., 2022].
al., 2019]. In machine learning, causal
Observational data, that is the data obtained directly from the unperturbed system, are, in general, insufficient identify system's causal structure and only allow to determine the structure up the so-called Markov Equivalence Class [Spirtes et al., 2000a, Peters et al., 2017]. (]. To overcome this limited identifiability problem, causal discovery algorithms commonly leverage interventional data [Hauser and Bühlmann, 2012, Brouillard et al., 2020, Ke et al., 2019], which are acquired by gathering data from an experiment perturbing a part of the system [Spirtes al., 2000b, Pearl, 2009]. The field of experimental design [Lindley, 1956, Murphy, 2001, Tong and Koller, 2001] is concerned with the
'These authors contributed equally. Corresponding author: mateusz. olk.ogmaill.coommmmmmmmmmmmm...m
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

acquisition of interventional data in a targeted manner to minimize the number of required experiments, which often requires spending a significant amount of time and physical or financial resources.
In this work, we introduce simple and effective experi- mental design algorithm called Gradient-based Interven- tion Targeting, or GIT for short, see Figure 1. GIT can be easily combined with various gradient-based causal dis- covery frameworks to provide an efficient active selection of intervention targets. Our method, which is grounded in the ideas from active and curriculum learning [Settles et al., 2007, Graves et al., 2017, Ash et al., 2020], collects interventional data that induce the biggest gradient on parameters of causal structure. GIT leverages the gradient- based nature of the underlying causal discovery framework and achieves better performance than the contemporary baselines.
Goadintt based Intervention Targeting 1611)
Sovee sing V1C
Gradea: beaed Caradl Discovery
(X-)
Dae
Innovention
do(X.)
Dar Dar 122
Figure 1: Overview of GIT's usage in a gradient-based causal discovery framework. The framework infers posterior distribu- tion over graphs from observational terventional data (denoted as Dobs and Denc) through gradient- basedd optimization. The distribution over graphs and the gradient es- timator (-(-) then used hy GIT in order to score the intervention targets hased on the magnitude of the estimated gradients. The intervention target with the highest score is then selected. upon which the intervention is performed. New interventional data Die are then collected and the procedure re- peated.
Our contributions include:
We introduce GIT, which is our knowledge, the first gradient-based intervention targeting method. Due it's plug-and-play nature, our method can be easily combined with various gradient-basee causal discovery frameworks.
in-
Our extensive experiments synthetic and real- world graphs demonstrate that GIT effectively reduces the amount of interventional data needed to discover the causal structure, and performs well in the low-data regime. This makes GIT compelling option when access to interventional data is limited.
We provide a theoretical justification of GIT and a suite of analyses introspecting its behavior and performance.
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 based on graph-theoreticet properties. Typically, a completed partially directed acyclic graph (CPDAG), describing an equiv- alence class of DAGs, is first specified. Then, either substructures, such as cliques or trees, are investigated and used to inform decisions [He and Geng, 2008, Eberhardt, 2008, Squires et al., 2020, Greenewald et al., 2019], or edges of a proposed graph are iteratively refined until reaching a prescribed budget [Ghassami et al., 2018, 2019, Kocaoglu et al., 2017, Lindgren et al., 2018), One limitation of graph-theorettiall approaches that misspecificattion of the CPDAG 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 (MI) between the observations and model parameters. MI is approximated in different ways: AIT [Scherrer et al., 2021] uses F-score inspired metric to implicitly approximate MI: CBED [Tigas et al.. 2022] incorporates BALD-like estimator [Houlsby et al., 2011]; 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 gradient-based causal structure learning methods. The most prevalent approaches are supe-supe formulations that optimize a data-dependent scoring metric (for instance, penalized log-likelihood to find the best causal graph G. Existing self-supervised methods that capable (or can be extended) of incorporating interventional data can be categorized based on

---

the underlying optimization formulation into: (i) frameworks with 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., 2022] and (ii) frameworks with alternating phases of optimization [Bengio et al., 2020, Ke et al., 2019, Lippe al., 2022]. While structural and functional parameters are optimized under 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 hypothesized) interventional samples and can serve as a base framework for our proposed gradient- based intervention acquisition strategy.
Gradients in Active and Curriculum Learning. Gradients have been successfully used as criterion select data to process in previous work. Settles et al. [2007] introduce Expected Gradient Length (EGL), computed under the current belief, as a criterion for active learning. A batch active learning method introduced in Ash et al. [2020] also targets data points with high gradient magnitude, including uncertainty and diversity in the decision. In the area of curriculum learning, Graves et al. [2017] considers Gradient Prediction Gain (GPG), which is defined as the gradient's ' magnitude and is meant to be proxy for expected learning progress. We take inspiration from those approaches to propose novel usage of the gradient criterion the field of causal discovery.
Preliminaries
3.1 Structural Causal Models and Causal Structure Díscovery
Causal relationships can be formalized using structural causal models (SCM) [Peters et al., 2017].
Each of the endogenous variables X (X (X....., X.,) is expressed as function X, = f( A, Ui) of its direct causes PA; C X and an external independent noise U/. It is assumed that the assignments are acyclic and thus associated with directed acyclic graph G (V, E).. The nodes V (1,,...... (I....,,))
represent the random variables and the edges correspond to the direct causes, that is (i,j) E E if and only if X, PAj. The joint distribution factorizes according
P(X,
X,,) = P(X,
Causal structure discovery aims to recover the ground truth graph G. The solution this problem is not uniquely defined when having access only to observational data from the ground truth distribution F. Formally, it can be determined solely up Markov Equivalence Class (MEC) [Spirtes al., 2000b, Peters et al., 2017] without additional restrictive assumptions. To achieve identifiability, data from additional experiments, called interventions, need be gathered.
single-node intervention on X, replaces the conditional distribution P(X, (PA,) with a new distribution denoted as IPX,) PA.), yielding so-called interventional distribution:
(X( A F(X.PAA) II F(X))PA)). j
The node i is called the intervention target. An intervention that removes the dependency of variable X; on its parents, yielding PP.),|PA.) P(X.), is called hard. In this paper, we use data gathered by performing single-node interventions.
3.2 Online Causal Discovery and Targeting Methods
In this work, we consider online causal discovery procedure outlined in Algorithm 1. Given causal discovery Algorithm A, the graph model yo is fitted using observational data Dabs- Following that, batches of interventional samples acquired iteratively and are used by the algorithm to improve the belief about the causal structure (line 7). Intervention targets are chosen by intervention targetting method M to optimize the overall performance, taking into account the current belief about the graph structure encoded in pi-1. Below we discuss two popular choices for the method M (with more details deferred to Appendix D).
3

---

Algorithm 1 ONLINE CAUSAL DISCOVERY
Active Intervention Targeting (ATT) AIT selects the intervention target according to an F-test inspired criterion [Scherrer et al., 2021]. assumes that the causal discovery al- gorithm A maintains a posterior distribution over graphs (by design or using bootstrap- ping). To select intervention target, set of graphs is sampled from the posterior dis- tribution, and interventional sample distribu- tions are generated by intervening on each of the sampled graphs. Each potential interven- tion target is assigned a score by measuring the discrepancy across the corresponding in- terventional sample distributions.
input causal discovery algorithm A (e.g.. ENCO, see
Sec 4.1), intervention targeting method M. num- ber of data acquisition rounds T, observational dataset Dabs
output final parameters of graph model: 4T
1: Dins f- Ø
2: Fit graph model y5o with algorithm A Dobs
3: for round i = 1, 2,..., do
4: It generate intervention targets using M
5: D f query for data from interventions
6: Dintt < Dint U D int
7: Fit P; with algorithm A on Dint and Dohe
8:
end for
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 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., 201 to sample batches of interventional targets.
4
GIT method
In this work, present a new intervention targeting method GIT. GIT chooses intervention targets that induce the largest update of the parameters modeling the causal structure. Inspired by hallucinated gradients exploited by [Ash et al., 2020] caleulate gradients imaginary data generated by the causal model, to score possible interventions for real data acquisition.
To formally introduce our method, we first describe the requirements that need to be fulfilled by causal algorithm in order to use it with GIT. We then explain how GIT works and follow up with a discussion about causal assumptions and theoretical justification of our approach. Finally, in Section 4.1, we present a practical implementation of our method with a causal discovery algorithm A, using popular ENCO algorithm an example.
Requirements for causal discovery algorithm A. The intervention targeting method GIT can be coupled with any mudient-based causal discovery algorithm A (see Algorithm 1) that fulfills the following conditions:
1. A models a distribution over the causal DAGs, denoted by a family of probability measures IP, (G) parameterized by p. that allows sampling.
2. For each causal graph G, A maintains a corresponding family of conditional distributions, (X.|PA(A.))) parametrized by ø, which induces the joint distribution Fo.y:
Pa Il Pa. (X.IPA(.)))
If G corresponds to the ground truth graph, Pa,s approximates the ground truth distribution over X.
3. A gives access to its loss function L and gradient of the loss function V with respect p.
These requirements are mildly restrictive and they fulfilled by many gradient-basse discovery methods (for instance, ENCO [Lippe et al., 2022), SDI [Ke et al., 2019]. DiBS [Lorch et al., 2021], DCDI [Brouillard al., 2020] or DECI [Geffner et al., 2022]).
Method. GIT scores each possible intervention target by calculating the expected magnitude of the gradient using imaginary interventional data generated by the causal model. Gradient magnitude serves proxy for the size of the update that can be induced on the parameters of the causal model.

---

The method picks intervention that has the highest score. Formally, for given intervention i E V we define its score s; as follows:
5 - Ex-Pp.s IV (x]
Note that the expected value is computed with the interventional distribution coming from the model, instead of ground truth, defined as:
P P.o.a (X)= - Σ PplG)Pa...:XX)
(5)
The summation in equation 5 is taken over all DAGs and PG.0 corresponds to the joint distribution from the model for graph G:
P
PX jfi
The computational procedure of GIT's intervention target selection is listed Algorithm 2. The expected value in 8; is approximated using the Monte-Carlo method, see line 4 of Algorithm 2. We also use a version of Algorithm 2 where real interventional data are used in line (instead of the imaginary from the model) and call it GIT-privileged. CIT-privileee serves soft upper bound in our analysis. Note however, that it is not practically useful, as collecting real interventional data would require intervention every node in the first place.
Assumptions of GIT. From the causal perspective, GIT relies exclusively the Markov property assumption, which al- lows factorization of joined distribution (see Equation 1). However, GIT as a plug- and-play extension for causal discovery algorithms A inherits their assumptions. This may include, for instance, causal sufficiency or faithfulness. Our method does not require any additional assump- tions on the variables X, and allows for both discrete and continuous setups.
Algorithm GIT'S INTERVENTION TARGET SELECTION
input parameters p distribution over graphs, functional parameters Φ, loss function L. graph nodes V output batch of intervention targets to execute: / 1: G 4 sample set of DAGs according to (G)
2: for intervention target E do
3: DG, f sample batch of data according to Po...
4: 8i 인ा Eoeg I 1I
5: end for
6: I + -select batch of targets with highest scores
Theoretical justification of GIT. We show the convergence of GIT in two contexts, First, we prove that the main setup of this paper, i.e., GIT with ENCO [Lippe et al., 2022], described in Section 4.1, converges. The detailed result can be found in Appendix B, but the gist of the argument is that vertices for which the model structure is not aligned with the ground truth will have non-trivial gradients and hence will be queried by GIT, allowing the model to improve. Moreover, we show empirically that GIT gradients are well correlated with the principled GPG signal of GIT-privileged, see Appendix F.6. Second, we show that given any convergent causal discovery algorithm, GIT converges if we allow uniform sampling of intervention with small probability e >> 0, see Appendix A. We call this approach e-greedy GIT. Importantly, on finite sample with small enough GIT and e-greedy GIT are statistically indistinguishable.
4.1 Applicability ENCO
We choose to use ENCO as the gradient-basee based causal discovery framework A in our main experiments (recall Algorithm 1) due to its strong empirical results and good computational performance on GPUs. ENCO maintains a parameterized distribution over graph structures, with the so-called structural parameters (Pt.) )..; representing the adjacency matrix and set of parameters modeling the functional dependencies, Φ. The structural parameters, Pi.j. are factorized into an edge existence parameter, "..j and an edge orientation parameter, 0.,j -0,.--
The parameters are updated by iteratively alternating between two optimization phases. The goal of the first phase is learn functions fo, (((,))) which model the conditional density of (A,,)) The training objective the log-likelihood loss. The second phase aims to update the parametrized edge probabilities Pi, To this end, ENCO collects data sample from mixture
5

---

Table I: We count the number of setups (24), where given method was best comparable the other methods (AIT. CBED, Random, and GIT; GIT-privileged 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, respectively, presented in parentheses.
AIT
CBED
Random
GIT (ours)
GIT-privileged
mean AUSHD
6 + 4) 10 64)
6 (4
12 (5 7)
18 (11 +7)
24 (12 + 12) 24 (12 + 12)
mean SHD
7 (4+3)
22 (12 + 10)
17 (10+7)
of interventional distributions denoted by P, The graph parameters optimized by minimizing Et--P,Lgahhh (X) where:
Lngraph (X) P..
Σ E
La(a;; a log Sox (a. (P((,G))))
For detailed description of the method, distributions, and the estimators see Appendix C.I.
GIT with ENCO details. The loss function L utilized by GIT is denoted Lgmph. We incorporate to compute
information from both structural parameters and use Lguph (X)) 2 V the score for the intervention in line 4 of Algorithm 2. In order to sample DAGs from the current graph distribution (line 1 of Algorithm 2), we [Scherrer et al., 2021, Section 3.2) as it is scalable and guarantees DAG-ness by construction opposed Gibbs sampling or rejection sampling techniques.
two-phase sampling procedure proposed in
5 Experiments
We compare GIT against the following baselines: AIT, CBED, Random, and GIT -IT-privileged. AIT and CBED are competitive intervention acquisition methods for gradient-based causal discovery (which we discussed in Section 3.2). The Random method selects interventions uniformly in round-robin fashion?. The last approach, GIT privileee,,, is the oracle method described in Section 4.
Our main result is that GIT brings substantial improvement in the low data regime, being the best among benchmarked methods for all considered synthetic graph classes and half of the considered real graphs in terms of the AUSHD metric (see Equation 9). On the remaining real graphs, our approach performs similarly to the baseline methods. Notably, in most cases, GIT surpasses MI-based approaches: CBED and AIT. We present the summary Table 1. 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 the DiBS framework [Lorch et al., 2021] 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 observational dataset of size 5000. We use T = 100 rounds, in each 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 and [Da.al I = 128 data samples from each graph for the Monte-Carke approximation of the GIT score. We tested different sizes of the Monte-Carlo sample and found that it does not have major impact on performance, see Appendix F.4. For all experiments in this section assume, following the approach of Lippe al. [2022], that all interventions single-node, hard, and change the conditional distribution of the intervened node to uniform.
Datasets We use synthetic and worl- datasets. The synthetic dataset consists of bidiag, chain, collider, jungle, fulldag and random DAGs, each with 25 nodes. The variable distributions are categorical, with 10 categories The real-world dataset consists of al alarm, asia, cancer, child,
A every step. a target node chosen uniformly random from set of yet not visited nodes. After every node has heen selected, the visitation counts are reset to O.
We create the datasets using the code provided by Lippe al. [2022]. See Appendix E.1 for details.

---

ART
CRED
Random
GT Coun)
GF Mileged
10
SAUSHD
bidiag
choin
collider
fulldag
Junglo
rannoom
Figure 2: The distribution of SAUSHD (see equation 10), calculated using 25 seeds, for synthetic graphs (lower is better). The intense color (left-hand side of each violin plot) indicates the low data regime (N = 1056 samples). The faded color (right-hand side of each violin plot) represents higher amount of data (N = 3200 samples). Note that even though the solution quality is improved when more samples available, typically. SAUSHD smaller the low data regime. This is because it measures relative improvement over the random baseline, which is most visible for the small number of samples in most methods.
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., 2022, Scherrer al., 2021].
Metries We use the Structural Hamming Distance (SHD) [Tsamardinos et al., 2006] between the predicted and the ground truth graph as 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 e and c',
SHD(c, = E1(es + Cjt f dy + dj cij + dg).
(8)
In the experiments, we always compute SHD between the predicted and the ground truth graph. In order to aggregate SHD values over different data regimes, we introduce the area under the SHD curve (AUSHD):
1 AUSHD m = T
SHD m. SHD := SSHD(Cgt (Cots Cm,))
where m is the used method, T' is the number of interventional data batches, Cge is the ground truth graph, and Cm, the graph fitted by the method m using interventional data batches. Intuitively, for small to moderate values of T', AUSHD captures a method's s speed of convergence: the faster the SHD converges to 0, the smaller the area. For large values of T. AUSHD measures the asymptotic convergence. Smaller values indicate better method. For visualizations, we use surplus of AUSHD over Random method (SAUSHD), which compares method m the the Random baseline. Precisely,
SAUSHD m := AUSHD m
[AUSHD* Random
(10)
where the expectation averages all randomness sources (e.g. stemming from the initialization). Again, smaller values indicate better method.
5.2 Main Result: GIT's Empirical Performance
GIT's Overall Strong Performance We evaluate GIT on 24 training setups: twelve graphs (syn- thetic and real-world, six in each category) and two data regimes. GIT is the best or comparable to the baseline methods (excluding GIT eripprivlleged) in 18 cases according to mean AUSHD, and
17 cases according to mean SHD, see Table 1. Additionally, GIT is stable, as the distribution of its AUSHD has most frequently the smallest variation among non-privileged methods (11 out of 24 cases), see Table 8 and Table in Appendix F.2.2. In terms of pairwise comparison with other methods, GIT is better in 45 cases and comparable in 35 cases, out of total of 96 (= 24 setups x4
7

---

ATT
GRED
Random
GTT tours)
15
10
SAUSHD
-10
-15
aloim
child
concer
3513
carthquake
sochs
Figure 3: The distribution of SAUSHD (see equation 10), calculated using seeds, for real-world graphs (lower is better). The intense color (left-hand side of each violin plot) indicates the low data regime (N 1056 samples). The faded color (right-han hand side of each violin plot) represents a higher amount of data (N 3200 samples). Notice that the plots have different scales.
other methods), see Table 7 in Appendix F.2.1. Interestingly, GIT's performance for graphs with fewer nodes (cancer, earthquake) is less impressive. We hypothesize that this is because in these cases, the corresponding Markov Equivalence Class is singleton (see Figure 4). Consequently. they require less interventional data to converge (see training curves in Appendix F.2.4), which diminishes the impact of different intervention strategies.
GIT is Especially Efficient for Low Data In the low data regime (N 1056), GIT is better comparable to all the other non-privileged methods for 11 out of 12 graphs, see Table 1. Pictorially, this phenomenon can be seen in Figure 2 and Figure 3, where the left-hand side of the GIT violin plot tends to display the most favorable behavior compared to AIT, CBED, and Random methods. This suggests that GIT could be good choice when access interventional data is limited or costly.
GIT Outperforms MI-based Approaches We also notice that the performance of MI-based approaches (CBED and AIT) is worse than the one of GIT, typically attaining significantly worse AUSHD (see Figure and Figure 3) and SHD values (see Figure 7 and Figure in the Appendix F.2). This problem is further corroborated in Section 5.3, where we show that even in the case of large interventional batch size, these methods occasionally underperform Random, unlike GIT, which clearly wins in such a scenario. We hypothesize the poor performance comes from approximation errors and model mismatches, subverting the MI criterion which should lead to near-optimal decisions in the case of exact mutual information computation Krause and Guestrin [2005], Nemhauser et al. [1978], Tigas et al. [2022].
GIT Approximates GIT- ClT-privileged's Decisions GIT-privileged performs the best, as it is better or comparable with all other methods for each graph and data regime (see Table 1). This strong perfor- mance is also visible in Figure and Figure 3, where the mass of the method consistently occupies the favorable regions of the SAUSHD metric. These results solidify the perception of GIT privileeeee as a soft upper-bound. Importantly, GIT follows it quite closely: the methods are equivalent in terms of performance in 10 cases in the low data regime, and in 5 cases in the regular data regime. Fur- thermore, the choices of GIT and GIT CIT-privileged correlate highly (Spearman correlation equal 73%), Appendix F.6. These results provide additional evidence in favor 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 results can be found in Appendix F.2.
5.3 Performance under larger interventional batch size
ENCO sensitive errors in the estimation of properties of interventional data. In particular, small interventional batch size may cause errors in the estimation of conditional likelihood and disrupt the causal discovery process [Lippe et al., 2022, Appendix B.2.3]. We hypothesize that those estimation errors are an important factor hindering the advantage of using our method over Random the larger data regime. Acquiring data with small batches may result a misaligned gradient for the model and, in consequence, the poor assessment of the next interventional target scores.

---

ear thquake
cancer
asia
sachs
child
0.20
6.15
AIT
Lab3
1.590
2216
2,332
CBED
0.00
LAL1
1.244
Figure 4: The interventional targel distributions obtained by different strategies on real-world data. The probability is represented by the intensity of the node's s color. The green color represents the edges for which there cxists graph in the Markov Equivalence Class that has the corresponding connection reversed. The number below each graph denotes entropy of distribution.
0.75
Jungle
0.5-
325
0.00
5.00
0123498789
bidlag
0.2
02
0223435787
439799
0123459789
Figure 5: Histograms intervention targets chosen by GIT. In this experiment, a node v was chosen (denoted by a red color; o's parents are indicated by green). Parameters were initialized so that the model is only unsure about the neighborhood of v. The solid lines denote known edges and dashed ones to be discovered.
We perform an additional experiment in modi- fied regime, where each intervention yields 1024 data points instead of the previous 32. Such regime is relevant in scenarios where setting up an intervention with a new target is costly but ob- taining the individual samples relatively cheap. We run the experiment on synthetic graphs with 25 nodes and we run for acquisition rounds. We present the AUSHD values in Table 2 and full SHD curves in Appendix F.3. In this setting, GIT outperforms all the standard baselines and is on with GIT-pric EIT-privileged. Importantly, GIT reaches the SHD value of 0 for all graphs. Additionally, found that GIT selects each intervention target exactly once, except for the chain graph, for which the discovery process converges already after only 15 rounds.
Table 2: Average AUSHD values (from 5 seeds) for experiments with interventional batch size equal 1024.
CBED
Random
GIT(cuns)
GUV-privileged
bidiag
22.6
17.6
20.4
16.8
15.4
chain
7.7
120.1
101.1
jumple
22.3
16.7
199
11.4
10.8
randomn
38.4
36.2
33.4
29.9
28.3
5.4 Investigating GIT's intervention target distributions
In order to gain a qualitative understanding of the GIT's behavior, we analyze the node distributions generated by respective methods the BnLearn graphs in Figure 4. We observe that GIT often selects nodes with high out-degree, as visible in the sachs and child graphs. Intuitively, interventions such nodes bring much information, as they affect multiple other nodes. In addition, the most frequently selected nodes in the sachs, child, and asia graphs are also adjacent to the edges for which there exists graph in the MEC that has the corresponding connection reversed (as indicated by the green color in Figure 4). Note that in general, establishing the directionality of such an edge (v, w) requires performing interventions on nodes v, w (recall Section 3.1).
We further explore the interventional targets and verify that GIT is able to target the most uncertain regions of the graph. In the considered setup, 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 in the standard way the parameters for E,, Such model is only unsure
'For example, in the ENCO framework the directionality parameter 0,, can only be reliably detected from the data obtained by intervening either variable X, or X; [Lippe al., 2022].

---

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 5.
The interventions concentrate on v (red color) and its parents (green color). This indicates the effi- ciency of our approach, these most relevant to discovering the graph structure. Indeed, to recover the solution, only the parameters for E Ey need to be found. Intervening on e changes the distri- butions of its descendants, providing information on the existence of edges between these variables.
6 Limitations and future work
The theoretical grounding of the method involves multiple assumptions. Further work that simplifies or relaxes the assumptions and identifies fail cases would benefit the community,
We provide proof that epsilon-greedy GIT converges with any causal discovery framework. As for pure GIT, we show its convergence only with the ENCO framework. The development of a more general theory that solidifies the approach is a promising future work direction.
Our method can be applied in the soft-intervention case, and providing appropriate experi- mental evaluation would be an interesting follow-up to this work.
Our method may need more interventions than the minimal number required to identify the causal structure. For example, GIT can be biased towards high-degree nodes, as interventions on them tend to affect a larger amount of structural parameters and result in larger gradients, which might cause suboptimal choices.
Intervention acquisition methods (including GIT) seem to be less effective in a continuous setting. We believe investigating this area would benefit the community.
7 Conclusions
In this paper, we consider the problem of experimental design for causal discovery. We introduce a novel Gradient-based Intervention Targeting (GIT) method, which leverages the gradients of gradient-based causal discovery objectives to score intervention targets. We demonstrate that the method is partieularly effective in the low-data regime, outperforming competitive baselines. We also provide theoretical justification for the method and perform several analyses, confirming that GIT typically selects informative targets.
Acknowledgments and Disclosure of Funding
The work of Piotr Miloš was supported by the Polish National Science Center grant UMO- 2017/26/E/ST6/00622 and UM0-2119/311///1//04466 The work of Michat Zajac was supported by the Polish National Science Center Grant No. 2021/43/B/STT601455 The research of Michat Zajac and Aleksandra Nowak has been supported by a flagship project entitled "Artificial Intelligence Computing Center Core Facility" from the Digi DigiWorld Priority Research Area under the Strategic Programme Excellence Initiative at Jagiellonian University. We gratefully acknowledge Polish high- performance computing infrastructure PLGrid for providing computer facilities and support. Our experiments were managed using https:/ //tp:://eeeeeeeeeeeeeeeeeeeeeee .ai. ai. We thank the Neptune team for providing us access to the team version and technical support. We thank Swedish National Supercomputing and the Berzelius Cluster for providing compute resources.
References
Raj Agrawal, Chandler Squires, Karren D. Yang, Karthikeyan Shanmugam, and Caroline Uhler. Abed-strategy: Budgeted experimental design for targeted causal structure discovery. In Kamalika Chaudhuri and Masashi Sugiyama, editors, The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Research, pages 3400-3409. PMLR, 2019. URL http: //proceedings.nt mlr wttp:/s......eeesssssss_ http////////gaaalllaaa html. (Cited 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.07635 2021. (Cited on page 3)
10

---

Jordan T. Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenRe- (Cited on page 2, 3,
view.net, 2020. URL htttp:://ppnrrvvex: http:ppwwwr.eiaeeeeeooaaarrrrrra 4)
Yoshua Bengio, Tristan Deleu, Nasim Rahaman, Nan Rosemary Ke, Sébastien Lachapelle, Olexa Bilaniuk, Anirudh Goyal, and Christopher J. Pal. meta-transfer objective for learning to disentangle causal mechanisms. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https: //openreview www.://weeeeeottnoueeeee /ttr:/rrrmmmdddddlgEPTR
(Cited on page 1, 3)
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, editors, Advances in Neural Information Processing Systems, volume 33, pages 21865-21877 Curran Associates, Inc., 2020. (Cited on page 1, 3, 4)
Daniel C Castro, Ian Walker, and Ben Glocker. Causality matters in medical imaging. Nature Communications, 1 1(1):11-0,, 2020. (Cited on page 1)
Chris Cundy, Aditya Grover, and Stefano Ermon. Bod nets: Scalable variational approaches for bayesian causal discovery. Advances in Neural Information Processing Systems, 34, 2021. (Cited on page 3)
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. In James Cussens and Kun Zhang, editors, Uncertainty in Artificial Intelligence, Proceedings of the Thirty-Eight Conference on Uncertainty in Artificial Intelligence, UAI 2022, 1-5 August 2022, Eindhoven, The Netherlands, volume 180 of Proceedings of Machine Learning Research, pages 2022. URL ptstps://preee //rp:://////ceenggsss mlr wwwpppressviiieee /el//0/deleee dulaa22a.....ee.meeeeeeeeee html.. (Cited on page 3)
PMLR,
Frederick Eberbardt. Almost optimal intervention sets for causal discovery. In David A. McAllester and Petri Myllymäki, editors, UAI 2008, Proceedings of the 24th Conference in Uncertainty in Artificial Intelligence, Helsinki, Finland, July 9-12, 2008, pages 161-168. AUAI Press, 2008. URL httpppp:://dspptttttt.t www./o///ggg////////eeee httg:///w//.ssppaartilllc.. wet.rrrtiieeeeaaals........aa sel.eetaillss.ippmmmsee..... jsp?mmuu=1ksmnus arriche_icc19@@@tpreeediii.. id=24. (Cited on page 2)
Imme Upert-Uphoff and Yi Deng. Causal discovery for climate research using graphical models.
Journal of Climate, 25(17):5648-56) 2012. (Cited on page 1)
Tomas Geffner, 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 2tti:2202.021995. 2022. (Cited on page 3, 4)
AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Elias Bareinboim. Budgeted experiment design for causal structure learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1724-1733. PMLR, 10-15 Jul 2018. URL https:// proceedings. mlr www.mmll..../eeeeeeemmemmm wwtpp//////epeeeeepeeeeeppep /rress//80/hhassaaaii html. (Cited on page 2)
AmirEmad Ghassami, Saber Salchkaleybar, and Negar Kiyavash. Interventional experiment design for causal structure learning. CoRR, abs0191, 2019. URL http://arxiv. org//bs/ 1910. 1910.05660 05651. (Cited on page 2)
Clark Glymour, Kun Zhang, and Peter Spirtes. Review of causal discovery methods based on graphical models. Frontiers in genetics, 10:524, 2019. (Cited on page 1)
Alex Graves, Mare G. Bellemare, Jacob Menick, Rémi Munos, and Koray Kavukcuoglu. Automated curriculum learning for neural networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1311-1320. PMLR, 2017. URL http: httptt:p/ppooeeeinng. mlr. press/v70/ //t0///raee/aaaaa html. (Cited on page 2, 3)
11

---

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. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL https: / ppw.eedings......c wwwpreediinnnneuuiine.eeeee neurips. wttss.ccppppr/////eeeee ccc/paper/211//file 5ee50098172266166622255aaaaaa Paper pdf. (Cited on page 2)
Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs. The Journal of Machine Learning Research, 13(1): 2409-2466 2012. (Cited on page I)
Yang-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::/jmlr www.oorg............o... papers/v9 htt///99/he00.0 httphhh08.aa.... (Cited on page
Neil Houlsby, Ferenc Huszar, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference learning. CoRR, abs/1112.5744 2011. URL httt:://aratt org/
abs/1112.574 5745. (Cited on page 2, 4, 20)
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: org/abs/ anrg/bss1911 0ttg/ab//1910000775555 (Cited on page 1, 3, 7)
Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Experimental design for learning causal graphs with latent variables. In I. Guyon, U. Von Luxburg, Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https: http///preeenn...////// neurips.. ctppsper//////////pppp/p 0077=11ie994440066664440ooo70660 Setpeddeeffcc-epprereeeeee pdf. (Cited on page 2)
Andreas Krause and Carlos Guestrin. Near-optimal nonmyopic value of information in graphical models. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, UAI'05, page 324-331, Arlington, Virginia, USA, 2005. AUAI Press. ISBN 0974903914. (Cited on page 8)
Erik M. Lindgren, Murat Kocaoglu, Alexandros G. Dimakis, and Sriram Vishwanath. Exper- imental design for cost-aware learning of causal graphs. In Samy Bengio, Hanna M. Wal- lach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Anmual Conference on Neural In- formation Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 5284-5294, 2018 URL. https://ptee /ttp:::///cocceednngee hew.riinninnsnssssseeeeeee cc/ pptppppppp//////////pe fa5599665111cctddc6565555522222
1bd Abstract. html. (Cited on page 2)
David Lindley. On a measure of the information provided by an experiment. Annals of Mathematical Statistics, 27:986-1000 1005, 1956. (Cited page 2,
Phillip Lippe. Taco Cohen, and Efstratios Gavves. Efficient neural causal discovery without acyclicity constraints. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL http::: /tttpss//openreviee... forum?id=eVciPrLuub (Cited on page 3, 4, 6, 7, 8, 9, 15, 18, 20)
Qiang Liu and Dilin Wang. Stein variational gradient descent: general purpose bayesian inference algorithm. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Gar- nett, editors, Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016. URL https: /stps://proceedingg/ wewpeeiiiinnnnnniiieeeeee neurips cttii...ccppppaeee cc/ppperr/216/file/ b3ba8f 1bee htt.eee22222270020080888000
Paper pdf. (Cited on page 19)
Lars Lorch, Jonas Rothfuss, Bernhard Schölkopf, and Andreas Krause. Dibs: Differentiable bayesian structure learning. Advances in Neural Information Processing Systems, 34:24111-241 2021. (Cited on page 3, 4, 6, 19)
Kevin P Murphy. Active learning of causal bayes net structure. 2001. (Cited page I)
12

---

G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions- i. Mathematical Programming, 14(1):265 294, Dec 1978. ISSN 1436-4646. doi: 10. (0.1007/BF01188977 URL http://////...oo/1110/0000/// on page 8)
(Cited
Judea Pearl. Causaliry. Cambridge University Press, Cambridge, UK, 2 edition, 2009. ISBN 978-0-521-89566 doi: 10.1017/CB097805 1 (Cited on page 1)
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 (Statistical Methodology), 78(5):947-102, 2016. (Cited on page 1)
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inferenceefoundatiion foundations and learning algorithms. The MIT Press, 2017. (Cited on page 3)
Karen Sachs, Omar Perez, Dana Pe'er, Douglas A Lauffenburger, and Garry P Nolan. Causal protein- signaling networks derived from multiparameter single-cell data. Science, 308(5721);:533-52,, 2005. (Cited on page
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, 6, 21)
Nino Scherrer, Anirudh Goyal, Stefan Bauer, Yoshua Bengio, and Nan Rosemary Ke. On the generalization and adaption performance of causal models. arXiv preprint arXiv:2206.04620 2022. (Cited on page 1)
Marco Scutari. Learning bayesian networks with the bulearn r package. Journal of Statistical Software, 35(3):1-22, 2010. doi: 10. (0.18877/sssv03335 v035.i03. URL battps://wwi/ http///wwwsttttttttt./t// org/ (Cited on page 7)
Burr Settles, Mark Craven, and Soumya Ray. Multiple insllancettteee active learning. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc 2007. URL https: : // http///oceeednggeee neurips cc/ pappr//200/ffile
Paper pdf. (Cited on page 2, 3)
Xinpeng Shen, Sisi Ma. Prashanthi Vemuri, and Gyorgy Simon. Challenges and opportunitics with causal discovery algorithms: application to alzheimer's pathophysiology. Scientific reports, 10(1): 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 3)
Chandler Squires, Sara Magliacane, Kristjan H. Greenewald, Dmitriy Katz, Murat Kocaoglu, and Karthikeyan Shanmugam. Active structure learning of causal dags via directed clique trees. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12. 2020, virtual, 2020. URL https: //tpa/////cocccoss...eom neurips ct/ccc//paa. httppp/ppp////aaaa/p/ 1577005ee5555553444444444 4aee444118--bbbaattt. Abstract html. (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://arxis org. harg/abs/2an abs/ 02016. (Cited on page 2, 4, 8. 20, 21)
13

---

Simon Tong and Daphne Koller. Active learning for structure in bayesian networks. In Bernhard Nebel, editor, Proceedings of the Seventennth International Joint Conference on Artificial Intelligence, IJCAI 2001, Seattle, Washington, USA, August 4-10, 2001, pages 863-869. Morgan Kaufmann, 2001. (Cited on page I)
Sofia Triantafillou, Vincenzo Lagani, Christina Heinze-Deml Angelika Schmidt, Jesper Tegner, and Ioannis samardinos. Predicting causal relationships from biological data: Applying automated causal discovery on mass cytometry data human immune cells. Scientific Reports, 1222:4 URL https://doi. org/10.
Oct 2017. ISSN 2045-2322. doi: 10. 10.103885445988-077--00 0055://41998-007-00888 x. (Cited on page 1)
Ioannis Tsamardinos, Laura E. Brown, and Constantin Aliferis. The max-min hill-climbing
bayesian network structure learning algorithm. Machine Learning, 65(1):31-78, Oct 2006. doi:
ISSN 1573-0565.
(09000099994-0-68899991 URL attps://doi org/10.1007
810994-006-6888 6889-7.8877 (Cited on page 7)
Q. Wu, Nanda Horeweg, Marco de Bruyn, Remi A. Nout, Ina Jürgenliemk-Schule Ludy C. H. W. Lutgens, Jan J. Jobsen, Elzbieta M. van der H. B. M. Smit, Tjalling Bosse, Carien Creutzberg, and Viktor H. Koelzer. Automated causal inference in application to randomized controlled clinical trials. Nature Machine Intelligence, 4(5):436-444, May 2022. ISSN 2522-5839, //doi. 1038/s42256 022 022-00470-y- (Cited on page 1)
Hans W. Nijman, Vincent T.
doi: 10. 0058/42255-022-044700 URL https:
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric Xing. Dags with tears: Continuous optimization for structure learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: http:////////////pe//e/eee http:ppp.s..pppppreeeeee/ee/.eee pppppr/2018/fi1lee 6347654119ff22233336600002222223 Paper, pdf. (Cited on page 19)
14

---

Appendix
A
Convergence of causal discovery with GIT
Suppose that we have some causal discovery algorithm AA which is guaranteed to converge to the true graph in the limit of infinite data. Here we investigate if such convergence property still holds if 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 - e, and otherwise, we choose randomly uniformly from all available targets. Proposition 1. the causal discovery algorithm A is guaranteed to converge given infinite amount of samples from each possible intervention target, then A with c-greedy GIT is also guaranteed to converge.
Proof. Since the e-cxploration guarantees visiting every target infinitely many times in the limit, the proof follows from the asserted convergence of A.
Remark 2. ENCO with e-greedy GIT is guaranteed to converge to the true graph under the standard assumptions [Lippe et al., 2022, Appendix B.1]. Remark Proposition
asymptotic and holds for arbitrary 6 0. However, a finite setup, we can choose small enough that c-GIT and GIT behave similarly. Our experiments show that GIT performs well (compared with other benchmarks) and is indistinguishable from an asymptotically convergent method.
B Convergence conditions of ENCO framework with GIT B.1
Preliminaries (ENCO recap)
In this section, we recall results from Lippe et al. [2022] for convergence of their causal discovery method ENCO. They formulate four theorems and of conditions that guarantee that the parame- ters of the structure converge to the true graph. For full proof and detailed explanation please refer to Appendix B in Lippe et al. [2022].
Remark 4, ENCO identifies common conditions for correct convergence directionality parameters. They go as follows (see theorems B. B.2, and appendix B.4 in ENCO):
1. For all possible sets of parents of X, excluding X,, adding X; improves the log-likelihood estimate of Xj under the intervention on X,, or leaves it unchanged.
Vpī(X,) S X-15 Eix,,x x [log X, (aapaaXX))))))) Xt)
log p( X, pa (X,)) 2
2. There exists a set of nodes pa(x)). for which the probability to be sampled as parents of X; is greater than O, and the following condition holds:
3pp(X,) C X- Eix,
X.) - log p ()x,(pp))))))) >
3. For all possible sets of parents of X, excluding X,. adding X, does not improves the likeeiild estimate of X; under the intervention X,, leaves it unchanged.
vpa(X,) S X EExx, x [lox)(X.lp@(xx)),. X3) p(X, pax))) 2
For least one parent set (a(X,). which has a probability greater than zero be sampled, this inequality is strictly smaller than zero.
Remark The following condition guarantees convergence existence parameters (see theorem B.3 in ENCO):
min (Xp))(())
Bizps ,0) B, loo (X, pa, X,) log log (X, Xy)p
Asparse
where gx,, have an edge to X, without introducing cycle, Pı_,(I) refers to the distribution over conducted interventions pr (I) excluding the intervention variable X,, and Aeparee is a positive constant.
) is a set of nodes excluding X, which, according to the ground truth graph, could
15

---

Theorem 6. (Theorem B.1 from Appendix B.4 in ENCO.) Consider the edge X; - X3 in the true causal graph. The orientation parameter 8ig converges to ((B;)) the conditions from remark are fulfilled.
Theorem 7. (Theorem B.2 from Appendix B.4 in ENCO.) Consider a pair of variables X;, X for which X, is an ancestor of Xj without direct edge in the true causal graph, Assume all edges that appear in the true graph have converged according to theorem 6. The orientation parameter Bsg converges to (B2g)) = -1 if the conditions from remark 4 are fulfilled.
By Appendix B.4 from ENCO, Theorems 6, 7 hold regardless of whether we collected interventional data from node X, or Xj.
Theorem 8. Consider an edge X; + X in the true causal graph. The parameter "ii converges to (1Hy) = 1 if the condition from remark holds.
Theorem 9. Assume for all edges X; + Xj in the true causal graph, o(0;)) and ((Ti)) have converged to one. Then, the likelihood of all other edges, ie. a(uw)) a((u)) will converge zero under the condition that Axporse O.
B.2 GIT-privileged proof
We follow with proof of ENCO convergence with the GIT-privileger acquisition method under the same set of conditions from remarks We show that GIT-privileged collects interventional data as long is needed for the orientation parameters to converge according to theorems 6 and 7. Then theorems 8 and can be applied to show that the algorithm reached convergence.
Assumption We assume that in all local minima of our loss function, the existence parameters take extreme values: Vi, ((rs) E {0,1], thus, when sufficient time for optimization is given, they stop contributing to the score, Hence in our analysis, we focus on describing only the behavior of orientation parameter gradients.
The proof is structured as follows:
1. We show that following GIT-privileged score allows collecting enough interventional data direct all edges that appear in the true graph correctly, proposition 12.
2. Then we show that, if required, additional interventional data that allows directing other edges according to theorem 7 will be collected, see proposition 13.
3. Finally, theorems 8 and 9 can be applied to show that we learned the correct graph, see proposition 14.
Proposition 10. Consider the edge X; + X2 in the true causal graph. The parameter "hy converges (1y)) under any set of interventions pi (I) if
min Eimp, ,(T) (B, [log (xx Xy, X.) log logp(X;lpo)) V_V.
Asparse
where V-, is the set of all nodes excluding X,, and pI_, (1) refers the distribution over conducted interventions (I) excluding the intervention on variable Xz.
Proof. The condition guarantees that the gradient of Tis is positive.
Proposition 11. Consider the edge X, X, in the true causal graph. When conditions from remark 4 are fulfilled V/V Limpni (X,,) = Lepph (X.)ll Va, Lgraph(Xr,)) = e[ Lyrap (X1,
and the edge converged to its true value if and only if we acquired interven- tional data from X, or X,.
Proof. First, recall that ENCO does not update orientation parameters unless the interventional data was acquired from neighboring node. Therefore, the gradient can only be zero before the intervention if the existence parameters converge zero. This situation is guaranteed not to happen by proposition 10.
Second, when interventional data is acquired, based the theorem 6, know that the edge converges to its true value.
16

---

Proposition 12. Choosing intervention targets with CIT-privileged score allows collecting enough data to direct all edges that appear in the true graph properly if the following is true:
For any pair of variables Xi, X3 without direct edge in the true causul graph, when conditions from remark 4 are fulfilled, and we acquired interventional data from either X; or X,, and sufficient time for the optimization process is given, then the orientation parameters will converge to extreme values (0.s). o(0x)) E {0,1} or the existence parameters will converge o (76s) = ((1g)) = O.
Proof. The assumption and proposition 11 imply that after collecting interventional data from a node, edges that are connected to this node will not contribute to the score anymore. Thus we will not intervene on the same node twice. On the other hand, proposition 11 guarantees the score of edges that appear in the true graph will be positive until they are directed.
Proposition 13. Consider a pair of variables Xi, for which X is an ancestor of Xj without direct edge in the true causal graph. Assume all edges that appear in the true graph has converged according to theorem When conditions from remark are fulfilled, and if ([ (X,,)h(X1,)) then the edge converged as , Lyuupp X1,) 1,)
1/ Iyraph (X1,) V [xgrap((11,) described in theorem 7 or its existence parameters converged to
Proof. To zero out the gradient either orientation or existence parameters had to converge. the orientation parameters converged we had to collect interventional data from neighboring node (because otherwise, ENCO does not update parameters). Thus, based on the theorem we know that the edge converged to its true value.
Given sufficient acquisition rounds and time for optimization ENCO with GIT- privileged intervention acquisition method will recover the true graph.
Proposition 14.
Proof. From propositions 12, 13 we have that GIT GiTppiivieeed will collect interventional data from new nodes until edges that appear in the true graph are correctly directed and edges between pairs of variables X,, Xj without a direct edge in the true causal graph either disappear from the model or are directed according to theorem 7. By theorems 8, 9 we conclude that we indeed acquired enough interventional data converge to the correct graph.
B.3 GIT convergence
Proposition 15. Given sufficient acquisition rounds and time for optimization ENCO with GIT intervention acquisition method will recover the true graph if the following is true:
For any graph G sampled from the structural belief P Ppl.) (recall equation 5) during GIT score estimation, the theorems and propositions from sections B. and B.2 hold when we use G instead of the true graph and compute gradient using data from the sampled model IP (X)) (recall equation 6).
Proof. First, note that thanks to proposition 10, if there is an edge X; X, in the true graph there exists a model, that can be sampled from the belief with non-zero probability, in which this edge appears.
For each undirected edge X; + X, in the structural belief for which the existence parameter converged to ar (84,) 1, there exists model (with a positive probability to be sampled), that will yield a gradient of positive magnitude if and only if there is no interventional data acquired from the node connected to it. This model contains the edge X; + Xj. thus by the assumption made above and proposition 11, it will yield a positive gradient. In consequence, expectation over all possible models, when the edge is not yet directed, will yield positive score.
Note that, when interventional data from X; or X, is acquired, the edge X, + X, directed and it does not yield gradient of positive magnitude under data sampled from (X) for any G~ (.). This stems from the fact that the gradient term zeroes out when parameter a (00y) takes extreme values (0 or 1).
17

---

Hence, GIT score will allow to sequentially "eliminate" undirected edges. Since to update our structural belief (,(() we use interventional data sampled from the true graph when all edges are directed, we are guaranteed (by B.2 section) that they are directed according to theorems 6, 7. Then the same argument as for CIT-privileged can be applied to show that we converged to the true graph.
L
C
Details about Employed Causal Discovery Frameworks
C.1
ENCO
We extend the description of the ENCO framework [Lippe et al., 2022] from Section 4.1.
Structural Parameters. ENCO learns a distribution over the graph structures by associating with each edge (i, for which j j. probability Pi.j ((.,)) Intuitively, the "i. parameter represents the existence the edge, while 0., -0, Oz. is associated with the direction of the edge. The parameters "i and f,g are updated in the graph fitting stage.
Distribution Fitting Stage. The goal of the distribution fitting stage to learn the conditional probabilities ((X.|PA(,.cy) for each variable X; given graph represented by adjacency matrix C, sampled from Cū, ~ Bernoulli(pt.)) Note that self-loops are not allowed and thus Pt, 0. The conditionals are modeled by neural networks fo, with an input dropout-mask defined by the adjacency matrix. In consequence, the negative log- log-probability of variable can be expressed as (X.).. log Sa, (PA(,c))(X:)), where (A obtained by computing C., @ X, with @ denoting the element-wise multiplication. The optimization objective for this stage is defined as minimizing the negative log-lik bogllikelihood (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:
LD = ExEo Lc(X,)).
(11)
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 I,
ENCO samples the data from the postinterventionl distribution P,. In experiments, in the current paper, where the variables are assumed to be categorical the intervention is implemented by changing the target node's conditional to uniform over the set of node's categories. As the loss, ENCO uses the sparse graph strcuture loss Lgraph defined in Equation 7 in the main text plus a regularization term AL y.0 that influences the sparsity of the generated adjacency matrices, where À is the regularization strength.
Gradients Estimators. In order to update the structural parameters y and 0 ENCO REINFORCE-inspired gradient estimators. For each parameter "t. the gradient is defined as:
OLG o' (THs))
(12)
Exxc_,,l4xx-a0 (X,) Lx, (X,) A),
where Ex,c_ij denotes all of the three expectations in Equation 7 (in the main text), but excluding the edge (i,.j) from C. The term Lx,4x, (X,) describes the negative log-likelihood of the variable X, under the adjacency matrix C-ij. while Lx,+x, (X,) is the negative log- likelihohhood computed by including the edge (i.j) C-iy- For parameters f., the gradient is defined as:
ŌLa d' d0(s))
00.,
(X₂) Lx, (X₂)]
|4x, +x (X:) Lx, (X:))),
(13)
where p(T.) the probability of intervening on node (usually uniform) and R,, is the same expectation Ex.c-.5 but under the intervention node i.
18

---

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(gg U4 UU)
(14)
1 1+ exp(a_aa(u vg))
Here, Pū is the random variable corresponding to the presence of an edge between i to is tunable hyperparameter and Wy V R$ are embeddings corresponding to node i and j. The entire set of learnable embeddings, i.e. U {u, ) V = {v: )t and Z = [U, V] E g2xdxk form the latent variables for which posterior inference needs to be performed. Such a posterior can then be used to perform Bayesian 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 and Wang, 2016]. SVGD uses a set of particles for each embedding uy and uy 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 term which enforces diversity of the particles using kernels. The prior over the latent variable is given by a Gibbs distribution with temperature which enforces soft-acyclicty constraint:
pZZ) exp(-xEppp (M(G)) II V[ 0, 0,)
(15)
Here, h is the DAG constraint function given by NOTEARS [Zheng et al., 2018].
D Details about Intervention Targetting 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 set of graphs = { sampled from this distribution. AIT assigns to each possible intervention target i E V discrepancy score that is computed by measuring the variance between the graphs BG) and variance within the graphs (VWG). The VBG, for intervention is defined as:
VBG, (mns Pi. P3, p44),
(16)
where M. is the mean of all samples drawn from graph 9j under the intervention on target i, and μ4; is the mean of all samples drawn from graphs under intervention target i. The variance within graphs is described by:
VWG, ΣΣ (IS Py.s, 18, - Mg,a).
(17)
where [Sy is the k-th sample from graph Gj under the intervention on target i. The AIT score is then defined as the ratio D, VWG. The method selects then the intervention attaining the highest score D..
VBC,
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
19

---

interventional data. Let the tuple (j, v) define the intervention, where j E V describes the intervention target, and v represents the change in the conditional distribution variable X,. Specifically, this means that the new conditional distribution of X; is distribution with point mass concentrated on v. Moreover, let Vij,e) denote the interventional distribution under the intervention (j,²), v), and let & denote the current belief about the graph structure (i.e. the random variable corresponding (p. o)). BOECD selects the intervention that
to the structural and distributional parameters v0-
maximizes [Tigas et al., 2022]:
,"' arg max (( (3))58)) D), (i.))
(18)
where D are the observational data. The above formulation necessities the use of an MI estimator. One possible choice is BALD-inspired estimator Tigas et [2022], Houlsby et [2011]:
()))) 1 D) (YG))) D) H (Y(,,)) D),
(19)
with - 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.1 Synthetic Graphs Details
The synthetic graph structure is deterministic and is specified by the name of graph (chain, collider, jungle, fulldag), except for random, where the structure sampled. Following ENCO [Lippe et al., 2022], we set the only parameter of sampling procedure, edge_prob, to 0.3.
The ground truth conditional distributions the causal graphs are modeled by randomly initialized MLPs. Additionally, a randomly initialized embedding layer is applied at the input to each MLP that converts categorical values real vectors. We used the code provided by Lippe et al. [2022]. For more detailed explanation, refer to Lippe et al. [2022, Appendix C.I.1J.
E.2 ENCO Hyperparameters
For experiments ENCO framework used exactly the same parameters reported by Lippe et al. [2022, Appendix C.1.1]. We provide them in Table 3 for the completeness of our report.
Table 3: Hyperparameters used for the ENCO framework.
parameter
value
Sparsity regularizer Asparse Distribution model
x 10-3
2 layers, hidden size 64, Leaky 0.1)
Batch size
128
Learning rate model
5 10-3
Weight decay- model
1 x 10
Distribution fitting iterations F
1000
Graph fitting iterations G
100
Graph samples
100
Epochs
30
Learning rate
x 10
Learning rate- 0
x 10
E.3
DiBS Hyperparameters
In Table 4, we present hyperparameters used for the DiBS framework.
E.4
Computational Cost
We used two hardware settings, one with GPU: single Nvidia A100, and another one with CPUs: 12 cores of Intel Xcon E5-2697 processor. In our synthetic graph experiments with ENCO GPU,
20

---

Table 4: Hyperparameters used for the DiBS framework.
parameter
value
Number of particles
20
Number of particle updates
20
Choice of Kernel
k([Z, 0) [z', e']) o2 exp( bz
|
Z'(l?))
+ de exp( he | (1|l-)
hz he oz de Optimizer
5
500
1
1
RMSProp 0.005
Learning rate Optimizer
single experiment takes on average 4 to run, with 57 min being used by GIT make decisions; the rest is devoted to the underlying causal discovery algorithm (in this case, ENCO). In the case of the CPU setup, an experiment takes on average 126 h, with the GIT part taking up only 6 h. We estimate the project's overall cost be around 50K GPUh and 2M CPUh.
F
Additional Experimental Results
F1 Experiments in DiBS Framework
Experimental setup The experimental setup closely follows the one from Tigas et al. [2022]. In the experiments, 10 batches of 10 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. For every method, we run 40 random seeds. 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 fixed at 0.
Random (uniform values): Intervention targets are chosen uniformly randomly. The intervention value is chosen uniformly randomly from the variable support.
Soft AIT: Intervention targets are chosen from the softmax probabilities of AIT scores [Scherrer et al., 2021], with the temperature GP-UCB 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.
The results are presented Figure 6. We can see the performance Soft GIT comparable that of Random (uniform values) in both considered graph classes. Soft AIT and Soft CBED behave similarly for Medos-Renni graphs, while for Scale-Free they seem to bring a small improvement.
F.2
Performance in ENCO Framework All Results
F.2.1
Ranking Statistics
We present ranking statistics in Tables 6, 7.
F.2.2
AUSHD Tables
We present all AUSHD results with confidence intervals in Tables 8, 9.
21

---

Erdos-Renyi
Scale-Free
160
Bandom (fowd val es)
Random (unifom: values)
110-
Soft AIT
expected SHD
expected SHD
80
100
70
80
60
60
50
batches
batches
Figure 6: Expected SHD metric for different acquisition methods on top of the DiBS framework, for graphs with 50 nodes and two different graph classes: Erdos-Renyi and Scale-Free. 95% bootstrap confidence intervals are shown.
Table We the number of training setups (24), where given method best at least comparable other methods (AIT, CBED, and Random; GIT-privileged was compared against), basing on 90% confidence intervals for AUSHD, Each entry shows the total count, broken down into two data regimes, N 1056 and N = 3200 resp., presented in the parenthesis.
AIT
CBED
Random
GIT (ours)
GIT-privilege
Best
0 (0 + 0) (2 + 4)
0 (0 + 0)
2 + 2)
8 (4 4)
5 4) 24 (12 12)
Best or comparable
6 24
12 (5
18 (11 7)
Table 6: We count the number of training setups (24), where given method was best or at least comparable to 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, broken down into two data regimes, N 1056 and N 3200 resp., presented in the parenthesis.
AIT
CBED
Random
GIT (ours)
priv. GIT
Best
(0
100 1) 7 (4 + 3)
(11+1)
3 (1+ 22 (12 10) 17 (10+)
(1++))
Best or comparable
10 (4 6)
24 (12 + 12)
Table 7: For each method show its pairwise performance against other methods (whether is better, comparable, or worse) based on 90% confidence intervals AUSHD, across two data regimes (N 1056 . = 3200) and all twelve graphs (hence for each method there are x 12 4 = 96 pairs to consider). Each entry shows the total count, broken down into two data regimes, N 1056 and N 3200 resp., presented in the parenthesis.
Better
Comparable
Worse
AIT CBED Random
(3+6)
27 (11+16)
60 (34+26)
(7+2)
35 (20+15)
52 (21+31)
34 (13+21)
36 (21+15)
26 (14+12)
GIT (ours)
45 (24+21)
35 (21+14)
16 (3+13)
GIT- GIT-privileged
57 (25+32)
39 (23+16)
0 (0+0)
F22.3 SHD Tables
We present SHD results for small and large data regime with confidence intervals in Tables 10, 11.
F.2.4
ENCO Training Curves
We provide SHD training curves for main experiments in Figures 7 and 8.
22

---

Table 8: AUSHD with 90% confidence intervals (in the parenthesis), for synthetic data and for low and regular data regimes (N= 1056 and N 3200 resp.).
AIT
BALD
Random
GIT (ours)
priv. GIT
bidiag
1056
24.7 (5.51
21.9 (2111
22.0 (21.5,
20.0 (1955 20.6)
(186, (186,209) 20.9
3200
14.0 (130, 154)
13.2 (125,
11.1 (10.5, 12.1)
9.4 (90.99)
9.3 (8D,
chain
1056
14.9 15.4)
12.2 (1.8, 12.7)
13.5 (13.1.
11.7 (11.3 12.1)
12.2
3200
11.,, 8.11
7.2 (68, 1.7)
6.3 (6.)
5.6 (5.2, 6.0)
6.3 (.5),
collider
1056
16.0 (15.2, 16.7)
16.1 (15.8 16.7)
14,6 (14.1, 15.1)
14,4 (13:4, 15.2)
11,8 (109, 13,0)
3200
10.9 (10.2, 11.7)
12.2 (11.6, 12.7)
9.7 (92, 10.3)
12.1 (109, 13.1)
7.8 (6.9,
fulldag
1056
133.0 (1312, 134.7)
141.6 (139.1,
121.7 (120.4, 122.9)
119.8 (11877
120.7 (119.1,
3200
72.8 (71.0.
100.6 (97.8, 103.8)
63.4 (62.0, 64.7)
67.9 (86.0, 70.3)
63,4 (61.2,
jungle
1056
23.2 (21.9, 24.6)
20.6 (19.6, 21.7)
20.9 (20.1, 21.7)
14.7 (14.1, 15.4)
13.9 (124, 15.5)
3200
11.2 (10.7, 11.90
13.3 (12.3, 14.3)
9.1 (83, 9.5)
6.9 (.25.722
6.9 (5.5,
random
1056
42.1 (40.5,
43.1 (41.5,440)
35,6 (34.6 36.7)
34.6 (53.7,
31.9 (504, 34.6)
3200
21.3 (2.34
30.7 32.5)
16.5 (1588 17.3)
17.0 (16.3, 17.7)
14.5 (136.
Table 9: AUSHD with 90% confidence intervals (in the parenthesis), for real-world data and for low and regular data regimes (N 1056 and 3200 resp.).
AIT
CBED
Random
GIT (ours)
priv. GIT
alarm
1056
42.8 (4L8, 43.8)
36,8 (358, 37.8)
39.7 (3.6, 40.)
28.8 (28.3, 29.3)
28.5 (27.0 29.6)
3200
35.0 (3.66.664)
31.6 (3.1)
28.8 (27.6 308)
24.0 (23.4.
21.5
asia
1056
3.6 (29.4.5)
3.5 (2.8.43)
(18.2.
2.2 (2.0,
1.8 1.9)
3200
(1.9. 3.3)
2.1 (1.9.255)
1.3 (1.2, 1.4)
1.5 (1.4. 1.6)
1.1 (1.0, 1.3)
cancer
1056
2.0 (1.9. 2.1)
2.1 2330,
2.4 (222266) 2.60
2.4 (2.2,
2.1 (1.6,26) 2.6)
3200
1.8 11.6,
2.1 (1.9.22)
2.2 (200233)
2.2 (2.0,
2.2 (1.7,26))
child
1056
14.4 (13.7,
10.4 (9.6. 11.2)
11.1 (10.7. 11.6)
8.3 (8.0, 8.7)
7.9 (7.0, 9.0)
3200
(7.1, 8.6)
7.1 (.05,
5.0 (4.7.
(4.2. 4.8)
3.9 (3.2,4.)
carthquake
1056
0.5 0.6)
0.5 (0.4.06)
0.4 (0.3.0.5)
0.6 (..5.0.)
0.4 (0.2,06)
3200
0.2 (..1..3)
0.2 (0.1.22)
0.1 (0.1.22)
0.3 (.5)
0.1 (0.1,02)
sachs
1056
3.1 (2.9.
2.9 (216.311)
2.9 (27,3.1)
2.5 (.74.
2.5 (2.2.28)
3200
1.4 (1.3, 1.6)
1.9 (1.7.22)
1.2 (31.
1.1 (1.0, 1.3)
0.9 (0.8.
Table 10: SHD with 90% confidence intervals (in the parenthesis), for synthetic data and for low and regular data regimes (N 1056 and 3200 resp.).
AIT
CBED
Random
GIT (ours)
GIT--priv.
bidiag
1056
11.4 (10.3,
10.1 (92. 11.0)
7.8 (zo,
6.3
7.4 (6.2,
3200
5.2
7.8 (7).87) 8m)
2.8 (23,
2.4 (1.8.9)
2.2 (0.83.6)
chain
1056
5.6 (48, 6.4)
5,4 (16.6.1)
4.3 (38..)9
3.6 (3.0422) 4.)
3.6 (20.48)
3200
3.2 (266, 3.7)
3.9 (3.4,4.)
2.2 (1.7.66))
1.8 (1.3.
1.8 (0.2, 2.6)
collider
1056
11.0 (10.1. 11.9)
11.8 (11.0. 12.7)
9.8 (9.1. 10.6)
13.3 (122, 14.4)
9.8 (7.6, 12.0)
3200
4.8
7.9 (6.8, 8.9)
3.7 (23,
9.7 11.6)
3.4 (1.4,50)
fulldag
1056
64.4 67.0)
91.4 (86.8, 96.0)
52.1 (50.0 54.3)
55.8 (534, 58.01
53.4 (49.8, 57.0)
3200
32.0 (30.0, 33.8)
75..4 (71.8, 79.0)
25.1 (228, 27.2)
27.3 (25.1, 29.8)
20.8 (1966 21.8)
jungle
1056
10.4 (9.2, 11.6)
11.6 (10.1, 13.2)
5.7 (500, 6.5)
5.1 (.84
5.2 (3.0, 7.4)
3200
3.5 (.9)
8.3 (1.2, 9:4)
1.9 (1.5.23)
2.2 (1.8.
3.0 (200 4.0)
random
1056
18.8 (17.3, 20.3)
27.5 29.5)
11.3 (1000 12.5)
12.5 13.5)
11.0 13.0)
3200
8.3 (7.0.
22. 24.44
5.0 (4.3,
5.3 (.14.611)
3.8 (22.5.4)
F33 ENCO large interventional batch experiment
We provide SHD training curves for experiments with the large interventional batch in Figure 9.
F.4 ENCO monte carlo sampling evaluation
We provide a performance evaluation of GIT with different amount of graphs sampled from the model in Figure 10.
23

---

Table 11: SHD with 90% confidence intervals (in the parenthesis), for real-world data and for low and regular data regimes (N= 1056 and N 3200 resp.).
AIT
CBED
Random
GIT (ours)
priv. GIT
alarm
1056
35.76 (34044 37,52)
28.44 (26.68 30.66)
26.0 (24.71 27.29)
19.84 (19.0 20.68)
25.0 27.0)
3200
26.15 (2415, 28.23)
24.33 (21.67,
16.0 (14.57, 17.14)
20.0 (18.77, 21.33)
1.2 15.2 (14.6 15.8)
asia
1056
2.0 2.68)
1.96 (1.44, 2.4)
0.96 (0.8. 1.12)
1.2 (1.0,
3200
1.56 (1,12, 1:92)
1.28 (1.0, 1.48)
0.88 (0.79, 1.0)
1.12 (0.96, 1.24)
0.8 (0.A, 1.2)
cancer
1056
1.72 (1.48, 2.0)
2.2 (24,2.4)
2.28 (2.04, 2.48)
2.12 (188, 2.4)
2.2 (1.8.24)) 2.4)
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 (5.92,
6,36 (5.52,
3.52 (2.84, 4.2)
3.72 (3.2, 4.24)
2.8 (1.4.4.)
3200
3.2 (2.56, 3.8)
4.68 (348)
1.04 (0.7, 1.35)
2.16 (1.8, 2.52)
1.8 (.0)
earthquake
1056
0.12 (0.0, 0.2)
0.12 (000 0.2)
(0.0, 0.0)
0.24 (0.08, 0.36)
0.0 (0.00..)) 0.0)
3200
0.04 (-0,4, 0.08)
0.0 (0.0, 0.0)
0.0 (0.0, 0.0)
0.2 (0.08, 0.52)
0.0 (0.00.0) 0.0)
sachs
1056
0.84 (0.68, 1.0)
1,28 (0.96, 1.6)
0.6 (0:4,
0.52 (0.32, 0.72)
0.4 0.)
3200
0.48 (0.32, 0.64)
1.48
0.24 (0.08,
0.48 (0.28, 0.68)
0.0 (0.0.00))
AT
CBED
Random
GIT (ours)
GrT
bidiag
chain
collider
50
25
30
40
20-
30
20
10
10-
10
5-
1000
2000
3000
0
1000
2000
3000
0
1000
2000
3000
fulldag
jungle
random
300
80-
40
200
60-
SHD
20
100
20
0
1000
2000
3000
0
1000
2000
3000
1000
2000
3000
data samples
data samples
data samples
Figure 7: Expected SHD metric for different acquisition methods on top of the ENCO framework, for synthetic graphs with 25 nodes. 95% bootstrap confidence intervals are shown.
F.5 ENCO Large Synthetic Graphs
In order to study the scalability of our method, we perform an additional evulation on selected synthetic graphs in which we increase the number of nodes to 100. We comapre the performance of different acquistion methods used with ENCO in Figure 11. We observe that GIT exhibits very good results, converging to lower SHD values with significantly less acquistion steps compared all the other methods. This confirms the superiority of GIT, even within a larger graph regime.
F.6 ENCO Correlation Scores
In Figure 12, we present the correlation of scores of the tested targeting methods. Importantly, the high correlation of GIT and GIT- ciT-privileged supports the hypothesis that imaginary gradients are credible proxy of the true gradients and thus validates GIT. Otherwise, correlations are relatively small, suggesting that the studied methods use different decision mechanisms. Understanding this phenomenon is an interesting future research direction.
Below, provide more details about computing the correlations. Let denote by si the score produced by method m for the batch b and the node i. In order to eliminate effects such changing
24

---

ATT
CBED
Random
GIT (ours)
GiT-privllgee
cancer
30
0
1000
2000
3000
1000
2000
3000
1000
2000
3000
child
earthquake
sachs
20
SHD
10
2
1000
3000
1000
2000
3000
1000
2000
3000
data samples
data samples
data samples
Figure 8: Expected SHD metrie for different acquisition methods on top of the ENCO framework, for graphs from BnLearn dataset. 95% bootstrap confidence intervals shown.
Random
GIT-riVileged
bidiag
chain
collider
25
40
20
15
10
10
10
5
5-
0-
fulldag
jungle
random
300
80-
200
SHD
100
20
0
10 15
25
5
10
20
25
0
10
15
20
25
interventional rounds
interventional rounds
interventional rounds
Figure 9: Expected SHD metric for GIT with an interventional batch size of 1024 samples. 95% bootstrap confidence intervals are shown, and results were computed using 3 random seeds.
scores scales during the discovery process, we normalize the scores as 5y
For every
E ag.
pair methods m, m' and node i, we compute Spearman's 's rank correlation score r. (3. 3Th) We average over the nodes to get the scalar correlation value corr(m, m') := EN (""),""))
In addition, present Pearson's correlations in Figure 13. Conclusions from the analysis of the Spearman's 's rank correlation hold; in particular, the correlation between GIT and CIT-privileged high.
25

---

GIT 10 graphs
GIT 30 graphs
GIT 50 graphs
GIT 70 graphs
GTTppivileged
bidiag
chain
collider
50
25
30
40
20
30
20
10
10-
10
5-
1000
2000
3000
1000
2000
3000
0
1000
2000
3000
fulldag
jungle
random
200
SHD
30
40
10
20
0
1000 data samples
2000
3000
1000
2000
3000
1000
2000
data samples
data samples
Figure 10: Expected SHD metric for GIT with different numbers of graphs samples used to estimate score for interventions line 2 in Algorithm 2). 95% bootstrap confidence intervals are shown, results computed using 10 random seeds.
Randomm
GIT (ours)
bidag
chain
fulldag
5000
1400
120
4500
1200
100
1000
80
4000
800
60
3500
600
interventional rounds
jungle
random
1400
200
1200
SHD
1000
800
100
600
50
0
20
40
60
0
20
40
60
interventional rounds
interventional rounds
Figure II: Expected SHD metric for different acquisition methods on top of the ENCO framework, for synthetic graphs with 100 nodes. 95% bootstrap confidence intervals shown.
E.7 ENCO Intervention Targets Distribution
In this section, we provide additional histograms and plots with regard to the interventional target distributions obtained by different intervention methods discussed in Section 5.4 in the main text.
In Figure 14, we present the histograms of the target distributions for the real graphs for each of intervention acquisition methods. Note that those histograms represent the same information as the node coloring in Figure 4. 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
26

---

GTT
1.00
0.73
0.13
0.03
CiT-privilged
0.73
1.00
0.09
0.01
CBED
0.13
0.09
1.00
0.15
0.03
GiT
Gft-privieged
CUEI
Figure 12: Spearman's 's rank correlation of the scores produced by different acquisition methods, averaged over nodes.
CiT-privleged
0.72
1.00
0.06
0.02
CBED 0,08
0.06
1.00
0.13
ATT
0.01
0.02
0.13
1.00
dit
GfT-grivieged
CBEI
AIT
Figure 13: Pearson correlation of the produced by different acquisition methods, averaged nodes. We can see similar trends as in case of Spearman's rank correlation, particular, high correlation of GIT and GIT elT-privileged.
earthquake
cancer
asia
sachs
child
alarm
GIT
014
AIT
005
600
CBED
04
605
Figure 14: The histograms of chosen interventional targets in all data acquisition steps for different strategies computed on the real-world data.
sachs and child datasets, for which the entropy of CBED approach is smaller (recall Figure 4). Note, however, that CBED underperforms on those graphs (recall Figure the main text or see Figure 8). This is in contrast GIT, which maintains good performance.
Finally, in Figure 15, we present the interventional target distribution on the alarm graph. We observe that each method intervenes on at least node incident to the critical edges in the Markov
27

---

GIT
AIT
CBED
0.15
0.100
0.05
0.00
Figure 15: The interventional target distribution for the alarm graph. The green color represents the edges for which there exists graph the Markov Equivalence Class Black color used to indicate node for each no data collected. We may observe that each method intervenes at least one node incident to the critical edges. However, both AIT and CBED do not converge for this dataset and struggle achieve good results.
the corresponding connection reversed.
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 observed Figure 8.
F.7.1 ENCO Obtained Synthetic Graphs
chain
bidiag
collider
jungle
fulldag
0.10
0.08
IN
0.04
0.02
080
Figure 16:
The interventional target distributions obtained by different strategies on synthetic data. The probability is represented by the intensity of the node's color. For clarity of the presentation, we choose not color the critical edges in the corresponding Markov Equivalence Classes. This is because all edges of all the presented graphs would need to be colored. The only exception is the collider graph, which is alone its Markov Equivalence Class.
addition, we present the results obtained the synthetic graphs in Figure and the corresponding histograms in Figure 17. Note that in this case the results are also averaged by different ground truth distributions, which means that any regularities selecting the nodes come rather from the graph structure than from data distribution.
28

---

Interestingly, we may observe that for the jungle and chain graphs GIT often intervenes on the nodes which are the first ones the topoloiiaa order (as indicated by low node numbers in the plots). This is again intuitive, as intervening on those nodes can impact more variables lower in the hierarchy. In addition, note that for the chain graph, knowing its Markov Equivalence Class and setting the directionality of an 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.
We may also observe that the CBED seems to focus only on the first nodes in the topologiaal order, despite the data distribution, which in some graphs (as the chain graph) may be desired, but in others seems be an oversimplified solution. Note that CBED often struggles to converge this may be observed in Figure 7.
chain
bidiag
collider
jungle
fulldag
0.01
0.05
0.00
3:06
0.05
0.04
0.00
0.02
DURZ
14
14
0.0%
0.05
0.00
0.55
AIT
0.00
0.04
0.03
0.01
0:53
8:52
0102
0.92
0.01
0.00
0.00
0.4
000
CBFD
0.3
044
0.075
0.2
0.000
03
0.05
34
14
9
34
Figure 17: The histograms of chosen interventional targets in all data acquisition steps for different strategies computed on the synthetic data.
F.7.2 Discussion on Small Real-World Graphs
We provide a more detailed discussion on the differences between the earthquake and cancer graph distributions and the way it affects the GIT method.
Consider Figure in the main text. Note that the middle node in the earthquake graph corresponds to setting off a burglary alarm, an event very unlikely to happen in observational data but which, when occurs, triggers a change in the distributions of the nodes lower in the hierarchy (see the conditional distributions in Table 12). The chance of starting an alarm is also very high in case burglary has happened (the left-most node in the graph). Hence the GIT concentrates on those two nodes as they have the largest impact the entailed distribution.
similar situation can be observed for the cancer graph, where the middle node corresponds to a 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 respectively) share a causal relationship with cancer, their impact on the cancer variable is limited. In other words, the chances of developing cancer, no matter whether being subject to high or low pollution or being a smoker or not, remain rather small (see the conditional distributions for cancer variable in Table 13). Hence, the only way which one can gather more information about the impact of having cancer on the distributions of its child variables (nodes 3 and 4) is by performing intervention. In consequence, 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.
29

---

Table 12: The conditional distribution in the earthquake graph
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.955, 0.05
Alarm
Burglar=False, Earthquake=True
[True, False]
0.29, 0.71
Alarm
Burglar=True, Farthquake-False
[True, False]
0.94, 0.06
Alarm
Burglar=False, Farthquake-False
[True, False]
[0.001, 0.999)
John Calls
Alarm='rrue
[True, False]
0.99 0.1] [0.05, 0.95]
John Calls
Alarm=False
[True, False]
Mary Calls
Alarm=True
[True, False]
0.7, 0.3]
Mary Calls
Alarm=False
[True, False]
00.01, 0.99)
Table 13:
The conditional distribution in the cancer graph.
Variable
Parents
Values
Distribution
Pollution
[Low, High]
[0.9, 0.1]
Smoker
[Truc, 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]
00.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]
00.65,
Dyspnoea
Cancer=False
[True, False]
[0.3, 0.7]
F8 ENCO Experiments with Pre-Initialization
0.75
sachs
0.50
0.30
0.50
0.25
0.25
0.25
0.00
15
0.00
0.00
0.4
0.6
child
0.244
310921416166
0.0
0.2 51012141518
0.0
2.244 1002244662
0.1
0.2
0.0
0.0
Figure 18: Histograms of intervention targets chosen by GIT. The red color corresponds to the selected node, while the green color indicates the node's ' parents. The edges on which standard initialization was used are indicated by gray dashed lines. The rest of the solution is given in the initialization.
In addition to the discussion on the target distributions 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.4), we present results of the same experiment computed on the real-world graphs. The results are presented in Figure 18.
30

---

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).
31


Reviews:
[{"review_id": "t50aZHZrKh", "reviewer": "Reviewer_6LvC", "summary": "The authors present an approach for inferring the most informative intervention targets for the task of causal discovery; where they propose an alternative to bayesian experimental design approaches. They use the gradients of the casual discovery algorithm's loss function to find the intervention targets, which helps the algorithm to learn about regions of the graphs that it is most uncertain about. They experiment with the ENCO causal discovery algorithm and show how their approach for interventional target acquisition outperforms other approaches on both synthetic and real data benchmarks.", "questions": "* The approach works with causal discovery algorithms that maintain a distribution over the structure of the graph. Is that assumption limiting in some manner? What about approaches where we do not maintain a distribution over graphs, could the approach be applied with a single-point estimate for the graph?\n\n* A related question to the previous one, how does the approach perform when we change the number of graphs sampled from the distribution over graphs? Are there ablations studies that test the effect of changing $|G|$ on the performance of the causal discovery algorithm?\n\n* The authors consider only single-node hard interventions for target acquisition; what are the reasons for not considering soft interventions? Is it a limitation of the proposed approach or soft interventions are not as informative as hard interventions for the task of causal discovery? ", "limitations": "Yes, the authors have addressed any potential negative societal impact of their work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* Since we can only learn the causal graphs up to an equivalence class using observational data, it is important to collect interventional data in an efficient manner for causal discovery. Hence, the authors consider a very relevant problem in the area. \n\n* The proposed approach is novel to the best of my knowledge and also technically sound with extensive experimentation to back it. The authors compare a good set of baselines and perform several ablation studies to understand the effectiveness of their approach. \n\n* The paper is very well written with good presentations of the experiment results and details of the proposed approach.\n\n* The proposed approach could be especially significant for large graphs with more nodes, where estimators for mutual information might not work well and the approaches based on them could suffer.", "weaknesses": "I do not think the paper has any serious weaknesses, but I have listed some of them in the questions section ahead. One suggestion for the authors would be to test their approach with synthetic data containing more nodes, as it could help us understand how the proposed intervention target acquisition approach scale with the size of the graph.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for a very encouraging review. We are glad that the Reviewer appreciated the importance of the problem, novelty, soundness of the approach and experiments, and clear presentation.\n\nBelow we answer the specific questions asked by the Reviewer:\n\n- [Scalability of the method]: We thank the Reviewer for suggesting studying scalability. For the rebuttal, we ran an additional experiment on the jungle graph with 100 nodes, in which we compared different acquisition methods used with ENCO (see Figure R.1 in the additional rebuttal PDF). We can indeed observe that GIT significantly outperforms Random and MI-based approaches given the intervention budgets as in our main text experiments. For the camera-ready version, we will prepare a section about scalability, with results on other synthetic graphs.\n\n- [Maintaining distribution over graphs]: In order to be compatible with GIT, the underlying causal discovery method needs to maintain a distribution over the graphs (causal DAGs). This assumption is explicitly mentioned in the paper, in Section 4, paragraph “Requirements for causal discovery algorithm A”. That being said, we note that the assumption is met for a broad class of recent causal discovery algorithms, including ENCO [1], DIBS [3], SDI [2], DCDI [4], and DECI [5]. In fact, we are not aware of any modern neural network-based approach for which this requirement would not be satisfied.\n\n- [Impact of number of graphs sampled]: We performed the mentioned ablation and reported the results in Figure 10 in Appendix. We varied the number of sampled graphs from 10 to 70 and observed no significant impact on the results. In the experiments in the main text, we always use 50 samples.\n\n- [Using soft interventions]: We thank the Reviewer for this interesting question. The main reason we considered hard interventions is easier comparability with prior works such as [1], which used hard interventions in their experiments. However, this is not a limitation of our method, and there is no reason for soft interventions not to work with GIT. We leave an empirical evaluation in such a scenario for future work.\n\n\nWe would like to express our gratitude once more for the Reviewer's positive rating and constructive feedback, which have contributed to the improvement of our paper.\n\n[1] P. Lippe, T. Cohen,  E. Gavves. Efficient neural causal discovery without acyclicity\nconstraints. arXiv:2107.10483.\n\n[2] N. R. Ke, O. Bilaniuk, A. Goyal, S. Bauer, H. Larochelle, B. Schölkopf, M.  Mozer, C. Pal, and Y. Bengio. Learning neural causal models from unknown interventions, arXiv:1910.01075. \n\n[3] L. Lorch, J. Rothfuss, B. Schölkopf, A. Krause. Dibs: Differentiable bayesian structure learning. Advances in Neural Information Processing Systems 34, 2021.\n\n[4] Ph. Brouillard, S. Lachapelle, A. Lacoste, S. Lacoste-Julien, A. Drouin. Differentiable causal discovery from interventional data. Advances in Neural Information Processing Systems, 33, 2020.\n\n[5] T. Geffner, J. Antoran, A. Foster, W. Gong, Ch. Ma, E. Kiciman, A. Sharma, A. Lamb, M. Kukla, N. Pawlowski, M. Allamanis, Ch. Zhang. Deep End-to-end Causal Inference. arXiv:2202.02195\n"}, {"review_id": "fXvsMOVz6k", "reviewer": "Reviewer_qbh5", "summary": "The paper studies the problem of efficiently inferring causal structure from data. Observational data often falls short in providing a full picture of the causal structure, while obtaining interventional data tends to be costly. Therefore, optimizing the collection of interventional data to reduce the number of necessary experiments becomes crucial. In this context, the authors present Gradient-based Intervention Targeting (GIT), a novel approach to enhancing causal discovery from data. Uniquely, GIT takes advantage of gradient estimators from gradient-based causal discovery frameworks, paving the way for efficient intervention targeting. Thanks to its plug-and-play nature, GIT is compatible with various frameworks. The authors validate the effectiveness of GIT via extensive tests on synthetic and real-world datasets, demonstrating its superior performance, especially in low-data scenarios.", "questions": "NA", "limitations": "NA", "rating": 8, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "-\tThe problem studied in this paper is important.\n-\tThe paper is written in a very clear way. The background, method, and empirical results are all presented nicely.\n-\tThe proposed method demonstrates very good empirical performance.\n", "weaknesses": "Typos:\n\n-\tIn the final sentence of the first page, the in-text citation should use \\citep instead of \\citet.\n-\tOn line 156, there appears to be a large space between 'A' and the period.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for positive feedback on our work. We are glad that the Reviewer considers the studied problem to be important and that they appreciate a very good empirical performance of our method. Is it good to hear that we managed to clearly describe our work and present the results nicely. \n\nWe thank the Reviewer for identifying the typos and will correct the typos in the camera-ready version of the paper.\n"}, {"review_id": "P6GIhcBhzQ", "reviewer": "Reviewer_8Vao", "summary": "This paper addresses the problem of targeting interventions to learn the causal graph. The ideal goal is to have the minimum number of interventions that is necessary to have identifiability.  The authors propose a Gradient-based Intervention Targeting method (GIT) that utilize the gradient estimator of a gradient-based causal discovery framework to provide signals for the intervention acquisition function. The paper includes extensive experiments on simulated and real-world datasets, demonstrating that GIT performs on par with competitive baselines, surpassing them in the low-data regime.\n", "questions": "1. The majority of the proofs in the appendix are just proof sketches, I think it is better to detail them so a more solid theory for the proposed method can be developed.\n2. While the method is intuitively appealing and the extensive experiments provide very good results, is it possible to fail for some edge-case joint probability distributions? \n3. Is there an empirical estimation of hte number of samples needed? Or a theoretical upper bound?\n4. As neural causal discovery is more on the heuristic side (at least to my understanding), if the method badly fits the data distribution, how does the error propagate to GIT?\n5. Do the author think (as a conjecture)  that GIT captures the minimum number of necessary interventions to have identifiability? Or do they think that there is a limitation to it, if so is it possible to give some examples? \n6. Can the authors provide details for the assumption of theorem 5 to 10 (also please note that theorem 9 is missing in the appendix). \n", "limitations": "The empirical results are extensive and show great performance of the proposed algorithm. A more theoretical understanding of the method can provide more understanding to its limitations. \n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The paper addresses a significant problem in causality and machine learning, presenting a new approach to intervention targeting.\n2. The proposed GIT method is model-agnostic and leverages the gradient estimator of a gradient-based causal discovery framework.\n3. The authors provide extensive experiments on both simulated and real-world datasets, demonstrating the effectiveness of their approach, especially in low-data scenarios.\n4. The paper is well written. \n", "weaknesses": "1. The paper could benefit from a more detailed explanation of the GIT method and its underlying principles. A summary of gradient based methods and why they work is also important to make the paper self-contained and easier to follow to people with a general background in causality and machine learning. \n2. The authors could provide more insights into the limitations of their method, including potential biases and assumptions. Especially, as there is no solid theoretical justification for the convergence of the method. To my understanding, the convergence claim only holds with ENCO and with hard-to-interpret assumptions. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the time and effort put into providing valuable feedback on our work. We are pleased to hear positive comments on the novelty of our work, the clarity of the manuscript, and the extensiveness of our experiments. We appreciate the constructive critique and questions which can help improve the publication. Below we provide answers to the Reviewer’s questions and concerns:\n\n1. [More detailed explanation] - We agree with the Reviewer that a detailed description of the method benefits any paper. We feel that we put effort into explaining GIT in detail and would like to bring the Reviewer’s attention to the appropriate parts in the main body of the text: (a) intuition (lines 147-150) with grounding in existing literature (lines 91-98); (b) a pictorial representation of the GIT (Figure 1); (c ) formalism (lines 169-183); (d) assumptions and pseudo-code (lines 184-195); and (e) intuitive argument for theoretical justification (lines 196-205). Furthermore, in Section 3 we offer brief descriptions of two related gradient-based causal discovery methods: DIBS and ENCO (with more details postponed to Appendix C). We are committed to making the description as clear and easy to digest as possible, so if the Reviewer still feels that some details are missing, we kindly ask for suggestions, so we can address them accordingly.\n\n2. [Insights into the limitations] - Thank you for this suggestion. We add the following limitations and future work section:\n* The theoretical grounding of the method involves multiple hard-to-interpret assumptions. Further work that simplifies the assumptions and identifies fail cases would benefit the community.\n* We provide proof that epsilon-greedy GIT converges with any causal discovery framework. As for pure GIT, we show its convergence only with the ENCO framework. The development of a more general theory that solidifies the approach is a promising future work direction.\n* Our method can be applied in the soft-intervention case, and providing appropriate experimental evaluation would be an interesting follow-up to this work.\n* Our method may need more interventions than the minimal number required to identify the causal structure. For example, GIT can be biased towards high-degree nodes, as interventions on them tend to affect a larger amount of structural parameters and result in larger gradients, which might cause suboptimal choices.\nWe would also like to bring the Reviewer’s attention to the following insights described in the paper: the method's reliance on interventional batch size (Section 5.2) and on the number of graph samples (in Appendix F.4), a thorough analysis of the method's behavior (Section 5.3), and detailed discussions in Appendices F.5 and F.6.\n\nQuestions:\n1. [Proof sketches] - Thank you for raising this issue. We will clarify Appendix B in the camera-ready version and formalize GIT convergence theorem.\n\n2. [Edge cases] - The proof in Appendix A shows that epsilon-greedy GIT has the same convergence guarantees as the underlying framework. Thus, for discussion on fail cases, we refer the Reviewer to the underlying causal discovery algorithm (for example, appendix B.2.4 in ENCO). \n\n3. [Estimation of samples needed] - Yes, we experimented with different sizes of interventional batch size. For the specific graphs we tested, 1024 samples allow the method to intervene on each node at most once before SHD converges to 0 (see Section 5.3 and in Figure 9 in Appendix F). We found this result satisfactory to conclude that 1024 samples for the purpose of our experiments is enough.\n\n4. [Error propagation] - Unsurprisingly, GIT is susceptible to the errors of the underlying methods. Due to a lack of proper theoretical frameworks, these are hard to quantify. However, our positive empirical results, let us have an optimistic belief that there is a significant resilience to these errors. We conjecture that this might be due to the fact that the probabilistic nature of the causal frameworks may, on average, shield us from the worst cases scenarios. \nWe also identified a case, in which the errors might be hard to overcome. Consider the collider graph from Figure 7 in the Appendix. The collider graph is difficult to learn because it is hard to model precisely conditional distribution in the collider node. Our method, together with BOED, struggles to extract useful information from the model in this example as they are not able to match the Random baseline.\n\n5. [Required number of interventions] - Thank you for this question. We do not expect that GIT needs only a minimum number of interventions. We add this to the limitation list. This is for two reasons: the underlying framework may not have this property (which is, for example, the case of ENCO), and GIT might not optimally choose the required interventions. On the positive side, our empirical results clearly demonstrate that GIT performs well and in practice outperforms existing methods. \n\n6. [Assumptions details] - The theorems 5-10 are a direct adaptation of the convergence results for the ENCO method. In consequence, apart from the observations 1-3 mentioned in our Appendix B, we also have to assume all the requirements made by ENCO - we refer to sections B.1 of the ENCO Appendix (Assumptions 1-5) and the explained intuition behind them in ENCO Appendix B.2.1. and B.2.2. We understand that the current proof is hard to follow. We will clarify the whole section in the camera-ready version.\n\nWe again thank the Reviewer for the valuable feedback. Should you have any other questions or concerns, please let us know. If the answers are satisfactory, we gently ask the Reviewer to consider raising the score. \n\nReferences:\n\n[ENCO] Phillip Lippe et al. Efficient neural causal discovery without acyclicity constraints. 2021. \n\n[DIBS] Lars Lorch et al. Dibs: Differentiable bayesian structure learning. NeurIPS, 2021.\n"}, {"review_id": "N6G0ezvSxa", "reviewer": "Reviewer_E5qP", "summary": "This paper proposes a method for efficient acquisition of interventional data. Specifically, given observational data and causal discovery algorithm A, the authors propose a method (GIT: Gradient-based Intervention Targeting) that chooses particular intervention(s) to enrich the data and enhance the causal discovery process. The norm of  the gradient (of the structural loss) is used as the acquisition function.\n\nThe paper indeed tackles an important problem (causal discovery with active experiment design), with no apparent restrictions on the random variables (though to varying degrees of success in the empirical evaluation). The paper provides a fair number of empirical evaluations and compares the method to a decent number of baselines. \n", "questions": "1. I like the results where you show the correlation of the scores produced by different acquisition methods. However, I think further exploration here would be valuable. For example:\n- How the correlation increases/decreases with increasing/decreasing number of samples in the Monte Carlo approximation ($|\\mathcal{D}_{G,i}|$). This may help understand the gap between the privileged and simulated gradients (i.e., does approximation error play a big role?). \n- Is the correlation in earlier batches lower than that of later ones? And by how much? I suspect the answer to the first question is yes since for later batches the estimated DAG is \"closer\" to the true DAG.\n\n2. I'd be interested to see an evaluation of the performance of \\epsilon-greedy GIT. My presumption is that it could serve as a useful safeguard against possible inaccuracies in gradient estimation or discrepancies with the \"real\" privileged gradient.\n3. I'd like to understand the rationale behind choosing Random-fixed as a baseline in the experiments under the DiBS Framework. From my viewpoint, this baseline selection seems somewhat arbitrary. Could you elaborate on why you chose this specific baseline?\n4. In algorithm 2, you choose a set of interventions in each round (32 as stated in section 5). Do these correspond to the number of data samples generated? Or are they the number of nodes intervened on? If the latter, does that mean only one point is generated per intervention? would increasing the number of samples per intervention help?\n5. From a quick read of appendix B, my understanding leads me to believe that these theorems are specific to GIT-Privileged and not GIT with “imaginary” interventional samples. Could you confirm if my interpretation is correct or if I may have misunderstood the points made?\n", "limitations": "No negative societal impact is expected. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper tackles an important problem, and provides a clean solution that seems to be  compatible with many causal discovery frameworks.\n2. The paper is generally well-written and easy to digest. \n3. Extensive empirical evaluations are provided which shows that the proposed method is superior especially in the low-data regime. ", "weaknesses": "1. I believe the main weakness of the paper is that I do not fully get why the gradients estimated from “ imaginary” interventional data approximate those you get from “real” interventional data. It would be great to: \n(i) give a hypothesis for why this is the case;\nand/or (ii) state clearly (in the main text) that it is indeed surprising and is an interesting direction of future work. \nI think this is an interesting phenomenon that should be highlighted more in the text.\n\n2. There is a clear improvement of GIT over baselines; however, I find it surprising that the random baseline is doing much better than other baselines. You state that this is due to approximation errors and model mismatches. Can you elaborate? Is it safe to conclude that in this setting, Random is the SOTA method (other than GIT)?  \n3. While the framework seems generic and not specific to categorical variables, the experiments suggests that GIT have minimal advantage over Random in the continuous settings. Figure 6 suggests that GIT only outperform Random-fixed (which I’m not sure is a reasonable baseline).  \n3. Nitpicks:\n\n- Line 291: section 5.3\n- Line 300: Did you mean SAUSHD instead of EAUSHD?\n- Result in A is not really specific to GIT; I believe it is true for all algorithms.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the Reviewer's feedback. It's gratifying to know that the Reviewer recognizes GIT as a robust solution to the crucial problem of intervention targeting, and acknowledges its compatibility with various causal discovery frameworks. We're also pleased that the Reviewer acknowledges the thoroughness of our empirical evaluation. Below, we address the raised concerns:\n\n1. [“Imaginary” gradients approximate the “real” ones] - Consider an algorithm (e.g., ENCO) that throughout the training consecutively learns to better approximate the real solution. In consequence, the “imaginary” data sampled from such a model progressively become a better approximation of the real interventional data. In Appendix F.5 we also empirically observe that the correlation between the scores of GIT and GIT-privilege is high. Note that the approach of using “imaginary” gradients is also well-grounded in the active learning literature (Ash, Jordan T., et al. 2019). At the same time, we agree that the properties of this process are far from being understood. We add this point to the future work section.\n\n2. [Strength of Random Baseline] - indeed, at first this came as a surprise for us as well, and, in our view, reinforces the need for theoretical understanding of the fail cases of those methods. We suspect that the observed behavior stems from the poor quality of approximations used internally by AIT and CBED. For example, MI used in CBED might be susceptible to errors in highly dimensional situations. \nNote, however, that random selection is a strong baseline in some active learning scenarios. For instance, (Lowell et al. 2018) observe that an actively-acquired dataset does not consistently outperform training on i.i.d sampled data. \n3. [Continuous variable setup and Figure 6] - Thank you for bringing up this point. Indeed, we only show that GIT is applicable to the continuous situation but not necessarily effective. We now add it to the limitations. Note that in this continuous setup, all the baseline methods (not only GIT) perform very similarly (except for the Random-fixed). We speculate that in the continuous case, it is perhaps more important to identify the values of the nodes than properly select the intervention nodes (consider the difference between Random-Fixed and Random-uniform in Figure 6 in our Appendix, and Figure 3a/b in Tigas et al. 2022). A detailed explanation is an interesting direction for future work. \n\nQuestions:\n\n1. [Further exploration of correlations] - Following the Reviewer's suggestion, we analyzed how correlations change over time. The results are shown in Figure R.3 in the Rebuttal PDF. Surprisingly, we noticed that although the correlation between GIT and GIT-privileged remains high, the overall correlation between different methods decreases as the number of acquired batches increases. We hypothesize that early in the training process, identifying the best target nodes is relatively easy, leading to similar solutions across methods. However, as the number of steps increases, finding nodes that significantly improve performance becomes more challenging (this idea is also supported by the initial rapid SHD convergence shown in Figure 7 in the Appendix).\n\n2. [Evaluation of \\epsilon-greedy GIT] - Thank you for your suggestion. We evaluated GIT, random, and $\\epsilon$-GIT ($\\epsilon$=0.33) on collider and jungle graphs. The results are presented in Figure R.2 in the rebuttal PDF. Interestingly, for the jungle graph (where GIT performed well, as shown in Figure 2 of the main paper), GIT and $\\epsilon$-GIT exhibit similar performance. Additionally, as pointed out by the Reviewer, $\\epsilon$-GIT seems to enhance performance in cases where GIT struggles due to inaccuracies or disparities with the true gradient. This is evident from the performance on the Collider graph in Figure R.2.\n3. [Rationale behind choosing Random-fixed] - We have chosen to include Random-Fixed to maintain compatibility with CBED (Tigas et al. 2022).\n\n4. [Number of interventions] - In Algorithm 2 we acquire data only from one intervention. The quantity 32 corresponds to the number of data samples drawn from the selected interventional distribution. We have also experimented with increasing this number (see Section 5.3). Those experiments show that increasing the number of samples to 1024 can significantly improve the results. \n5. [Theorems in Appendix B] - the results are applicable to the GIT method. More specifically, Theorems 5-9 guarantee the “local convergence” of ENCO meaning that when acquiring enough real interventional data from a specific node parameters of all neighboring edges will converge and stop generating gradient. Based on this observation we conclude, in theorem 10, that if we choose any node that has a positive gradient magnitude, we will be able to discover more graph structure. We understand that the current proof is hard to follow. We will clarify the whole section in the camera-ready version.\n\nWe again thank the Reviewer for the useful feedback. We hope that our answers clarify the issues. We would be happy to answer more questions, if needed, otherwise if everything is clear, we gently ask that the Reviewer consider raising the score. \n\nReferences:\n* Lowell, David, Zachary C. Lipton, and Byron C. Wallace. \"Practical obstacles to deploying active learning.\" arXiv preprint arXiv:1807.04801 (2018).\n* Tigas, Panagiotis, et al. \"Interventions, where and how? experimental design for causal models at scale.\" Advances in Neural Information Processing Systems 35 (2022): 24130-24143.\n* Ash, Jordan T., et al. \"Deep batch active learning by diverse, uncertain gradient lower bounds.\" arXiv preprint arXiv:1906.03671 (2019).\n"}, {"review_id": "5MVLR7gh0S", "reviewer": "Reviewer_zVWz", "summary": "The paper proposes to exploit the gradient information to efficiently select intervention targets. The novel approach is called Gradient-based Information Targeting (GIT), it is claimed that it is the first gradient-based intervention targeting method. A number of realistic benchmarks are used to validate the approach. ", "questions": "I would like a clarification: the parameters of the model are associated with graph edges. So, the gradient information is the information on the edges. Once a batch of targets with the highest scores are identified, what information (observation) is added exactly? If I remember, the BNlearn generates data as a matrix: number of observations (rows) \\times variables (nodes, in columns). So, if you decide that you need more information on a particular node (column), how can you add such a partial information? Aren't you going to get missing values for other nodes in this case?  ", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The approach is sound, and it is reported that it performs quite well. ", "weaknesses": "The idea to make use of the gradient information is not new. The actual method relies on the scores (eq. 4) that are proportional to the expected magnitude of the gradient. Although it might be novel to apply the gradient information to identify the nodes for interventions, the gradient magnitude information was already well studied both in a number of theoretical and practical publications. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the feedback. We are glad that the Reviewer appreciates that GIT is sound and experiments are well tailored for the problem. Below we provide answers to the Reviewer's questions and concerns:\n\n1. [Lack of novelty]- It is true that the idea of using gradient signal in guided data selection has been proven to be fruitful in many contexts throughout machine learning, especially in active and curriculum learning. However, it is not immediately clear how to apply these ideas to intervention targeting, and even if so, there still is a gap between expectations and how to achieve them. Our work bridges this gap: we are the first to associate gradients of the structural loss used by causal discovery methods with intervention targeting. We show how to bring all the necessary components together in a simple manner that achieves strong empirical performance and is agnostic to the underlying gradient-based causal discovery framework. GIT is accompanied by a theoretical analysis, which underpins its validity. We believe all this is a proper scientific contribution with value to the community. \n\n*Questions:*\n1. [Clarification of interventional data acquisition] - Once a target node with the highest score is identified, an intervention is performed on that node (in the real, underlying model). This effectively changes the joint distribution of the data (see Equation 2 in our paper and lines 107-116). We sample observations of all random variables in the graph from this *new* distribution. We then add this new information to the set of interventional data $D_{int}$ (see Algorithm 1) and retract the intervention in the real model. BnLearn apart from datasets provides also models which allow conducting such operations and collecting arbitrary large datasets. \n\nPlease let us know if the above answers the Reviewer’s comments and questions. We would also be more than happy to address any other suggestions. In case there are none, and given the Reviewer’s positive outlook on soundness, presentation, and contribution, we would gently ask the Reviewer to consider increasing the score.\n"}]

Author rebuttal:
We would like to thank all the Reviewers for taking the time to review our work and providing us with insightful feedback. We are glad that the Reviewers appreciate the strengths of our paper, including clear writing and good presentation (Reviewers 6LvC, qbh5, 8Vao, E5qP), extensive experimental results (Reviewers 6LvC, qbh5, 8Vao, E5qP), significance of the studied problem (Reviewers 6LvC, qbh5, 8Vao, E5qP), and novelty of our approach (Reviewers 6LvC, 8Vao). It is good to hear that our study has no serious weaknesses (Reviewer 6LvC), is technically sound (Reviewers 6LvC, zVWz), and presents a clean solution (Reviewer E5qP). 

We provide specific answers to the Reviewers' individual concerns posted as separate comments below and attach a pdf file with figures referenced in individual responses.


Meta-review: The paper introduces a novel approach called Gradient-based Intervention Targeting (GIT) for efficiently selecting intervention targets in the context of causal discovery. It utilizes gradient information to identify the most informative intervention targets, with a focus on minimizing the number of interventions required for causal graph learning. The authors extensively validate GIT through experiments on both synthetic and real-world datasets, showcasing strong performance, particularly in low-data scenarios. There were some questions and concerns raised by reviewers including the performance of the baselines and how partial information is added. The paper would benefit from addressing these comments.
Decision: Accept (poster)