Interventional Causal Discovery in a Mixture of DAGs
Authors: Burak Varıcı
Dmitriy A Katz
Dennis Wei
Prasanna Sattigeri
Ali Tajer
Venue: NeurIPS 2024 poster (2024)
Keywords: causal discovery
intervention design
mixture of DAGs
mixture models
Primary area: causal_inference

Abstract: Causal interactions among a group of variables are often modeled by a single causal graph. In some domains, however, these interactions are best described by multiple co-existing causal graphs, e.g., in dynamical systems or genomics. This paper addresses the hitherto unknown role of interventions in learning causal interactions among variables governed by a mixture of causal systems, each modeled by one directed acyclic graph (DAG). Causal discovery from mixtures is fundamentally more challenging than single-DAG causal discovery. Two major difficulties stem from (i) an inherent uncertainty about the skeletons of the component DAGs that constitute the mixture and (ii) possibly cyclic relationships across these component DAGs. This paper addresses these challenges and aims to identify edges that exist in at least one component DAG of the mixture, referred to as the *true* edges. First, it establishes matching necessary and sufficient conditions on the size of interventions required to identify the true edges. Next, guided by the necessity results, an adaptive algorithm is designed that learns all true edges using ${\cal O}(n^2)$ interventions, where $n$ is the number of nodes. Remarkably, the size of the interventions is optimal if the underlying mixture model does not contain cycles across its components. More generally, the gap between the intervention size used by the algorithm and the optimal size is quantified. It is shown to be bounded by the *cyclic complexity number* of the mixture model, defined as the size of the minimal intervention that can break the cycles in the mixture, which is upper bounded by the number of cycles among the ancestors of a node.

Interventional Causal Discovery in a Mixture of DAGs
Burak Varier' Carnegie Mellon University
Dmitriy A. Katz
Dennis Wei IBM Research
IBM Research
Prasanna Sattigeri IBM Research
Ali Tajer Rensselaer Polytechnic Institute
Abstract
Causal interactions among group of variables are often modeled by single causal graph. some domains, however, these interactions are best described by multiple co-existing causal graphs, e.g., in dynamical systems genomics. This paper addresses hitherto unknown role of interventions learning causal interactions among variables governed by mixture of causal systems, each modeled by one directed acyclic graph (DAG), Causal discovery from mixtures is fundamentally more challenging than single-DAG causal discovery. Two major difficulties stem from (i) an inherent uncertainty about the skeletons of the component DAGs that constitute the mixture and (ii) possibly cyclic relationships across these component DAGs. This paper addresses these challenges and aims to identify edges that exist in least one component DAG of the mixture, referred as the frue edges. First, establishes matching necessary and sufficient conditions the size of interventions required to identify the true edges. Next, guided by the necessity results, an adaptive algorithm designed that learns all true edges using (n=)) interventions, where n is the number of nodes. Remarkably, the size of the interventions is optimal if the underlying mixture model does not contain cycles across its components. More generally, the gap between the intervention size used by the algorithm and the optimal size is quantified. It is shown to be bounded by the cyclic complexity number of the mixture model, defined the size of the minimal intervention that can break the cycles in the mixture, which is upper bounded by the number of cycles among the ancestors of a node.
1 Introduction
The causal interactions in system causally related variables are often abstracted by a directed acyclic graph (DAG). This is the common practice in various disciplines, including biology [1], social sciences [2], and economics [3]. wide range of applications, however, the complexities of the ob- served data cannot be reduced to conform
single DAG, and they are best described by mixture of multiple co-existing DAGs over the same set of variables. For instance, gene expression of certain can- types comprises multiple subtypes with different causal relationships [4]. In another example, mix- ture models are often more accurate than unimodal distributions in representing dynamical systems [5], including time-series trajectories in psychology [6] and data from complex robotics environments [7].
Despite the widespread applications, causal discovery for a mixture of DAGs remains an under- investigated domain. Furthermore, the existing studies on the subject are also limited to using only observational data [8-11]. Observational data alone highly insufficient in uncovering causal relationships. It is well-established that even for learning single DAG, observational data can learn a DAG only up to its Markov equivalence class (MEC) [12]. Hence, interventions, which refer to
* Work done when BV Ph.D. student Rensselaer Polytechnic Institute.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Algorithm: We design an adaptive algorithm that identifies all directed edges of the individual DAGs in the mixture by using O(n²) interventions, where is the number of variables. Re- markably, the maximum size of the interventions used in our algorithm is optimal if the mixture altering the causal mechanisms of a set of target nodes, have potentially significant role in improving identifiability guarantees in mixture DAG models. Specifically, interventional data can be used to learn specific cause-effect relationships and refine the equivalence classes.
Using interventions for learning single DAG is well-investigated for various causal models and interventions [13-17]. In this paper, we investigate using interventions for causal discovery in a mixture of DAGs, a fundamentally more challenging problem. The major difficulties stem from (i) an inherent uncertainty about the skeletons of the DAGs that constitute the mixture and (ii) possibly cyclic relationships across these DAGs, For a single DAG, the skeleton can be learned from observational data via conditional independence (CI) tests and the role of interventions is limited to orienting the edges. On the contrary, in a mixture of DAGs, the skeleton cannot be learned from observational data alone, making interventions essential for both learning the skeleton and orienting the edges. Uncertainty in the skeleton arises because, in addition to true edges present in at least one individual DAG, there are inseparable random variable pairs that cannot be made conditionally independent via CT tests, even though they are nonadjacent in every DAG of the mixture. These types of inseparable node pairs, referred to as emergent edges [1 I]. cannot be distinguished from true edges using observational data alone.
In this paper, we aim to characterize the fundamental limits of interventions needed for learning the true edges in a mixture of DAGs. The two main aspects of these limits are the minimum size and number of the interventions. To this end, we first investigate the necessary and sufficient size of interventions for identifying true edge. Subsequently, we design an adaptive algorithm that learns the true edges using interventions guided by the necessary and sufficient intervention sizes. We quantify the optimality gap of the maximum intervention size used by the algorithm as a function of the structure of the cyclic relationships across the mixture model. We note that the component
DAGs of the mixture cannot be identified without further assumptions even when using interventions (see examples in Appendix I). Hence, our focus is on learning the set of true edges in the mixture as specified above. Our contributions are summarized as follows.
We establish matching necessary and sufficient intervention size to identify each node's mixture parents (i.e., the union of its parents across all DAGs). Specifically, we show that this size is one more than the number of mixture parents of the said node.
Intervention size:
Tree DAGs: For the special case of a mixture of directed trees, we show that the necessary and sufficient intervention size is one more than the number of DAGs in the mixture.
ancestors of node (i.e., the union of its ancestors across all DAGs) do not form cycle.
Optimality gap: We show that the gap between the maximum intervention size used by the proposed algorithm for given node and the optimal size is bounded by the cyclic complexity number of the node, which is defined as the number of nodes needing intervention to break cycles among the ancestors of the node, and upper bounded by the number of such cycles.
We provide an overview of the closely related literature, the majority of which is focused on the causal discovery of single DAGs.
Causal discovery of mixture of DAGs. The relevant literature on the causal discovery of a mixture of DAGs focuses on developing graphical models to represent CI relationships in the observed mixture distribution [8-11]. Among them, [8] proposes a fused graph and shows that the mixture distribution is Markov with respect to it. The study in [9] proposes a similar mixture graph but relies on longitudinal data to orient any edges. The study in [10] constructs a mixture DAG that represents the mixture distribution and designed an algorithm for learning maximal ancestral graph. The algorithm of [10] requires the component DAGs of the mixture to be poset compatible, which rules out any cyclic relationships across the DAGs. The study in [11] introduces the notion of emergent edges to investigate the inseparability conditions arising in the mixture of DAGs. The study in [18] proposes variational inference- based approach for causal discovery from mixture of time-series data. Despite their differences, all these studies are limited to using observational data.
Intervention design for causal discovery of single DAG. We note that the structure of a single DAG without latent variables can be learned using single-node interventions. Hence, the majority of the literature focuses minimizing the number of interventions. Worst-case bounds the number
2

---

