Separability Analysis for Causal Discovery in Mixture of DAGs
Authors: Burak Varici
Dmitriy Katz
Dennis Wei
Prasanna Sattigeri
Ali Tajer
Venue: Accepted by TMLR ()

Abstract: Directed acyclic graphs (DAGs) are effective for compactly representing causal systems and specifying the causal relationships among the system's constituents. Specifying such causal relationships in some systems requires a mixture of multiple DAGs -- a single DAG is insufficient. Some examples include time-varying causal systems or aggregated subgroups of a population. Recovering the causal structure of the systems represented by single DAGs is investigated extensively, but it remains mainly open for the systems represented by a mixture of DAGs. A major difference between single- versus mixture-DAG recovery is the existence of node pairs that are separable in the individual DAGs but become inseparable in their mixture. This paper provides the theoretical foundations for analyzing such inseparable node pairs. Specifically, the notion of \emph{emergent edges} is introduced to represent such inseparable pairs that do not exist in the single DAGs but emerge in their mixtures. Necessary conditions for identifying the emergent edges are established. Operationally, these conditions serve as sufficient conditions for separating a pair of nodes in the mixture of DAGs. These results are further extended, and matching necessary and sufficient conditions for identifying the emergent edges in tree-structured DAGs are established. Finally, a novel graphical representation is formalized to specify these conditions, and an algorithm is provided for inferring the learnable causal relations.

Published in Transactions on Machine Learning Research (01/2024)
Separability Analysis for Causal Discovery in Mixture of DAGs
Burak Varieı
varich @ rpi. rpi.edu
Electrical, Computer, and Systems Engineering Rensselaer Polytechnic Institute
Dmitriy Katz-Rogozhnikon
dkatzrog @ us. ibm.com
IBM Research
Dennis Wei
dwei us. iwm.imm.com
IBM Research
Prasanna Sattigeri IBM Research Al
psattig @ us. uus.bbm.com
Ali Tajer
enjer@ecse.pii.ckt
Electrical, Computer, and Systems Engineering
Rensselaer Polytechnic Institute
Reviewed on Optpr//ww...prrr/oooorrreee//eer
Abstract
Directed acyclic graphs (DAGs) are effective for compactly representing causal systems and specify- ing the causal relationships among the system's constituents. Specifying such causal relationships in some systems requires mixture of multiple DAGs a single DAG insufficient. Some examples include time-varying causal systems aggregated subgroups of population. Recovering the causal structure of the systems represented by single DAGs is investigated extensively, but it remains mainly open for the systems represented by mixture of DAGs. A major difference between single- versus mixture-DAG recovery is the existence of node pairs that are separable in the individual DAGs but become inseparable in their mixture. This paper provides the theoretical foundations for analyzing such inseparable node pairs. Specifically, the notion emergent edges is introduced to represent such inseparable pairs that do exist the single DAGs but emerge in their mixtures. Necessary conditions for identifying the emergent edges established. Operationally, these conditions serve sufficient conditions for separating pair of nodes in the mixture of DAGs. These results further extended, and matching necessary and sufficient conditions for identifying the emergent edges in tree-structured DAGs are established. Finally, novel graphical representation is formalized to specify these conditions, and an algorithm provided for inferring the learnable causal relations.
Introduction
1.1 Motivation
Causal Bayesian networks can effectively represent causal relationships among random variables generated in network of interacting agents. Such a network can be specified by, for instance, a directed acyclic graph (DAG) and joint probability distribution that factorizes with respect to the DAG. Causal discovery the process of using observational data and inferring a DAG's causal structure, i.e., its edges' locations and orientations. One common approach to causal discovery involves performing statistical tests for determining conditional independence relationships the observation data. When the system can be represented DAG, the inferred independence relationships are subsequently converted

---

Published in Transactions on Machine Learning Research (01/2024)
into DAG (d-separation) separation statements to infer the structure (Spirtes et al., 2000: Colombo et al., 2012). These approaches are known as constraint-based methods. Other notable approaches include score-based methods (Chickering, 2002; Tsamardinos et al., 2006), hybrid methods (Nandy et al., 2018), and continouu-opiimizatoon--ssss methods (Zheng et al., 2018).
A widely used assumption in causal discovery is that the observed data independent and identically distributed (i.i.d.) according to one DAG. This is not valid in a wide range of settings and applications in which more complex mechanisms generate the observed data. Such complex data can be modeled more accurately by multiple distinct causal models the same set of variables. For instance, in fMRI data analysis, different brain regions interact differently under various activities of the subjects (Neumann et al., 2010). Another example is gene expression data from certain diseases, like ovarian cancer, which comprises multiple subtypes that are challenging to distinguish (Reid et al., 2017). In successful cene-editing technique CRISPR-Cas9 (Ran et al., 2013), Cas9 enzyme cuts the DNA at a specific location. However, depending on an array of factors, such as the delivery method of the gene-editing tool and the complexity of the genetic alteration needed, the gene-editing tool is not always successful, resulting in ambiguity while grouping gene expression samples based on the corresponding distribution. In psychological studies, often multiple time-series trajectories (e.g., perression-related symptoms over period of time) are collected from different patients (Bulteel et al., 2016). This data is fitted better with mudti-modal linear dynamic systems instead of a single model, and labels of the trajectories model membership of the samples are unknown to the researcher. For more examples of mixture models in dynamical systems, we refer to Chen & Poor (2022). Furthermore, in some settings, the causal models are cyclic. For instance, the processes that regulate hormones without reaching an equilibrium state (Pirahanchi et al., 2023). The statistical models of the data in such heterogeneous systems cannot be represented with a single DAG and require mixture of them.
1.2 Contribution
Despite the significance of causal discovery from complex models, it is far less investigated compared to causal discovery in single DAGS. The advances in the discovery of single DAGs are due to well-specified frameworks that facilitate formalizing various causal discovery objectives and are amenable to tractable analysis. However, the counterparts of such frameworks for more complex models are not well-established in the literature. This paper formalizes a framework that facilitates addressing causal discovery objectives in systems represented by a mixture of DAGs. The first important step towards this goal is establishing possibility results, that is, identifying and discerning the causal relationships that can possibly be learned from those that are impossible to learn. It can be readily verified that some natural choices generally investigated in single DAGs are impossible when working with mixture models. For instance. mixing the models renders learning the constituent DAGs' structures impossible. Similarly, recovering the union of the edges of individual DAGs is ill ill-posed without additional information or assumptions on the causal models. To address such learnable versus unlearnable dichotomy to develop the key ideas, we consider a mixture of two DAGs.
We formalize the separability framework in which the inferential decisions are centered around separability analysis, which refers to identifying the pair of random variables that cannot be made conditionally independent in the mixture distribution. Accordingly, we refer to the node pairs associated with inseparable random variables as inseparable pairs. We introduce proper edge notations to visualize such edges graphically. Given this framework, we investigate what can be learned about the underlying DAGs in a mixture model. We adopt a constraint-based approach and use conditional independence (CI) tests on the mixture distribution to identify inseparable node pairs. We note that faithfulness - conditional independencies in the data being due to the separations in the true DAG is a core assumption in constraint- based causal discovery (Spirtes et al., 2000; Pearl, 2009). Hence, we adopt a mixture faithfulness assumption in this paper, similar to the existing literature on causal discovery in a mixture of DAGs. Once the inseparable node pairs are identified, we construct mixture graph with these node pairs as its edges. The main challenge in interpreting the mixture graph is the existence of node pairs that are not adjacent (connected) in all individual DAGs but are not conditionally independent in the mixture distribution for any conditioning set. Due to their importance, we analyze this subset of inseparable pairs and refer to them as emergent edges. We observe that the set of nodes with varying conditional distributions across the individual DAGs, denoted by A, plays a critical role in forming inseparable pairs in the mixture. We start by investigating a mixture of two arbitrary DAGs and establish conditions under which any arbitrary pair of nodes in the mixture model is separable. Equivalently, for a node pair form an emergent edge, these
2

---

Published in Transactions on Machine Learning Research (01/2024)
conditions necessarily do not hold. Furthermore, we specialize these results tree-structured DAGs, for which we establish the necessary and sufficient conditions for node pairs to be separable. Our main contributions are as follows.
We introduce a mixture graph to represent the inseparable pairs of nodes in the mixture distribution. To interpret the edges of the mixture graph, we present a sufficient condition for two nodes be separable. This result sheds light the inadequacy of an existing graphical representation in the literature.
We strengthen the results for a mixture of tree-structured DAGs and establish necessary and sufficient conditions for two nodes to form an emergent edge in the mixture.
We introduce new edge notations for inseparable node pairs to represent the above conditions and partially orient the skeleton of the mixture graph. We discuss the inference of these oriented edges from unshielded triples and show that v-structures upon nodes in the A set can be recovered. Finally, we devise an algorithm built on our theoretical results to recover the learnable causal relationships.
1.3 Related Work
Causal discovery of a mixture of DAGs. There are three studies closely related to this paper. The shared objective of these papers is to develop a graphical model to represent as many CI relationships in the mixture distribution as possible. Spirtes (1995) proposes fused graph and shows that the mixture distribution is with respect to the fused graph. However, it does not provide separability theorems for pair of nodes. Strobl (2023) proposes mixture graph such that the mixture distribution is Markov with respect to the proposed graph. However, this study does not provide counterparts of our separability results either. It proposes an algorithm that is designed exclusively for time-series data. In the work most closely related to this paper, the study by Saeed et al. (2020) considers a mixture of DAGs and proposes a composite DAG that satisfies the Markov property. Subsequently, it represents the mixture distribution with a maximal ancestral graph (MAG) to use the existing structure learning algorithms directly. This approach is only valid under a strict assumption called poset compatibility that rules out any conflicting ancestral relationships across individual DAGs (e.g. cycles). Importantly, none of these studies provide conditions for when an emergent edge arises. In this paper, mainly focus on tree-structured component DAGs, but we do not restrict the topological order of the individual DAGs and do not consider time-series data.
Causal discovery from multiple clusters/contexts. Another approach to our problem is to divide it into two independent stages: clustering the samples and then performing structure learning on each cluster individually (Zhang & Glymour, 2020; Chen et al., 2021). Learning from multiple contexts is a well-studied topic the causality literature, especially in interventional (experimental) settings (Huang et al., 2020; Zhang et al., 2017: Mooij et al., 2020; Jaber al., 2020). In these studies, the context of an observed sample, i.e., which graph it belongs to, is assumed to be known in contrast to observing a mixture distribution. In another line of work, several algorithms perform causal discovery of cyclic causal models by assuming that the observed distribution is the equilibrium state of multiple involved causal models (Forré & Mooij, 2017; Bongers et al., 2021: Améndola et al., 2020; Ghassami et al., 2020). The study in Winn (2012) addresses the problem of representing context-specific independence via leveraging factor graphs with interventions. This is an interesting yet underexplored approach compared to the graphical modeling of interventions based on (Pearl, 2009). The study in Thiesson al. (1998) aims to learn the parameters of multiple Bayesian networks from combined data. Specifically, heuristic score-based algorithms are proposed for jointly learning the structure and parameters of multiple Bayesian networks. Finally, Meila & Jordan (2000) consider learning discrete mixture-of-trees distribution. However, the considered model is not causal.
Applications of tree-structured DAGs, Causal trees are shown to be computationally effective while still being useful to closely approximate more complex models (Acid & de Campos, 1994). Beyond their convenience for providing tractable analysis, they are widely studied in causal discovery literature and have real applications, e.g., in biological networks. Specifically, protein signaling pathways are commonly modeled by causal trees. For instance, bi-partite causal graphs are used to model gene networks, in which genes induce protein expressions, and the expressed proteins either inhibit or activate other genes (Kontou et al., 2016). NF-kB protein signaling pathway, which activates mammalian immune system cells to produce antibodies against inflammation, is also modeled by causal trees (Lodish, 2016).
'Specifically, tree-structured DAG is a DAG whose underlying undirected graph tree. This structure can be referred to as directed tree, polytree or singly connected network well.
3

