Sample Efficient Bayesian Learning of Causal Graphs from Interventions
Authors: Zihan Zhou
Muhammad Qasim Elahi
Murat Kocaoglu
Venue: NeurIPS 2024 poster (2024)
Keywords: Causal Discovery
Bayesian Learning
Sample Efficiency
Primary area: causal_inference
TL;DR: We propose a sample efficient causal discovery algorithm that learns  the causal graph in a Bayesian approach.

Abstract: Causal discovery is a fundamental problem with applications spanning various areas in science and engineering. It is well understood that solely using observational data, one can only orient the causal graph up to its Markov equivalence class, necessitating interventional data to learn the complete causal graph. Most works in the literature design causal discovery policies with perfect interventions, i.e., they have access to infinite interventional samples. This study considers a Bayesian approach for learning causal graphs with limited interventional samples, mirroring real-world scenarios where such samples are usually costly to obtain. By leveraging the recent result of Wienöbst et al. [2023] on uniform DAG sampling in polynomial time, we can efficiently enumerate all the cut configurations and their corresponding interventional distributions of a target set, and further track their posteriors. Given any number of interventional samples, our proposed algorithm randomly intervenes on a set of target vertices that cut all the edges in the graph and returns a causal graph according to the posterior of each target set. When the number of interventional samples is large enough, we show theoretically that our proposed algorithm will return the true causal graph with high probability. We compare our algorithm against various baseline methods on simulated datasets, demonstrating its superior accuracy measured by the structural Hamming distance between the learned DAG and the ground truth. Additionally, we present a case study showing how this algorithm could be modified to answer more general causal questions without learning the whole graph. As an example, we illustrate that our method can be used to estimate the causal effect of a variable that cannot be intervened.

Sample Efficient Bayesian Learning of Causal Graphs from Interventions
Zihan Zhou'
Muhammad Qasim Elahi"
Electrical and Computer Engineering
Electrical and Computer Engineering Purdue University elahi0@ purcueeeeuue
Purdue University zhou1 Mhou1244@purduee edu
Murat Kocaoglu
Electrical and Computer Engineering
Purdue University
Saoocaogluupurducee
Abstract
Causal discovery is fundamental problem with applications spanning various areas in science and engineering. It is well understood that solely using observational data, one can only orient the causal graph up to its Markov equivalence class, necessitating interventional data to learn the complete causal graph. Most works in the literature design causal discovery policies with perfect interventions, i.e., they have access infinite interventional samples. This study considers a Bayesian approach for learning causal graphs with limited interventional samples, mirroring real-world scenarios where such samples are usually costly obtain. By leveraging the recent result of Wienöbst et al. (2023) time, we can efficiently enumerate all the cut configurations and their corresponding interventional distributions of a target set, and further track their posteriors. Given any number of interventional samples, our proposed algorithm randomly intervenes on set of target vertices that cut all the edges in the graph and returns a causal graph according to the posterior of each target set. When the number of interventional samples is large enough, we show theoretically that our proposed algorithm will return the true causal graph with high probability. We compare our algorithm against various baseline methods simulated datasets, demonstrating its superior accuracy measured by the structural Hamming distance between the learned DAG and the ground truth. Additionally, algorithm could be modified to answer more general causal questions without learning the whole graph. As example, we illustrate that our method can be used to estimate the causal effect of a variable that cannot be intervened.
uniform DAG sampling in polynomial
present case study showing how this
Introduction
Causal discovery refers to learning the underlying causal graph of data generating process using combination of observational and interventional data. This a fundamental problem with applications across various areas including economics, genomics, meteorology, could computing, and etc. [Pearl]
2009| Hoover 1990 King et al. [2004] Ikram et al., 2022 Runge et al. 2019]. In recent decades, the technological progress has facilitated the accumulation of vast quantities of observational data, i.e., data collected without perturbing the underling causal mechanisms. However, with only observational data, can only recover the causal graph up its Markov equivalence class (MEC) [Verma 1991
Andersson et al. 1997]. In general, interventional data, i.e., data collected after a perturbation in
*Equal Contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the system, is needed to learn the whole graph. Therefore, many recent works aim to use both observational and interventional data [Choo al. 2022 Squires et al. 2020 Shanmugam et al. 2015
He and Geng
2008 Hauser and Bühlmann
2014
These works perfect do(X) intervention [Pearl 2009 on set of intervention targets X and can be categorized along various dimensions. One such dimension is whether they are adaptive on non-adaptive. Non-adaptive approaches (Shanmugam et al. 2015), determine the intervention targets before any interventions (experiments), whereas adaptive algorithms [Squires et al. 2020 Choo et al. 2022] can suggest the next intervention targets based on previous experiments. Non-adaptive methods can parallelize experiments, while adaptive ones are sequential but demand fewer interventions to learn the entire graph [Choo and Shiragur] [023). J. These works provide theoretic guarantees that
the experiments are sufficient to learn the graph. Diang and Aragam| (2024) established conditions under which latent causal graphs are nonparametrically identifiable and can be learned from unknown interventions.
Nevertheless, these studies operate under the assumption that an infinite amount of interventional data can be gathered after each intervention. However, in most real-world scenarios, collecting interventional data is considerably more challenging. For instance, while modern single-cell RNA sequencing technologies have facilitated the collection of vast amounts of gene expression data for downstream tasks [Stuart and Satija 2019 Zhou et al. 2022]. accurately perturbing each gene remains difficult [Chandrasekaran et al., 2024 Uhler and Shivashankar] [017]|Sharma Sharma et al.) [2022]. Consequently, practical upplications tend to favor interventional methods that require fewer data, although this aspect receives less attention. To bridge this disparity, our work assumes access to an infinite oracle of observational data, while only a finite number of interventional samples can be acquired for each intervention.
Among those that consider a limited number of interventional samples, the majority employ Bayesian approach. This method offers several advantages, including the ability to make finer distinctions among different graphs and resilience erroneous categorical decisions in the face of limited interventional samples. These studies can be categorized based on whether they assume a parametric structural causal model (SCM). Many works, such as those by Heekermann al.] [1997). Annadani et al. [2024), Toth et al. (2022). make certain assumptions about the SCM, such as additive Gaussian noise or linear causal models. However, their results will be inaccurate if the underlying SCM does not adhere to these assumptions. In contrast, the only non-parametric work [Grrenewall jet al.) 2019] assumes that the ground truth causal graph is forest of trees. Each undirected component of a tree with n nodes contains n Directed Acyclic Graphs (DAGs) in its MEC, which facilitates the tracking of the posterior of each possible DAG. For general undirected graphs, the MEC size could be exponential to n [He et al. 2015 Meek 1995] which makes the Bayesian posterior updating intractable. In this study, we adopt a non-parametric approach to mitigate the risk of erroncous outcomes resulting from assumptions about the SCM while mediating the problem of exponentially many DAGs in the MEC. We additionally assume causal sufficiency and faithfulness. Causal sufficiency asserts the absence of latent confounders, while faithfulness implies that every conditional independence relation that holds in the probabilistic model is entailed by the d-separation property of the causal graph. Given these assumptions, the PC algorithm (Spirtes al. [000]] can be employed to identify all v-structures in the causal graph, followed by the application of Meek Rules [Meek] [995] to derive the essential graph. The subgraph induced by the unoriented edges in the essential graph comprises multiple chordal chain components and can be oriented independently from other unoriented chain components and the oriented subgraph [Andersson al. 1997]. Given our assumption of infinite observational data and that PC algorithm and Meek Rules are complete, i.c., they orient all the edges that can be identified from the data, our focus lies on fully orienting the undirected chordal chain graphs (UCCG) of the essential graph of the ground truth causal graph. The main contributions of our work are listed below:
We study the causal discovery problem with limited interventional samples and propose an algorithm to solve this problem in an Bayesian approach. We analyze this algorithm and show in theory that it can learn the true causal graph with high probability given a large enough number of interventional samples and calculate the convergence rate.
We conduct experiments on simulated datasets with random chordal DAGs to compare our algorithm with other baseline methods. The results show that our algorithm outperforms other baselines in that it takes fewer interventional samples to receive the same accuracy.

---