of interventions with unconstrained size are established in [13], and heuristic adaptive algorithms are proposed in [14]. Intervention design on causal graphs with latent variables is studied in [19-21]. The study in [20] also shows that single-node interventions are not sufficient for exact graph recovery in the presence of latent variables. another direction, [16] studies interventions under size constraints, establishes lower bound for the number of interventions, and shows that ( log log k) randomized interventions with size & suffice for identifying the DAG with high probability. In the case of single-node interventions, adaptive and non-adaptive algorithms are proposed in [22], active learning of directed trees is studied in [23], and a universal lower bound for the number of interventions is established in [17]. [24] also studies the universal lower bound problem and [25] provides an exact characterization for the number of interventions required to recover the DAG from the observational essential graph. A linear cost model, where the cost of an intervention is proportional to its size, is proposed in [26]. It is shown that learning the DAG with optimal cost under the linear cost model is NP-hard [27]. The size of the minimal intervention sets is studied for eyclic directed models in [28]. Specifically, it is shown that the required intervention size is at least Ç - where Ç denotes the size of the largest strongly connected component in the cyclic model. A related problem to intervention design is causal discovery from a combination of observational and interventional data. In this setting, the characterization of the equivalence classes and designing algorithms for learning them is well-explored for single DAG [29-32].
Causal discovery from multiple clusters/contexts Another approach to causal discovery from a mixture of DAGs is clustering the observed samples and performing structure learning on each cluster separately [33-37]. Learning from multiple contexts is also studied in the interventional causal discovery literature [38-41]. However, these studies assume that domain indexes are known. In a similar problem, [42] aims to learn the domain indexes and perform causal discovery simultaneously.
2 Preliminaries and definitions
2.1 Observational mixture model
DAG models. We consider K > 2 distinct DAGs Gr A Ez) for E (I,..., K} defined over the same set of nodes V é . m... the paper, we refer to these as the mixture component DAGs. We use (i) cha (f), (i). and dez(i) to refer to the parents, children, ancestors, and descendants of node in DAG Gé, respectively.
Eg denotes the set of directed edges in graph Gp. Throughout
We also use i f j to denote i E anm(j). (j). For each node i E V, we define pa (i) as the union of the nodes that are parents of i at least one component DAG and refer to pa (i) as the mixture parents of node i. Similarly, for each node i E V we define ch (t), alm (i), and dem (i).
Mixture model. Each of the component DAGs represents Bayesian network. We denote the random variable generated by node E V by X; and define the random vector X 2 (Xi..... X,," For any subset of nodes A C V, we use XA to denote the vector formed by X; for i E A. We denote the probability density function (pdf) of X under Ge by pe, which factorizes according to Ge as
(x(
II pe( (t)) Vl [R]. kE(M)
For distinct e, e E [K], pe and pe can be distinct even when E, - Eg. The differences between any two DAGs are captured by the nodes with distinct causal mechanisms (i.e., conditional distributions) in the DAGs. To formalize such distinctions, we define the following set, which contains all the nodes with at least two different conditional distributions across component distributions.
A é {i E V 36, l' [K] Pe(X,
Xpa,(i) # pe (X, (pmp()))
(2)
We adopt the same mixture model as the prior work on causal discovery of mixture of DAGs [8- 11, 18]. Specifically, observed data is generated by a mixture of distributions {pr :6 [K]]. It unknown to the learner which model is generating the observations X. To formalize this, we define L E {l,.... K) as latent random variable where L = l specifies that the true model is pe. We denote the probability mass function (pmf) of L by r. Hence, we have the following mixture distribution for the observed samples X.
Pm (x) A
r(e) Pp(x))
(3)
[E[K]
3

---

Next, we provide several definitions that are instrumental to formalizing causal discovery objectives.
Definition (True edge). We say that j + is a true edge i E pamm (i). The set of all true edges is denoted by
E,
= E par(1))
(4)
A common approach to causal discovery is the class of constraint- based approaches, which perform conditional independence (CI) tests on the observed data to infer (partial) knowledge about the DAGs' structure [43-45]. In this paper, we adopt a constraint-based CI testing approach. Following this approach, the following definition formally specifies the set of node pairs that cannot be made conditionally independent in the mixture distribution.
Definition 2 (Inseparable pair). The node pair (i.j) is called inseparable if X, and X, are always sta- tistically dependent in the mixture distribution Pm under any conditioning set. The set of inseparable node pairs is specified by
E, - ((i (((--))- :),E,V,, A (1.):: X, X, XA
Pm)
(5)
Note that when (j + is true edge, the pair (i.j) will be inseparable. significant difference between independence tests for mixture models and single-DAG models is that not all inseparable pairs have an associated true edge the former. More specifically, due to the mixing of multiple distributions, a pair of nodes can be nonadjacent in all component DAGs but still be inseparable in mixture distribution Pm- We refer to such inseparable node pairs as emergent pairs, formalized next.
Definition 3 (Emergent pair). An inseparable pair (i,j) E, is called an emergent pair if there is no true edge associated with the pair. The set of emergent pairs is denoted by
Eg A ((1,5) E E, pam
pa (i))
(6)
The conditions under which emergent edges arise in mixture models are recently investigated in [11], where is shown that the causal paths that pass through a node in the set defined in (2) are instrumental for their analysis. These paths are specified next.
Definition& 4 (A-through path). We say that causal path in Ge between i and j is A-through path if it passes through at least one node in A, i.e. there exists u E A such that u ~o j. If E ci)(i), the path is also called s-child-throue path.
8 F
2.2 Intervention model
In this section, we describe the intervention model we use for causal discovery on a mixture of DAGs. We consider stochastic hard interventions on component DAGs of the mixture model. A hard intervention on a set of nodes I S V cuts off the edges incident on nodes i I in all component DAGS G. for E [K]. We denote the post-intervention component DAGs upon an intervention I by : l E []]- We note that hard interventions are less restrictive than do interventions, which not only remove ancestral dependencies but also remove randomness by assigning constant values to the intervened nodes. Specifically, in Ge,z, the causal mechanism of an intervened node E I changes from pr(x; (p))(() to (x.)). Therefore, upon an intervention I C V, the interventional component DAG distributions are given by
(z) & II (x(())
II iEVII
pe(a, (1)
Vl E [K]
IEI
Subsequently, the interventional mixture distribution (x)) is given by
(x)
Σn (()-pez(x)) [E[K]
(8)
We note that an intervened node i has the same causal mechanism (x;); for all interventions I C V that contain i. This is because an intervention procedure targets set of nodes in all mixture components at the same time. Hence, resulting 9: (X,) shared for all component models, owing to the same intervention mechanism, e.g., gene knockout experiments [46]. Hence, the set of nodes with distinct causal mechanisms across the components of the interventional mixture model becomes Ar A A I. Next, we specify the T-mixture DAG, which extends the mixture DAG defined for observational data in [10, 11] and will facilitate our analysis.

---

11
12
11
2
2
22
2
2
y/
3
3
31
32
3
31
32
4
4
42
4
4
4
42
(a) 9i
(b) O2
(c) 9m
(d) G1.z
(e) 92,z
(l) gm,z
Figure 1: (a)-(b): sample component DAGs; (c) the mixture DAG for I 0, note that A 3,
(when the distribution of node 1 remains the same) : (d)-(e): post-intervention component DAGS
for I [2]: (f): corresponding Z-mixture DAG. Also note that true edges E, ((1 2),
3), (3 - 2), (3 + 4), + 4)), inseparable pairs E; = {(1 - 2), (1 3), (1 4), (2 3)
4), (3 4)}. and emergent edges E.
Definition 5 (Z-mixture DAG). Given an intervention I on a mixture of DAGs, I-mixture DAG 9m.II graph with nK +1 nodes constructed by first concatenating the K component DAGs and then adding single node to the concatenation. Furthermore, there will be directed edge from to every node in Az in every DAG {Gt,I E [K]]. In the I-mixture DAG Gm.I, we use ig denote the copy of node i Gr, Accordingly, for any V
we define :i::i A, 8 LE [K]].
Figure illustrates an example of mixture of K component DAGs, different edge types, an intervention I on the mixture, and the construction of the Z-mixture DAG from post-intervention component DAGs G1,z and G2,I. We define the observational mixture DAG as the T-mixture DAG when the intervention set is I = 0 and denote it by 9m. It is known that pm specified in (3) satisfies the global Markov property with respect to observational mixture DAG [10, Theorem 3.2]. It can be readily verified that this result extends the interventional setting for Pm.I and Gm.z. We make the following faithfulness assumption to facilitate causal discovery via statistical independence tests.
Assumption 1 (I-mixture faithfulness). For any intervention I C V, the interventional mixture distribution P (z) is faithful to Gm,I, that XA 1L XB Xo in PmI( then A and B are d-separated given C in Im,I.
Finally, we note that the observational counterpart of Assumption i.e., when I = 0, is standard in the literature for analyzing a mixture DAGs [9-11]. ]. In working with interventions, we naturally extend it to interventional mixture distributions. Also note that Assumption 1 does not compare observational and interventional distributions. Hence, it is not comparable to various faithfulness assumptions in the literature on the interventional causal discovery of single DAG, e.g., [29, 31].
2.3 Causal discovery objectives
We aim to address the following question: how can we use interventions to perform causal discovery mixture of DAGs, with the objectives specified next.
The counterpart of this question well-studied for the causal discovery of a single DAG. Since the unoriented skeleton of the single DAG can already be identified by CI tests on observational data, interventions are leveraged to orient the edges. Interventions are generally bounded by pre-specified budget, measured by the number of interventions. The extent of causal relationships that observational data can uncover in a mixture of DAGs is significantly narrower than those in single DAGs. The striking difference is the existence of emergent pairs specified in (6). Therefore, the objective of intervention design extends to distinguishing true cause-effect relationships from the emergent pairs as well determining the direction of causality. Specifically, we focus on identifying the true edges specified in (4) as the edges exist in at least one component DAG of the mixture. For this purpose, two central objectives of our investigation are:
1. Determining the necessary and sufficient size of the interventions for identifying true edges E,,
2. Designing efficient algorithms with near-optimal intervention sizes.
5

---

3 Interventions for causal discovery of a mixture of DAGs
In this section, we investigate the first key question of interventional causal discovery mixture of DAGs and investigate the size of the necessary and sufficient interventions for identifying mixture parents of node. First, consider mixture of general DAGs without imposing structural constraints and establish matching necessary and sufficient intervention size for distinguishing a true edge from emergent pair. Then, we strengthen the results for mixture of directed trees. The results established in this section are pivotal for understanding the fundamental limits of causal discovery of a mixture of DAGs. These results guide the intervention design in Section 4.
Our analysis uncovers the connections between the mixture distribution under an intervention I and the structure of cost-intervention component DAGs {Ge.z L E [K]}. We know that the interventional mixture distribution Pm.I satisfies the Markov property with respect to I-mixture DAG Gm.I specified in Definition 5. Therefore, in conjunction with the Z-mixture faithfulness assumption, the separation statements in Im,r can be inferred exactly by testing the conditional independencies in Pm,I- To establish the necessary and sufficient intervention sizes, we recall that set A plays an important role in the separability conditions in Z-mixture DAG Im, since A allows paths across different component main result.
DAGs. The following result serves an intermediate step in obtaining
Lemma Consider an inseparable pair (i.j) E E, and an intervention I S V. We have the following identifiability guarantees using the interventional mixture distribution Pm)
(i) Identifiability: It is possible determine whether (1)m(1) if I and there do not exist A-throuhh paths from j to i in Gi,Z.orr any & E [K]-
(ii) Non-identifiabiiliyy It is impossible to determine whether E pa (1) ifj E Az or there exists a A-child- thhild- path from j to i in at least one Ge where E E [K].
Lemma I provides intuition for characterizing sufficient and necessary conditions for identifying a true edge. The identifiability result implies that it suffices to choose an intervention I that reduces the viable A -throuugh paths in Im,z to true edges from j to i. Similarly, the non-identifiability result implies the necessity of intervening on A-child nodes. Building on these properties, our main result in this section establishes matching necessary and sufficient intervention sizes for identifying true edges.
Theorem 1 (Intervention sizes). Consider nodes i, E V in a mixture of DAGs.
(i) Sufficiency: For any mixture of DAGs, there exists an intervention I with [I] S |pam (4) + that ensures the determination of whether j E pam,() using CI tests on Pm.I-
(i)) Necessity: There exist DAG mixtures for which it is impossible to determine whether j E p) using CI tests on (()) ()) for any intervention I with [I] S (i)]-
Theorem represents a fundamental step for understanding the intricacies of mixture causal discovery and serves as a guide for evaluating the optimality and efficiency of any learning algorithm. We also note that the necessity statement reflects a worst-case scenario. As such, we present the following refined sufficiency results that can guide efficient algorithm designs.
Lemma 2. Consider nodes i, V in mixture of DAGs. It is possible determine whether
j E pam (i) using CI tests on Pm.II and any of the following interventions:
(i) I = (i) Y UeEjKT {pay(1) de: (i) or
(ii) I- = (f) (O)UUeeEKK {ang(() (i) ; or
(iii) I (5) U USE[K] (ane(i) ())
Note that the three interventions in Lemma 2 can coincide when parents of in a component DAG are also children of j and are in A. This case yields the set I pa, (i) {i} with size (paa,. (i) + 1). Since this can be rare occurrence for realistic mixture models, partial knowledge about the underlying component DAGs, e-g., ancestral relations or the knowledge of A, can prove to be useful for identifying pam (i) using interventions with smaller sizes. Finally, we note that our results in Theorem and Lemma 2 are given for a mixture of general DAGS, and they can be improved for special classes of DAGs. In the next result, we focus on mixtures of directed trees. Theorem 2 (Intervention sizes trees). Consider nodes i, V in a mixture of K directed trees.
(i) Sufficiency: For any mixture of directed trees, there exists an intervention I with [Z] S K +1 such that it is possible to determine whether j E pam (i) using CI tests on Pm.I.

---

(ii) Necessity: There exist mixtures of directed trees such that it is impossible to determine whether pam (i) using CI tests on Pm. for any intervention I with [ K.
Theorem 2 shows that, unlike the general result in Theorem 1, the number of mixture components plays a key role when considering a mixture of directed trees. Hence, prior knowledge of the number of mixture components can be useful for the causal discovery of mixture of directed trees.
4 Learning algorithm and its analysis
In this section, we design an adaptive algorithm that identifies and orients all true edges, referred to as Causal Díscovery from Interventions Mixture Models (CADIM). The algorithm is summarized in Algorithm I, and its steps are described in Section 4.1. We also analyze the performance guarantees of the algorithm and the optimality of the interventions used in the algorithm in Section 4.2.
4.1 Causal discovery from interventions mixture models
The proposed CADIM algorithm designs interventions for performing causal discovery on a mixture of DAGs. The algorithm is designed to be general and demonstrate feasible time complexity for any mixture of DAGs without imposing structural constraints. Therefore, we forego the computationally expensive task of learning the inseparable pairs from observational data, which requires O 22") CI tests [11], and entirely focus on leveraging interventions for discovering the true causal relationships. The key idea of the algorithm is to use interventions to decompose the ancestors of a node into topo- logical layers and identify the mixture parents by sequentially processing the topological layers using carefully selected interventions. The algorithm consists of four main steps, which are described next.
Step 1: Identifying mixture ancestors. We start by identifying the set of mixture ancestors am for each node E V, i.c.. the union of ancestors of in the component DAGs. For this purpose. we use single-node interventions. Specifically, for each node E V, we intervene on I {i} and construct the set of nodes that are marginally dependent on X; in Pm,z, i.c.
de(i) = ( X, A X2 in (m,
ViEV.
Then, we construct the sets ain(t) {j : de())) for all V. Under I-mixture faithfulness, this procedure ensures that de(i) = dem. (f), and ain(i) = anm (i) (see Lemma
3). The rest of the algorithm steps aim to identify mixture parents of a single node i, pa (i), within the set ain(i. Hence, the following steps can be repeated for all E to identify all true edges.
Step Obtaining cycle-free descendants. In this step, we consider given node E V and aim to break the cycles across the nodes in an by careful interventions. Once this is achieved, for all j E ain(
will refine j's descendant set de(j)) to cycle-free descendant set do, (j). The motivation that these refined descendant sets can be used to topologically order the nodes in ain. The details
of this step work as follows. First, we construct the set of cycles
(()) A { (T...... #e) Wi Te Vu [] Tu E ain(t) A Tu E ai(
(10)
Subsequently, if C(i) is not empty, define minimal set that shares at least one node with each cycle in C(i),
(()) a minimal set such that VT E C(i) [B(i) 2
(11)
We refer to B(i) as the breaking set of node since intervening on any set I that contains B(i) breaks all the eyelic relationships in C(i). Then, if C(i) is not empty, we sequentially intervene
I = I=B(i) U [i} for all j E ain(i), and construct the cycle-free descendant sets defined as
dei(i) + {k E ain(i) U (i) X, J Xx in Pm.I), where I= B(i) U (i).
(12)
Note that (j) is a subset of dem (j) since intervening on j makes it independent of all its non- descendants. Finally, we construct the set A = {j ai(() dc.(j)}.
Step 3: Topological layering. In this step, we decompose ain(1) into topological layers by using the cycle-free descendant sets constructed in Step We start by constructing the first layer as
(1) (i E A: de, nA= A=0) 0}
(13)
7

---

Algorithm Causal Discovery from Interventions on Mixture Models (CADIM)
1: Step I: Identify mixture ancestors
2: for E V do
3: Intervene on I = { observe samples from Pm.II
4: de(i) < {j X P X; in Pm,z)
mixture descendants of node i
5: for E V do
6:
ain(i) t U Ú:iE de(j)}
mixture ancestors of node i
7: Repeat Steps 2, 3, 4 for all E V
8: Step 2: Obtain cycle-free descendants
9: Find cycles among ain(i)
10: C(i) < {x = (II,..-,, T++1) m = Te+1 Vu E [4] Ta E aai(() A tu E ann(Tu-1)}
11: if C(t) is empty then
12: B(i) < 0
for j E ai) do
14:
de;(r) - (de(j) n an)) U (?)
15: else
16:
B(i) < a minimal set such that Vx E C(i) (m)) 21 for E sin(i) do
18:
Intervene on I B() de,(f) (k u X3 A X2 in Pm.z) cycle-free descendants of node
D break cycles among ain(i)
19:
20: A - E (i) i de)
b refined ancestors
21: Step 3: Topological layering
22: t 0
23:
while |A 2 do ++++1
24:
25:
(1) < A: n
26:
A A Sii
27: Step 4: Identify mixture parents
pa(11) 0
29:
for (1...... .. do for j E (1) do
30:
31:
Intervene on I pa(i) BB) if X; A X; in Pm.I then pa(i) + [5}
32:
33:
Return (i(()
The construction of cycle-free descendant sets ensures that S (i) is not empty. Next, update A + A \ (i) by removing layer Si()) to conclude the first step. Then, we iteratively construct the layers (1) (j E A:: de()) n = 0) and update A + A \ (1) as in Line 26 of the algorithm. We continue until the A exhausted, and denote these topologiaal layers by (Si(i)..... (,))..
Step 4: Identifying the mixture parents. Finally, we process the topological layers sequentially identify the mixture parents in each layer. For node S, (i), whether j E (i) can be determined from marginal independence test on Pm,I where I = B(i) U (j). Leveraging this result, when processing each (i), we consider the nodes E S.(i) sequentially and intervene on I pa(i) U (3) U [ where pa(i) denotes the estimated mixture parents. Under this intervention, a statistical dependence implies true edge from to Hence, we update the set pa(i) as follows.
pa(1) + U if X2 A X, in Pm. where I (
(14)
After the last layer (i) processed, the algorithm returns the estimated mixture parents pa((). By repeating Steps 2, 3, and 4 for all V. we determine the true edges with their orientations.

---

4.2 Guarantees of the CADIM algorithm
In this section, we establish the guarantees of the CADIM algorithm and interpret them vis-à-vis vis the results in Section 3. We start by providing the following result to show the correctness of identifying mixture ancestors.
Lemma 3. Given I-mixture faithfulness, Step I of Algorithum I identifies {anm (1) E [n]] using single-node interventions.
Note that the mixture ancestor sets {all(())) do not imply a topological order over the nodes V, e.g., there may exist nodes v such that u E anm (v) and v E all (u). As such, a major difficulty in learning mixture of DAGS compared to learning single DAG is the possible cyelic relationships formed by the combination of components of the mixture. Recall that the breaking set is specified in (1I) treat such possible cycles carefully. We refer to the size of B(i) as the cyclic complexity number of node i, denoted by Tr, and the size of the largest breaking set by Tm as
B())
ViEV V.
and
T
max T EV
(15)
Note that T; is readily bounded by the number of cycles in C(t). Next, we analyze the guarantees of the algorithm for a node i in two cases: T; O (cycle-free case) and т; 2 1 (nonzero eyclic complexity).
Cycle-free case. Our next result shows that if TÜ i.e., there are no cycles among the nodes in anm (i), then we identify the mixture parents pa,.. (i). i.c., the union of the nodes that are parents of i at least one component DAG, using interventions with the optimal size.
Theorem 3 (Guarantees for cycle-free ancestors). If the cyclic complexity of node i is zero. then Algorithm ensures that paa (t) = (i) by using Janm (i)) interventions where the size of each intervention is at most pm (i) + 1.
Theorem shows that by repeating the algorithm steps for each node i E V, we can identify all true edges with their orientations using Liev [anm S n(n 1) n interventions, where the size of each intervention is bounded by the worst-case necessary size established in Theorem I.
Nonzero cyclic complexity. Finally, we address the most general case, in which the mixture ancestors of node i might contain cycles. In this case, our algorithm performs additional interventions to break the cycles among anm (i). Hence, the number and size of the interventions will be greater than the cycle-free case, which is established in the following result.
Theorem (Guarantees for general mixtures). Algorithm 1 ensures that pa(i) = pa (1) by using Janm(2 (i) interventions with size + 1, and |an (i) interventions with size most |pam (1) + TO +
Theorem 4 shows that, Algorithm achieves the causal discovery objectives by using a total of + 2 E [a (1)l S n n 2n(n 1) O(n²) interventions, where the maximum intervention size for learning each pa,, (t) is at most т, larger than the necessary and sufficient size |pa,, (i) + 1. This optimality gap reflects the challenges of accommodating cyclic relationships in intervention design for learning in mixtures while also maintaining quadratic number of interventions O(n)).
5 Experiments
We evaluate the performance of Algorithm for estimating the true edges in a mixture of DAGs using synthetic data and investigate the need for interventions, the effect of the graph size, and the cyclic complexity. Additional results for varying the number of components, parameterization, and number of samples are provided in Appendix E !
Experimental setup. We use an Erdös-Rényi model G(n, p) with density p = 2/n n to generate the component DAGs (Ge e E [K] for different values of nodes n and mixture components K. We adopt linear structural equation models (SEMs) with Gaussian noise for the causal models, in which the noise for node is sampled from (M,,, where μi is sampled uniformly in [-1, 1| and of is sampled uniformly in [0.5, 1.5]. The edge weights are sampled uniformly in = 2]. We
'The codebase for the experiments can be found at https: /ttp://///tttbb//// com/bvaric/
interventionnmixturee

---

14
1.50
Recovary adgess
31-
0.9
2.0
0.4
0.95
0.34
+ OUS Sroevvenion (ssel)
0.6
0b0o Aisorvation votion aased
recall
0.90
20 Number of nodes
0.5
Number of nodes
Number of nodes
(a) Skeleton recovery for observa- tional and interventional methods
(b) Varying the number of nodes v. for mixture of K 3 DAGs
(c) Empirical cyclic complexity
for varying and K values
Figure 2: Mcan true edge recovery rates and quantification of mean cyclic complexity of a node.
consider the case where change in the conditional distribution of node i is only caused by changes in the parents of across different DAGs, We use a partial correlation test to check (conditional) independence in the algorithm steps, similar to the related work [10, 11]. We repeat this procedure for 100 randomly generated DAG mixtures for each of the following settings.
Need for interventions. We demonstrate the need for interventions for learning the skeleton in the mixture of DAGs, unlike the case of single DAGs. To this end, we consider a mixture of K DAGS and learn the inseparable node pairs via exhaustive CI tests (see Algorithm 2 in Appendix E). Figure empirically verifies the claim that true edges (even their undirected versions) cannot be learned using observational data only.
Recovery of true edges. We evaluate the performance of Algorithm I on the central task of learning the true edges in the mixture. For this purpose, we report average precision and recall rates for recovering the true edges. We look into the performance of Algorithm under a varying number of nodes [5, 30) for mixture of K 3 DAGs and using 5000 samples from each DAG. Figure 2b demonstrates that Algorithm maintains strong performance even under 30 nodes. We provide additional results for the number of DAGs in the range K E 10] and varying number of samples in Appendix E.
Quantification of cyclic complexity. We recall that for finding the mixture parents of a node i, the maximum size of the intervention used in Algorithm is at most 7ı, i.e., cyclic complexity, larger than the necessary size. In Figure 2c, we plot the empirical values of average cyclic complexity - both the ground truth and estimated by the algorithm. Figure 2c shows that even though average т; increases with K, it still remains very small, e.g., approximately 1.5 for mixture of K = 3 DAGs with 10 nodes. Furthermore, on average. the estimated 7, values used in the algorithm are almost identical to the ground truth т, Therefore, Algorithm maintains its close to optimal intervention size guarantees in the fimite-sample regime.
6 Conclusion
In this paper, we have conducted the first analysis of using interventions to learn causal relationships in a mixture of DAGs. First, we have established the matching necessary and sufficient size of interventions needed for learning the true edges in mixture. Subsequently, guided by this result, we have designed an algorithm that learns the true edges using interventions with close to optimal sizes. We have also analyzed the optimality gap of our algorithm in terms of the cyclic relationships within the mixture model. The proposed algorithm uses total of (n²) interventions. Establishing lower bounds for the number of interventions with constrained sizes remains an important direction for future work, which can draw connections to intervention design for single-DAG and further characterize the differences of causal discovery in mixtures. Finally, generalizing the mixture model to accommodate partial knowledge of the underlying domains can be useful in disciplines where such knowledge can be acquired a priori.
Acknowledgments and disclosure of funding
This work was supported by IBM through the IBM-Renssllaer Future of Computing Research Collaboration.
10

---

References
[1] Nir Friedman, Michal Linial, Iftach Nachman, and Dana Pe'er. Using Bayesian networks to analyze expression data. In Proc. International Conference Computational Molecular Biology, Tokyo, Japan, April 2000.
[2] Nicolai Meinshausen, Alain Hauser, Joris M Mooij, Jonas Peters, Philip Versteeg, and Peter Bühlmann. Methods for causal inference from gene perturbation experiments and validation. Proceedings of the National Academy of Sciences, 113(27):7361-736 2016.
[3] Guido Imbens. Potential outcome and directed acyelic graph approaches to causality: Relevance for empirical practice in economics. Journal of Economic Literature, 58(4):1129- 1179, 2020.
[4] Brett M Reid, Jennifer B Permuth, and Thomas A Sellers. Epidemiology of ovarian cancer: A review. Cancer Biology & Medicine, 14(1):9, 2017.
[5] Yanxi Chen and H. Vincent Poor. Learning mixtures of linear dynamical systems. In Proc. International Conference on Machine Learning. Baltimore, Maryland, July 2022.
[6] Kirsten Bulteel, Francis Tuerlinckx, Annette Brose, and Eva Ceulemans. Clustering vector autoregressive models: Capturing qualitative differences in within-person dynamics. Frontiers in Psychology, 7:1540, 2016.
[7] Emma Brunskill, Bethany R. Leffler. Lihong Li, Michael L. Littman, and Nicholas Roy. Provably efficient learning with typed parametric models. Journal of Machine Learning Research, 10 168):1955-1983 2009.
[8] Peter Spirtes. Directed cyclic graphical representations feedback models. Proc. Conference on Uncertainty in Artificial Intelligence, Montréal, Canada, August 1995.
[9] Eric V. Strobl. Causal discovery with mixture of dags. Machine Learning, 112(11):401142255, 2023.
[10] Basil Saeed, Snigdha Panigrahi, and Caroline Uhler. Causal structure discovery from distribu- tions arising from mixtures of dags. In Proc. International Conference on Machine Learning, virtual, July 2020.
[11] Burak VaniIı, Dmitriy Katz, Dennis Wei, Prasanna Sattigeri, and Ali Tajer. Separability analysis for causal discovery mixture of DAGs. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https: openreview net/ / forum? d=ALRRwTT RLZ.
[12] Thomas Verma and Judea Pearl. An algorithm for deciding if set of observed independencies has a causal explanation. In Proc. Conference on Uncertainty in Artificial Intelligence, Stanford, CA, July 1992.
[13] Frederick Eberhardt and Richard Scheines. Interventions and causal inference. Philosopy of Science, 74(5):981-99) -955, December 2007.
[14] 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, June 2014.
[15] Antti Hyttinen, Frederick Eberhardt, and Patrik O Hoyer. Experiment selection for causal discovery. Journal of Machine Learning Research, 14(1):00113071, 2013.
[16] Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Learning causal graphs with small interventions. In Proc. Advances in Neural Information Processing Systems, Montréal, Canada, December 2015.
[17] Chandler Squires, Sara Magliacane, Kristjan Greenewald, Dmitriy Katz, Murat Kocaoglu, and Karthikeyan Shanmugam. Active structure learning of causal DAGs via directed clique trees. In Proc. Advances in Neural Information Processing Systems, December 2020.
11

---

[18] Sumanth Varambally, Yi-An Ma, and Rose Yu. Discovering mixtures of structural causal models from time series data. arXiv:2310.06312. 2023.
[19] Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Experimental design for learning causal graphs with latent variables. Proc. Advances in Neural Information Processing Systems, December 2017.
[20] Raghavendra Addanki, Shiva Kasiviswanathan, Andrew McGregor, and Cameron Musco. Efficient intervention design for causal discovery with latents. In Proc. International Conference on Machine Learning, July 2020.
[21] Raghavendra Addanki, Andrew McGregor, and Cameron Musco. Intervention efficient algo- rithms for approximate learning of causal graphs. Algorithmic Learning Theory, March 2021.
[22] Yang-Bo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9Nooemmeer::253 2547, 2008.
[23] Kristjan Greenewald, Dmitriy Katz, Karthikeyan Shanmugam, Sara Magliacane, Murat Ko- caoglu, Enric Boix Adsera, and Guy Bresler. Sample efficient active learning of causal trees. In Proc. Advances in Neural Information Processing Systems, Vancouver, Canada, December 2019.
[24] Vibhor Porwal, Piyush Srivastava, and Gaurav Sinha. Almost optimal universal lower bound for learning causal dags with atomic interventions. In Proc. International Conference on Artificial Intelligence and Statistics, virtual, March 2022.
[25] Davin Choo, Kirankumar Shiragur, and Arnab Bhattacharyya. Verification and search algorithms for causal dags. In Proc. Advances in Neural Information Processing Systems, New Orleans, LA, December 2022.
[26] Murat Kocaoglu, Alex Dimakis, and Sriram Vishwanath. Cost-optimal learning of causal graphs. In Proc. International Conference on Machine Learning, Sydney, Australia, August 2017.
[27] Erik Lindgren, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Experimental design for cost-aware learning of causal graphs. In Proc. Advances in Neural Information Processing Systems, Montréal, Canada, December 2018.
[28] Ehsan Mokhtarian, Saber Salehkaleybar, AmirEmad Ghassami. and Negar Kiyavash. A unified experiment design approach for cyclic and acyclic causal models. Journal of Machine Learning Research, 24(354): 1-31, 2023.
[29] Karren Yang. Abigail Katcoff, and Caroline Uhler. Characterizing and learning equivalence classes of causal DAGs under interventions. In Proc. International Conference Machine Learning, Stockholm, Sweden, July 2018.
[30] Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Causal discovery from soft interventions with unknown targets: Characterization and learning. In Proc. Advances Neural Information Processing Systems, December 2020.
[31] Chandler Squires, Yuhao Wang, and Caroline Uhler. with unknown intervention targets. In Proc. Conference in Uncertainty in Artificial Intelligence, August 2020.
Permutation- crmutettoon-ased causal structure learning
[32] Philippe Brouillard, Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. Differentiable causal discovery from interventional data. In Proc. Advances in Neural Information Processing Systems, December 2020.
[33] Bo Thiesson, Christopher Meek, David Maxwell Chickering, and David Heckerman. Learning mixtures of DAG models. In Proc. Conference on Uncertainty in Artificial Intelligence, Madison, WI, July 1998.
[34] Biwei Huang, Kun Zhang, Pengtao Xie, Mingming Gong, Fric P Xing, and Clark Glymour. Spe- cific and shared causal relation modeling and mechanism-based clustering. In Proc. Advances in Neural Information Processing Systems, Vancouver, Canada, December 2019.
12

---

[35] Kun Zhang and Madelyn RK Glymour. Unmixing for causal inference: Thoughts on Mccaffrey and Danks. The British Journal for the Philosophy of Science, 2020.
[36] Wei Chen, Yunjin Wu, Ruichu Cai, Yueguo Chen, and Zhifeng Hao. CCSL: causal structure learning method from multiple unknown environments. arXiv:2111.088 1.09666, 2021.
[37] Alex Markham, Richeek Das, and Moritz Grosse-Wentrup. Wentrup. A distance covariance-basee kernel for nonlinear causal clustering in heterogeneous populations. In Proc. Conference on Causal Learning and Reasoning, Eureka, CA, April 2022.
[38] Biwei Huang, Kun Zhang, Jiji Zhang, Joseph D Ramsey, Ruben Sanchez-Romerg Clark Glymour, and Bernhard Schölkopf. Causal discovery from helcrogenoousshonsatioonnyy data. Journal of Machine Learning Research, 21(89):1-53, 2020.
[39] Kun Zhang, Biwei Huang. Jiji Zhang, Clark Glymour, and Bernhard Schölkopf. Causal discov- ery from nonstationary/heeergeeene data: Skeleton estimation and orientation determination. In Proc. International Joint Conference on Artificial Intelligence, Melbourne, Australia, August 2017.
[40] Joris M. Mooij. Sara Magliacane, and Tom Claassen. Joint causal inference from multiple contexts. Journal of Machine Learning Research, 21(99):1-108, 2020.
[41] Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Causal discovery from soft interventions with unknown targets: Characterization and learning. In Proc. Advances in Neural Information Processing Systems, virtual, December 2020.
[42] Chenxi Liu and Kun Kuang, Causal structure learning for latent intervened non non-stationary data. In Proc. International Conference on Machine Learning, Honolulu, Hawaii, July 2023.
[43] Peter Spirtes, Clark Glymour, Richard Scheines, and David Heckerman. Causation, Predic- tion, and Search. MIT Press, Cambridge, MA, 2000.
[44] Judea Pearl. Causality. Cambridge University Press, Cambridge, UK, 2009.
[45] Joris M Mooij and Tom Claassen. Constraint-based causal discovery using partial ancestral graphs in the presence of cycles. In Proc. Conference on Uncertainty in Artificial Intelligence, virtual, August 2020.
[46] Ann Ran, Patrick Hsu, Jason Wright, Vineeta Agarwala, David A Scott, and Feng Zhang. Genome engineering using the crispr-cas9 system. Nature Protocols, ((11):2281-2300) 2013.
[47] Geoffrey J McLachlan, Sharon X Lee, and Suren I Rathnayake. Finite mixture models, Annual Review of Statistics and Its Application, 6(1):355-378, 2019.
[48] Abhinav Kumar and Gaurav Sinha. Disentangling mixtures of unknown causal interventions.
In Proc. Uncertainty in Artificial Intelligence, July 2021.
13

---

Interventional Causal Discovery in a Mixture of DAGs Appendices
Table of Contents
A Auxiliary results
14
B Proofs for Section 3
15
Proof Lemma
B.2 Proof of Lemma
B.3 Proof of Theorem
15
B.4 Proof of Theorem 2
16
Proofs for Section 4
Proof Lemma
C.2 Proof of Theorem 3
16
C.3 Proof of Theorem 4
18
Additional examples
20
Partitioning true edges into component DAGs
20
D.2 An example of cyclic complexity
20
E Additional experiments
21
A Auxiliary results
Lemma 4 (Markov property, [10, Theorem 3.21), Let A, B,C C V be disjoint. If À and B are d-separated given in the mixture DAG. then XA and XB are conditionally independent given Xc in mixture distribution.
Lemma ([11, Theorem 5]), Consider nodes i.j E V such that i and j are not adjacent in any of the component DAGs, i.e., & p)) and j pi.,(i).
(i) Ifi A and A: and j are always inseparable, i.e., (i- an emergent edge.
(ii) i & A and j A: if and inseparable, then there exist component DAGs Gü. Gv such that Ge contains a A-through path from i to j and Gr contains a A-through path from
(iti) if A and j A: if and j inseparable, then least one component DAG contains Atthrough path from i to j-
Lemma 6 ([11, Theorem 6)). Suppose that GI....,KK GR are directed Irees. Consider nodes i, V such that and j are not adjacent in any component DAG, i.e., & pa (j) and $ pa (i).
(i) if A and A: and j are always inseparable.
(ii) ifi & A and j A: i and j are separable if and only if there does not exist Go. Gø such that the two DAGs contain A-child-the -thruuhh paths between and j in opposite directions.
(ii)) i & A and E A: and j are separable if and only if none of the component DAGs contains A A-child- child-through from i to j.
14

---

B Proofs for Section 3
B.1 Proof of Lemma
Proof of identifiability: Since j E I. we have j $ Âz. Then, Lemma (iii) implies that if (j - i) true edge and there does not exist A-through path from in any Ge,T, then and j separable in Pm,z- Consequently, whether j E pa (f) can be determined from Pm.I-
Proof of non non-identifiabilitty First, note that using Lemma 4, for any intervention I, Pm, I is Markov with respect to the Z-mixture DAG 9m.I. Then, for E Az, also E Áz, and j are inseparable in Pm,, regardless of whether there is true edge between and j. Hence, whether j pa (i) cannot be determined using CI tests on P.u.I- For the second statement, recall that intervention cuts off all incoming edges to nodes of I in all component DAGs. Then, if I, cannot determine whether j E pam (i) since the possible influence of on é cut off by the intervention. Suppose in is given by - ~4 for some k Σz. Since i Az, the T-mixture DAG Im,z also contains the path - k: f y - i. Since these paths cannot be blocked simultaneously by conditioning on a set of nodes, and j are inseparable regardless of whether j E pam. Therefore, whether j E pam. (i) cannot be determined using CI tests Pm,I-
that i Ar. and let be -child-througee path from
component DAG Gi,z. Zr i.e.,
B.2 Proof of Lemma 2
We start by providing a general statement that will be used for the proof of the three subcases. Let I be an intervention such that component DAG Grzz. z. In this case, using Lemma 5, if (j + i) is not true edge, then i and j are true edge.
and there does exist A-through path from j to i in any
separable Pm.I. Subsequently, if and are inseparable Pm,.I, then (j -
Let π be a A A-through path from j to i in some Gezz Note that, for any of the following three intervention sets,
ii I (i) U
U (par(i)
[E]K]
(ii) I U
U
[E[
(iii) I = 0
(dex(i)) [E[K]
U
cannot contain node between j and i. Therefore, j (1). there does not exist A-through path from j to Subsequently, if and are not separable Pm.I for any of these three interventions,
means there exists j S for some component DAG 9r. Therefore, whether j pam (i) can be determined by checking whether i and are separable in Pm,z for any of these three interventions.
B.3 Proof of Theorem
The sufficiency result immediately follows from Lemma since each the three interventions in stated in Lemma is subset of pam (i) {.}. To show the worst-case necessity of intervention with size at least [pa.,. (i)l + 1, we construct the following example. Consider component DAGs (Ge [K]} such that G1 contains single edge 4 j. the rest of the component DAGs, for any k S i edge, let us also draw j & k. We do not put any constraints the other possible connections in (G, E (2....,K] K}}. Note that this construction yields that pam. (1) U (i,j} C A. Consider the paths
_ +i, and (i 4 i: pa,. (i))
(16)
For any intervention I C V \ {i) that does not contain all nodes in pa,, (i) U (i), at least of these paths will be active in the T-mixture DAG Gm, regardless of whether there exists & i, i E (,...., K} edge. Therefore, at the worst-case, whether j (a) cannot determined from Pm..I for any intervention I with size < |pa,, (i)).
15

---

B.4 Proof of Theorem 2
Proof of sufficiency. Consider an inseparable pair (i-j) Pm- For a mixture of directed trees, Lemma 6 implies that if there does not exist -h-hhul- path from j to in any component DAG, then ()) corresponds true edge. Consider the intervention
I U U (a n (ch n n
(17)
[E[K]
which cuts off all b-child-through paths from j to in component DAGs. Also note that (ane(1) n che(i) A S since each Ge contains most one causal path from j to Then, and are inseparable in Pm,z if and only if j E pam (1), since I cuts off all 4 edges. Therefore, can determine whether j E pa (i) from Pmn.I with an intervention I where
1
Σ (((ane()) (che + 0) SK BE[K]
(18)
Proof of necessity. For the worst-case necessity, consider component trees {G: E [K]] such that each graph contains a A-child-through path from j to i which the children of in each graph is distinct. Also, let l: E (5) but A par(s) for all E (2..... KJ. This construction yields that
I - U U (anr(t) n (he [E[K]
(19)
Consider the paths
3 - y +i, and { ii J \{H)
(20)
For any intervention I S V {i} that does not contain all nodes in J {i), (f), at least one of these paths will be active in the T-mixture DAG Gm,I. regardless of whether one of the A-child
-child-through through paths is
j 4 itself. Note that if & pa (i), then this specific construction yields that |J {i}] K 1.
Therefore, at the worst-case, whether j E pa,. cannot be determined from Pm.z for any intervention I with size 7 K.
C Proofs for Section 4
C.1 Proof of Lemma
Consider intervention I = ( and the corresponding interventional mixture distribution Pm. I and I- mixture DAG 9m,z. We will show that (j : X, y. X; in Pm,I] is equal to the mixture descendants
dem(i). First, let i E (j) i.e., there exists a path -4 j for some E [K]. Then, by Z-mixture faithfulness, Xj y1. X; in Pm, For the other direction, let X; A. X₃ in Pm,II Then, there must be an active path between j and in T-mixture DAG Gm.z. Since is intervened and there is no
conditioning set, the path cannot contain any collider, which implies that the path is in the form 4 for some& E [K]. Therefore, we have
E an (1)
X, A X, in Pm.
(21)
which concludes the proof.
The choice of single-node interventions in Step 1. We note that the choice of single-node interven- tions for learning the mixture ancestors (an, (i) E V) deliberate for simplicity. It is possible to achieve the same guarantee using fewer than interventions by designing multi-node interventions, e.g., using separating systems with restricted intervention sizes [16]. Nevertheless, using n interven- tion does not compromise main results since show in the sequel, the number of total inter- ventions in the algorithm will be dominated by the number of interventions in the subsequent steps.
C.2 Proof of Theorem
Lemma 3 ensures that Step of Algorithm I identifies anm (i) and dem (i) correctly for all i E [m]. Hence, in this proof use anm (i) and (i) for ai) and de(i), respectively. We consider the
16

---

case where there are no cycles among the mixture ancestors of node induced by the mixture ancestral relationships, i.e., the following set of cycles is empty.
C(i) + {- ( In this case, Step 2 of Algorithm 1 only creates the sets
Te)
ne Vu [ - 1. anm (i) A Ta amm (fu+1))
(22)
de, A de()) n {ain(i) Lij = dem (i) n (anm(() Ui)
Vi amm (i),
(23)
and am (t). The lack of cycles implies that the nodes in A can be topologically ordered, i.e. there exists ordering (A Alam, such that Aj (AA) implies < k. In Step 3, we leverage this key property for constructing hierarchically ordered topological layers.
Next, recall the definition of S (1) in (13),
Si {j E anm dcm 0 am (1) 0}
(24)
Then, since there are cycles among the nodes in alm (i). Si (t) is not empty, e.g., the first node of
the topological order described above has no mixture descendant within anm (i). Consider j E S (i). Since anm (4) O dem (J) = 0. must be a mixture parent of i. Therefore, (i) S pa (t). We will use induction to prove that topological layering in Step and the scquential interventions in Step ensure identifying pam (t).
Base case.
Consider (2) defined as
Si) {j E anm (i) \ (1) dem(s)) {anm (1) (1)) S1()) 0)
(25)
Note that we have pa(i) = (1). Consider a node j E S2()) and intervene on I ( (j).
j E pam( (i), then by Z-mixture faithfulness, X; fll X; Pm.I- On the other direction, suppose that X, Al X; in Pm.I. If j & pa (t), then there exists an active path between j and in Im,I. Since the conditioning set empty, there cannot be any colliders on the path. Then, since pam (i),
the path has the form j - k - for some &s E anm and é E [K]. We know that k (i) since intervention I contains S₁ (t). Then, & E dem n (anm()) (i)), which contradicts with j (2) by definition of (2)).. Therefore, X, P. X; Pm,z implies that j pa (i). Subsequently, for j E S2()), we have
j pa (i)
X, M X; in Pm.I
(26)
Note that this step uses [S2(1) interventions, one for each j E S2(1), and each intervention has size [Z| S (i) +1
Induction hypothesis. Assume that we have identified the set (1) O pa (1) correctly for E
(1....,u 1}. i.e., we have pa(t)= = U Sa(1) O (i). We will show that the algorithm also
A=
identifies (1) n pa (1) correctly.
Let A = anm U (1) and consider (1) defined as
A=1
S.(1) = {j e A: de.. (1)
(27)
Consider node j S1) and intervene
I= (=) (0) U (
(28)
k=1
If j E pam (i), then by Z-mixture faithfulness, X, f. X, in Pm, For the other direction, suppose that X, A X; Pm, If j & (i), then there exists an active path between j and in Z-mixture DAG 9m,z. Since the conditioning set is empty, this path has the form j S. k S i for some k dem(i) n A, which contradicts with j E (1) by the definition of (i). Subsequently, for j (i), we have
jE pamm.. (i)
X2 A X in Pm.II
(29)
Therefore, by induction, the algorithm identifies (i) n pa (i) correctly for all (1.
17

---

Finally, note that while processing each layer (i), the algorithm uses [5,(1) interventions, one for w-1
each j E (1), with size [I| = pa ( n U ( + This is upper bounded by |pa.. (7) + 1,
&
which is shown to be the worst-case necessary intervention size in Theorem Then, including n single-node interventions performed in Step I, for identifying pam (1) for all i V, Algorithm uses a total
(s)
+
Jan (i) = On2²)
(30)
interventions, which completes the proof of the theorem.
C.3 Proof of Theorem 4
We start by giving a synopsis of the proof. Lemma ensures that Step of Algorithm identifies anm (1) and m correctly for all i E V. Hence, in this proof we use aDm (t) and de (i) for ain(i) and dem (i), respectively. In this theorem, we consider the most general case in which the nodes in mixture ancestors an, (i) can form cycles via their mixture ancestral relationships. These cycles will be accommodated by the procedure in Step 2. Intuitively, by intervening we can break all the cycles in C(i) in the new interventional mixture graphs. Then, we would be able to follow Steps 3 and 4 similarly the proof of Theorem 3, albeit using interventions with larger sizes.
small number of nodes,
Step 2. First, recall the definition of cycles among mixture ancestors of i, Vu E [ - 1] mu E an((i) A an((Fu11),, (31)
C(i) {Nt ( me)
and the associated breaking set,
B(i) minimal set s.t. VT C()), [B()
(32)
We denote the size of the breaking set by r; - [B( and refer to as the cyclic complexity of node i. The intervention I (() breaks all cycles in C(i). To this consider a cycle = (T...... : Mt) in C(i) and suppose that pi. E B()). Then, intervening on Tu breaks all causal paths from - to which breaks the cycle. Step node j E alm()) (t). Specifically, for each each j E anm (i), we intervene on I = B(i) U {i} and set
leverage this property obtain cycle-free descendants of each
de, (j) = {ks anm (i} X, A X in Pm.I)
(33)
Note that if pam (1), then dj, Hence, after constructing these cycle-free descendant sets, we refine the ancestor set
A {j E an (1) : E de:(i))
(34)
which contains all (i). will use induction to prove that topological layering in Step and sequential interventions Step 4 ensure identify pa (i) from A.
Base case.
Consider (i) defined as
(1) = [jj A: de
(35)
First, show that S (i) is not empty. Otherwise, starting from node mi E A, we would have
de;(m)) ) 0 A 0 de;(Tz2 /
3 E dei(m)) nA
(36)
3 π& E (e,( 044
(37)
(38)
(c;( nA
3m E de:( nA
(39)
since A has finite elements. However, this implies that none of the (T.,... TE} are contained in B(i) due to the construction de; sets with interventions I B(t) U ()). This contradicts with the definition of the breaking set B(i) as it does not contain any node from the cycle { m.).
18

---

Next, consider a node j E (i) and intervene on I = (() (1). We will show that
j E (1)
Xj nl X; in Pm.I
(40)
If E pim then by Z-mixture faithfulness, X, A X; in Pm.I. We prove the other direction, that X; A. X; Pm,I implies that j E pa (1) as follows. First, note that X; A. X; in Pm,I does not have a conditioning set. Then, it implies that there exists an active path j An in Ge,z for some & [K]. Suppose that j & pam (i), which implies that j - k is in Ge,I, and k & B(i) for path being active. However, in this case we have & E de;(j) O A.A. which contradicts with j E (i) due to definition of S1 (i). Hence, for j E (i), X, fL X, in Pm,I implies that j E pam (t), which concludes the proof of the base case.
Induction step. Assume that we have identified the set S,()) n pa (i) correctly for a E e-1
Ul....u--1. 13. Let A (1) \ U Si( and consider (1) defined as k=1
(i) (j E A: de:(i) n A 0}
(41)
Note that, after processing ,,,,...,,..... correctly, we have
m-1
pa(i) pam (1) U Sa(1).
(42)
k=
Consider a node j E (i) and intervene on
I = Upa(t) (() (1) U
Se(1) O pa (1)
(43)
k=1
We will show that
j E pam
N in Pm.Z.
(44)
If j E pam (i), then by I-mixture faithfulness, X, f1 X, in Pm.I. We will prove the other direction, that is X, y. X; in Pmn,I implies j E (1), similarly to the base case. First, note that X, n X; in PM,I does not have a conditioning set. Then, it implies that there exists an active path j & i in Ge,z for some E [K]. Now, suppose that j & pam (f), which implies that the active path has the form E -, in Ge,I for some é E [K] and l & I. Since l pam (i), k ş I implies that (j) n A. which contradicts with l: E S)) due definition
& U S.((). Then, we have of (i). Therefore, for j E (i) and I B(i) U pi(i) U() X, P X, in Pm,r implies that j E (i), which concludes the proof of the induction step. Therefore, by induction, the algorithm identifies S. pa (i) correctly for all u E (t....,t).
Finally, note that while processing each layer (i). the algorithm uses [i)( interventions, one for M-1
each j (1), with size [Z] ppa ( U (a) B(1) + 1, where 7; [B(i] is referred to as k=1
the cyelic complexity of node i. Therefore, the size of the largest intervention set is
pa (4) + T: 1.
(45)
We note that this upper bound the intervention size is T, larger than the necessary size Ipa,, (1) +1 shown in Theorem This optimality gap reflects the effect of the cyclic complexity of the problem. Finally, adding n single-node interventions performed in Step for identifying pam(i) (i) for all i E V, Algorithm uses a total of
jan (i)
+
Σ i=
(S)( = n n +
Janm (i)) < 2n² - O
(46)
interventions, which completes the proof of the theorem.
19

---

D Additional examples
D.I Partitioning true edges into component DAGs
We have emphasized in Section that the component DAGS of the mixture cannot be identified without further assumptions even under our interventional setting. We discuss few examples of this matter.
1. Consider the following mixtures of K DAGS
Mixture I: Edge sets E, {1 + 2, 3) and E₂ =
Mixture 2: Edge sets E₁ {1 + 2} and E₂ {1 11-3) 3}
In this case, distributions of the mixtures can still be the same under all intervention sets I S (1, 3). Hence, without additional assumptions (e.g., model parameterization), we cannot distinguish the mixtures via only conditional independence tests. Instead, can only learn the set of true edges, E, = {1 + 2, + 3} for both mixtures.
2. Consider mixture of two DAGs with edge sets E = {1 + 2,2 3} and E, = {3 1}. Recall that in Stage of Algorithm 1, we learn the mixture ancestors of the nodes an intermediate step. Hence, after learning the set of true edges in the mixture via the rest of the algorithm, we have the following information:
1 E allm (3), & pa (3), 1 (2m
(47)
2 E pam (3), 2 é anm (1),
(48)
3 E pam (1), é anm (2)
(49)
Suppose that we know = Then, we can see that the only possible component DAGs that result in this mixture are Ej {1 2, 3) and E₂ = {3 - 1}. This is because 3 1 cannot be in the same DAG as the other two edges due to the known ancestral relationships. Hence, learn the component DAGs in this case. However, without learning the true edges, we would not be able to know that we can learn the component DAGs of the mixture model.
These examples show that our work a necessary first step into the interventional causal discovery of mixtures. Furthermore, we hope that it can inspire future work for the use of interventions in mixture of models, e.g., establishing graphical conditions for (partial) recovery of individual DAGs, leveraging the side information.
Finally, we note two things regarding the possible side information that can enable stronger results. First, mixture distributions (the underlying component distributions Pe (z)s) can be identified under some assumptions, e.g., Gaussian mixture models [47]. Second, in a related line of work, disen- tangling mixtures of unknown interventional datasets is studied under specific conditions on the intervention sets and given the distribution of the observational DAG [48]. Establishing the necessary and sufficient conditions for achieving similar disentangling objectives tasks in our mixture model is an open problem for future work.
D.2 An example of cyclic complexity
We have empirically quantified the average cyclic complexity in Section 5. In addition, we give a visual example here. Consider the mixture of two DAGs in Figure By definition of mixture ancestors, we have
alm (1) = (2,5)
(50)
alm (2) = [3,5},
(51)
anm (3) =0,
(52)
all (4) = =11,2,3,5),
(53)
anm
(5) = (1,
(54)
20

---

2
2
3
3
1
5
4
91
G
== 0. Figure Sample DAGs for mixture of two DAGS
Then, by definition of C() in (10), we have
C(1) ((2.5.2) C(2) = 0,
(55)
(56)
C(3) 0,
(57)
C(4) = ((2,5.2), 1, 5,, (1,5,1))
(58)
((5) 0
(59)
Subsequently, an example of minimal breaking sets and cycle complexities are given by
B(1) {2}
1,
(60)
((2)
T2
0
(61)
= 0, B(3) 0 =
(62)
((4) (5)
74 14=1, ((5) =
(63)
(64)
This example illustrates that even though the mixture model contain many cycles, the eyclic complexity of the nodes can be small.
E
Additional experiments
Effect of the number of samples. For the same experimental setting in Section 5, we investigate the effect of the number of samples on the performance Algorithm 1. Figure 4a demonstrates that the algorithm achieves almost perfect precision even with as few as = 1000 samples under the parameterization described in Section 5. The recall rates are lower than the precision; however, when the number of samples is increased to = 10000, the gap is closed, and the recall rates also become closer to perfect.
Varying the true edge weights. Recall that in Section 5, we have considered the case where the weight of true edge is constant across the component DAGs it belongs to. However, our theory and algorithm can handle the general case, in which conditional distributions pe Px(;; X (p),()) and pe (X, Xxpa (6)) can be different even the parent sets pa. (1) = pa. (i) for two component DAGs
Ge and Ge. For instance, when considering a mixture of DAGs where (1 + 2) E E,, (1 + 2) & E,, and (1 2) E E, relations, the edge weight from node to node 2 can be different in GI and G3- performance of our algorithm
this general setting, we consider the following parameterization. When randomly generating the weight of true edge (i 5) E E, it has two options: (i) With probability 0.5, it is constant across the component DAGs it belongs to, (ii) with probability 0.5, it is different (randomly sampled) for every component DAG it belongs to. Figure 4b shows that the performance of the algorithm is virtually the same for this setting compared to the main setting considered in Section 5.
To investigate
Skeleton (true edges) versus inseparable pairs. In Section 5, we demonstrate the need for interventions by learning inseparable pairs from observational mixture data and comparing them to skeleton of the true edges. To learn the inseparable pairs specified in (5), we perform exhaustive conditional independent tests in [11], summarized in Algorithm 2. Note that mentioned in Section 4.1, this exhaustive search requires O(n² 2n) CI tests, which we perform only for this experiment setting and omit in proposed Algorithm 1.
21

---

true edges
Recovery true edges
0.98
0.95
0.96
0.90
0.94
0.85
n=10- precciinn
n-5
0.92
precisoon
10 recall
0.80
1000
2000
5000
10000
0.90
20
samples
Number of nodes
(a) Varying number of samples for mixture
(b) Recovery for varying true edge weights mixture of DAGs
K 3 DAGs
Figure 4: Additional experiment results for true edge recovery
Algorithm 2 Mixture skeleton learning via observational data [11, Algorithm 1 Stage 1]
1: Input: Samples from mixture distribution Pm
2: Return: Inseparable pairs of the mixture E
3: Form complete undirected graph: E; f- ((i-))
4: for all i, E V do
5: for all S E V
{i,j} do X; IL Xy Xs then
6:
7:
Remove (i - j) edge: Eω + EM \ (i - and SepSet(i.)) + S.
8:
break
9: end
end for
11: end for
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Sections and establish the results claimed abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including 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 include aspirational goals as motivation 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: The limitations the work are clarified throughout the paper and discussed in Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
22

---

The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on 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, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails 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 to address problems of privacy and faireess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, 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]
Justification: The assumptions for the theoretical results clearly stated in the theorem statements, and the proofs of the results are provided in Appendix B and C.
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 or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a 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
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 of whether the code and data are provided or not)?
Question:
Answer: [Yes]
The algorithm details are summarized in Algorithm 1, and described in Sec- tion 4. The experimental procedure is described in Section 5, and detailed parameterization is given in Appendix E. The code for reproducing the main experimental results can be found at https: htt.tht..b..gg//g//// thub. com com/bvarti aivariii.. www.teneentiiiiineeeeee on- xture-DAG.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
23

---

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 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 to 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 a 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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be 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 welcome describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to 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?
Answer: [Yes]
Justification: The code for reproducing the main experimental results can be found at ht attps: //ggt/gttuu/////// wtt.///w//iiieeee comm/bvarrii///teeeeeettt htt.innnteeeniiiin mwwtmrittteeeeee -DA.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https:/ /tts:://niss..t/ cc/
public/ /aaiic//gges///eeeeeeeeeeieeeee/ //o///odeuuuoo/ee ssi sssoPoolicyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NewrIPS code and data submission guidelines (https: / /nips. cc/
/nipsscccppblicc httpp/ublcccccc http/publc///uuuieseesseeee guwiee///e///eegeeeoo Codee Submi ssnisssonn oooolling for more details.
The authors should provide instructions on data access and preparation, including how to 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).
24

---

Providing as much information as 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: The experimental procedure described in Section 5, and detailed parameteri- zation is provided in Appendix E.
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: The plots in all figures are given for an average of 100 experiments.
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, least for the experiments that support the 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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-simma error bar than state that they have 96% CI, if the hypothesis of Normality of errors 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 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 exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Experiments are run on a single commercial CPU.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
25

---

The paper should provide the amount of compute required for each of the individual experimental runs as 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 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: /nnuriursss.... httpp//ccc/.llcc//tccccceeellle.
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics and confirm that the research in this paper conforms with the code of ethics.
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 circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper is mostly theoretical and does not pose potential negative societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal
impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeett 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to 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 to 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 (c.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 a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper is mostly theoretical and does not pose such risks.
26

---

Guidelines:
The answer NA means that the paper poses no 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 to 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 challenging, and many papers do not require this, but 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 are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Portions of the publicly available code of [11] is adopted in the code of experiments.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if 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 (c.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, paper a thoode com/ datasets has curated licenses for some datasets. Their licensing guide help determine the license of a dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors are encouraged to reach out the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The codebase for the experiments can be found at https: / htw.ttttbhb..../ com/ bvarici/intervent wwwerentiooiiiituuieeeeeeeeeeeee DAG, and is released under Apache 2.0 license.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model 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 anonymize your assets (if applicable). You either create an 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 details about compensation (if any)?
27

---

Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor 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 the NeurIPS Code of Ethies, 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
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor 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 to the NeurlPS 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.
28


Reviews:
[{"review_id": "lLKm66Qvz4", "reviewer": "Reviewer_5C9J", "summary": "In the case of a single DAG, conditional independence tests specify the skeleton (under faithfulness) and interventions are limited to orienting edges. In the case of data coming from a mixture of DAGs, it is possible for two variables to not be adjacent in any of the components but still be conditionally dependent for every conditioning set. This paper proves that the necessary and sufficient intervention size to identify the \"true\" edges of the mixture, i.e. node pairs where there is an edge in at least one component DAG is the size of the union of parents in all components + 1. It also designs an algorithm to do so.", "questions": "Already asked in the weakness section.", "limitations": "Addressed implicitly in a conclusions section", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Causal discovery given data from a mixture of DAGs seems to be an important problem with applications in several domains. Existing work has focused on the observational data regime. But this is not sufficient in the mixture case because of the phenomenon of \"emergent pairs\". This is the first paper that studies this problem assuming presence of interventional data. Using interventional data to pinpoint DAGs  among an equivalence class is also a relevant thread of interest. \nThe paper is written well with a clear flow of ideas. I didn't check all the proofs but the ones that I didn't, appear sound. The analysis of the problem appears quite complete in a sense with the optimal intervention sizes characterized and the algorithm's gap to optimality also characterized.", "weaknesses": "The results heavily depend on the interventional model where the modified distribution of the intervened variable does not change across component DAGs. I was wondering if there was any practical motivation for considering such an intervention model. If so, it would make sense to include it in the paper. \n\nI also could not find connections to existing results on intervention sizes for single DAG which should be a special case of thie mixture case. Is this because of the interventional model, again?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a thorough review and insightful comments. We address the questions as follows.\n\n**Modified distributions of an intervened variable:** We considered an intervention model in which an intervened node $i$ has distribution $q_i(X_i)$ for all component DAGs. The reason is that an intervention procedure targets a specific node on all component models at the same time. For instance, when considering a gene knockout experiment (e.g., via CRISPR technique (Ran et al., 2013)), all the edges from parents are cut off, and the new distribution $q_i(X_i)$ is expected to be the same across all DAGs as result of the same intervention mechanism.\n\nF Ann Ran, Patrick D Hsu, Jason Wright, Vineeta Agarwala, David A Scott, and Feng Zhang. “Genome engineering using the crispr-cas9 system”. Nature Protocols, 8(11):2281–2308, 2013.\n \n**Intervention sizes for single DAGs:**\n- First we note that an assumption in our analysis is that we have $K \\geq 2$ component DAGs. Hence, unfortunately we cannot recover the counterpart results for single DAGs as a special case. Furthermore, when considering a single DAG, there are no multiple component DAGs. As such, the lack of a detailed discussion on single DAGs is not due to our interventional model but it is simply due to the nature of the mixture model that does not subsume the single DAG model.\n \n- After these clarifications,  we kindly note that we discussed the interventions on single DAGs in Lines 83-98. To elaborate further, single DAGs in causally sufficient systems, i.e., no unobserved confounders, can be learned using **single-node** interventions. Hence, almost none of the papers cited in the paragraph \"Intervention design for causal discovery of a single DAG\" investigates the required intervention sizes. Therefore, we did not discuss the specific results of those papers that are not related to our investigation. To give an example [16] shows that $\\cal{O}(\\frac{n}{k}\\log \\log k)$ randomized interventions with size $k$ suffice for identifying the DAG with high probability. In another direction, different cost models are proposed to minimize the total intervention cost incurred by the number and size of the interventions ([20], [24], [25]). In the presence of latent variables, multi-node interventions can be required. However, for this case, [19]-[20]-[21] study strongly-separating sets, again based on unconstrained intervention sizes.\n \n- To our knowledge, only related work for the required size of interventions is [26]. Specifically, it considers **cyclic** directed models and shows that the required intervention size is at least $\\zeta-1$ where $\\zeta$ denotes the size of the largest strongly connected component (nodes $i$ and $j$ are said to be strongly connected if they are both ancestors of each other). We will add this note to the revised paper.", "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": "M8J5uegzKy", "reviewer": "Reviewer_bGit", "summary": "This work studies an important problem in causal discovery for its relevance in the real world -- identifying the causal relationship when the underlying data-generating process comes from a mixture of different DAGs. They give the necessary and sufficient size of intervention set to identify the union of all the parents of a node across components. They also give an algorithm that requires $O(n^{2})$ interventions to identify all the directed edges of individual DAG. Finally, they also quantify the gap between the number of interventions used by the proposed algorithm and the optimal size in terms of cyclic complexity number.", "questions": "1. This is not directly relevant to the proposed algorithm and might be a direction for future work.  But is it possible to partition the identified true edges into subsets for each of the individual components? Can we even identify the number of components in the mixture?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. The paper is well-written and easy to follow.\n2. Studying a mixture of DAG is underexplored but will help bring the application of causality closer to the real world. This paper furthers the line of work in this direction and is thus important. \n3. This paper characterizes the necessary and sufficient conditions to identify the \"true\" edges, i.e., the edges that are actually present in at least one of the components of the mixture from the emergent edges. Also, they don't impose restricting assumptions on component DAGs like poset compatibility from previous work, thereby generalizing the results to a richer mixture family. \n4. Also, to the best of my knowledge, this is the first work in causal discovery for a mixture of DAGs that allows for the use of interventional data, thereby improving identifiability.", "weaknesses": "1. It is understandable that this paper doesn't show the sample complexity of identifying the true edge set, but maybe the empirical section could be more diverse with a larger number of nodes and components to get a sense of the proposed algorithm's statistical efficiency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments and assessment of our paper. We address the raised questions as follows.\n \n**Experiments**: In the additional experiments in the global response, we demonstrate that our algorithm is scalable to higher dimensions – up to $n=30$ nodes and $K=10$ component DAGs – without a significant change in the performance. Please refer to the global response for details.\n \n \n**Partitioning true edges into individual component DAGs**: Thank you for the suggestion that is an important future direction. However, it will most certainly require additional assumptions. For instance, in our current formulation, consider two sets of mixture DAGs:\n-    *Setup 1*: $K=2$ DAGs with edge sets $E_1 = \\\\{1\\rightarrow 2, 1\\rightarrow 3\\\\}$ and $E_2 = \\emptyset$\n-    *Setup 2*: $K=2$ DAGs with edge sets $E_1 = \\\\{1\\rightarrow 2\\\\}$ and $E_2 = \\\\{1\\rightarrow 3\\\\}$\nIn this example, no interventions can distinguish the two setups. Similarly, in general, we cannot determine the number of components in the mixture.\n \nThat being said, under certain assumptions we expect the partitioning to become possible. For instance, in a similar problem, Kumar and Sinha (2021) study disentangling mixtures of unknown interventional datasets under specific conditions on the intervention sets and given the distribution of the pre-intervention DAG. Establishing the necessary and sufficient conditions for achieving similar disentangling objectives tasks in our mixture model is an open problem for future work.\n \n- Kumar, Abhinav, and Gaurav Sinha. \"Disentangling mixtures of unknown causal interventions.\" Uncertainty in Artificial Intelligence. PMLR, 2021.", "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": "f0rrdOQjSb", "reviewer": "Reviewer_2inT", "summary": "The paper studies the setting where data is generated from a mixture of DAGs and one wishes to recover the \"true edges\" (edges that exist in at least one of the underlying DAGs). Similar to the usual causal discovery setting, observational data alone is insufficient and interventions are required. The paper characterize the set of interventions needed to learn these true edges and provide an algorithm for doing so. Some small scale experiments and source code were given.", "questions": "General questions:\n- [1] also studied the universal lower bound problem that you mentioned on Line 92, and [2] eventually provided an exact characterization for the number of interventions required to recover the DAG from the observational essential graph. You may want to consider adding these references in your revision.\n- Can you motivate why it is sufficient/useful enough to recover \"true edges\" (objective 1 on Line 195)? Your approach cannot identify which DAG each of the recovered edges belong to within the mixture of DAGs, right?\n- Is the number $K$ of mixture models given to the algorithm as input? The phrase \"a priori knowledge of the number of mixture components\" on Line 251-252 seem to suggest that $K$ is typically not given. Also, Algorithm 1 is independent of $K$. However, $K$ features prominently in the characterization (e.g. Theorem 2), so how does one perform the correct set of interventions without $K$ as input?\n- On Line 282, you mention \"intervening on any set $I$ that contains $B(i)$ breaks all the cyclic relationships in $C(i)$\". Why is this so? I thought some \"edge cutting\" (i.e. exactly one endpoint of the edge is in intervention set) is needed in order to distinguish edge directions? For example, intervening on the entire set of vertices will trivially include $B(i)$ but this does not provide any useful information, right?\n- In Line 290, do you want to perhaps write $(A \\setminus (S_1(i) \\cup \\ldots \\cup S_{n-1}(i)))$ since the algorithm is \"removing the layer $S_u(i)$ from $A$ after each iteration\", or at least reference Line 26 in Algorithm 1?\n- In equations (23) and (24) of Appendix C, shouldn't are you missing $\\cup \\{i\\}$? I don't think you defined descendants and ancestors to include $i$ itself, or maybe I'm mistaken?\n- On Line 620, you wrote $S_1$. I don't see this defined anywhere (please correct me if I missed it). I don't think this is a typo of $S_1(i)$ here since $j \\in S_1(i)$ and $j \\not\\in pa_m(j)$. This undefined notation also appears in the remaining of this proof and is inhibiting my ability to verify Theorem 3.\n- The mixture in Figure 2 assumes that $P_{G_1}(1) = P_{G_2}(1)$ since the $y$ node does not point to the $I$-mixture DAG (definition 5 and equation (2)), right? This assumption was not mentioned in Appendix D.\n\nExperiment questions:\n- The graph sizes in the experimental evaluation were extremely small. Is there a reason for this? In Appendix E (line 727), you say \"only a marginal decrease in performance\" when $K = \\{2,3,4\\}$ and $n \\in \\{5,\\ldots,10\\}$. I'm not sure if that is enough scale to draw such a conclusion...\n- By setting p = 2/n in the Erdos-Renyi G(n,p) graph generation, the graphs will likely be disconnected (random graph theory tells us we need about p ~= log n / n for the graph to be connected). Will this be a problem for your experiments if you scale to larger graphs?\n- Consider mentioning the edge weights of your linear Gaussian model in the main paper instead of the appendix. Line 348 claims that s = 1000 samples are sufficient for almost perfect precision but finite sample guarantees for \"good recovery of the graph\" scale non-trivially with the correlation strength, e.g. see the finite sample analysis for linear Gaussians in [3].\n- What is the mixture skeleton learning algorithm?\n- In Appendix E, you mentioned that \"the same edge weight is assigned to all realizations of a true edge across all component DAGs\". Why is this reasonable? I thought the whole point of mixture models is that $p_\\ell \\neq p_{\\ell'}$ in general? See Line 117.\n\nPossible typos:\n- Extra bold of \"ixture\" on Line 255?\n- Equation (57): Do you mean $C(5) = \\emptyset$?\n\nReferences:\n\n[1] Porwal, Vibhor, Piyush Srivastava, and Gaurav Sinha. \"Almost Optimal Universal Lower Bound for Learning Causal DAGs with Atomic Interventions.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022.\n\n[2] Choo, Davin, Kirankumar Shiragur, and Arnab Bhattacharyya. \"Verification and search algorithms for causal DAGs.\" Advances in Neural Information Processing Systems 35 (2022): 12787-12799.\n\n[3] Kalisch, Markus, and Peter Bühlman. \"Estimating high-dimensional directed acyclic graphs with the PC-algorithm.\" Journal of Machine Learning Research 8.3 (2007).", "limitations": "Nil", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The concept of mixture of DAGs provide an alternative framework to capture cyclic causal system and, to my understanding, is under-explored. This paper aims to fill some of these gaps.", "weaknesses": "The paper strives to recover \"true edges\" (objective 1 on Line 195) but I don't think they can map these edges to the appropriate underlying DAG within within the mixture of DAGs. It is unclear why it is interesting to be able to know these edges without the context of the DAG they belong to. To me, this severely weakens the motivation/usefulness of this work.\n\nThe experimental evaluation felt rather weak.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the exceptionally detailed and thoughtful review. We address the raised questions as follows.\n \n## General questions\n \n**Motivation for recovering the true edges**: The observation is correct that, without further assumptions, we cannot identify which true edges belong to which DAGs. To see why this is impossible in general, consider two mixtures:\n-    Mixture 1: $K=2$ DAGs with edges $E_1=\\\\{1\\rightarrow 2, 1\\rightarrow 3\\\\}$ and $E_2=\\emptyset$\n-    Mixture 2: $K=2$ DAGs with edges $E_1=\\\\{1\\rightarrow 2\\\\}$ and $E_2=\\\\{1\\rightarrow 3\\\\}$\nIn this example, no intervention can distinguish the two mixtures.\n \nThen, if we cannot disentangle the individual DAGs, we argue that finding the true edges is the best we can do, and it is still useful for causal inference tasks. The motivation is that the mixture model is generally composed of DAGs with similar contexts. For instance, different subtypes of ovarian cancer create a mixture model (Lines 27-28). Identifying a causal connection (a true edge) in this setting is crucial even if it appears in only some subpopulations (i.e., some of the component DAGs).\n\n**Number of mixture components $K$ is unknown**: The algorithm does not take $K$ as an input. Our algorithm is designed for general DAGs (without structural restrictions). Hence, the guarantees associated with the algorithm are given for general DAGs in Theorems 3 and 4. The mentioned Theorem 2 is specific to trees and aims to provide a theoretical understanding separate from the algorithmic approach.\n \n**Breaking set in Line 282**:\n-    First, we elaborate on the procedure. When considering an intervention on $B(i)$, we already have the ancestor set $\\hat{\\rm an}(i)$. Hence, for $j\\in\\hat{\\rm an}(i)$, we investigate the *single* direction $j\\rightarrow i$. Since $i\\notin B(i)$, we avoid making a useless intervention, e.g., intervening on both $i$ and $j$ at the same time.\n-    Next, recall the definition of $C(i)$: set of cycles in which all nodes of the cycle belong to $\\hat{\\rm an}(i)$. By definition, $B(i)$ contains at least one node from each cycle in $C(i)$. Therefore, by intervening on $B(i)$, we cut off a link in each cycle.\n \n**Additional references**: Thanks! Indeed, both [1] and [2] are related to the discussion in our literature review. We will add them to the revised paper.\n \n**Example in Figure 2**: Your observation is correct. For simplicity, we have used an example in which the root node $1$ has the same marginal distribution on two components. We will mention it in the caption of Figure 2.\n \n**Typos and minor fixes**:\n \n-   **Proof of Theorem 3**: We are truly sorry for the typos here. In Line 620, it should be $S_1(i)$ *and* ${\\rm pa}_{\\rm m}(i)$. Since Theorem 3 considers a single node $i$, all $S_t$ sets are supposed to be $S_t(i)$. The entire list of fixes:\n    -   $S_1\\to S_1(i)$ in Lines 620, 628, 629, and eq. (26)\n    -   $S_u\\to S_u(i)$ in Lines 633, 635, 643\n    -   $S_k\\to S_k(i)$ in Line 634.\n \n-   **Line 290**: Thanks for the suggestion. We update Lines 289-293 as follows:\n\n    *Next, we update $\\mathcal{A}\\gets\\mathcal{A}\\setminus S_1(i)$ by removing layer $S_1(i)$ to conclude the first step. Then, we iteratively construct the layers $S_u(i)=\\\\{j \\in \\mathcal{A}:\\hat{\\rm de}(j)\\cap\\mathcal{A}=\\emptyset\\\\}$ and update $\\mathcal{A}\\gets\\mathcal{A}\\setminus S_u(i)$ as in Line 26 of the algorithm. We continue until the set $\\cal{A}$ is exhausted, and denote these topological layers by $\\\\{S_1(i),\\dots,S_t(i)\\\\}$.*\n-   **Eq.(23) and (24)**: You are right that descendant and ancestor definitions *do not* include $i$. Hence, Eq.(23) and (24) should have $\\cup i$, as correctly given in line 14 of the algorithm. Correcting another typo in Eq.(24), we have\n    ${\\rm de}_i(j)=\\hat{\\rm de}(j)\\cap\\\\{\\hat{\\rm an}(i)\\cup i\\\\}={\\rm de}\\_{m}(j) \\  , \\ \\forall j \\in{\\rm an}\\_{\\rm m}(i)\\ .$\n-   **Eq.(57)**: You are right that we mean $\\mathcal{C}(5) = \\emptyset$, we will fix it.\n-   **Line 255**: It should be **M**ixture.\n\n## Experiment questions:\n \n**Increasing graph size and number of components**: Please refer to the global response in which we report experiments up to $n=30$ nodes and $K=10$ components.\n \n**Connectedness of the graph**: Our theory and algorithm do not require the DAGs to be connected. So it wouldn't be a problem for experiments. As the reviewer points out, large random graphs with small densities would consist of a giant connected component and many small components. In this case, we’d expect the \"giant connected component\" to dominate the complexity of our algorithm (e.g., the number of total interventions).\n \n**Edge weights**: We will move the “experimental procedure” paragraph in Appendix E to the main paper and will add the statement “under this parametrization” to the discussion on the number of samples in Line 348.\n \n**Parametrization of true edges**: You are right that in general, conditional distributions $p_l(X_i\\mid X_{{{\\rm pa}\\_{l}}(i)})$ and $p_{l'}(X_i\\mid X_{{{\\rm pa}\\_{l'}}(i)})$ can be different even if ${\\rm pa}_l(i)={\\rm pa}\\_{l'}(i)$. For simplicity of the exposition of experiments, we considered the special case of mixtures in which a change in the conditional distribution is only caused by changes in the parents so that $\\Delta$ becomes the set of nodes with varying parents across the component DAGs. We perform additional experiments for the most general case where true edges can have different weights across the components. Please see the global response for the results and details.\n\n**Mixture skeleton learning**: It is done via exhaustive CI tests. For every pair $(i,j)$, we test the conditional independence of $X_i$ and $X_j$ given every $S\\subseteq[n]\\setminus\\\\{i,j\\\\}$ (as in Algorithm 1 of [11]). We will add this detail to the experiments in the revised paper. Note that, as mentioned in Line 262, we omit this step due to its $\\mathcal{O}(n^2 2^n)$ complexity and only perform it for the comparison in Figure 1b.", "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": "RHTdal00xa", "reviewer": "Reviewer_Tiwj", "summary": "This paper deals with using interventions to learn the causal links in a mixture-of-DAGs model.\nThey find the minimum number of intentions that are required to learn \"true edges\" where a true edge from a node X to a node Y indicates that at least in one mixture component, X is a parent of Y. They also present an algorithm that learns true edges via interventions. They show that in terms of the number of interventions, the proposed algorithm is close to optimal.", "questions": "Is there any existing and open-source real-world dataset where the data generation mechanism is a mixture of DAGs? If yes, is there a reason that such a dataset is not utilized in this paper?", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Up to my knowledge this is the first time that the problem of using interventions to learn the mixture of causal DAGs is studied. \n2. As far as I could follow, the presented theorems on the number of sufficient and necessary interventions as well as the proposed algorithm are correct.", "weaknesses": "1. To present their theorems and algorithm, they require several definitions and this can be confusing in the first read. If they could provide a simple running example (i.e. a mixture of DAGs) by which they could illustrate/clarify all definitions, the paper would be easier to follow --in my opinion.\n\n2. The provided experimental results are on synthetic data only. This, I think is the main weakness of this paper. If (as claimed in the abstract and intro) many causal systems are mixtures of DAGs, it would be helpful if the authors could present and analyze at least one such real-world system in the experiments section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for thoughtful evaluations and feedback. We hope the following explanations can clarify the reviewer’s concerns.\n\n**Running example:** Thank you for the suggestion. Figure 2 in Appendix D illustrates the mixture of DAGs and construction of $\\cal{I}$-DAG. Due to space limitations, we have had to defer it to the appendix. We will move it to the main paper and add the following details to its caption:\n- True edges $E_{\\rm t} = \\\\{1 \\rightarrow 2, 2 \\rightarrow 3, 3 \\rightarrow 2, 3 \\rightarrow 4, 1 \\rightarrow 4\\\\}$\n- Emergent pairs $E_{\\rm e} = \\\\{ (1,3), (2,4) \\\\}$\n- Inseparable pairs $E_{\\rm i} = \\\\{ (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) \\\\}$\n- $\\Delta$-through path examples: $1 \\rightarrow 2 \\rightarrow 3$ in $\\mathcal{G}_1$; $3 \\rightarrow 4$ in $\\mathcal{G}_2$\n \n \n**Real-world dataset:** We emphasize that the focus of our work is establishing the needed *theory* for using interventions on a mixture of DAGs. While we acknowledge the importance of real-world applications, establishing the novel theory *and* demonstrating the real-data usefulness can be beyond the scope of one paper. In the following, we elaborate on the challenges of a direct real-world application and explain why our theoretical contribution is an important step toward that direction.\n\n\n- **Lack of a proper real-world dataset:**   The existing benchmark causal discovery datasets, such as protein signaling network in Sachs et al. (2005) or ovarian cancer dataset of Tothill et al. (2008), are known to be *not* perfect single DAGs. For instance, the “true DAG” for protein signaling network is challenged under new evidence (Ness et al., 2017), and there is no strong consensus over the ground truth DAG. Furthermore, the existing interventional single DAG learning algorithms do not perform well in terms of standard metrics, e.g., structural Hamming distance (e.g., Squires et al. (2020), Wang et al. (2018), Varici et al. (2021)) despite the strong theoretical guarantees. These observations suggest that a single DAG may not be the best approach for modeling such real-world datasets. To our knowledge, there is no commonly accepted and well-defined dataset in which the data generation mechanism is a mixture of DAGs.\n\n- **Access to interventions:**  We note that the existing datasets come with a predefined set of interventions, e.g., single-node or two-node genomics interventions, and we cannot \"simulate\" any desired intervention. This makes it difficult to evaluate any interventional learning algorithm that fully learns the graph. For instance, as discussed in Lines 84—87, the majority of the existing results in the single-DAG setting consider “unconstrained” intervention sizes. Our results in Theorem 1 and 2 contribute to our understanding of the *required* intervention sizes, which can shed light on the extent of identifiability given a real-world dataset (without a simulator).\n\nIn light of these, we leave the investigation of real-world datasets/applications (and related partial identifiability results) to future work. \n \n**References**\n \nK. Sachs, O. Perez, D. Pe'er, D. A. Lauffenburger, and G. P. Nolan, “Causal protein-signaling networks derived from multiparameter single-cell data,” Science, vol. 308, no. 5721, pp. 523– 529, 2005.\n \nR. W. Tothill et al. “Novel molecular subtypes of serous and endometrioid ovarian cancer linked to clinical outcome,” Clinical Cancer Research, vol. 14, no. 16, pp. 5198–5208, 2008.\n \nR. O. Ness, K. Sachs, P. Mallick, and O. Vitek, “A Bayesian active learning experimental design for inferring signaling networks,” in Proc. Research in Computational Molecular Biology, Hong Kong, May 2017, pp. 134–156.\n \nC. Squires, Y. Wang, and C. Uhler, “Permutation-based causal structure learning with unknown intervention targets,” in Proc. Conference on Uncertainty in Artificial Intelligence, August 2020.\n \nY. Wang, C. Squires, A. Belyaeva, and C. Uhler, “Direct estimation of differences in causal graphs,” in Proc. Advances in Neural Information Processing Systems, Montreal, Canada, December 2018.\n \nB. Varici, K. Shanmugam, P. Sattigeri, and A. Tajer. “Scalable intervention target estimation in linear models,” in Proc. Advances in Neural Information Processing Systems, December 2021.", "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:
We thank all reviewers for their thorough evaluation and thoughtful questions. To demonstrate the scalability of our algorithm, we performed additional experiments under the same settings described in the paper.
 
**Increasing the number of nodes**: The submitted paper presents experiment results for up to $n=10$ nodes. In Figure 1a of the pdf attached to the global response, we report the average precision and recall rates (of 50 runs) for varying the number of nodes up to $n=30$ under a mixture of $K=3$ DAGs.
 
**Increasing the number of components in the mixture**: The submitted paper presents experiment results for up to $K=4$ component DAGs. In Figure 1b of the pdf attached to the global response, we report the average precision and recall rates (of 50 runs) up to $K=10$ component DAGs with $n=10$ nodes.
 
Both results show that there is only a marginal decrease in the performance of recovering the true edges which shows that our algorithm is scalable.

**Parameterization of true edges**: 
We also performed additional experiments to demonstrate that the algorithm can handle true edges with different strengths across component DAGs. Specifically, in general, conditional distributions $p_l(X_i\mid X_{{{\rm pa}\_{l}}(i)})$ and $p_{l'}(X_i\mid X_{{{\rm pa}\_{l'}}(i)})$ can be different even if the parent sets are the same, ${\rm pa}_l(i) = {\rm pa}\_{l'}(i)$ (as mentioned in Line 117). For the experiments for this setting, we consider $n\in\\{10,15,20\\}$ nodes and $K=3$ DAGs. The weight of each true edge has two options:
-    With probability 0.5, it is fixed across the component DAGs it belongs to
-    With probability 0.5, it is different for every component DAG it belongs to.

Figure 2 in the attached pdf shows that the performance of the algorithm is virtually the same for this setting and the main setting we considered with fixed true edge weights.

Meta-review: The paper is well received across the board overall, with most reviewers enthusiastic about the acceptance of the paper. 

I-mixture faithfulness is swept under the rug a bit too quickly. Authors simply say they have to use this for learning from interventions. Please compare this proposed assumption with the more standard interventional faithfulness assumptions in the literature. Does one imply the other and vice verse? Please add a remark on this. 

I appreciate the matching lower bounds authors provide. 

Please also add the more explicit quantitative comparison and discussions related to single DAG learning results in the literature, as in your answer to Reviewer 5C9J. 

Based on Reviewer bGit's and Reviewer 2inT's questions, please emphasize that the proposed method cannot identify individual DAGs without further assumptions and include the examples you provided in the rebuttal in the main paper. The goal of the paper and what "true edges" mean should be very clear from the start, which I think is not as explicit as it could be at times.
Decision: Accept (poster)