---

Published in Transactions on Machine Learning Research (01/2024)
2 Separability Framework for DAG Mixtures
DAG Models. In this section, we provide DAG mixture model and introduce the notations needed for analyzing them. For clarity purposes, we initially focus on mixture of two DAGs and discuss the generalization to mixture of an arbitrary number of DAGs in Appendix B.
Consider two component DAGs 9 - EV) and G2 & (V, E2) defined over the same set nodes V A {I,... n). Eg denotes the set of directed edges in graph Gr. for E f1.2). We define pay(i), chr(i), an, de, and sp, (i) to denote parents, children, ancestors, descendants, and spouses (i.e., nodes that share common child) of node in graph Ge for & {1,2). respectively. We denote the maximum in-degree of node in either component DAG by d. We augment the set (i) by adding the node to it and denote the augmented set by pa (i) paa(i) U {i). Similarly, we also define the augmented sets ch² (i), def (i), and an (i).
We extend these notations to any desired subset of
nodes. Specifically, for any A C V we define
pac(A) & U Upar(t),
(1)
iEA
and define (A)( ane (A)) (A), and (A) similarly.
Probability Models. The random variable associated with node i V is denoted by X,, which can be continuous or discrete. Accordingly, we define the vector of variables X - (., Xx," For any subset of nodes A S X, we define X A (X; i E A). We denote the probability distributions of X under G1 and G2 by pı and p2, respectively. These distributions factorize with respect to their associated DAGs according to
pe(x) = II pe(a; Fpae(t)) 44 (1,2]
:E|n]
This factorization implies that pl and p2 can be distinct even when E, and E2 identical. Hence, the differences between the two causal models should be defined through the nodes with varying causal mechanisms, i.c., conditional distributions. We denote the set of nodes that have distinct conditional distributions across two models by A, i.e.,
A A fi V Pi(; (1) + p2(X; (pa,(1))
(3)
Observations Mixture Model. The observed data is generated by a mixture of distributions p1 and p2. The model generating the observation at given instance is unknown. To formalize this, we define I, E [1,2] as a latent random variable that accounts for the true model underlying the observed data, where L = l specifies that the true model is ps. We denote the probability mass function (pmf) of L by q. We assume that L and X are statistically independent. These render the following mixture distribution for the observed samples X.
(M)
Σ q(() Pr(x). [E(12)
(4)
Next, we introduce the notations and definitions for formalizing the separability framework, formulating the causal discovery objectives, and describing the analytical results. Connectivities between node pairs, represented by edges, in graphical representation of causal models are collectively denoted by the skeleton of the graph. An edge between two nodes essentially means that the random variables associated with the nodes cannot be made conditionally independent. Such nodes are cquivalently (under faithfulness) referred as inseparable nodes. The exact meaning and orientation of the edges can change across different representations, e.g., directed edges in DAGs and bidirected edges in MAGs, but the inseparability requirement remains the same.
The existing literature on studying mixture of DAGs focuses on establishing a graphical representation that can (partially) represent conditional independence relations in the mixture distribution PM (Spirtes, 1995: Saeed al., 2020; Strobl, 2023). While effective for inferring the separability statements, the existing approaches do not represent some of the important aspects of the mixture models such as interpreting the cycles across the individual DAGs. We specify four directed and undirected graphical models, each serving distinct purpose in the analysis. In these graphs, we use the following edge notations:
4

---

Published in Transactions on Machine Learning Research (01/2024)
i }): the undirected edge from node i to node j.
j: the directed edge from node to node j.
j: the directed edge from node to node j in Eg.
i j: denotes i an)()).
We call the tuple of nodes (i, k. an unshielded triple in ge if (i (G-Ke k) and (j k) are edges of Ge but i and are not adjacent. If we further have - l & j. node k is called a unshielded collider in ge and (i - é j) is called a v-structure. We introduce an auxiliary node denoted by y. representing the latent variable L of the mixture model.
Definition 1 (Union Graph) The union graph, denoted by Gu & Eu). is an undirected graph constructed by setting Eu as the union of all edges in 91 and G2 after removing their orientations, i.e.
Ev A f) iijee, E E : 4
(5)
By recalling the definition of A in (3), next we define fused graphs.
Definition 2 (Fused Graph (Spirtes, 1995)) The fused graph GF - (Vr, Ep) is a directed graph constructed by setting VF - V [y), superposing the edge sets E₁ and Ez, and adding from y to the nodes in A, i.e.
Ep - (litj;i, V, 32 E (1,2) 4 1 -niuuuy-iii +i:ie
(6)
A fused graph can contain cycles but does not necessarily encode the complete set of conditional independencies in mixture distribution. Next, we specify a composite DAG?, defined by Saeed et al. (2020). The composite DAG involves concatenating 91 and G2 with a single-node graph G, _ ((v), 0) between them. Figure shows an example of constructing a composite DAG from component DAGs. The composite DAG is formalized next.
Definition 3 (Composite DAG (Saeed et al., 2020, Definition 3.1)) Given graphs G1, G2 and Gy 2 (1y). the composite DAG Go constructed by series composition of 91, gy. and 92- The composite DAG Ge inherits the directed edges of 91 and G2 and additionally includes directed edges from node y to nodes A in G1 and Gz.
The composite DAG consists of 2n + 1 nodes. We refer to the node corresponding to node i in Ge by ig. Accordingly, for any A C V we define A A {ie : A, E (1,2)}.
Definition 4 (Composite DAG d-separation) For any disjoint sets A, B, d-separated in the mixture model when given C, Å and B are d-separated in Ge We denote such d-separation by
V, we say that given C, A and B are
A 11 M B C.
Definition 5 (Mixture Global Markov Property) We say that mixture distribution PM satisfies the global Markov property with respect to Go if for any disjoint sets A, B, C C V such that A 11 B C, we have XA and X B are conditionally independent given Xc. This is denoted by X LL XB Xc-
Definition 6 (Mixture Faithfulness) The converse of the Markov property between Gc and pM is called mixture faithfulness, that is pMa is faithful to Gc if XA 11 XB Xc in PM implies A 11 B C.
Mixture faithfulness facilitates forming inferences on the graph structure from CI tests on distribution, and it is adopted by constraint- causal discovery literature. In this paper, we work under the mixture faithfulness assumption. While the composite DAG is not the representation we are characterizing in this paper, it captures important conditional independence relations among X; and X,, which facilitate our separability analysis. Next, we define mixture graphs, distinct from the composite DAGs defined above. The purpose of the mixture graph to represent the inseparable node pairs compactly over nodes V. In Section 4 we will analyze the properties of mixture graphs
Definition 7 (Mixture Graph) The mixture graph, denoted by GM & EV,EM), graph over V with undirected edges between the pair of nodes that always dependent in the mixture distribution PM, i.e.,
EM A ((i - j) : i,j.v RAC (1,3): X, X, Xx).
(7)
Referred as mixture DAG (Saced et al., 2020).
5

---