Additionally, the performance of our algorithm is stable across different settings (order and density of the random DAGs).
We discuss how we can modify our algorithm to answer more general causal questions without learning the whole graph using DAG sampling from the MEC. We show how we can estimate the posterior of a set to be the backdoor adjustment set of a causal query given the essential graph and some interventional data as an example. We further show through simulated experiments that we can modify our algorithm to estimate causal effects of variables that cannot be intervened.
Outline of the paper: In Section 2 summarize the related works. In Section 3 we state the preliminary notations and background knowledge. In Section 4 we describe how we setup the initialization steps of the main algorithm. In Section we describe the algorithm with details and analysis on the convergence to the ground truth. In Section [ we discuss how our algorithm can be modified answer more general causal questions with an example. In Section 7 experiment results on simulated datasets and compare with baselines. In Section discussion of limitations and future extensions.
we present the
we conclude with
2 Related Works
We can roughly divide the causal discovery methods into 3 categories: non-adaptive, adaptive, and Bayesian. Non-adaptive methods design intervention targets for each experiment before retrieving interventional samples. Since no information is shared between experiments, they can be conducted
in parallel. Eberrardd [2007] discussed non-adaptive methods as fixed searching strategies and they show that in the worst-case scenaris Olog n. size "
2 interventions are necessary to orient the whole causal graph, regardless of the adaptivity of the afgorithm. [Hyttinen et al.) (2013) show the connection between orienting causal graph via intervention and the concept of separating system from combinatorics. Ghassami et al. (2018) studied the problem of orienting the maximum expected number of edges with a budgeted number of size 1 interventions. Kocaoglu al. [2017). Lindgren
it al. (018)) studied the problem of non- non-adaptive causal graph learning while minimizing intervention costs when each vertex is assigned with a different intervention cost. Many of the early works in causal discovery are non-adaptive, and therefore they construct the theoretical basis of causal discovery algorithm. Separating system is also used in our proposed method.
Adaptive methods make the decision of next intervention based on the results of previous experiments. Less interventions usually required than non-adaptive counterparts. [Eberhardi] [2007] compares adaptive strategies with non-adaptive ones and propose a heuristic algorithm. He and Geng (2008)
proposed MinMaxMEC and MaxEntropy algorithms that select the next intervention target that minimizes the maximum /-MEC size or maximizes the intervention entropy respectively. |Hassrr and Bühlmann 20014) proposed OptSingle which calculates the target that minimizes the maximum number of unoriented edges in the interventional graph. Squiires et al. (2020) show that any algorithm would take at least [ size 1 interventions to recover the whole graph and proposed a two-stage active learning algorithm. In the first stage, it finds the directed clique tree representation of the unoriented graph and orient the residuals separately in the second stage. Choo et al. [002 show that a size I invervention set can orient the whole graph if and only if it cuts all the covered edges in the ground truth DAG, and propose learning algorithm that intervenes on a separator in each experiment to iteratively decrease the size of the currently unoriented components.
The aforementioned works all assume the existence of infinite intervention oracle. The Bayesian approach is usually used when this assumption is untenable. Heckerman et al. (1997) investigated learning Structural Causal Models (SCMs) under the assumption that each local likelihood is combination of multinomial distributions and all variables are discrete. Similarly. Buntine [994] discussed simple linear local likelihoods involving both discrete and continuous variables. Tong and Koller [200T) proposed an active learning algorithm for Bayesian network learning. Previous studies typically employed Markov Chain Monte Carlo (MCMC) for sampling Directed Acyelic Graphs (DAGs) to estimate posterior distributions over DAGs and function parameters, which grow exponentially with the size the model. AAchary et al. (2188) studied the problem of distinguishing two causal models on the same graph with limited interventional samples. Nishikawa- TooiiaaawwTToyyyy et al. [2022] uses variational inference and GFlowNets [Bengio et al. 2023] to learn and parameterize the joint posterior distribution over DAGs and mechanisms while assuming lincar model and equal
3

---

noise variances. Recent researches Lorch et al. 2021 C Charpentier et al., 2022 Cundy et al. 2021 Toth al., 2022 Hägele et al. 2023 started leveraging gradient information for more efficient inference, while they suffer from poor inference quality. These studies all make specific parametric assumptions regarding functions or noises in the SCM, which lead to incorrect outcomes when these assumptions are violated. Kuipers et al. [2022) combines constraint-based methods and MCMC methods to efficiently search DAGs, but no guarantee of convergence is provided. To circumvent such issues, Greenewald et al. [011 directly update the posterior of specific subgraph containing the root when the graph is a tree without any constraint on the SCM. However in practice, causal graphs are usually more complicated than trees, which motivates our work.
3 Preliminaries
A causal graph D = (V, E) is a directed acyclic graph (DAG) where the vertex set V represents group of random variables. In the context of D, directed edge (X, Y) E E from variable X to variable Y (denoted as X + Y) signifies that X serves as an immediate parent of Y. We denote the parent set of variable Y by pa(Y). The cut at vertex set X, denoted as E V \ X], constitutes the set of edges between X and some vertex in the set V X. According to the Markov assumption, the joint distribution can be decomposed specific conditional independence (CI) relationships among variables via d-separation statements. The d-separation serves as criterion to determine whether set of variables X is independent of another set Y, given a third set Z. This approach links dependence to connectedness, meaning the existence of connecting path, while it associates independence with the absence of connection or separation. A set of DAGs is deemed Markov equivalent when they entail identical conditional independence (CI) statements. All Markov equivalent DAGs must have the same adjacencies and unshielded colliders (or v- s-ruucctures). An unshielded collider is graph structure of the form A + B t C' where A and C' are non-adjacent vertices. The set of all Markov equivalent DAGs called Markov Equivalence Class (MEC). We denote the set of all DAGs that is Markov equivalent to D as (D).
P(v) = P( P(v)lpa(X,)) (a)).)) A causal graph entails
Definition (Faithfulness (Zhang and Spirtes, 2012]. If the population distribution exhibits a conditional independence relation only when there exists corresponding d-separation statement in the causal graph, then we say that the population distribution is faithful to the causal graph.
The positivity assumption is fundamental for making causal inferences. It asserts that, in theory, every individual possesses a non-zero chance of being both exposed and unexposed [Hernan and Robins 2020). In many cases, we have access to abundant observational data, which allows for precise estimation of the true observational distribution. The no positivity violation assumption is merely needed for theoretical guarantees to hold while not required by the algorithm. We assume access to the observational distribution, and the observational distribution is faithful to the true causal graph, with no positivity violations.
partially directed acyclic graph (PDAG) is partially directed graph free from directed cycles. All Markov equivalent DAGS can be represented by a completed partially directed acyclic graph (CPDAG), denoted by C. A DAG D can be represented by CPDAG when they share the same set of adjacencies and unshielded colliders, and every oriented edge in the CPDAG is also present in DD [Meck] 2013). CPDAGs are chain graphs with chordal chain components [Andersson et al. 1997]. In graph theory, chordal graph is one in which cycles of four more vertices always contain an additional edge, called a chord. We denote the set of all chain components of PDAG P as CC)
An intervention on a subset of variables W C V, denoted by the do-operator do W w). involves setting each W, E W to Wj. For every intervention, we have an induced post-interventional graph denoted by D3 with incoming edges to vertices in S removed. We denote the interventional and observational distributions as PD (v) and (v) respectively for given DAG D. Using the truncated factorization formula over the post-interventional graph (Dz), we have the following:
(V) P(V do ( = w)) II P(ulpa(v)) veW
Where must be consistent with the intervention do(W- w). Consider a set of intervention targets = (S1, .2., Sn where each S, C for all E [n]. For every target S. E S, we define the collection of all possible cut configurations, i.e., all possible orientations of edges in E(S,, V StJ, as C₁ (S.) for all A [ns:]. Also note that rss < 2 2/. where dn is the maximum degree of the graph.

---

Additionally, for bounded size intervention targets i.e., | S k, we have ng, 2h We use the notation Ps ( (V) to represent the interventional distribution in (() with the cut configuration (S,). Also we use the notation (S,) for the cut configuration in the true DAG D Given an intervention set Sj, if we assume perfect intervention, one can recognize all the edges adjacent to vertices in S; and further apply Meek Rules. The resulting PDAG is called an interventional essential (I-essential) graph of 'D denoted as (D)) When S₁ empty, essential graph. I-essential graphs are also known to be maximally oriented partially directed acyelic graphs (MPDAGs). We denote an MPDAG as M and the I-essential graph with (s,) as (S.) MPDAGs are also chain graphs with chordal components [Hauser and Bühlmann 2012). We denote the KL divergence between two distributions p, q as (KL(p)
the observational
Algorithm Initializations
Assume the true DAG is D', our algorithm aims to return a most 'probable' causal graph D given N interventional samples. With the access to infinite observational data, we can retrieve the essential graph G = E(D") by PC algorithm (Spirtes et al. 2001] and joint distribution P(V). Here we describe how we compute the separating system of G' and the causal effect of given intervention set.
4.1 Separating System
As mentioned in Section 2 separating system plays the key role for non -on-adaptive intervention design of causal discovery. Roughly speaking, separating system of subsets such that for every pair of elements from the set, there exists at least one subset which contains exactly one element from the pair. Consider an undirected complete graph G of vertices indexed as 1...., n,, a separating system S on [zi] would cut every edge of G. In the worst case, a separating system is needed to learn the causal graph with G as its essential graph (Shanmugam et al. 2015). 5) If we further bound the size of each S E S such that [S] < k, k < 2 the resulting set is called (7t k)) -eeparrtg system. We provide the formal definition below:
of elements is collection
Definition 2 (n, -SSepaarag System Katona 1966 Wegener 1979]. An (n, -s)-sprraating system on [n] is a set of subsets S = {S,, , S2, Smf such that [S.] S. k and for every pair i,j there is subset S 8 such that either S,j $ S o & S.j S.
We discuss the detailed steps of how we construct the (n, k)-separating system in Appendix D
4.2 Enumerating Causal Effects
To use Bayesian approach, we need to construct set of disjoint events and track their posteriors. Here we consider the events as interventional causal effects when we intervene on a set of vertices. By the assumption of faithfulness, Lemma I shows that the post-interventional distribution is determined by the edge configurations that are adjacent to vertices in the intervention set. |Perkovic (2020) proposed formula is identify any causal effect in MPDAG. One can enumerate all valid edge cuts and use the identification formula to calculate the post-interventional distributions. Here we propose simple Algorithm to enumerate through all possible configurations of given S
and calculate the post-interventional distribution C(()) (V) via DAG sampling. For each candidate configuration (S), we check if it contains invalid structures, i.e. unshielded colliders cycles. If it is valid, we apply Meek Rules to get the MPDAG Mo,(s) which is an I-essential graph (D*) for some DAG (c) E [D*] that is consistent with (S). The chain components of M are chordal graphs and can be oriented independently [Hauser and Bühlmann, 2012). To efficiently calculate the interventional distribution, we use a DAG sampler [Wienöbst et al. 2023) to sample a DAG for each chain component and replace the edges in Mc, with the ares the sampled DAG to get fully oriented graph D. The sampling process takes linear time. Given the DAG D, the interventional distribution could be calculated by using the Equation Oover the DAG.
5 Algorithm Design and Analysis
In the previous section, we discuss two key steps for the algorithm initialization, which include the construction of (n, (nnkk)sssppa -eeparrrtg systems and enumerating causal effects for all possible cutting edge
5

---

configurations for all the intervention targets in the separating system. For a given intervention target S,, we utilize the following result that under the faithfulness assumption, shows that we have unique interventional distribution for every cutting edge orientation Cy(S.).
Lemma 1. (Elahi et al. 2024y Assume that the faithfulness assumption holds and D' is the true DAG. For any DAG D1 + D if P... = P for some S S V, they must share the same cutting edge orientation C(S).
Lemma Tallows to uniquely orient cutting edges for every intervention target in the separating system, which in turn orients every edge and gives us the true DAG. We use the notation Dab
DKL( (KL (C.((s)) (V) (. (V)) > Va + b, Va, b E [ns, and D == millyagb Va,be(ns,] ab- The idea is to use the interventional data do(S, = s;) to determine the true cutting edge con- figuration (S,),) and repeat this for all intervention targets in the separating system. Suppose we have access to Ma i.i.d. samples from the intervention do(S, 8;), which we denote as Datado(e.) {Vi, -2, Vm,, J. We define the posterior probabilities of (S, for all possible cutting configurations at S,, i.e., for all j E [ns,] where ns, S 2kmm as follows:
Definition 3. (Posterior Probabilities of Cutting Edge Configurations) Consider an intervention target S, and collection of all possible cutting edge configurations C,(S,) for all possible cutting configurations at S,, L.e., for all j E [ns,] and the interventional dataset of iid. samples Data
{V1, V2, Vms.): J. We define probabilities of Cutting Edge Configurations as:
(S,) (V1, V2:... Vm., Pj
(SC) Datado(s;))
Vj E [ns.] VS, E
(2)
Σ 128;
Ps. (8.)) (V1, V2, ... Vmn.) Pa
where Po for all a E [ns,] are the set of priors such that Exs Pa
Given the fact that the interventional samples are i.id we can rewrite the posterior probabilities as
Ths Pe.
(S.)
(V+)) Pj
(S.)(S.) Data
Vj [ns.]. VS: S
(3)
U8: Σ
I p. (8:) (S.( (Ve) Pa
Assumption 1. We assume access the observational distribution that is faithful the true causal graph. Furthermore, we have log (fa(8.)
< B for every intervention set S E S and for all
a. E [ns,]-
The second half of the assumption can be seen as a version of the positivity assumption commonly used in causal discovery and many other applications. We show that for the problem of learning the true cutting edge configuration, the posterior consistent, i.e., as the number samples ms - oc, the posterior of the true cutting edge configuration given the data converges to I with high probability.
Lemma 2. (Posterior Consistency) Consider an intervention target S; E S and the corresponding true cutting-edge configuration (*.).. As the number of samples ms; - oo in Datado(s.) = {V1, ......, Vm,,) }, the posterior of the true cutting-edge configuration (S.) Datado(ss)) converges to with high probability. More precisely, we have the following high probability lower bound on the posterior probability of the true cutting-edg edge configuration.
1
PSC*(S.) Datado(a)) 2
w.p. al least 1 -
1 + an exp (0(m))) - az az my In
(4)
Where and are constants depending on the prior and the problem instance. Thus, for any smull choice of the probability with a sufficiently large number of samples ms the posterior of the true cutting-edge edge configuration (S.) Datado(s.)), converges with a probability at least 1 - 6.

---

Note that the randomness in the seshh-rbbbbilityy result in Equation 4 arises from the finite sample size. Lemma gguarantees that with sufficiently large number of samples from interventions on S, the posterior of the true cutting edge configuration (S, Dota) converges to with high probability. However, in scenarios where we want know ahead of time how many interventional samples we need from every target S; E S to ensure that the posterior of the corresponding true cutting orientations (S.) Datado(s,) 2 - 7 with high probability, we need to determine the required number of samples. The parameter 7 2 0 represents the error tolerance. We extend Lemma to provide the minimum number of samples ms required for an intervention on the target set S; to ensure that the posterior of the corresponding true cutting orientations is greater than some threshold.
guaranteess
Theorem 3. Given that the Assumption hold, consider an intervention target S, E S such that [S&] S k and the corresponding true cuiling edge configuration C* (S:)). If the number of samples Mss in Datado(s.) (V1, V2,.., Vm,;) } salisfies the following:
28 (De y2
2(++
2
2kdm (1 - -7)(1 - p²)
Ma
In
In Doc
(5)
8
p'
where p' is the prior assigned to the true cutting-edge configuration C*:S)), then we have (S)) Datado(s.)) 2 1 with probability least 1 ò.
Since we have multiple intervention targets in the (n, -seeparttng system of the form S S2..Sp such that [S:] S k for all i E [p]. We can have a total of bad events one for every target set S, E S where posterior of corresponding true cutting edge configuration (*,S)) is not greater than the desired threshold 1 - 7. Thus we extend the Theorem Bas follows:
Corollary 4. Given that Assumption[] hold, consider a separating system of the form S = S2, such that [Si] S k for all E (p). If the number of samples my; in Datado(s.) {V1, V2,..., Vmn,) for every target set S; E S satisfies the following:
2,3
2(k++))dm
2 Ds.
2kdm (1- 7) 1²))
(Dai )2 (In
my.
5'
p"7
where p" is the prior assigned to the true cutting edge configuration C* (S:) and = p. then we
have (S.) Datado(s.)) 2 1 with probability at least 1 - 5 for every S E S.
To ensure that for every target set S, S, we have the posterior probability of the corresponding true cutting-edge configuration P(C* Data 2 1 1-7, we need ms samples (as in Equation 6) from every target. Therefore, for the causal discovery problem with p targets in separating system, we require total of p ms, samples.
Based on the analysis, we propose Algorithm as the main algorithm. We start by calculating (n, k)>separating system S using the labeling procedure described in Appendix for the essential graph G (D"). and them identify all valid configurations C(S), VS E S using Algorithm 3 For each valid configuration. one can simply assume that their priors are uniform. In our algorithm, we assume that each possible DAG in [D*] are equally likely be the true DAG. Therefore we can calculate the prior more accurately using the MEC counting algorithm (Wienöbst et al. 2023). Specifically, for each valid configuration C& we find the MPDAG Mcx(S) that matches with by applying Meek Rules. Mc. is chain graph with chordal components that can be oriented independently. Thus, the interventional MEC size of Mc.(s) could be calculated by:
[M
II
||]]
MECO(M
The prior of each configuration could then be estimated by:
[[Mc
P(C)(S)) = Ec [[Mc(s))]
(8)
we are allowed to collect N total interventional samples, we can randomly choose target set from the (n, -)sseaarg system for each sample. Algorithm itterate all valid configurations to calculate
7

---

Algorithm 1: Sample efficient causal discovery in Bayesian approach
Data: Input UCCG G = (V; E), (n, separating system S, and observational joint distribution Pobs (V), prior of each configuration (SC(()), number samples N
Result: Output posterior Is p (v)os)))) of each configuration to be true and candidate DAG
for i [N] do
Randomly choose larget set S E S:
Sample do((S) from Ps; for C&(S) C(S) do
L Calculate likelihood P(vaes)CC((S) using Algorithm
for Cx(S) C(S) do
Update posterior and prior: P (CL())(C) + (eeos)) P(Cass) PS)+ ( Vao(s))
P(C4(S))xP(Maas)) (a))
D 4- G. Svisit 0:
while S & Swinit do
C2(S) arg (8) (S) I' (CL
if (S) not compatible with Swint then
Remove Cs(S) from C(S);
Pass:
Replace edges in D with ares in (S););
Suisie + Suisit U (8);
return (C(S) (C(S))v
the likelihood P(V))(5) (S)) by sampling DAG from the interventional MEC. After calculating all the likelihoods, we can update the posteriors and priors. For the last step, we need to combine all the configurations of each (n, k) seeparatig set return DAG. We consider greedy approach. At each step, we choose the configuration with the highest posterior across all unvisited target sets that compatible with chosen configurations. Given the anytime nature of our algorithm, can propose a candidate DAG after each interventional sample. With a large enough sample number, according to Theorem our algorithm will return the true DAG with a high probability.
6
Case Study: Estimating Causal Effects of Non-Intervenable Vertices
Here we show how to use DAG sampler to estimate the causal effect when some vertex cannot be intervened in the causal graph. The detailed problem setup follow. D (V, E) is an undirected underlying causal graph, X, Y E V are non-adjacent vertices. We want to estimate p(y do(x)) using interventional data while X is not intervenable in the graph. Thus we cannot directly in Perkovic 2020) to estimate the causal effect. With the DAG sampler, we can first intervene on X's neighborhood Ne(X) and then sample DAG estimate the likelihood of each configuration being the true one in the causal graph. When we have large sample size, the posterior of the true configuration will go to with a high probability according to Lemma 2 Then, we iterate through each configuration and their posterior calculate the average divergence between the estimated and true causal effect. The divergence D here can be KL divergence or Total Variation Distance (TVD). If the ground truth causal effect is p", the interventional data is Data then D is formally defined
the method
D
Σ
C (xldo((()) P(C, P(Ca
(9)
C.EC((E(X))
In this experiment, we randomly create 50 causal graphs with n 5, p- 0.3, 0.6 using similar approach described in Section Then we randomly choose pair of non-adjacent vertices X, Y. We then intervene X and collect 100,000 samples. We plot D L and DIvD between estimated causal effect and the ground truth given different number of interventional samples. The mean and standard deviation are plotted in Figure We can see that as the number interventional samples increases, the estimated causal effect gets close to the ground truth and the variance is also decreasing. The differ- ence decreases sharply w.r.t. the number of samples, showing the efficiency of our proposed approach.
8

---

(a) n = 5, P =000003 0.3
(b) 1 = 6, 0.3
(c) n 7, p 0.3
(d) 7 5, 0.6
(c) 6, 0.6
(f) 7, 0.6
Figure 1: Average KL divergence and TVD between estimated causal effect and ground truth vs number interventional samples for random causal graphs.
7 Experiments
We compare the proposed Bayesian Causal Discovery algorithm with existing baselines. The first baseline, Random Intervention, intervenes randomly the graph separating system. In each step, one interventional sample is collected, and then we perform independence tests to learn the cuts the targets based on the collected samples from each intervention target. The second baseline is Active Structure Learning of Causal DAGs via Directed Clique Trees (DCTs) (Squires et al. 2020 The third baseline is the Staattvvty-ssensitvv search algorithm proposed in Choo and Shiragur [2033] It chooses the intervention target based on the clique tree representation of a chordal graph.
We generate random connected moral DAGs with order and density p using modified Erdös-Rényi sample approach, similar the process Squires al. [2020]. We start by generating a random ordering 7 over vertices. Then, for the tth vertex, we sample le its in-degree X; mar(1, Bin(n 1, p)). The vertices precede it in the ordering are uniformly assgined as parents. the last step, we apply the elimination algorithm in Koller and Friedman (2009) to chordalize the graph. The elimination algorithm uses an ordering that is the reverse of r. Based on the generated graph, we randomly sample the conditional probability table (CPT) that is consistent with the graph and strictly positive. The essential graph of the generated DAG is then fed into the causal discovery algorithms together with the Bayes network that is consistent with the DAG.
To measure the performance of the algorithms, we plot the Structural Hamming Distance (SHD) between the ground truth and learned DAGs with respect to the number of collected interventional samples. SHD counts the number of edge insertions, deletions, or flips transform from one DAG sample 50 random DAGs and calculate the mean and
into another. For each setting of n and standard deviation of SHD by each causal discovery algorithm. The mean is plotted as a curve and the shaded area around the curve represents the standard deviation. We use Chi-Square independence test from the Causal Discovery Toolbox [Kalainathan et al. 2020) to perform statistical tests with limited samples.
The results in Figure andd] show that our algorithm outperforms other causal discovery algorithms. Figure 2 shows the performance of causal discovery algorithms on complete graphs with order 5, 6, and respectively. Our algorithm uses significantly less samples reach low SHD and the number of samples required does not increase much with the order of the graph compared to the other algorithms. Figure 3 shows the results graphs with the same order but varying densities. Similarly. our algorithm uses comparable number of samples across different densities. In contrast, the baseline algorithms require much more samples denser graphs to reach the same SHD. To wrap up, in both cases, algorithm reaches low SHD using much fewer samples than the baselines

---

and is more stable across different settings. The results on larger graphs (n = 20) are provided in Appendix H..I The algorithm code provided at lnttps://github. com Catr/CuusaaaMaaa /
SaattnSaamlleeeeeee Discovery
()) n 5, Figure 2: SHD vs number of interventional samples for random complete graphs
(h) p
(c) n = 7,
ACIh LANO snveld
seriing UIROEC
(a) n 10, 0.1
(b) n 10, p == 0.15
(c) n 10, 0.2
Figure 3: SHD number of interventional samples for random sparse chordal graphs
8 Conclusion
In this work, we discuss the problem of learning causal graphs with minimum number of interventional samples. We propose an algorithm that solves this problem in Bayesian approach. Specifically, we keep track of the posteriors of interventional distributions of each target set in the (n, k) }>sepaarating system and then combine the configurations that have high posteriors to propose DAG. We show in theory that given enough samples, our algorithm can return the true causal graph with a high probability. Also, according to the Bayesian nature of our algorithm, anytime and check the output graph. Experiments on simulated datasets show that compared with the baselines, algorithm use significantly fewer interventional samples to achieve the same SHD. Additionally in the case study, we demonstrate that we can modify our algorithm to answer special causal queries with DAG sampling. For future extensions, it of great interest to decrease the space of posteriors being tracked, since on large dense graphs, it will be intractable to track all interventional distributions of target set. Besides, we can try to remove/weaken the assumptions like causal sufficiency and faithfulness while maintaining theoretical guarantees. Our work can potentially have some societal consequences including ethical considerations related to performing interventions and the risk of biased or partial understandings which may cause misled decision Decciiionmmkkin in real-world cases.
can stop the algorithm
Acknowledgement
This research has been supported in part by NSF CAREER 2239375, IIS 2348717, Amazon Research Award and Adobe Research.
References
Jayadev Acharya, Amab Bhattacharyya, Constantinos Daskalakis, and Saravanan Kandasamy. Learn- ing and testing causal models with interventions. Advances in Neural Information Processing Systems, 31, 2018
10

---

Steen A Andersson. David Madigan, and Michael D Perlman. A characterization of markov equiva- lence classes for acyclic digraphs. The Annals of Statistics, 25(2):505-54) 1997.
Yashas Annadani, Nick Pawlowski, Joel Jennings, Stefan Bauer, Cheng Zhang, and Wenbo Gong. Bayesdag: tradient-basee posterior inference for causal discovery. Advances in Neural Information Processing Systems, 36, 2024.
Yoshua Bengio, Salem Lahlou, Tristan Deleu, Edward J Hu, Mo Tiwari, and Emmanuel Bengio. Gflownet foundations. Journal of Machine Learning Research, 24(210)11-55, 2023.
Wray Buntine. Operations for learning with graphical models. Journal of artificial intelligence research, 2:159-225, 1994.
Srinivas Niranj Chandrasekaran, Beth A Cimini, Amy Goodale, Lisa Miller, Maria Kost-Alimova, Nasim Jamali, John Doench, Briana Fritchman, Adam Skepner, Michelle Melanson, et al. Three million images and morphological profiles of cells treated with matched chemical and genetic perturbations. Nature Methods, pages 1-8, 2024.
Bertrand Charpentier, Simon Kibler, and Stephan Günnemann. Differentiable dag sampling. arXiv preprint arXiv:2203.08520 2022.
Davin Choo and Kirankumar Shiragur. Adaptivity complexity for causal graph discovery. In Uncertainty in Artificial Intelligence, pages 391-402. PMLR, 2023.
Davin Choo, Kirankumar Shiragur, and Arnab Bhattacharyya. Verification and search algorithms for causal dags. Advances in Neural Information Processing Systems, 35:12787-12799, 2022.
Chris Cundy, Aditya Grover, and Stefano Ermon. Bed nets: Scalable variational approaches for bayesian causal discovery. Advances in Neural Information Processing Systems, 34:7095-7110, 2021.
Frederick Eberhardt. Causation and intervention. Unpublished doctoral dissertation, Carnegie Mellon University, 93, 2007.
Muhammad Qasim Elahi, Lai Wei, Murat Kocaoglu, and Mahsa Ghasemi. Adaptive online experi- mental design for causal discovery. arXiv preprint, 2024.
AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Elias Bareinboim. Budgeted experiment design for causal structure learning. In International Conference Machine Learning, pages 1724-1733. PMLR, 2018
Kristjan Greenewald, Dmitriy Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Kocaoglu llu, Enric Boix Adsera, and Guy Bresler. Sample efficient active learning of causal trees. Advances in Neural Information Processing Systems, 32, 2019.
Alexander Hägele, Jonas Rothfuss, Lars Lorch, Vignesh Ram Somnath, Bernhard Schölkopf, and Andreas Krause. Bacadi: Bayesian causal discovery with unknown interventions. International Conference Artificial Intelligence and Statistics, pages 1411-1436. PMLR, 2023.
Alain Hauser and Peter Büthlann. Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs. The Journal of Machine Learning Research, 13(1): 2409-2464, 2012.
Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 55(4):926-939, 2014.
Yang-Bo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9(Nov) 2008
Yangbo He, Jinzhu Jia, and Bin Yu. Counting and exploring sizes of markov equivalence classes of directed acyclic graphs. The Journal of Machine Learning Research, 16(1):2599-2699, 2015.
David Heckerman, Christopher Meek, and Gregory Cooper. A bayesian approach causal discovery. Technical report, Technical report msr-tr-97-05, Microsoft Research, 1997.

---

MA Hernan and J Robins. Causal inference: What if. boca raton: Chapman & hill/cre. Taylor and Francis, 2020.
Kevin D Hoover. The logic of causal inference: Econometrics and the conditional analysis of causation. Economics & Philosophy, 6(2):207-234 1990.
Antti Hyttinen, Frederick Eberhardt, and Patrik O Hoyer. Experiment selection for causal discovery. The Journal of Machine Learning Research, 14(1):3041-307,, 2013.
Azam Ikram, Sarthak Chakraborty, Subrata Mitra, Shiv Saini, Saurabh Bagchi, and Murat Kocaoglu. Root cause analysis of failures in microservices through causal discovery. Advances in Neural Information Processing Systems, 35:31158-33 111111111-177,,,,0 2022.
Yibo Jiang and Bryon Aragam. Learning nonparametric latent causal graphs with unknown interven- tions. Advances in Neural Information Processing Systems, 36, 2024.
Diviyan Kalainathan, Olivier Goudet, and Ritik Dutta. Causal discovery toolbox: Uncovering causal relationships in python. Journal of Machine Learning Research, 21(37):1-5, 2020.
Gyula Katona. On separating systems of a finite set. Journal of Combinatorial Theory, 1(2):174-19, 1966.
Ross King, Kenneth Whelan, Ffion Jones, Philip GK Reiser, Christopher H Bryant, Stephen Muggleton, Douglas B Kell, and Stephen G Oliver. Functional genomic hypothesis generation and experimentation by a robot scientist. Nature, 427(6971):247-255 2004.
Murat Kocaoglu, Alex Dimakis, and Sriram Vishwanath. Cost-optimal learning of causal graphs. In International Conference on Machine Learning, pages 1875-1884, PMLR, 2017.
Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
Jack Kuipers, Polina Suter, and Giusi Moffa. Efficient sampling and structure learning of bayesian networks. Journal of Computational and Graphical Statistics, 31atticss,110 31(3):639-650, 2022.
Erik Lindgren, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Experimental design for cost-aware learning of causal graphs. Advances in Neural Information Processing Systems, 31, 2018.
Lars Lorch, Jonas Rothfuss, Bernhard Schölkopf. and Andreas Krause. Dibs: Differentiable bayesian structure learning. Advances in Neural Information Processing Systems, 34:24111-24123, 2021.
Lars Lorch, Scott Sussex, Jonas Rothfuss, Andreas Krause, and Bernhard Schölkopf. Amortized inference for causal structure learning. Advances in Neural Information Processing Systems, 35: 13104-13118, 2022.
Daniel Malinsky. A cautious approach constraint-based causal model selection. arXiv preprint 1rXiv:2404.182322 2024.
Christopher Meek. Causal inference and causal explanation with background knowledge. In Proceedings of the Eleventh conference on Uncertainty artificial intelligence, pages 403-410, 1995.
Christopher Meek. Causal inference and causal explanation with background knowledge. arXiv preprint arXiv:1302.4972 2013.
Mizu Nisikkawa-Toomey, Tristan Deleu, Jithendaraa Subramanian, Yoshua Bengio, and Laurent Charlin. Bayesian learning of causal structure and mechanisms with gflownets and variational bayes. arXiv preprint arXiv:2211.0276. 2022.
Judea Pearl. Causality, Cambridge university press, 2009.
Emilija Perkovic. Identifying causal effects in maximally oriented partially directed acyelic graphs. In Conference Uncertainty in Artificial Intelligence, pages 530-539, PMLR, 2020.
12

---

Jakob Runge, Sebastian Bathiany, Erik Bollt, Gustau Camps-
Camps-Valls,, Valls, Dim Coumou, Ethan Deyle, Clark Glymour, Marlene Kretschmer, Miguel D Mahecha, Jordi Muñoz-Marí, et al. Inferring causation from time series in earth system sciences. Nature communications, 10(1):2553, 2019.
Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Learning causal graphs with small interventions. Advances in Neural Information Processing Systems, 28, 2015.
Atul Sharma, Pranjal Jain, Ashraf Mahgoub, Zihan Zhou, Kanak Mahadik, and Somali Chaterji. Lerna: transformer architectures for configuring error correction tools for short-and long-read genome sequencing. BMC bioinformatics, 23(1):25, 2022.
Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, prediction, and search. MIT press, 2001.
Chandler Squires, Sara Magliacane, Kristjan Greenewald, Dmitriy Katz, Murat Kocaoglu, and Karthikeyan Shanmugam. Active structure learning of causal dags via directed clique trees. Advances in Neural Information Processing Systems, 33:21500-21511, 2020.
Tim Stuart and Rahul Satija. Integrative single-cell analysis. Nature reviews genetics, 20k5)257-277. 2019.
Robert E Tarjan and Mihalis Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyelicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on computing, 13(3):666-579 1984.
Simon Tong and Daphne Koller, Active learning for structure in bayesian networks. In International joint conference on artificial intelligence, volume 17, pages 863-869, Citeseer, 2001.
Christian Toth, Lars Lorch, Christian Knoll, Andreas Krause, Franz Pernkopf, Robert Peharz, and Julius Von Kügelgen. Active bayesian causal inference. Advances in Neural Information Processing Systems, 35:16261-16275 2022.
Caroline Uhler and GV Shivashankar. Regulation of genome organization and gene expression by nuclear mechanotransdductinn Nature reviews Molecular cell biology, 18(12):11-7277, 2017.
Ts Verma. Equivalence and synthesis of causal models. In Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence, 1991. Elsevier, 1991.
Ingo Wegener. On separating systems whose elements are sets of at most k elements. Discrete Mathematics, 28(2):219-222 1979.
Marcel Wienöbst, Max Bannach, and Maciej Liskiewicz. Polynomial-time algorithms for counting and sampling markov equivalent dags with applications. Journal of Machine Learning Research, 24(213):1-44 -5, 2023.
Jiji Zhang and Peter Spirtes. Strong faithfulness and uniform consistency in causal inference. arXiv preprint arv: 1212.2500 2012.
Zihan Zhou, Zijia Du and Somali Chaterji. Kratos: Context-aware cell type classification and
interpretation using joint dimensionality reduction and clustering, In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2616-2625, 2022.
13

---

Supplemental Material
A Proof of Lemma !
Consider an intervention target S; and a collection of all possible cutting edge configurations (,,) for all possible cutting configurations at S,, i.e. for all j E [mss.] and the interventional dataset of i.i.d. J. We revisit some notations from the main paper. We denote samples Datado(s.) {VI, V2,..., Vm
the interventional distribution with cut configuration (S,) by (S,(S)). have ns, different cut configurations which we denote by (S.)). C2(S,) Cns, (S). Under faithfulness assumption we have (S.) + Ps: CC((S)) for all a + b, a, E [ns,]l Also note that for with (n, k) separating system we have ni; S 2kdm Without loss of generality assume Ci (S,) is the true cutting edge configuration.
We use the notation Dab == DRI( P.. (S.)) (V) I (C(())) (V) ) > 0 Va o b, Va, E [Ms.] and D == millyagb Va,beIns, Dab-
Let us consider Ps. (S.)) and (C,(())) only for now.
Ps. (C.()
(VL. V2, Vmn,)
Let L log
(10)
pe (8,) (V1, 12 Ven..
Since interventional dataset is composed of i.i.d samples we have:
may
(C(.s)) (v₂)
=
log
si Pss
(11)
(vj)
(c.((s))(v))) (v,)
1:
Let L log
(12)
Psi
(S.) (v,)
Lj
(13)
j=1
me,
(14)
1=1
Since C, (S)) is the true cutting edge configuration the interventional samples actually sampled
from p.c (S.) So we have the following:
C22(8.)
E|4 E
v. (86)
log PC (.. (S:)
(15)
log p.. (C.(S.) (v;)
E [(yg] E
v, (g~p(((81)
(C,( (v,)
(16)
E [[T,]] DRL(
Pe. (S.( (V)
CC.( (V) 17 > 0
(17)
Under the Assumption L; < 8 Vj E [ma.] for all Lj = log pC2 (v))
using hoeffding
p p,..::)
inequality with ma; samples we have:
20
P( L mg
De
12 2 c) < 2e
(18)
14

---

Suppose 2
2e 188
which implies c 2 In 2
1 2 me,
2x2edm
2m
Thus we have the following:
2 x 2kdm
8
P( - My, D
m32 In
(19)
2k
which implies that with probability of at least
2 we have:
2 2kd
-L mg D22
V 2 In
(20)
Using the definition of we have:
Ps: (Ca()s)) (V1, V2 on Vmn,
2 2hdm
log (((S))
2 my Di2 282ma, In
(w.p. at least
1- 2kd
(v1, V2. .... Venn)
5
(21)
Ps. (C((S))) (V1, V2y... Vmna)
Se maa Di2 D m2 in 2xahdem
(w.p. at least 1 2kd
(22)
Ps. (S.)
(Vi, V2,... Vmng)
pCa(S:) (V1, V2,..., Vmn,) ) S e (me; Dū2s 1012-- 223mmm, In 2x
((((S)) (V1. V2,..., Vengg)
(C((S))(V.
(23)
The equation 23 holds with probability at least 1 2mdm
Similarly using the union bound we have
with probability at least 8 we have the following Vj o 1, E [ns.]:
(S:) (V1, V2..... Vm.,) e (ma, Dij 2.9 2295m., In 2 ps.
(S. (V1, V2. Ven.) (24)
Now, suppose we assign a non-zero prior P/ > O to the all cut configuration C,(S:) Vj E [ms,] such that Σ = The posterior distribution can written as:
(S,) (V1, V2.... V Pl
(S,) Data
(25)
P.. (8.)) (V1, V2. Vmn.) Pj
From the result in Equation 24 with probability least 5 we have:
p4 (V1 (Vi
(S.) Datado(s.)) 2
16 (8.) (v....................... ps+ +,7 (6: (82) (V ( Van... (1 1% - 10
Pb
(26)
With probability at least 1 - we have:
P(C)(S.) Datado(e.)) >
(27)
118 (m., D.j mm, In 2xzztedm
D1 Di
pj
Since ns. < 2kd and D = milraaeb Ya,bE|ns,) D
With probability at least
we have:
P1
(S,) Data N
(28)
P1 + (1 kmdm e (ma, D*. v 2/33mmm 2xgkdm
15

---

(SC) Datado(s;)) 2 1
(w.p. at least 1-6)
me, Do: v //28mmm ma, in 2x2kdm
+ [1-P1]
p1 22kdm
(29)
which can equivalently written as follows:
PSC)(S)) Datazo(s.) 2 1
(w.p. at least 1 6)
1 an exp (( Ov - ms. In {)
(30)
Where on and 02 are constants depending the priors used and the problem instance. Note the in our proof the true cutting edge configuration C*(S.) Ci (S.). This completes the proof Lemma
B Proof of Theorem 3:
The Proof of the Theorem is the continuation of the proof of Lemma
Suppose we want
(S,) Datado(s.)) 2 ? we have:
(1 p1) p1)2kdmn e (mm,, D. 20 2x 2k2h
PLY
S
(31)
1-7
e ma; Der -0----2-1-000 2282mm 2x2kdm
P17
S 2kd (1 - -7)(1- - -p2)
(32)
2 2kd
2kd (1 (1 PI)
ma D
V 2,8mm
log
(33)
8
P1Y
Solving the above equation for number of interventional samples my; we have:
4.2 In 2(k+ +4D0
24dm (1-))(1-1))))))))
1624 lu2 g(k+1)dm
3 +3289 D* In 2kk+1)dm In 2kdda (2-x) pp.)
ms
1(D")
(34)
In order to simplify the expression we select the number of interventional samples ma as follows:
4 In 2) +4D"t In 24dm (1 (1--a1---- p1)
4,3a In 2(k+1)em +40%s In 2heem 71(1-p11
my;
1(D%)2
(35)
4,2 In 234+
24 (1 (1-2)(1-p))
4D= In
Ma
Pi7
(36)
2(De.}2
2.2
1(k+1)dm
2
2kd (1 (1- (1 P1)
Ms;
(De:yz
ln
De:
In
PTY
(37)
for the above choice of number of samples ma; we have the following result:
(S.) Data 2 1-7 (w.p. at least 1- 6)
(38)
16

---

Now, suppose p" is the prior assigned to the true cutting-edge configuration C*(S)). Consequently, for the following choice of number of samples ms.
2
2)
2
2kd (1 1--)(11- pp")
Ma. (De:)2
In
In
(39)
8
D
We have (S)) Datado(s,)) 2 1 1-7 with probability at least 1 8. Note the in our proof the
true cutting edge configuration C* C*(S:) (i,).. This completes the proof of Theorem 3
C Proof of the Corollary 4
Consider a separating system of the form S2,, .Spp such that [s;] I for all i e [p]. The Proof of the Corollary is simple application of union to result in Theorem if replace 5 by A in the Equation 39 for number of samples nwx then for particular S, E S we have p (S.) Datado(=;)) 2 with probability at least 1 E Taking union bound we have the
following result:
If the number of samples ma, in Datado(s:) {V1, V Vmn, } for every target set S S satisfies
the following:
2,2
(kk+))dm 8'
2
2kd (1 (1-))(1-
ms
(De.)2
De.
In
p'y
(40)
where p" is the prior assigned to the true cutting edge configuration (S,) and 8' 4. Then
p'
have with (S,) Data))(s.)) 2 1 -- with probability least 5 for every target set S E S. This completes the proof of Corollary
D Procedure to Construct Separating Systems
D.1 (n, -eeparatgg System
Lemma 5 (Shanmugam et al. 2015 ). There exists a labeling procedure that gives distinct labels of length I. for all elements [n] using letter from the integer alphabet {0, I.....a,, where = [log, ni
Furthermore, in every position, any integer letter is used at most [2] times.
The labeling method in Lemma 5 from Shanmugam et al. [2015] is described as:
Labelling Procedure: Let a >> be a positive integer. Let x be the integer such that a" < n S a=+1 [log, n2]. Every element E [n] is given label L(j) which is string of integers of length x + 1 drawn from the alphabet 10.,...., a} of size a + 1. Let n Paa" + ra and pa- + ra-1 for any integers Pd, Td, Td-1, where rа < a and rd-1 < d-1 Now,
we describe the sequence of the d-th digit across the string labels of all elements from n:
1. Repeat the integer 0 a total of ad11 times, and then repeat the subsequent integer, 1, also dd1 times from (0, 1..... a - 1} till p
2. Following this, repeat the integer o number of times equal [ 1, and the repeat the integer [ times, continuing this pattern until we reach the nith position. It is evident that the nith integer in the sequence will not exceed
3. Each integer that appears beyond the position d- Paa1 is incremented by 1.
Once we have set of string labels, can easily construct (n, -eeparrting system using the following Lemma:
Lemma 6 (Shanmugam et al. 2015). Consider alphabet A = 10: [ of size [T] + where 2. Label every element of an n element set using a distinct string of letters from A of length
72 k <
1 [log a n using the labeling procedure in Lemma 5 with
-[- For every 1 S S l and 1 < b < mn we choose the subset Ta of vertices whose string's a-th letter is b. The set of all such
subsets S = ( bf is k-separating system n elements and [S] S (T [log e n².
17

---

D.2
G-Separating System
While an (n, -spparatgg system separates every edge the complete graph of order n, usually the causal graphs are sparse with much fewer edges. Thusly, we also provide simple algorithm to construct a separating system that cuts all the edges in graph.
Definition 4 (G-Separating System, Definition of Kocaoglu et al. 2017 Given an undirected graph G (V, E), set of subsets I S 2V is G-separating system if for every edge {u, E, there exists E I such that either (u E I; and u & I;)or (u & I and u E I.).
Kocaoglu et al. [2117] show that an intervention set learns every DAG entailed by G if and only is G-separating system. For graph with vertices, G-separating system 8 = S1, S2 .2., S. such that |S s k; vi E [m]. is called a (n, -ssppratt system. There are many ways to get a G-separating system. Algorithm[]es gives simple algorithm that uses vertex coloring. We first find the perfect elimination order (PEO) of G. PEO can be found by maximum cardinality search [Tarjan] and Yannakakis 1984]. Then based on the reverse PEO, vertex with a number 7 E [سي] where w is the clique number of G. w colors are guaranteed to color G since G is a perfect graph. In each step, not used by its visited neighbors, thus no adjacent vertices will have the same color. For each vertex, the union of and its visited neighbors induce a clique, meaning that its color number is bounded by w. Consequently, Algorithm reeturss a G-separating system with w intervention sets as it cuts every edge G. We use f(-) to represent function that maps set of vertices set of colors that are used by the vertices. N (N) denotes the neighborhood of a vertex v E V.
apply greedy coloring to assign each
assign a vertex with the minimum color number that is
Algorithm 2: G-separating system of given unoriented graph G
Data: Input UCCG G (V. E): [V| n
Result: Output the G-separating system S Initialization: Find the PEO and w of G by Maximum Cardinality Search; L + Reverse L. S; = 0, vi [w]. f(V) = {0}:
for i to do
f min
f(N().))):
f(4,) + (
S. - Sc, {L}}
Ungwu (S:}:
return
E Algorithm for Enumerating Causal Effects
Algorithm 3: Enumerating all interventional distributions and priors of intervention set on an undirected graph G
Data: Input UCCG G (V, E), intervention V
Result: Output all possible interventional distribution pC (V) and P(C(S))
Initialization: Enumerate all possible edge configurations C(S) that are adjacent to vertices for (s) C(S) do
if (S)
(S) not valid then
Remove (s) from C(S); Pass:
Get the MPDAG Mc by applying Mcek Rules; for H E (C(M) do
Sample DAG DD from [H];
Replace edges in G with ares in Dir;
Calculate P (8) (V) with Equation
Calculate the prior (SC) with Equation
return C(S), (8)) (V), ((C(S))
18

---

F Discussion on Computational Complexity
For Bayesian approach of learning causal graph, we mainly care about the space complexity because for run time, all the steps (e.g. calculating likelihood, updating posteriors) are efficient. For dense graphs, a fully Bayesian method and our algorithm are both computationally expensive. For example, for complete graph with order n. Fully Bayesian method needs to store (n!) distributions because there are such many DAGs in the MEC. Our method needs to track O(2"-1) posteriors, which is less than fully Bayesian but still exponentially many and would be intractable when n is large. However, our method would be a lot better when the given graph is sparse, i.e. the maximum degree in the UCCG G' is around log n. If we consider atomic interventions, the valid configurations around vertex V E V, [[(v] < 2d n. While the MEC size of a UCCG with order n. is at least n, i.e., |[G]] 2 n. The equality holds if and only if G' is tree. Thus, our method is at least as good as a fully Bayesian method. However, even for sparse graphs, its MEC size could be exponentially many in n. Let's consider the following example. Given sparse UCCG G with order n. G consists of Tlogn] small cliques Each small clique contains [log m| vertices. The cliques are connected together to form a "cliuue line'. The MEC size of G' would be:
|[_]| [[log]])) [T
(41)
According to Stirling's Approximation, we have:
||ā]| O(( log n] yloR m) (log n) -b)
(42)
E O[log n [lox ml -1 [log r1] m 3)
(43)
E Olelogllog [log " [log n| -)
(44)
E On log (1
(45)
Which is approximately Onlood(oogn) If we consider an interventional target of size k for our algo- rithm, there are at most 2kd = n² configurations to track. If is large enough, h < log[log n), Ak > 0. Thus, the MEC size for G is greater than any polynomial complexity, while our algorithm tracks at most polynomially many configurations.
G Further Discussion on Case Study
we mentioned that the Causal Identification Formula for MPDAG from Perkovic [220)] could also be used when enumerating the causal effects. Here we show that our use of DAG sampler provides a more flexible and general approach of causal discovery with special queries that do not rely on the cut configurations of the MPDAG. In many real-world settings, our focus is specific queries rather than understanding the entire graph. For instance, when a cloud computing system encounters an error, we aim to efficiently identify the root cause. Similarly, when a patient exhibits symptoms of cancer, we want to determine if certain attributes of the patient are direct causes of the cancer. Here, we consider the scenario mentioned in Malinsky (2024), where the goal is to estimate the posterior probability of a set of variables being the adjustment set of a causal query given the essential graph. The adjustment set is crucial in estimating the causal effect. Given the essential graph G, denote the variable of a set S being the adjustment set as As. As = 1 if is the adjustment set and 0 otherwise. We want to estimate P(As) v), where could be any data collected, both observational and interventional, Denote the true DAG as DD' the posterior could be expressed as:
In Section 4.2
P(Aslv) & Σ P(Aslv. ((v1)))))
(46)
DE(E(D-)
Where P(Aslv, = P(As P) is an indicator function. Equation 46 could be rewritten as:
Es Fo--co-
(47)
Which can be approximated by sampling DAGs from the MEC [D*). If we have M DAG samples,
define S as
M
S= Σ PAA.DD/PNDD)PDD))D.EE.CCCC
(48)
19

---

According to Hoeffding Inequality, the difference between & and Es could be bounded by
P(
Es 2 6) S eep((-23 -2
(49)
M
By estimating the posteriors for both P(As 1|v) and P(As 0|v), we can normalize them get the exact posterior. For large and dense graphs which are hard to iterate through each DAG, we could estimate efficiently by sampling DAGs according to intended accuracy. With enough DAG samples, it shows that the estimation converges to the true posterior with high probability.
H Additional Experiments
H.1 Additional Experiments on Large Graphs
We further test our proposed algorithm against the baseline methods on larger random chordal graphs. The results are shown in Figure 4 We can see that our algorithm converges very fast to low SHD. The performance of our algorithm does not differ much from that in small graphs. The baselines, on the other hand, require a lot more samples reach the same SHD as in small graphs. For extremely large graphs, it would be intractable to store the whole observational distribution, instead we could all the conditional distributions of the factorizations. Given large enough observa- tional samples, the conditional distributions will be accurate and then we can perform the Algorithm for Bayesian learning.
Adaal Clacn
03.0
2
(a) 20, p 0.05
(b) 20, 0.1
(c) 20, P 0.15
Figure 4: SHD vs number of interventional samples for large random Erdós-Rényi chordal graphs
H.2 Additional Experiment Scale-Free Graphs
In this experiment, we demonstrate the performance of our proposed algorithm on scale-free graphs. For each experiment settings, we generate 50 random DAGs from Barabási-Albes (BA) model. The results are plotted in Figure Our proposed method still outperforms other methods.
Action Laamnng
Learnin Kunder tlave VAe
Tamberr lavosie
2.2
235
8 0.7
1.2
3.3
(a)
7, m.
(b) n 7,
Figure 5: SHD vs number of interventional samples for scale-free graphs generated from Barabási- Albert (BA) model. We generated random DAGs under two settings and plot the average SHD and standard deviation.
20

---

H.3 Additional Experiment on Other Baseline
In this experiment, we compare our proposed algorithm with Bayesian causal discovery method, AVICI, proposed in Lorch et al. [022]. For AVICI, we fine-tuned the pretrained models, scm-v0 and neurips-rff. with 50 random complete graphs, each with 1000 observational samples. The results are plotted in F We used SHD to measure our algorithm and expected SHD for AVICI. Here, since AVICI can not take in too many samples, we just show the performance with 1000 interventional samples. At each step for both methods, we choose the interventional target randomly. For AVICI, we feed in 1000 observational samples together with the interventional samples. The results show that our algorithm performs better, while AVICI failed to learn the causal structure with high expected SHD. AVICT's bad performance in this setting may be caused by its parametric model on the SCM or noise. Also, there is no theoretical guarantee on AVICI's performance and convergence to the ground truth. Furthermore, our algorithm benefits has the advantage of being able to update the posterior given any number of samples, while AVICI would fail when the number of samples is large.
300
(a) 71 P
Figure 6: SHD vs number of interventional samples for random complete graphs. We generate 50 random DAGs and plot the average SHD and standard deviation. scm-v0 and neurips- off are pretrained models in the paper.
21

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We discuss this in Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss this in Section g
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

Justification:
We discuss this in Section 5 Section 3 and Appendix g
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We discuss this in Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
23

---

Answer: [Yes]
Justification:
We discuss this in Section
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//uuuii wwwtii/gguie///eeeeceoocc CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We discuss this in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We discuss this in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
24

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We discuss this in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: htttps://eeur: wwt.rrissccpppuuuu httpprip...cppuullccccccccccitto
Answer:
[Yes]
Justification:
We conform with the NeurIPS Code of Ethies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss this in Section
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
25

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do use any dataset or model that has this concern.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: cite the assets and mention the license explicitly in the paper and Readme of the code.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpsspipeaattteeeeee thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
26

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We provide the descriptions in the Readme file.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our work does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work does involve crowdsoureing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "tcinDrVJcX", "reviewer": "Reviewer_uDQi", "summary": "In this paper, the authors present a Bayesian method to learn the causal graph from observational data and limited interventional data. The authors assume that there are plenty of observational data, which can be used to learn a ground-truth CPDAG. Then, by using the efficient DAG enumeration method to sample DAGs and calculate the posterior, one can find the DAG that is most consistent with the interventional data.", "questions": "It seems that Algorithm 3 could be improved further. If the authors orient the edges of $\\mathbf{S}$ one by one and update the graph with Meek rules (due to the completeness of Meek rules in incorporating background knowledge), the complexity will be reduced and there is no need to detect unshielded colliders or cycles. Am I right?", "limitations": "No.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "In practice, the number of interventional data is limited, thus considering causal discovery with limited data is valuable. The whole idea in this paper is sensible. Despite some missing related studies, the authors give a detailed introduction to some of the relevant studies.\n\nThe theoretical results seem interesting, though I do not dig into the details.", "weaknesses": "Using Bayesian method to learn causal relations is not novel. There are many existing studies in the literature. Further, from the viewpoint of considering limited samples, it is more sensible to take the uncertain in learning the CPDAG into account.\n\nThe writing could be improved. There are a lot of contents in introduction that are better to appear in Related works. Besides, it is not quite clear that what role Section 4.1 play in Section 4: Algorithm Initializations.\n\nIt is better to distinguish \\citet and \\citep.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their thorough and constructive feedback. Below, we address each of the points raised.\n\n**Weakness of Objective:**\n\nThere are indeed plenty of studies in the literature that use Bayesian methods for causal discovery, but most of them have parametric assumptions like a linear causal model or additive Gaussian noise (see related works section). These methods fail when the assumptions do not hold. Our approach differs in that we do not make such assumptions, and we show the convergence rate theoretically.\n\nIn our study, we assume access to the observational distribution, which naturally leads to the CPDAG. Our work can be extended to the setting of uncertain CPDAGs by updating and tracking the posteriors of the CPDAGs together with the configurations.\n\n**Weakness of writing:**\n\nWe will try to improve the writing and clarity of the paper to make it easier to follow. We will move some content from the introduction to the related works section to better position our paper.\n\nSection 4.1 is intended to briefly describe the separating system since it is used in the algorithm and the analysis in Section 5.\n\n**Weakness of citation:**\n\nWe will fix the citations.\n\n**Questions:**\n\nIn practice, we can list all the configurations and examine them in parallel which is fast since cycle detection and unshielded collider detection algorithms are efficient. The suggested approach saves memory but has to be performed in sequence.\n\n**Additional Thoughts**\n\nWhile we value constructive criticism that can help us improve our work, we believe that the weaknesses mentioned are generic and can be easily fixed. For instance, comments regarding typos and writing, while valid for copyediting purposes, do not significantly impact the contributions of the paper. The reviewer mentions a lack of novelty as a weakness but does not provide specific points to substantiate this claim. In fact, our work has a clear position, which we state in the introduction and related works section.\n\nA score of 3 suggests significant issues with the paper's contributions, methodology, or results. However, the reviewer does not articulate any major flaws that would warrant such a score. We thus kindly request that the reviewer reconsider the score or provide more justification for the decision to reject our paper. We thus kindly request that the reviewer reconsider the score or provide additional justification for their decision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dLsvjV2zmX", "reviewer": "Reviewer_UxJA", "summary": "The paper considers the problem of learning causal graphs using limited interventional samples through the a Bayesian perspective. An algorithm is proposed which returns the most probable causal graph given a limited set of samples. The approach is empirically evaluated and code is given.", "questions": "- Lines 39-41 discusses the trade-off between non-adaptive and adaptive methods. This was explored in [1], a paper you have already cited. You may want to consider adding a reference to [1] in this section of the introduction in your revision.\n- Line 104: Typo of $O(\\log n)$?\n- Line 104: Is it size 1 or size $n/2$ interventions? For example, see Page 58 of [2] which you cited.\n- Line 243 and 514: Do you mean $D_{KL}$? Also, you should define KL divergence properly somewhere in the preliminaries.\n- Equation (2): Do you mean $p_j$ in the numerator?\n- Line 605: Typo of \"Enumerating\"?\n\n[1] Davin Choo and Kirankumar Shiragur. \"Adaptivity complexity for causal graph discovery.\" Uncertainty in Artificial Intelligence. PMLR, 2023.\n\n[2] Frederick Eberhardt. \"Causation and intervention.\" Unpublished doctoral dissertation, Carnegie Mellon University 93 (2007).", "limitations": "Nil", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I did not check the proofs in detail but the approach is sound and experimental results are promising.", "weaknesses": "The experiments feels a little \"small scale\". This is probably due to the need to enumerate all possible configurations via Algorithm 3 for this approach to work (please correct me if I am mistaken).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their thorough and constructive feedback. Below, we address each of the points raised.\n\n**Weakness of \"small scale\" experiments:**\n\nIn this work, we assume the access to the joint observational distribution. When the graph is large, it is intractable in practice to handle the joint distribution. For example, in our implementation, we use binary variables. A graph of 50 vertices would lead to a table of $2^{50}$ numbers. Also, to enumerate the configurations of a set of target of $k$ vertices, we have to consider up to $2^{kd}$ configurations in the worst case where $d$ is the maximum degree of the target. This will be huge complexity for large dense graphs, so we just experimented on \"small scale\" graphs. Although in practice, causal graphs can be large, they are usually sparse and with observational distribution, it can be divided into small chain components and orient independently.\n\n**Question about citations:**\n\nWe will add this mentioned paper to this section.\n\n**Questions about typos:**\n\nThanks for pointing out the typos. We will fix them in revision.\n\nWe hope that our rebuttal has clarified the reviewer's concerns, and we would be more than happy to engage in further discussions if the reviewer has additional questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Dh0Nd4Pe60", "reviewer": "Reviewer_i7ee", "summary": "This paper proposes a Bayesian approach for learning causal graphs with limited interventional samples. The proposed algorithm first constructs a separating system to design intervention targets and then enumerates the causal effects for all possible cutting edge configurations for each target, and tracks their posteriors. The authors provide theoretical guarantees on the convergence to the true causal graph with sufficient interventional samples, and the experiments on simulated chordal graphs demonstrate that the proposed method requires significantly fewer interventional samples than baselines to achieve low SHD.", "questions": "1. Please see the questions in the Weaknesses part.\n\n2. How is the value of $k$ of the $(n, k)$-separating system determined in the experiments? \n\n3. How is the prior of each configuration defined?", "limitations": "The authors adequately addressed the limitations of their work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The authors provide a detailed theoretical analysis, proving that the proposed algorithm converges to the true causal graph with high probability given sufficient interventional samples.\n\n2. The related work part is comprehensive and easy to read and understand.\n\n3. Experiments on simulated chordal graphs demonstrate that the proposed method achieves low SHD using significantly fewer interventional samples compared to baselines.", "weaknesses": "Major:\n1. The proposed method should not be classified strictly as \"Bayesian learning of causal graphs,\" because it does not calculate the posterior distribution over causal graphs directly. Instead, it computes posterior probabilities of specific cutting edge configurations within the graph. Based on these probabilities, the proposed method updates the output DAG accordingly. It would be better if the authors clarified that in the paper to avoid any confusion.\n\n2. It is unclear to me how the proposed method selects intervention targets at each step. I wonder if the authors could further clarify whether the proposed method also designs the intervention targets or the interventions are performed randomly.\n\n3. The authors did not discuss the computational complexity in the paper. The sizes of nodes in the experiments are also relatively small. I wonder if the authors could discuss the complexity of the proposed method and whether it could scale up to graphs with a larger number of nodes.\n\n4. In the experiments, the authors only consider simulated chordal graphs, which naturally fit the proposed method. I think the authors should conduct more experiments on different types of graphs (e.g., scale-free graphs) and perhaps some semi-synthetic graphs (e.g., graphs simulated using realistic simulators [1]).\n\n5. The authors only consider 3 baselines in the experiments, and I wonder if the authors could compare the proposed method with Bayesian causal discovery methods that can handle interventional data (e.g., [2], [3]).\n\n\nMinor: \n1. Missing related work: [3].\n\n2. Please use \\citet and \\citep correspondingly rather than only using \\citet. For example, in line 72: Meek Rules Meek [1995] --> Meek Rules [Meek, 1995] \n\n\n[1] Dibaeinia, P., & Sinha, S. (2020). SERGIO: a single-cell expression simulator guided by gene regulatory networks. Cell systems, 11(3), 252-271.\n\n[2] Lorch, L., Sussex, S., Rothfuss, J., Krause, A., & Schölkopf, B. (2022). Amortized inference for causal structure learning. Advances in Neural Information Processing Systems, 35, 13104-13118.\n\n[3] Hägele, A., Rothfuss, J., Lorch, L., Somnath, V. R., Schölkopf, B., & Krause, A. (2023, April). Bacadi: Bayesian causal discovery with unknown interventions. In International Conference on Artificial Intelligence and Statistics (pp. 1411-1436). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their thorough and constructive feedback. Below, we address each of the points raised.\n\n**Weakness of Major 1:**\n\nOur approach differs from most of the Bayesian causal discovery paper in that we do not have a parametric representation of the structure. We do not directly calculate the posterior of each DAG since the size of MEC could be large and intractable **[1]**. Instead, we partition the DAGs into different configurations of a given target set to avoid keep tracking of posteriors of all the DAGs in an Bayesian approach. We could explicitly mention this difference in the paper.\n\n**Weakness of Major 2:**\n\nIn our implementation, the interventional target is selected randomly. If the maximum posterior of a configuration is close to 1 ($>0.99$ for example), we remove this target to improve efficiency. This target selection process could be made adaptive to further improve the algorithm.\n\n**Weakness of major 3:**\n\nIn our work, we assume the access to observational distribution. In our simulation, we use binary variables, so it takes $2^n$ in memory. When the graph is large, it is intractable. For a target of $k$ vertices, in the initialization step where we need to enumerate all the configurations, the complexity would be up to $2^{kd}$ where $d$ is the maximum degree. This can be large when the graph is large and dense. If the graph is large, our algorithm can only work when it is sparse, i.e., the maximum degree is less than $\\log n$. However, usually causal graphs are sparse, and can be divided into smaller chain components with observational distribution, which can be oriented independently.\n\n**Weakness of major 4:**\n\nWe can also compare the algorithms on other graphs like BA graph. We show the results in the extra pdf in Figure 1. We can see that our algorithm still outperforms others for scale-free graphs. In fact, with the access to the observational distribution, our algorithm does not rely on the type of graphs since the chain components are proved to be chordal **[2]** and can be oriented independently **[3]**. We could not run our algorithm with the mentioned real-world simulator since it does not provide the observational distribution.\n\n**Weakness of major 5:**\n\nWe compared with the Avici model in **[4]** and the result if shown in the 1-page pdf of Figure 2. We compare with both 'scm-v0' and 'neurips-rff' model and the result shows that our method performs better. In fact, Avici does not seem to be converging with our simulated data. There could be several reasons for that. First, Avici has no guarantee of performance as mentioned in the paper, thus it might not perform well for some data. Besides, Avici may not work well with discrete data. Also, Avici could not take in too large data since it only loads data once, while our approach has this anytime property to return the optimal DAG with any amount of samples available.\n\n**[5]** is also an important work. As it assume unknown interventions, we did not compare with it here, but we will add it in the related work section in revision.\n\n**Weakness of minor 1, 2:**\n\nWe will fix these typos in the revision.\n\n**Question 2:**\n\nIn the experiments, we use $k=3$ for small graphs ($n\\leq10$) and $k=1$ for $n=20$. When the graph is small, using a slightly larger $k$ could make the algorithm more efficient, but when the graph gets large, we just use atomic interventions to avoid using too much memory.\n\n**Question 3:**\n\nIn this study, we assume that at the beginning, all the DAGs in the MEC are equally likely to be the causal graph. Thus, we use equation 7 to calculate the prior of each configuration. More specifically, we divide the MEC size of the configuration by the MEC size of the whole graph. The MEC size could be efficiently calculated using algorithm in **[6]**.\n\n**[1]** *He, Yangbo, Jinzhu Jia, and Bin Yu. \"Counting and exploring sizes of Markov equivalence classes of directed acyclic graphs.\" The Journal of Machine Learning Research 16, no. 1 (2015): 2589-2609.*\n\n**[2]** *Steen A Andersson, David Madigan, and Michael D Perlman. A characterization of markov equiva-389\nlence classes for acyclic digraphs. The Annals of Statistics, 25(2):505–541, 1997.*\n\n**[3]** *Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 55(4):926–939, 2014.*\n\n**[4]** *Lorch, L., Sussex, S., Rothfuss, J., Krause, A., and Schölkopf, B. (2022). Amortized inference for causal structure learning. Advances in Neural Information Processing Systems, 35, 13104-13118.*\n\n**[5]** *Hägele, A., Rothfuss, J., Lorch, L., Somnath, V. R., Schölkopf, B., and Krause, A. (2023, April). Bacadi: Bayesian causal discovery with unknown interventions. In International Conference on Artificial Intelligence and Statistics (pp. 1411-1436). PMLR.*\n\n**[6]** *Marcel Wienöbst, Max Bannach, and Maciej Li ́skiewicz. Polynomial-time algorithms for counting\nand sampling markov equivalent dags with applications. Journal of Machine Learning Research, 24(213):1–45, 2023.*\n\nWe hope that our rebuttal has clarified the reviewer's concerns and would request that they reconsider their score. We would be more than happy to engage in further discussions if the reviewer has additional questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3daePMBzNC", "reviewer": "Reviewer_HSDU", "summary": "This paper introduces a way of doing causal discovery from interventional samples using bayesian inference. They prove some theoretical results of convergence of the task at hand. Finally, they test their approach against common benchmarks on synthetic data.", "questions": "I’m still unsure about the overall significance of the paper. Yes, there is section 6 where the authors give a case study for estimating the probability of a set being a valid adjustment set. Furthermore, the authors briefly explain the case of cloud computing and cancer research. However, I don’t understand how that relates to querying interventional data from the system. Could the authors please expand on this? I have not reduced the score from this because I currently believe the strength of the paper are the theoretical results and the approach itself.", "limitations": "See questions", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "- Apart from the related work section (see weaknesses) the paper is clear and well organized.\n- The experiments support the proposed method against the benchmarks.\n- The theoretical results are interesting and I believe using the results by Weinöbst et.al. (2023) is a creative solution to decrease the time complexity of the task.", "weaknesses": "In my opinion, the related work section is not written very well. It reads like a list with one sentence of what they are doing and not putting your research in the context of previous research. The only exception is line 124.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their thorough and constructive feedback. Below, we address each of the points raised.\n\n**Weakness of Writing:**\n\nWe will rearrange the related work section in the revision to position the previous works and our study better.\n\n**Questions of Overall Significance:**\n\nThe main contribution of this study is the Bayesian learning algorithm for causal discovery. We use DAG sample to efficiently compute the interventional distributions. With section 6, we want to show that the DAG sampler could be used in more general cases to estimate general causal queries and the case of \"a set being a valid adjustment set\" is presented as an example. We mentioned real-world scenarios of cloud computing and cancer detection. They can also be transformed into such causal queries without learning the whole graph. To elaborate more, for the root cause analysis in for cloud computing, we could estimate the posterior of the configuration of a vertex to be all outgoing from that vertex to its neighbors. For direct cause analysis in cancer research, we could estimate the posterior of that edge being directed from the potential cause to the cancer variable. Regarding the study of interventional experimental design, there have been plenty of works in the literature (**[1]**, **[2]**, **[3]**, **[4]**, ...), while few of them consider the cases of limited interventional samples. However, these cases are common in real-world settings since interventional samples are usually a lot more costly to retrieve then observational samples. Thus, in this paper we assume the access to observational distribution while limited intervetinoal samples to reflect such scenarios and our proposed algorithm outperforms previous works.\n\n**[1]** *Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Learning causal graphs with small interventions. Advances in Neural Information Processing Systems, 28, 2015.*\n\n**[2]** *Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 55(4):926–939, 2014.*\n\n**[3]** *Yang-Bo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9(Nov):2523–2547, 2008.*\n\n**[4]** *Chandler Squires, Sara Magliacane, Kristjan Greenewald, Dmitriy Katz, Murat Kocaoglu, and Karthikeyan Shanmugam. Active structure learning of causal dags via directed clique trees. Advances in Neural Information Processing Systems, 33:21500–21511, 2020.*\n\nWe hope that our rebuttal has clarified the reviewer's concerns, and we would be more than happy to engage in further discussions if the reviewer has additional questions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**Extra Experiments**

We included the results of extra experiments in the pdf as required by the reviewers. 

**Experiment for Scale-Free Graphs**

We generate 50 random scale-free graphs under 2 setting: $n=7, m=2$ and $n=7, m=4$, and compare with the baselines. The results are plotted in Figure 1. Our proposed algorithm outperforms other methods.

**Experiment to Compare with Avici**

Avici is a Bayesian causal discovery model proposed in **[1]**. We compare our method with 2 pretrained models "scm-v0* and *neurips-rff" provided by the authors. Both models are trained on non-linear SCMs. We generated 50 random complete DAGs with 5 vertices. Since Avici cannot take in large data, we just compare the algorithms on 1000 interventional samples. The result is shown in Figure 2. Our algorithm outperforms both Avici models.

**[1]** *Lorch, L., Sussex, S., Rothfuss, J., Krause, A., and Schölkopf, B. (2022). Amortized inference for causal structure learning. Advances in Neural Information Processing Systems, 35, 13104-13118.*

Meta-review: This work presents Bayesian approaches to the challenging problem of active learning of causal graphs via interventions. Reviewers were overall positive and I recommend acceptance. That said, reviewers did raise issues with various aspects of the writing - authors please do incorporate the recommendations and address the comments as promised in the rebuttal.
Decision: Accept (poster)