Published in Transactions on Machine Learning Research (01/2024)
E
E2
E1 n E2
EM
1
1
12
2
2
2
2
y
21
22
2
3 3
3
3
31
32
3
4
41
42
4
(a) 91
(b) O2
(c) Gu
(d) Gp
(c) Gc
(1) Рл
Figure I: (a) and (b) are the component DAGs; (c) is the union graph; (d) is the fused graph; (e) the composite DAG; and (f) is the mixture graph. Note that mixture graph GM has emergent edges Eg {(1 3), (2 4)}. This example
assumes that if parents of node invariant, then its conditional distribution is also invariant, and set A (2,3).
Clearly, if the pair (i,j) is connected in at least one of the graphs 91 and G2, then EM will contain the edge (i J)- Finally, we specify the set of edges in the mixture graph Gha that are separable in each individual distribution pı and p2 but become inseparable in the mixture distribution PM-
Definition 8 (Emergent Edge) The edge (i j) in the mixture graph GM is called an emergent edge if the pair of nodes and j are not adjacent in G1 and G2 but become inseparable in PM. The set of emergent edges is given by
Eg 2 {(i -) L.EV. (t- Eu A VA 1 XA}
Based on the definitions of Eu and Eg we clearly have EM Eu U Eg. Finally, we define a set causal paths that pass through one or more nodes in A. These causal paths are instrumental in specifying the separability conditions.
Definition 9 (A-through Path) We say that causal path in Ge between i and j is a A-through path, denoted by A j. if passes through at least one node in A, i.e. there exists E A such that & u or j.
3 Causal Discovery Objective
We aim address the following questions. What causal relationships can be learned about mixture of DAGs? What is graphical representation that can effectively specify these relationships?
These questions are well-investigated when analyzing individual DAGs. In the individual DAG Gr, each edge denotes an inseparable pair in pe. The components of G. that are learnable from observational data are characterized by Markov equivalence class (Verma & Pearl, 1992) and represented by a completed partially DAG (CPDAG). Such notions and decisions do not have well-established counterparts when the observations are generated by a mixture distribution pM arising from a mixture of DAGs.
Identifying the inseparable node pairs is the comnertoone of constraint-based causal discovery. Therefore, the leap from the causal discovery of individual DAGs to causal discovery from mixture of them critically hinges on determining the separability of nodes in the mixture model. We use the undirected mixture graph GM. which represents the inseparable pairs, to identify such pairs. This will be the critical initial step for the graphical representation of a mixture of DAGs. We note that the existence of emergent edges, i.c., the pair nodes that are inseparable in mixture distribution but are separable in component distributions, is the main challenge that makes the causal discovery of mixture of DAGs more complex than that of single DAG. Therefore, objectives in the paper centered around separability analysis, and they include:
Objective,: establishing the conditions that make pair of nodes an emergent edge; Objectivez: graphically representing these conditions by orienting the edges of the mixture graph;
Objectivez: and partially recovering these orientations.

---

Published in Transactions on Machine Learning Research (01/2024)
4 Separability Analysis in Mixture Graphs
In this section, we first study Objective; and investigate the conditions under which a pair of nodes in mixture model are inseparable. We start by considering an arbitrary pair of DAGS 91 and G2 without any constraints. We establish sufficient conditions under which any arbitrary pair of nodes in the mixture of Gi and G2 is separable. In the next step, we focus on tree-structured DAGs for which we tighten our sufficient conditions results and also show that these conditions are the necessary conditions, establishing the tightness of the results for tree-structured DAGs. For Objectivez, i.., orienting the mixture graph, we introduce new edge notations and graphically represent the established necessary and sufficient conditions. For Objectivez, we analyze which of these edges can be inferred by performing conditional independence tests. For each result, we discuss the implications of our results and representations with respect the existing representations of DAGs' mixtures. Finally, we devise algorithm for learning the mixture graph based our theoretical results. Proofs of the results are deferred to Appendix A.
4.1 Separability in General Graphs
Our separability analysis requires establishing connection between the mixture distribution and the structure of the component DAGs. Composite DAG representation provides us with this connection through the following result.
Theorem 1 (Markov property, et al., 2020, Theorem 3.2)) Let A, B, be disjoint. If A and are d- separated given C in composite DAG, then XA and Xg are conditionally independent given X in mixture distribution.
We note that Theorem 1 in conjunction with the mixture faithfulness assumption implies that all conditional indepen- dencies that can be tested from PM can be inferred by the separation statements in Go. Using Theorem I and mixture faithfulness, we can immediately conclude that the definition of emergent edges in (8) is equivalent to
Ep [(i ((i-)) :ijeeee (i- & Ev V
\ {i.j}: i M j ||
Hence, the separability of two nodes in mixture distribution is equivalent to the separability of the nodes in composite DAG Gg. Hence, an important observation is that the separability of two nodes depends on whether they have distinct conditional probability models in the component DAGs, i.c., their membership in defined in (3). This is because the paths that stretch over 9 and 92 9G necessarily pass through nodes in A. The following theorem investigates all possible configurations and presents sufficient conditions for two nodes to be separable mixture of arbitrary DAGs.
Theorem 2 (Separability- - SSufficient Conditions) Consider nodes i,j E such that i and j are not adjacent in either component DAG, ie.. (i - j) & Eu.
Case 1) E A,j A: and j are always inseparable.
Case 2) i & A, & A: and j are separable if the component DAGs do not have A-through paths between and j in opposite directions. That is, if one DAG contains a A-through path from to j. then the other one does not have a A-through path from j to i.
Case 3) i A.j E A: and j are separable neither of the component DAGs contains a A-through path from to j-
The inseparability of the nodes i,j E A is due to the path i E y/ - j in composite DAG. The second case of Theorem 2 implies that if nodes $ A.j & A are inseparable, i.c., they form an emergent edge, then for some distinct e, E (1,2), we have i A4 j and j Ag j. The third case implies that if i & A and E A are inseparable, then we have 144 j for some E E 21, We have | 2 for all three cases. Hence, when | = 1, the mixture of DAGs does not create any cycle, and we have EF 0. The next observation of Theorem 2 is on the different formations of cycles in mixture of DAGs. To highlight the shortcomings of the fused graph GF in representing mixture of DAGs, provide the following remark and example.
Remark Note that 2 j and j 3. imply a cyclic relationship between i and j in fused graph Gv- However, the reverse direction not always true, i.e., i and j can be part of a cycle in Ge without being ancestors of each other in the component DAGs.
7

---

Published in Transactions on Machine Learning Research (01/2024)
E
E2
E1
0
E2
EM
2
3
4
5
1
2
3
4
5
5
2
1
3
y
4
3
(a) 91 and G2
(b) Gr
(c) Gm
Figure 2: An example of the cases discussed in Remark 1. In this example, we have a cycle passing through all nodes. However, 2 and are separable since there is no A-through path from 2 to 4.
Example. Figure illustrates the shortcomings of the fused graph through an example. Fused graph 9F allows to visualize cycles in single directed graph over V U {y). However, two nodes that are part of cycle in this representation do not necessarily form an emergent edge. For instance, despite the cycle (1 2 3 - 4 + 5 - 1) in Gp. neither of the pairs (2 4) or (3 5) forms an emergent edge. Furthermore, Gp implies that one of the paths + 3 + 4 (if 3 is not conditioned on) and 2 + 3 4 + (if 3 is conditioned on) is always active. However, we have M 1. In fact, 2 and 4 are unconditionally independent, showing that GF is not a great representation. Therefore, for modeling mixture of DAGs, it is important distinguish between the directed paths in a component DAG and those formed by superposing the two component DAGS.
So far, we have discussed mixture of DAGs without any structural constraints on the components of the mixture. Next, we focus on the mixtures of tree-structured DAGs and further improve the separability results.
4.2 Properties of Tree Mixtures
Imposing tree structures DAGs 91 and G2 facilitates tighter analysis of the separability of two nodes (or, equivalently, the conditions in which emergent edges are formed). The following theorem establishes sufficient conditions for the separability of node pair in mixture of tree DAGs. These sufficient conditions are less stringent than those presented for general DAGs in Theorem 2. Specifically, instead of ruling out all A-through paths from i to j. we rule out only subset of them in which the child of i on the path is in A. Furthermore, we show that the refined conditions are necessary conditions too.
Theorem 3 (Separability Tree Structures Necessary and Sufficient Conditions) Suppose that G1 and G2 are tree-structured DAGs. Consider nodes i.j E V such that and j are not adjacent in component DAGs, i.e., (i-j) j) & Ev.
Case 1) e A and j e A: and j are always inseparable.
Case 2) i $ A and j & A: i and j are separable if and only if component DAGs do not have A-through paths between i and in opposite directions such that the children of and j on the paths are in A.
Case 3) i & A and j E A: and j are separable if and only if neither of the component DAGs contains A A-through
path from to such that the child of on the path is in A.
The first case is identical to the first case of Theorem 2. However, the sufficient conditions for i and j being separable in the second and third cases are tighter than their counterparts in Theorem Specifically, the existence of A A-through paths refined the existence of A 3-through paths with the additional condition that the child of the ancestor node of the path is in A. Furthermore, this tightened sufficient condition is also shown be necessary.
Theorem 3 also implies the necessary and sufficient conditions for (i (j) being emergent edge since if (i (i-j) & Eu and i and j are inseparable, then (i - .]) is an emergent edge. Formally, Case 2 implies that, for $ A, $ A, we have
36, E (1,2), Eu, A, u # u : u Ls and 1 S. i.
ji E EE
(10)
Next, Case implics that for i & A E A, we have
(i (i-)) j) E Eg + 32 [1, Eu E AAi
(11)
8

---

Published in Transactions on Machine Learning Research (01/2024)
Hence, Theorem 3 provides complete explanation for the emergent edges in mixture graph GM1 Notably, the approach of Saeed et al. (2020) is not valid for mixture of tree-structured DAGs in general. Specifically, motivated by the latent representation of the mixing variable via node y, (Saced et al., 2020) constructs MAGs Me from the sub-DAG induced by composite DAG Gc over the nodes Ge U {y} and takes a union of MM's. It proceeds to learn the union MAG by performing fast causal inference (FCT) (Spirtes et al., 2000). However, to obtain a valid union MAG, M1 and M2 should have a shared partial order on V. This assumption (called poset compatibility) is violated by the condition in (10) due having a cycle in the mixture and by (11) due to having causal path between two nodes in A.
Searching for separating set. After establishing the conditions for two nodes to be separable, our next result shows that the size of the smallest separating set is bounded.
Lemma 1 (Size of the separating set for mixture of trees) Suppose that I1 and G2 are tree-structured DAGs and j are separable in their mixture. Then, there exists a separating sei S with size at most |S| S 3d where denotes the maximum in-degree of a node in any component DAG.
We use Lemma to establish the computational complexity of our approach in Section 4.3 and compare it to that of causal discovery in single DAGs.
Interpreting the results from an interventional learning perspective. By its definition, A can be viewed as the set of soft intervention targets for which p1 and p2 denote the observational and interventional distributions, respectively. As characterized in (Hauser Bühlmann, 2012; Yang et al., 2018; Jaber al., 2020) and further scrutinized in (Varicı et al., 2021), additional information gained by observing samples from an interventional distribution amounts inferring the non-intervened parents of an intervened node. This means the unoriented edges adjacent a node i A U pa (A) in the CPDAG remain unoriented after the intervention. The parallel observation in mixture model is as follows. i & {A U pa, (A) U (a)), }, then for any node j, the edge (i - j) does not fit any of the conditions in Case of Theorem 3. (10) and (11), implying that (i - j) & Eg. Hence, node i is unaffected by mixing Pi and p2, and the edges adjacent to node are due to component DAGs. Even though observing pM is strictly less informative than the setting of interventional causal learning literature where samples from Pi and p2 are observed separately, Theorem 3 reflects the importance of parents of A similar way.
Orienting the edges of the mixture graph. After establishing the conditions for two nodes be separable and interpreting them, we look into Objectivez of assigning orientations to the inseparable pairs, i.e., edges of Gm. to represent these conditions. We introduce the following edge notations (-*) and (4+) for orienting the undirected mixture edges EM-
Edge + j= We use this notation to refer to mixture edges in the following cases.
The edges that point towards j & A in both graphs.
Emergent edges that point towards j A.
Edge # j
We use this notation to refer to the mixture edges in the following cases.
Emergent edges between E A and & A. Mixture edges between E A and j E A.
We orient the mixture edges Ex according to these edge notations and denote the oriented edges by EM- Finally, we define G% & (V,E to denote the oriented version of the mixture graph GM- Figure illustrates an example of constructing Gi1-
Inferring orientations. Finally, we address Objective, by partially recovering edge orientations. To that end, we investigate what can be inferred about Eg via CI oracle. By its definition in (7), undirected edges Ex can be identified by exhaustively performing CI tests. The definition of a collider carries to our representation, i.e., node l is a collider on a path if edges on both sides of k have an arrow pointing towards k. Analogous to the (partial) recovery of the edge orientations of a single DAG, we rely on the separability conditions unshielded triples of (i, k) in GM. The following lemma summarizes the partial information we can recover about E
Lemma 2 Suppose that 9, and 92 are tree-structured DAGs. Consider nodes & A and E V that are separated by set S. Consider node l E V \ S for which k) an unshielded triples in GMs Then, we have the following edge orientations in Ezg-

---

Published in Transactions on Machine Learning Research (01/2024)
E
E
Ej Eg
EM
2
2
2
2
3
3
4
3
3
(a) G1
(b) G2
(c) 9M
(d) PM
Figure 3: An example of (a)-(b) Component DAGs; (c) associated undirected mixture graph; (d) oriented mixture graph.
1. i & AE A, then we have i - k 4 j.
2. jf kek& A. then we have i + k 4 j.
3. j A. k A, then we have i k 4 i # k 4 j.
Jf E A, k E A, then we have k + or + k * j or u - j.
Connections to v-structures. Strobl (2023) has provided example of DAGs' mixture with additional latent nodes where v-structures cannot be identified from CI oracle alone. We make similar observation in Case 4 of Lemma 2 that some v-structures in the mixture cannot be inferred without additional information (for instance, i & k # j and K k + j are indistigguishable) On the other hand, Case I and 2 of Lemma 2 show that if we know A, we can orient edges of an unshielded triple upon E A. Hence, (partial) knowledge of the set A, which may be available in certain applications, allows us to infer important information about the cause-effect relationships in a DAGs' mixture.
4.3 Algorithmic Perspective
We leverage our theoretical results to devise an algorithm for learning the mixture graph. The details of the algorithm are as follows. Algorithm takes samples from the mixture distribution PM as the main input and Å S A as an optional input when it is available, which accounts for the (possibly partial) knowledge of the nodes with varying conditional distributions. We assume access to CI oracle to perform conditional independence tests. The algorithm has two main stages:
Stage 1:
In Stage 1, we start with a complete graph, then consider every node pair and remove the edge between them if there exists a conditioning set that makes the random variables corresponding to the node pair independent. We record the separating sets for each removed edge to use in the orientation phase. Note that this skeleton learning phase applies to a mixture of arbitrary graphs.
Stage 2: If the component DAGs are known to have tree structures, we continue with Stage 2 and use the additional
input Å to partially orient the skeleton of the mixture graph. As discussed in Section 4, set A plays a crucial role in the separability of nodes i, j E V in mixture distribution and the orientation of the inseparable pairs (i (5-j) j) E EM- Therefore, we first orient the edges between i E Å and j E Å nodes. Next, we consider the unshielded triples in the skeleton such that the connecting node of the triple is not contained the separating set of the non-adjacent nodes of the triple. While orienting the edges, a circle on one end denotes the ambiguity about the orientation, e.g., we use o to denote that the edge can be either > or *. We follow this convention to orient as many edges as possible. If have partial knowledge of A. e.g., we are given Å C A, we only orient one end of the edges that point towards nodes in A in an unshielded triple. However, if we know that given Å is exactly equal to A, we can orient more edges by considering each unshielded triple with respect to its nodes' inclusion in A.
In the rest of this section, we connect the outputs of Algorithm to the theoretical results presented before. The following lemma states the implications of an edge in the output of Stage and is essentially equivalent to Theorem 2.
Lemma 3 (Stage Output) Assume that the mixture faithfulness assumption holds. If (i (6-)) j) E EM at the end of Stage of Algorithm 1, then there is an edge between and j in at least one of the component DAGs, and otherwise one of the following statements is true:
10

---

Published in Transactions on Machine Learning Research (01/2024)
Algorithm
1: Input: Samples from mixture distribution PM. Á
2: Stage I: Skeleton of GM = (V, EyA)
Form complete undirected graph: EM +- : for all i,
do
for all S E V {i.j} do
> for trees, only for the sets: |S| 3d
6:
if X; 11. X, Xs then
7:
Remove (i - j) edge: EM + Ex (i- j), and SepSet(i,)) + S.
8:
break
9: end if
10: end for
11:
end for
12: Stage 2: Orientation rules for mixture of trees
13: Denote all pairs (i - j)) Εы as o-o j: EM < fio- j: :i: (i- E Em}
14: for all j E Å do
15: Orient x j in EM
16: end for
17: Unshielded triples with non-separator connectors:
u = ((i,k,)): k) E EM, (i - k) EM, (i - 5) & EM. k & SepSet(i, j)}
if we have Å A then
18:
19:
for all (i, f) E E do
20:
if A, A, & A then Orient + k # j in EM
21:
22:
else if E A A,j E A then
23:
Orient + * j in Ex
24:
else if k A, A,j & A then
25:
Orient k + in Ex else if & A, A, & A then
26:
27:
Orient ik #-oj in EM else if k & A, i & A,j E A then
28:
29:
Orient io k o-o j in EM
30:
else if & A, E A, & A then
31:
Orient o ø-j Ex
32:
end if end for
33:
else if have Å C A then
34:
35:
for all (i, j) E E do
36:
if E â then
37:
Orient ik K-oj in EM
38:
end if
39:
end for
40: end if
41: return EM. EM
I. i e A and j E A.
i & and j & A, and component DAGs have A-through paths between and j in opposite directions.
3. i A and j E A, and at least of the component DAGs contains A-through path from j-
11

---

Published in Transactions on Machine Learning Research (01/2024)
Next, we provide the separability necessary and sufficient conditions for the output of Stage 1 when the component DAGs have tree structures. These conditions are equivalent to those for separability given in Theorem 3.
Lemma 4 (Separability in Tree Structures) Suppose that G1 and G2 are tree- strusstrut DAGs. Consider the skeleton EM at the end of Stage I of Algorithm I and assume that mixture faithfulness holds. If there is an edge between and j EM- Otherwise, we have
in at least one of the component DAGs, then (i ()- j]
Case 1) e A and j E A: (i- is in EM-
Case 2) i o A and & A: (i-j) 5) is in Eua if and only if component DAGs have A-through paths between and j in opposite directions such that the children i and j on the paths in A.
j) is in EMa if and only if at least one component DAG has A-through path from i to j such that the child of on the path is in A.
Case 3) i & A and j E A: (i-j)
Finally, we consider the edge orientations in Stage 2. In Section 4.2, we defined edge orientations {-*, * and constructed oriented mixture graph 9 (V, E2g) accordingly. Then, in Lemma 2, we have established what partial orientations can be learned from unshielded triples. Under mixture faithfulness, Stage 2 of Algorithm 1 follows Lemma 2 to construct partially oriented edge set Ex-
Computational complexity We note that for general graphs, Theorem 2 provides only sufficient conditions for the separability of two nodes without establishing matching worst-case necessary conditions. Therefore, for general graphs, Stage has O(n². 22") exponential complexity. On the contrary, for a mixture of trees, Lemma shows that checking all sets S of size at most 3d is sufficient to identify all mixture edges. This procedure is repeated for (2) node pairs. Note that Stage directly reads off the unshielded triples and saved separating sets for all separable node pairs from Stage output. Therefore, the total complexity of Algorithm for mixture of tree-structured DAGs is O(n)d+2). We also recall that the complexity of the well-known PC algorithm (Spirtes et al., 2000) for structure learning of a general DAG is (2242)) The difficulty in our setting comes from having to block all paths between nodes i and j across multiple graphs, which may contain causal relationships in opposite directions.
5 Empirical Evaluations
We evaluate the performance of Algorithm for estimating the skeleton of the mixture graph and partially orienting the recovered edges using synthetic data.
Experimental setup. To generate G1 and G2. we use Erdōs-Rényi model with G(n, p) with density p 2/n for n E (6, 8) for each of the component DAGs. We repeat sampling graphs from Erdös-Rényi model until both G1 and G2 have tree structures. Note that the component DAGs are generated independently and do not necessarily share the same topological order. For the causal relationships, we follow linear structural equation models (SEM) with additive Gaussian noise for both component DAGs, Edge weights are sampled uniformly in + [0.25, 2). and shared directed edges between two graphs are assigned the same weights. The mean of the Gaussian noise for each node is sampled uniformly in 2, 2] with a standard deviation of 1 and set to be equal in both graphs. Note that this parameterization implies that A consists of the nodes with varying parent sets across two graphs. We use a partial correlation test as a conditional independence test routine for simplicity even though the true distribution PM is a mixture of Gaussian distributions. The threshold for the p-vuuue of the CI test is set to a = 0.1. For each case, we run the algorithm with & E (1e3, 3e3, 1e4, 3e4, 5e4, 1e5) number of samples from each component DAG. We repeat this experimental procedure for 500 randomly generated 91 and G2 tree pairs and report the average results. We investigate the effects of the choice of CI test and varying mixing rate of two component distributions in Appendix C.
Skeleton recovery. Figure 4 illustrates the precision and recall rates for recovering the skeleton EM with varying numbers of samples for = 6 and = 8. The observations are shared between two graph sizes, with the performance at smaller graphs being higher, as expected. The first observation is that we have very high precision rates even with as few as s = 1000 samples (shown by the blue curves). On the other hand, high recall rates become possible given large enough number of samples (shown by the orange curves). Recall that mixture edges consist of two disjoint sets: edges that exist in at least one component DAG (i.e., union edges) and emergent edges. We further look into the decomposition of the overall recall rate into the recall rate of union and emergent edges (green and red curves,
12

---

Published in Transactions on Machine Learning Research (01/2024)
n= 6
n=
1.0
1.0
0.9
0.9
0.8
0.8
0.7
0.6
der preieiss
dktk-peeic
dee- meal
0.5
skekmrett
unioreedpre-mcall
criergett regesreccal
0.4
emeggent olpes rocal
10a
10"
10'
10
10*
30'
Number otsamp les from each component DAG
Number of samples from eath component DAG
(a) Skeleton recovery results for n -
(b) Skeleton recovery results for n 8
Figure Skeleton recovery rates
n
0.90
0.90
0.85
0.05
0.80
0.70
antentationncaal
onterbation an-f3
0.65
artentation-11
10a
10f
10'
30'
10'
10'
Number of samples from each component DAG
Number samples from each component DAG
(a) Orientation recovery results for n
6
(b) Orientation recovery results for n
Figure 5: Orientation recovery rates
respectively). The main observation is that emergent edges require more samples than union edges to achieve the same recall rates. This can be explained by the dependence of the two nodes of an emergent edge is only due to the mixing of two distributions. contrast, a union edge denotes a strong dependence between two nodes at least one component DAG, which comprises half of the observed samples. It is, however, noteworthy that the gap between the recall rates of union and emergent edges narrows the number of samples increases.
Orientation recovery. For recovering the orientation of the edges, we take Å = A as input for evaluating our results for diverse combinations of node pairs. In this case, (i * j) orientations for i E A and j E A are already known by the input A. Hence, we report the results for the recovery of non-trivial orientations of + and o-*, Figure 5 plots the precision, recall, and rates for recovering the oriented edges EM with varying numbers of samples for n = and n The first observation similar skeleton recovery the sense that precision rates are higher than recall. We note that emergent edges had relatively lower recall rates in Figure Excluding the emergent edges between two nodes in A for orientation recovery (due already being oriented given A) explains the higher recall rates in Figure 5 compared Figure 4. We also that precision rates in Figure 5 are slightly lower than the ones in Figure 4. This is due to the fact that separating set decisions in Stage 1 of Algorithm I may contain errors even if the undirected edge of the skeleton is correctly recovered.
6 Discussion
Summary. In this paper, we have taken the challenge of causal discovery in a mixture of DAGs. We focused on analyzing the key node pairs that are inseparable in the mixture model but separable in individual DAGs. In our analysis, we have provided sufficient conditions for separating a pair of nodes for a mixture of arbitrary DAGs. We have further improved these conditions and have shown them be necessary for a mixture of tree-structured DAGs, We have also formalized a novel graphical characterization represent the new causal relationships that arise the DAGs' mixture and established results for partially recovering the orientations of the graph's 's edges.
13

---

Published in Transactions on Machine Learning Research (01/2024)
Limitations. The main limitation of this paper is some of our results (Section 4.2) exclusive to mixture of tree-structured DAGs. A practical limitation can be the computational burden of checking every possible separating set to determine if two nodes are inseparable in the mixture.
Future work. This paper formalizes the separability framework for the broad problem of causal discovery of a mixture of DAGs. Extending the theoretical results and graphical representations for a mixture of trees to mixture of arbitrary graphs an important future direction. Developing efficient algorithms for identifying the inseparable node pairs (similar to the PC algorithm for structure learning of single DAG) is important accommodate a mixture of DAGs with a large number of nodes in practice. Finally, generalizing the mixture data model to a block mixture model can provide essential additional information for the causal discovery of the mixture graph. For instance, in dynamical system in which there is a gradual smooth transition between the component models, one can perform change-point detection and dynamic model tracking and estimating. We note that such a setting would also require developing a counterpart for the graphical models for the new mixture distribution while still preserving Markov properties.
Acknowledgements
This work was supported by the Rensselaer-IBM AI Research Collaboration (htt::/aarrc.ri..cdd)) part of the IBM AI Horizons Network (http://ibm.bizi) /iooriii//.....sss............l
References
Silvia Acid and Luis M de Campos. Approximations of causal networks by polytrees: An empirical study. In Proc. International Conference on Information Processing and Management of Uncertainty in Knowledge-Baid -Based Systems, pp. 149-158, Paris, France, July 1994.
Carlos Améndola, Philipp Dettling, Mathias Drton, Federica Onori, and Jun Wu. Structure learning for cyclic linear causal models. In Proc. Conference on Uncertainty in Artificial Intelligence, virtual, 2020.
Stephan Bongers, Patrick Forré, Jonas Peters, and Joris M Mooij. Foundations of structural causal models with cycles and latent variables. Annals of Statistics, 49(5):2885-2915. 2021.
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.
Wei Chen, Yunjin Wu, Ruichu Cai, Yueguo Chen, and Zhifeng Hao. CCSL: A causal structure learning method from multiple unknown environments. arXiv:21 (XXi::2111006666 2021.
Yanxi Chen and H. Vincent Poor. Learning mixtures of linear dynamical systems. In Proc. International Conference on Muchine Learning, Baltimore, Maryland, July 2022.
David Maxwell Chickering. Optimal structure identification with greedy search. Journal of Machine Learning Research, 3(155:077555, 2002.
Diego Colombo, Marloes H. Maathuis, Markus Kalisch, and Thomas S. Richardson. Learning high-dimensional directed acyclic graphs with latent and selection variables. Annals of Statistics, 40(1):294-321, 2012.
Patrick Forré and Joris M Mooij. Markov properties for graphical models with cycles and latent variables. arXiv:1710008775, 2017.
AmirEmad Ghassami, Alan Yang, Negar Kiyavash, and Kun Zhang. Characterizing distribution equivalence and structure learning for cyclic and acyclic directed graphs. In Proc. International Conference on Machine Learning. virtual, 2020.
Arthur Gretton, Kenji Fukumizu, Choon Hui Teo, Le Song, Bernhard Schölkopf, and Alexander Smola. A kernel statistical test of independence. In Proc. Advances in Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 2007.
Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs. Journal of Machine Learning Research, 13(1):2409-246) 2012.
14

---

Published in Transactions on Machine Learning Research (01/2024)
Biwei Huang, Kun Zhang, Jiji Zhang, Joseph D Ramsey, Ruben Schölkopf. Causal discovery from helerngeneouuynonstatiinnny data. Journal of Machine Learning Research, 21 (89):1-53, 2020.
Clark Glymour, and Bernhard
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.
Panagiota Kontou, Athanasia Pavlopoulou, Niki L Dimou, Georgios A Pavlopoulos, and Pantelis G Bagos. Network analysis of genes and their association with diseases. Gene, 590(1):68-78, 2016.
Harvey F. Lodish. Molecular Cell Biology. W.H. Freeman, New York, NY, Eighth edition, 2016.
Marina Meila and Michael Jordan. Learning with mixtures of trees. Journal of Machine Learning Research, 1:1-48, 2000.
Joris M Mooij and Tom Claassen. Constraint-based causal discovery using partial ancestral graphs the presence of cycles. In Proc. Conference on Uncertainty in Artificial Intelligence, virtual, August 2020.
Joris M. Mooij, Sara Magliacane, and Tom Claassen. Joint causal inference from multiple contexts. Journal of Machine Learning Research, 11999):1-108, 2020.
Prectam Nandy, Alain Hauser, and Marloes H Maathuis. High-dimensional consistency in score-based and hybrid structure learning. Annals of Statistics, 46(6A)::151-3188; 2018.
Jane Neumann, Peter T Fox, Robert Turner, and Gabriele Lohmann. Learning partially directed functional networks from meta-analysis imaging data. Neuroimage, 49(2):1372-1384, 2010.
Judea Pearl. Causality. Cambridge University Press, Cambridge, UK, 2009.
Yasaman Pirahanchi, Fadi Toro, and Ishwarlal Jialal. Physiology, thyroid stimulating hormone. StatPearls [Internet], January 2023.
F 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-233 2013.
Brett M Reid, Jennifer B Permuth, and Thomas A Sellers. Epidemiology of ovarian cancer: A review. Cancer Biology & Medicine, 14(1):9, 2017.
Basil Saced, Snigdha Panigrahi, and Caroline Uhler. Causal structure discovery from distributions arising from mixtures of dags. In Proc. International Conference on Machine Learning, virtual, 2020.
Rajen D. Shah and Jonas Peters. The hardness of conditional independence testing and the generalised covariance measure. Annals of Statisties, 48(3):1514-1588, 2020.
Peter Spirtes. Directed cyclic graphical representations of feedback models. In Proc. Conference on Uncertainty in Artificial Intelligence, Montreal, Quebec, Canada, August 1995.
Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman. Causation, Prediction, and Search. MIT Press, Cambridge, MA, 2000.
Eric V. Strobl. Causal discovery with mixture of dags. Machine Learning, 112(11))4001-4225 2023..
Bo Thiesson, Christopher Meek, David Maxwell Chickering, and David Heckerman. Learning mixtures of Bayesian networks. Cooper Moral, 1998.
Ioannis Tsamardinos, Laura E Brown, and Constantin F Aliferis. The max-min hill-climbing Bayesian network structure learning algorithm. Machine Learning, 65(1):31-78, 2006.
Burak VaneI. Karthikeyan Shanmugam, Prasanna Sattigeri, and Ali Tajer. Scalable intervention target estimation in linear models. In Proc. Advances in Neural Information Processing Systems, December 2021.
15

---

Published in Transactions on Machine Learning Research (01/2024)
Thomas Verma and Judea Pearl. An algorithm for deciding if set of observed independencies has causal explanation. In Proc. Conference Uncertainty in Artificial Intelligence, Stanford, CA, July 1992.
John Winn. Causality with gates. In Proc. International Conference on Artificial Intelligence and Statisties, La Palma, Canary Islands, Spain, April 2012.
Karren Yang, Abigail Katcoff, and Caroline Uhler. Characterizing and learning equivalence classes of causal DAGs under interventions. In Proc. International Conference on Machine Learning, Stockholm, Sweden, July 2018.
Kun Zhang and Madelyn RK Glymour. Unmixing for causal inference: Thoughts on Mccaffrey and Danks. The British Journal for the Philosophy of Science, 2020.
Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. In Proc. Conference on Uncertainty in Artificial Intelligence, Barcelona, Spain, July 2011.
Kun Zhang, Biwei Huang, Jiji Zhang, Clark Glymour, and Bernhard Schölkopf. Causal discovery from nonstation- ary/heterogeneous data: Skeleton estimation and orientation determination. In Proc. International Joint Conference Artificial Intelligence, Melbourne, Australia, August 2017.
Xun Zheng, Bryon Aragam, Pradeep K Ravikumar, and Eric P Xing. Dags with no tears: Continuous optimization for structure learning. Proc, Advances Neural Information Processing Systems, Montréal, Canada, December 2018.
16

---

Published in Transactions on Machine Learning Research (01/2024)
A Proofs of the Main Results
A.1 Invariant conditional distributions and parent sets
The following result states that if node has invariant causal mechanisms across two DAGs, i.e., invariant distributions conditioned on its respective parents in 91 and G2, then the parent sets must be equal.
Lemma 5 if & A, then have pad (i) (1)
Proof Consider a node & A. We prove that pa, (i) - paa((i) by contradiction. Suppose the contrary and assume pa, (i) * (i) Without loss of generality, let pay(i) (i) # 0. and consider j E paz(i) pa, (i). Let 5 - (1) (5). Since i & A, the conditional probability distributions of given its parents the same, i.e.,
pi (z; paa (1) p2 [p))()) = p2(x;; [g)
(12)
By definition of causal parent, there exist realizations Xs = 0", Xj = a" and Xj = b* such that
(x = z; X = 0" X, = a²) + P2 (X; = X 0*, X, = b*).
(13)
Otherwise, X, has no effect on X; conditioned on set S, and it is not a parent of in Go. Now consider a realization of X Xpa (1) are determined by 0- Then, we have
X (f) = 10" for which the values
Pr (xx; = X (1) x²) p2(X; = Xs xz)
(14)
Note that the left-hand side of (14) is independent of Xj. However, the right-hand side of (14) takes distinct values for realizations X, = a" and X3 = b*, which is a contradiction. Therefore, pay(1) \ pa, (i) = @ and by similar line of argument, we have pa, (i) \ (a² = 0. This concludes the proof that if & A, then pa (i) = pag(i).
A.2 Proof of Theorem 2
First, we provide a counterpart of Theorem 2, which states the necessary conditions for nodes i and j being inseparable (forming an emergent edge). The proof of Theorem 2 will readily follow from this result.
Theorem 4 Consider nodes i. E V such that i and are not adjacent in either component DAG, i.e., (i - j) & Eu-
Case 1) E A and E A: and j are always inseparable, i.e., (i - ÿ) is an emergent edge.
Case 2) i & A and j $ A: if and j are inseparable, then the component DAGs have A-through paths between i and j in opposite directions. That is, one DAG contains a A-through path from to j and the other one contains a A A-through path from j
Case 3) i & A and j E A: i and j are inseparable, then at least one component DAG contains a A-through path from to
Proof The first case is trivial as inseparability of the nodes E A and j E A due to the path i & y -- j in composite DAG. We prove the non-trivial cases as follows.
Case 2: For & A and & A, we have pa, (1) (1) and pa, (f) = p)) by Lemma 5. Let the pair (i - -j) be inseparable and consider the set S = pa( (a)).. Then, there exists an open path π between and j given S on composite DAG Gc. Since pa(i) given, any path that starts with f is blocked for E {1,2]. Without loss of generality, let start with an edge i 3, We investigate two possibilities for
Let y & т. Then, ग must be of the form i 1 ... - j. Without loss of generality, suppose that i & dei (j). However, there exists collider k on æ such that & E (j) Then, for и to be open, node E det (k), which also a node in (j). must be given in S. However, 2 & pa(i) since i & do; (j) and z $ pa(j) due to acyclicity. Therefore, the case of y & is not possible.
17

---

Published in Transactions on Machine Learning Research (01/2024)
Let y E и. Without loss of generality, suppose that и contains do k ...... For x to be open, a E def (k) ...y. must be given in S = pa(i) U pa(j), which implies that k ani (j). Subsequently, i - j. Repeating the same line of arguments, we find that j 2 i. Finally, note that if none of the nodes the path i ~ is not contained in A, then we have the same path in G2 as i 2 j. which contradicts with j 2 i. Therefore, there exist A A-through paths between and] j in opposite directions the two component DAGs.
Case 3: Since & A, have pad (i) - pay(1). Let (i j) be inseparable and consider the set S = pa(i). Then, there exists an open path between i and j given S on composite DAG Gc. Since pa(i) is given, any path that starts with í is blocked, and necessarily starts with i S edge. If a contains collider k such that i A k, then S pii) must contain a node from dež (k) for x to be open. This contradicts with k E dee()). Hence, there is no collider on π and we have f j. Since j E A. w4 j is A-through path.
Proof of Theorem 2. Case 1 of Theorem 2 the same as Case of Theorem 4. For a pair of nodes i, that are not adjacent in component DAGs, we define the following statements.
P: and j are separable,
Q component DAGs do not have A-through paths between and j in opposite directions
R: : neither of the component DAGs contains a A-through path from i to
Then, Case 2 of Theorem 4 shows that if & A and A, we have -P = -Q. This equivalently means that
Q
P, which is Case 2 of Theorem 2. Next, Case 3 of Theorem 4 shows that if i & A and j A, we have
P R.. This equivalently means that R = P, which is Case 3 of Theorem 2, and the proof is completed.
A.3 Proof of Theorem
Case is the same as Case of Theorem 2 and is trivial since inseparability of the nodes E A and j E A is due to the path i f y S. j in composite DAG. We prove the non-trivial cases as follows.
Case 2: i i A and j & A. Note that the theorem statement is equivalent to: and j are inseparable if and only if the component DAGs have A-through paths between and j in opposite directions such that the children of i and j on the paths are in A. We prove the two directions of this equivalent statement as follows.
Let there exist A A-through paths between i and j in opposite directions such that the children of i and j on the paths are in A. Then, without loss of generality, let i 4 ~4 j and j 3 2 i where u, v E A. Suppose that (i - j) is not an emergent edge, and set S separates them. Then, S must contain nodes from de (u) and dež (v) to block both A-through paths. However, this opens the path i 2 u _ 3 u 2 j. which contradicts with and j being separated. Therefore, and j are inseparable and (i -5-31 j) E Eg.
Let j) be inseparable. By Theorem 4, without loss of generality, we have i 1 u 2. j and j 2 2 i. We prove that u E A by contradiction. Suppose the contrary and let u of A. Consider S = pp((i)) U Upa(j) U (u) U V(i.. Let x be an open path given S. Since pa(i) and pa(j) are given, π starts with i 4 edge and is not a causal path from i to j. Then, π must contain a collider & E (e) i.e., л contains L k é. For ा to open, some 2 E (ee(k) must be in S. Due to acyclicity, 2 & pa(i). Recall that Ge is a tree, and there can be only one directed path from to j in Ge. Then, if 2 E pa(j). having - u & j and & k d 2 - imply that u is и and blocks n, which contradicts with being open. If = E pa then i - and 4 u imply that In this case, x becomes - é, which is blocked by pa(u), and is not open. We find contradiction in each possible configuration for u & A. Therefore, we find that E A. By following similar line arguments, we can find that e E A as well, which concludes the proof of this case.
Case E A and j E A. Note that the theorem statement is equivalent to the following statement: i and j are inseparable if and only then at least one component DAG contains a A-throuhh path from i to j such that the child of i on the path is in A. We prove the two directions of this equivalent statement as follows.
18

---

Published in Transactions on Machine Learning Research (01/2024)
Let 1 u - j without loss of generality such that u E A. Suppose that (i- is not an emergent edge, and set S separates them. Then, S must contain a node from det (u) to block the causal path i ~ j. However, conditioning on node from def (u) opens the path i - < y + j. which contradicts with i and j being separated by S. Therefore, i and j are inseparable.
Let (i j) be inseparable. By Theorem 4, without loss of generality, we have i + u d j. We prove that u E A by contradiction. Suppose the contrary and let u & A. Consider S = pa(i) U pat pat(u)) \ {i). Let i be an open path given S. Since pa(i) are given, π starts with i - edge. Let there exists collider k E dez(i) on then some 2 E dee(k) must be in S for π being open. Then, < k <4 z implies that 2 & pa(i) due to acyclicity, and we have E pa* (u). However, for tree- condiiioiiinnnn on Ge, we must have h = 2 = u, and ι is blocked due to S u f. Therefore, there is no such collider & E dee(t), and π is a causal path i ~ j. Since + u ~ j path is blocked by u E S, ग is of the form i 3 2 j. If A, π is causal path from to j in which the child of is in A, and the proof is completed. Suppose the contrary and let A. Now, consider S' = pa(i) U paa((1) U (v) \ {i). Let n' be an open path given S", and without loss of generality, n' starts with i 3. Note that n has to contain a collider k E dei since the only causal path of the form 2 j ji blocked by u. For T' being open, some 2 E de (k) is given in S'. We have & pa(i) due to acyclicity. we have z E pa (u), tree-structured 91 implies that & = z = u, and T' blocked by pa(u). Finally, if z E pa pa)(),, v, and I' is blocked by pa(v). Hence, u & A is not possible, and we have u E A, and the proof is completed.
91 being a tree implies that
A.4 Proof of Lemma 1
We prove the desired result by investigating all possible cases. Since i and are separable, at least one of them is not in A. Without loss of generality, assume that & A.
(i) i & (j) and & an)()): Consider S pa(i). Suppose that x is an open path between and j given S on Gc- Since pa(t) is given, without loss of generality, ा starts with an edge i 4. Since & an1 contains collider l such that i ..b, k A. For π to be open, 2 E def (k)) must be in S = pa()), which contradicts with acyclicity. Therefore, S = pa(i) is a separating set for i a.d
(i) i E an (), & (i) and j A: Let + u ~ j. Since and j are separable, by Theorem 3, u & A. Consider S pa()) U (pa + (u) i}. Suppose that π is open path between i and given S on Gc. Since pa(i) is given, π starts with an edge i S. Since is given, contains a collider k such that i f k E. For x to be open, 2 E dež (k) must be in S. However, a cannot be in pi(i) due to acyclicity. Also, 2 cannot be in pa(u) since otherwise there would be multiple causal paths from to u in Ge. which contradicts the tree structure. Using the tree structure again, т starts with S u f. However, since pa (u) is given, π cannot be open. Therefore, S = pa()) U {pa (u) \i) is a separating set for and j.
(ii) If E in) i & anz(s), and j & A: Let i 4 w j. We investigate this case in two subcases. First, suppose that j & (1), and consider S = pa(j). Suppose that is an open path between j and i given S on Gc- Since pa(j) is given, π starts with an edge j 4. Since j is not an ancestor of i in either graph, π contains a collider At such that j <. k e For ι to be open, a 2 E def (k)) must be in S = pa(j). which contradicts with acyclicity. Therefore, S = pa(j) is a separating set for and j. Second, suppose that j E anz()), and let j 3 U 2 i. Since and j are separable, by Theorem 3, at least one of u and is not in A. Without loss of generality, let & A and consider S = pa(() U {pa (u) \ (). Following (ii), S is separating set for and j.
(iv) If i E an)()), i E anz(j), and j E A: Let 1 u 3, j and i 3 u 3. j. Since i and j are separable, by Theorem 3, u & A and u & A. Consider S = pa(i) U {pa + (w) \ ( U (pa+(u) \ i). Since pa(i) is given, л starts with an edge i 4. Since u and are given, π contains a collider 1 such that & & without loss of generality. For x be open, a 2 E dež (k) must be in S. However, & cannot be in pa(i) due to acyclicity. Also, z cannot be in pa(u) (or (r)) since otherwise, there would be multiple causal paths from
19

---

Published in Transactions on Machine Learning Research (01/2024)
i to u (or v) in Ge which contradicts with the tree structure. Using the tree structure again, starts with
i - & (or 4 v Â). However, since pa+(u) (and pa (v)) is given, cannol be open. Therefore, = pa(1) U (pa* (u) \ U (pat (u) \ {i] is a separating set for i and j.
(v) If i E an (j), i E an) and j $ A: Consider = pa(j). Similar to the first subease of (iil), S a separating set for i and j.
We have exhausted all possible cases. In summary, if and j are separable, then at least one of the sets pa(i), pa(j), pa(i) U (pa (u) \ i.., and S - pa(i) U (pa+(w) \ d U (pa+(u) ) \ij is a separating set for i and j. Note that the size of these sets is upper bounded by 3d where d denotes the maximum in-degree of a node in component DAG.
A.5 Proof of Lemma 2
We prove the four statements in order.
Proof of Case There are three possible configurations for orientations of (i - k)) and (j - k) pairs. We show that only i + k 4 j is valid.
(i - k # j): By definition of the edge - without loss of generality, there exist paths i 3 J. and
j 3 2 where u, v A. Note that and are not necessarily distinct from k. Then, conditioning on & opens
the path
1 y
3 1 E
(15)
since and are colliders on the path and y is latent node. This implies that E S, and this is valid case.
(k * and ks + j): Since $ A and j A, these orientations imply that (i- k) and (j - k) are not emergent edges. Then, we have i & k 4 j for all & E {1,2}. Then, & must be contained S to separate and j. which contradicts with & S, and this is not valid case.
(k + and j + k): Without loss of generality and using Theorem let 4 u. ~ k 4 i in which a e A and k 3 Note that u and k are not necessarily distinct. Since S separates and j. it contains node E dej (u). However, in this case, the path j 1 u + 1 l 1 i is opened since & S. Therefore, this is not a valid case.
Proof of Case 2. There are two possible configurations for (i - k)). If - i, then i k 4 blocked without conditioning on k. contradicting with & & S. Then, we have i + k. Without loss of generality, let 1 u J. & for some u E A. Note that S does not contain k. Otherwise 1, u + y 1 path would be open. Hence, this a valid case.
path cannot be
Proof of Case 3. There are three possible configurations for orientations of (i - k)) and (j - 1)) pairs. We show that two of them are valid.
1. (i + k and j + le): Since & & A, this implics - k & for all {1,2). Then, conditioning on k opens the path i S k E for all f E {1,2) This implies that & & S, and this is a valid case.
2. (1 # 1 and j # k): By using Case 2 of Theorem 3, without loss of generality, we have i 1 u 3, and k 3 v .. for some u, U A. There are two possibilities for (j k). First, k + ~h j and j 3 w 22 for some
2, E A. However, in this case, we have i - ~ j and 3 . i, which implies that and j are inseparable
by Theorem 3 and contradicts with the premise that and j are separable. Then, we must have - z 3, j and
j w L. k for some 2, w E A. In this case, conditioning on opens up the path 4 & y 3 2 j. This implies that k & S. and this is valid case.
20

---

Published in Transactions on Machine Learning Research (01/2024)
3. (i + k and j * K): By using the Case of Theorem 3, without loss of generality have
j + u n x and i 3 l: 3 1 3
(16)
where A. Since k & S, some E de (v) is given in S to block the latter path. Then, for the path i 3 3 2 + _ j to be blocked, S does not contain any node in der (u). However, this implies that
j 3 u v A open given S, which yields a contradiction. Hence, this not a valid case.
Proof of Case 4. There are six possible configurations for orientations of (i - k) and (j - k) pairs. We show that three them are valid.
1. (i + k and j + ky: Since k & A, this implies - k & for all E {1,2}. Then, conditioning on k opens the path i S f for all E {1,2) This implies that k & S, and this is a valid case.
2. (i x k: and + k): By Case 2 of Theorem 3, without loss of generality, we have i 4 ~ k 2 and j 3 3 2, where u, v E A. Since is not an ancestor of j in either graph, and j can be separated. Also,
conditioning on k opens up the path i i & y + j. This implies that k S, and this is valid case.
+ and j + k): Since & S, without loss of generality & ls _ path open given Hence, this is not valid case.
4. (i + and + j): Since & A, we have 4 k, 3 k. and without loss generality, & 4 my where u E A. To block the path + k + u na j. some E dei (u) must be conditioned on. However, doing so opens up to the path + k f f y + Hence, and cannot be separated without conditioning k. Therefore, this is not valid case.
(k + and + i): The paths i E k 4 2e and & k - & y 4 cannot be blocked simultaneously without conditioning k. Therefore, this is not valid case.
6. (i <->> l and k j): Without loss of generality, we have 4 L and k 3, 2. i where u, A. For 1 - j. there are two possibilities. If k + ~ j for some 2 E A, we have i 1 u A. k ~e j. Subsequently, i + j which contradicts with and j being separable. Therefore, we have k - occur in the second graph as 1: 3, z 2. j. Conditioning on k opens up the path + & 3 since (n). This implies that & S,
and this is valid case.
A.6 Proof of Lemma 3
Recall that using mixture faithfulness assumption and Theorem 1, we have that X; 11 X, | X if and only if IL M. S composite DAG Ge. Then, if (i - j) E EM, either there an edge between and j in at least one component DAG or j) )) an emergent edge. For the latter case, the inverse of the sufficient conditions for separability statements in Theorem exactly gives the statements of this lemma.
A.7 Proof of Lemma
If there is an edge between and j at least one of the component DAGs, then X; and X, are not independent for any conditioning set, and we have (i j) E Ex. The inverse the necessary and sufficient conditions for separability statements in Theorem exactly gives the statements of this lemma.
B Generalization to an Arbitrary Number of Component DAGS
In this section, we show that the results presented in Section 4 can be readily extended a mixture of m DAGs. To this end, we extend all the definitions in Section 2 for component DAGs. We skip repeating the generalizations of simple definitions that are apparent from the context and just present the important ones here.
21

---

Published in Transactions on Machine Learning Research (01/2024)
We consider m component DAGs, {9e _ (V, : E [m]] with associated distributions (pe l [m]). Then, the definition of A is generalized as
-
{i E V 36, E mm] such that pe(X; px) * per (e; (())
(17)
Latent random variable L E [mm] accounts for the true model underlying the observed data, where L = l specifies that the true model is ps. We denote the probability mass function (pmf) of by Then,
(M)
(()) pe(())
(18)
te/m
Accordingly, the definition union edges is updated as
Eu - (1- :iSEV, BEE [m] :1 :14 5
(19)
The definition of the edges of the mixture graph GM remains the same. The definition of the emergent edge becomes: The edge (i j) in the mixture graph Gla is called emergent edge if the pair of nodes and j are not adjacent any Ge, & E [m.. but become inseparable in PM. The set of emergent edges is given by
Ep
{11 - j) i,j V, ji & Ev A 1AC (4:)
X, 1
(20)
We note that Theorem is already given for mixture of m DAGs in (Saeed et al., 2020). Hence, can still use it for inferring separation statements in composite DAG Gc.
For generalizing our separability result for general graphs (Theorem 2), we generalize its equivalent form Theorem 4 presented in Appendix A.
Theorem 5 Consider nodes j V such that and are not adjacent in any of the component DAGs, i.e., (i-j) & Ev.
Case 1) E A and A: and j are always inseparable, i.e., (i () is an emergent edge.
Case & A and; A: i and are inseparable, then there exist two component DAGs Ge, Ge such that Ge contains A-through path from i j and Ge contains A-through path from j to i.
Case i & A and A: if and j are inseparable, then least one component DAG contains a A-through path from j.
Proof Note that Case 1 and Case 3 are identical to those of Theorem 4, and their proofs follow identically. Proof of Case 2 follows similarly as well. For i & A and j & A, we have (1) = p1) and pa,(j) = pa. (j) for all l E [m]. Let the pair (i - j) be inseparable and consider the set S = pa( U pa(j). Then, there exists an open path ı between and j given on composite DAG Gc. Since pa(i) is given, any path that starts with i & blocked for all E [m]] Without loss of generality, let æ start with an edge 4. The case of y & follows identically to that of proof of Theorem 4. Let y E Without loss of generality, suppose that contains i ~ / .... and 2, k 2... For æ to be open, a E det (k) must be given in S = pa()) L pa(j), which implies that & E anj (j). Subsequently, i ~4 j. Repeating the same line of arguments, we find that j 2 i. Finally, note that if none of the nodes on the path i , j is not contained in A, then have the same path in G2 2, j. which contradicts with j 2 i. Therefore, there exist A A-through paths between i and in opposite directions in component DAGs G1 and G2.
...y.
Next, we generalize our separability result for mixture of tree DAGs (Theorem 3).
Theorem 6 (Separability in Tree Structures - Necessary and Sufficient Conditions) Suppose that II...., Gm are sree-structured DAGs. Consider nodes i E V such that i and j are not adjacent in any component DAG, i.e.,
(i-1) j) & Eu.
Case 1) i E A and j E A: and j are always inseparable.
Case i & A and j & A: and are separable if and only if there does not exist Gr. Gr such that the two DAGs contain A A-through paths between i and j opposite directions such that the children of and j on the paths in A.
22

---

Published in Transactions on Machine Learning Research (01/2024)
8
0.8
0.7
0.85
0.6
0.80
0.5
0.75
10k
0.4
10k
100k
100k
0.3
Number of component DAGS
Number of component DAGs
(a) Union edges recall rates
(b) Emergent edges recall rate
Figure Skeleton recovery results for varying number of component DAGs and number of samples
Case i & A and j A: i and j are separable if and only none of the component DAGs contains A-through path from to such that the child of the path is in A.
Proof
The proof follows almost identically to the proof of Theorem 3 by setting and L' without loss of generality, and using Theorem instead Theorem 4.
Finally, by using Theorem instead of Theorem 3, Lemma 2 can be readily generalized a mixture of tree-structured DAGs.
C Additional Simulations
C.1 An Arbitrary Number of Component DAGs
In this section, we empirically support our claims in Section B that our approach can be generalized to mixture of an arbitrary number of DAGs. To this end, we repeat the simulations in Section 5 for mixtures of m E {2, 3,,4,17 5} component DAGs.
Figure 6a shows that the recall rate of union edges decreases as m increases. This not surprising since many union edges become weaker as m increases in the sense that only 1 1/m-th of all samples come from the model that the edge belongs to (unless the edge is shared over all components). That being said, the performance still stronger than the recall rates of emergent edges, which comment next.
Figure 6b shows that there is no apparent change in the performance of recovering emergent edges in the skeleton of the mixture graph. This interesting observation can be explained by the effect of the number of component DAGs in two opposite directions. First, increasing m also increases the size of as more nodes are likely to be affected by the changes in the environment. However, the number union edges also increases as yn increases. This, turn, reduces the number possible emergent edge pairs. As result, the emergent recall rates remain around the same values as increases.
C.2 The Choice of CI Test
In the experiments in Section 5, we have used partial correlation test as CI test, similar to the most closely related work to ours which also uses a partial correlation test even though the true mixture distribution is not Gaussian (Saeed et al., 2020). We note that there exist more sophisticated alternatives such as generalized covariance measure (GCM) (Shah Peters, 2020), kernel-based conditional independence test (KCI) (Zhang al., 201 1), or Hilbert-Schhidt independence criterion (HSIC) (Gretton al., 2007). However, the partial correlation much faster than these alternatives and usually achieves comparable performance (Mooij & Claassen, 2020). Still, of comprehensiveness,
23

---

Published in Transactions on Machine Learning Research (01/2024)
1.0
1.0
0.0
0.8
0.6
0.6
past emnegenteeegeeeeee emergent edges
emergenteedgyeeeet uniineddpee-eeal
omergent edges
0.0
10
10
10
10*
Number of samples each DAG
Number of samples from each
(a) Skeleton recovery results for
(b) Skeleton recovery results for
Figure 7: Comparison of partial correlation and GCM CI tests at skeleton recovery
8
0.85
3.5
0.80
0.95
0.4
0.75
0.94
0.70
24
0.30
0.00
0.30
0.50
0.29 0.00
Misinn
Maxing
(a) Skeleton precision rates
(b) Emergent edges recall rate
(c) Union edges recall rates
Figure 8: Skeleton recovery results for = 8 at varying mixing rate and number of samples
we repeat a subset of the simulations reported in Section 5 using GCM as CI test and compare the results with that of the partial correlation test.
We use the same setting as Section 5 to generate mixture models and repeat experimental procedure for 100 randomly generated tree pairs for E {1e3, 3e3, 1e4} number of samples. Figures 7a and 7b show that there is apparent difference in the performance of skeleton recovery while using either partial correlation GCM tests. Therefore, the observations made in Section 5 remain the same when the partial correlation test is replaced with the GCM test.
C.3 Varying the Mixing Rate
In Section 5, we have used an equal number of samples for each component DAG while creating the mixture model. In this section, we investigate the effect of varying this mixing rate. Specifically, we consider 8 nodes and total number of samples E [3e3, 1e4, 3e4, while varying the ratio of the dominant distribution (0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.99). We repeat the experiments 500 times and report the average results for skeleton recovery in Figure
Figure 8a shows that the very high precision rates preserved even at extreme mixing rates of 0.95 and 0.99. The more important observation is regarding the recall rates. Figure 8b and Figure 8c show that the recall rates of both union edges and emergent edges are not significantly affected while varying the mixing rate from 0.5 to 0.8. However, when one of the models in the mixture becomes more dominant, indicated by a mixing rate over 0.9, the performance decreases significantly. This is, in fact, not surprising due the following reason: When one model becomes extremely dominant in the mixture, then two edge types become weaker, (i) the emergent edges that arise due to mixing of the components, and (ii) the edges exist in the minor model, which accounts for part of the union edges. Figure 8b illustrates the first observation.
24

---

Published in Transactions on Machine Learning Research (01/2024)
8, = 30000 samples
1.0
0.9
0.7
0.6
union edges recall
recall
0.5
0.80
0.85
0.99
Mixing rate
Figure Skeleton recovery results for varying mixing rate and number of samples
8
1.0
0.8
0.6
0.4
equal noise union recall
0.2
unequal noise var: union recall
equal naise var: emergent recall
unequal noise var: emergent recall
0.0
104 Number of samples
103
Figure 10: Skeleton recovery results for varying mixing rate and number of samples
Next, we scrutinize further to understand the behavior in Figure 8c better. We break down the union edges into E₁ and E, components, for which E, corresponds to the edges that exist in the dominant model. Note that an edge is shared in both models, then it is included in both E, and Eg. Figure 9 shows that, accordance with our expectations, the performance degradation due to the edges of the minor model. Specifically, recall rates of Ej become higher and recall rates of Eg become smaller as the ratio of the samples from 91 increases. This surprising since edges in Eg become weaker in the mixture model. This result can guide practitioner which approach use when treating mixture if each component model is responsible for at least 10% of the
mixture model, e.g., treating the model samples, or treating it is as single model and dealing with weak edges using different method if the minor model is responsible for only a few percent of the data samples.
C.4 Changing the Noise Variance
In the simulations presented in the previous sections, we have used equal noise variance 1 explained in the experimental setup. We repeat the same experimental procedure with unequal noise variances such that the noise variance of each node is sampled uniformly from [0.5, 1.5]. Figure 10 shows that the equal and unequal noise variance settings result in almost identical performances at the recovery of both emergent and union edges.
25


Reviews:
[{"review_id": "t47GzWlLRF", "reviewer": "Reviewer_73B5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I think this is an interesting work on a topic that is largely understudied in the community. The authors do a very nice job of clearly laying out the problem that is being considered, clearly describing the assumptions and delineating and contextualizing within the relevant recent work. I think the results provided here are things that can serve as a strong basis for future work to build on. The algorithm provided is sensible and relatively simple, and is also well described by the authors. \n\nIn terms of the weaknesses of the paper:\n(1) (small) As acknowledged by the authors, the strongest results make an assumption of tree structured networks. This is a fairly common assumption, but it's not clear when we should expect this to hold especially since we need it to hold over _each constituent network_\n(2) (small) There is an implicit assumption here that there is a \"hard membership\" model for the mixtures. This clearly can be sensible in many cases but not always (e.g., in the dynamical systems example it's fairly easy to imagine a smooth transitioning between states)\n(3) (medium) The paper implicitly assumes, and explicitly tests against in the experiments, the case where there are just two components in the mixture. It would seem that unless there is a very large amount of overlap this solution (and perhaps any solution) would lead to a lot of emergent pairs. \n(4) (medium) The experimental section is very limited. It would be useful if the authors could test against a larger number of components, unequal variances for the noise distributions, etc. \n\nTo summarize here, overall I think this a nice paper, and would like to see some small modifications to improve some of the takeaways for readers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work is concerned with identifying the causal structure of data that is collected from a mixture of underlying distributions/causal structures. The authors present work complimentary to the approach in Saeed, et al. (2020). The key difference between the two is that the approach in Saeed requires an ordering of the constituent networks. The present work drops that assumption, replacing it with the assumption that each constituent graph is tree structured for some of the more substantive results. The authors describe identifiability conditions for edges, and describe when we should expect to see edges which are unidentified in the mixture graph despite being identified in the constituent component graphs. A constraint based learning algorithm is described for recovering the mixture graphs, and a small set of experiments run on some simpler synthetic data show promising results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "(a) (minor) If the authors could provide some discussion for points (1)-(3) above that would be great\n(b) (minor-moderate) It would be nice if there were some additional results provided on more challenging data simulation settings to glean more intuition above the propose behavior from empirical results. \n(c) (very minor) There are some references that should probably be included:\n    (i) \"Causality with Gates\" by John Winn addresses the problem here with a different approach (leveraging factor graphs). \n    (ii) Both \"Learning Mixtures of Bayesian Networks\" by Thiessen, et al. and \"Learning with Mixtures of Trees\", by Meila & Jordan look at the problem of learning DAGs/ Tree structured graphs. They are both non-causal but are relevant enough they should probably receive a citation.", "broader_impact_concerns": "I do not have broader impact concerns here.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EBsP1yIkqn", "reviewer": "Reviewer_JUCG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- The paper considers a topic that is not well explored \n- The approach is novel to the best of my knowledge\n- Theoretical conditions are provided for separability\n\nWeaknesses\n- The relation to prior work could be better explored. While prior work is mentioned, it's difficult to determine the specific differences and how related and novel this work is.\n- While computational challenges are mentioned, they're not well described. It's not clear why in the first stage, a PC style approach could not be used to select edges (but the algorithm given is searching over all subsets). Furthermore, if this is the approach that is taken, it's not clear how the empirical results were generated for n=8.\n- The empirical results could be made to convey more information - it's not clear what insights the reader should take away from the results. The ER assumption is also probably not realistic.\n- It's clear that the tree-structured assumption makes the problem easier and the results more interesting, but it's not clear that one can realistically assume this in any contexts.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers learning causal DAGs from observational data in the case where the observed data comes from a mix of multiple underlying causal structures. Specifically, the paper is mostly an investigation into conditions where two edges are separable when they are nonadjacent in one or more of the underlying DAGs.\n\nSufficiency conditions are given for separability in general and necessary and sufficient conditions are given for tree structured DAGs. Finally, an algorithm for selecting and orienting edges (that can be oriented) is provided for both circumstances. \n\nSome empirical results from simulations are provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- In addition to mentioning the related work, can the authors clarify the novelty and relation of the results provided to prior work (specifically the theorems about separability with and without the tree-based assumption?\n- Can the authors characterize the computationally complexity of their approach, whether it's occurring at the orientation phase only, whether a PC style approach can be used at the edge selection phase and what specifically about the approach leads to the computational difficulties?\n- Can the authors list any contexts where it would be appropriate to make the tree-based assumption?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "mbR3V38yae", "reviewer": "Reviewer_mJ6F", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "As well as allowing orientations I think the theoretical results also\nhave some independent interest to basically understand how \"emergent\nedges\" between inseparable nodes arise. (One can also have emergent non-edges but these would be rare,\nand are not considered in this paper.)\n\nFor Stage 1 of the algorithm (ie Algorithm1) we may have to consider\nevery possible conditioning set S to conclude that there should be an\nedge in the mixture graph so this stage has exponential\ncomplexity. Lemma 1 also requires that we know that k is not in \"any\nseparating set of i and j\". (These problems are noted in the\n\"Limitations\" part of the Discussion.) So we don't have a really\npractical algorithm. The paper would be improved if we could be given\nsome idea if there is a realistic prospect of developing the\n\"efficient algorithms\" mentioned in Future Work. Also since we are\nusing an oracle here, at some point we will need to consider the\nstatistical problems that need to be addressed when learning from\n(finite) data. The paper does not give a convincing case that this is an initial step to practical learning of DAG mixtures.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "A good way to evaluate this paper is to start from the \"Causal\nDiscovery Objective\": \"What causal relationships can be learned about\na mixture of DAGs .. ?\" and work backwards. Given a conveniently\navailable CI oracle one can, of course, detect CI relations in the\nmixture distribution (just as with any distribution) and represent the\npresence/absence of these using an undirected graph (here called the\n\"mixture graph\"). One could, of course, continue from here by ignoring\nthat this is a mixture distribution and continuing, say, with the\nPC/FCI/RFCI algorithm. However, it is clearly more interesting to\nattempt to uncover causal information in the component DAGs.\n\nTo this end the authors devise an orientation notation for edges in\nthe mixture graph and, more importantly, identify cases where these\norientations can be inferred from CI tests. Unsurprisingly, unless we\nhave additional knowledge - here about \"\\Delta\" (the set of variables\nwith differing conditional distributions in the component DAGs) it\nappears we cannot make further progress. With no knowledge of \\Delta,\nthe authors do not provide a method for orientation - I suspect there\nis none. In the case where we know some members of \\Delta some\norientation is possible which represents a causal relation (Lemma 1).\n\nThe most important result is Theorem 1 about the composite DAG. Since\nthat is from an earlier paper the issue is how useful the additional\nresults are. The main contributions are Theorem 2 and Theorem 3. The\nproofs of both these theorems work by analysing paths in the composite\nDAG; the composite DAG and the assumption of \"Mixture Faithfulness\"\nare thus key to the results in this paper. Theorem 2 gives sufficient\nconditions for separability whereas Theorem 3 gives both necessary and\nsufficient conditions when the component DAGs are tree DAGs and is\nused to prove Lemma 1 which allows some orientation. The proofs of the\ntheoretical results in this paper are done by consideration of\ndifferent cases and then reasoning about open paths in the composite\nDAGs. I found no errors (apart from a typo) and each individual part\nof the proofs are not too complex. This case-by-case approach is\ncommon in combinatorics, so not too surprising it is used here.\n\nBuilding on the theoretical work an oracle-based constraint-based algorithm for learning \"mixture graphs\" is given.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Although Lemma 1 is in Section 4.2 on Tree Mixtures I think the\nrestriction to tree DAGs should be explicitly given in its\nstatement. Since this is currently missing, strictly speaking Lemma 1\nis incorrect.\n\nNeed to be clearer: \"not adjacent (connected) in the individual DAGs\":\ndoes this mean not adjacent in all individual DAGs or in at least one\nof them? Theorem 2 should be stated as \"not adjacent in either component DAG\"\n\nThe assumption of faithfulness should be stated earlier in the paper,\nnamely on p2. where inseparable pairs are defined to be \"random variables\nthat cannot be made conditionally independent in the mixture\ndistribution.\" At present it is only mentioned parenthetically at the\nbottom of p3 and properly stated at the bottom of p4.\n\nWhy not use some other test, e.g one that does not assume the true\ndistribution is Gaussian?\n\nWhat is the true mixing rate (in the Experimental Setup)? Presumably\n50/50? It would be interesting to see what happens as it varies.\n\nIn the proof of Theorem 2 \"\\neq P \\Rightarrow \\neg R\" should be \n\"\\neg P \\Rightarrow \\neg R\"", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors and reviewers engaged in discussion and the authors made changes to the manuscript to improve it based on the reviewer comments. The resulting manuscript is much improved and supported for acceptance by the reviewers.
Decision: Accept (poster)