Learning Mixtures of Unknown Causal Interventions
Authors: Abhinav Kumar
Kirankumar Shiragur
Caroline Uhler
Venue: NeurIPS 2024 poster (2024)
Keywords: causal discovery
mixture
Primary area: causal_inference
TL;DR: A mixture of observational and unknown causal interventions can be efficiently disentangled and causal graph can be learnt upto IMEC within the linear SEM framework with Gaussian additive noise.

Abstract: The ability to conduct interventions plays a pivotal role in learning causal relationships among variables, thus facilitating applications across diverse scientific disciplines such as genomics, economics, and machine learning. However, in many instances within these applications, the process of generating interventional data is subject to noise: rather than data being sampled directly from the intended interventional distribution, interventions often yield data sampled from a blend of both intended and unintended interventional distributions.

We consider the fundamental challenge of disentangling mixed interventional and observational data within linear Structural Equation Models (SEMs) with Gaussian additive noise without the knowledge of the true causal graph. We demonstrate that conducting interventions, whether do or soft, yields distributions with sufficient diversity and properties conducive to efficiently recovering each component within the mixture. Furthermore, we establish that the sample complexity required to disentangle mixed data inversely correlates with the extent of change induced by an intervention in the equations governing the affected variable values. As a result, the causal graph can be identified up to its interventional Markov Equivalence Class, similar to scenarios where no noise influences the generation of interventional data. We further support our theoretical findings by conducting simulations wherein we perform causal discovery from such mixed data.

Learning Mixtures of Unknown Causal Interventions
Abhinav Kumar
Kirankumar Shiragur
LIDS, Massachusetts Institute of Technology Broad Institute of MIT and Harvard akumar030mit.c
Microsoft Research
Sahiragur@microsoft. com
Caroline Uhler
LIDS, Massachusetts Institute of Technology Broad Institute of MIT and Harvard
Abstract
The ability to conduct interventions plays a pivotal role in learning causal rela- tionships among variables, thus facilitating applications across diverse scientific disciplines such genomics, economics, and machine learning. However, in many instances within these applications, the process generating interventional data is subject to noise: rather than data being sampled directly from the intended interventional distribution, interventions often yield data sampled from a blend both intended and unintended interventional distributions.
We consider the fundamental challenge disentangling mixed interventional and observational data within linear Structural Equation Models (SEMs) with Gaussian additive noise without the knowledge of the true causal graph. We demonstrate that conducting interventions, whether do soft, yields distributions with sufficient diversity and properties conducive to efficiently recovering each component within the mixture. Furthermore, we establish that the sample complexity required disentangle mixed data inversely correlates with the extent change induced by an intervention in the equations governing the affected variable values. As result, the causal graph can be identified up to its interventional Markov Equivalence Class, similar to scenarios where noise influences the generation of interventional data. We further support our theoretical findings by conducting simulations wherein we perform causal discovery from such mixed data.
Introduction
Interventions are experiments that can help us understand the mechanisms governing complex systems and also modify these systems achieve desired outcomes 21]. For example, causal discovery, interventions are used to infer causal relationships between variables of interest, which has
applications in various fields such as biology 5 [2], economics [8]. and psychology
B 21).
Given their extensive applications, there has been significant research in developing methods and Despite significant efforts to develop sophisticated experimental techniques to perform interventions, they often encounter noise 4 6 30 For example, the CRISPR technology, extensively used to perform gene perturbations (or interventions), is known to have off-target effects, meaning the interventions do not always occur the intended genes 6 30). Consequently, in many applications, performing interventions generates data from a mixture of intended and unintended interventional distributions. Analyzing such mixed data directly can lead to incorrect conclusions, adversely affecting downstream applications. Hence, it is essential to disentangle the mixture and recover the components correspond- ing each individual intervention for further in downstream tasks like causal discovery.
experimental design strategies to conduct interventions under different scenarios 32 24
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In our work, we formally address the challenge of disentangling mixtures of unknown interventional and observational distributions within the framework of linear structural equation models (Linear- SEM) with additive Gaussian noise. Given iid samples from mixture with a fixed number of components as input, we present an efficient algorithm that can learn each individual component. Our results are applicable to both do and more general soft interventions.
We chose study our problem in the Linear-SEM with additive Gaussian noise framework for its fundamental importance in the causal discovery literature. Shimizu et al. 12 showed that observational data sufficient for learning the underlying causal graph when the gata-generating process is a Linear-SEM with additive non- Gaussian noise with no latent confounders. However, in the same setting with Gaussian noise, the causal graph only identifiable up its Markov Equivalence Class (MEC) [18 25). Thus, performing interventions (possibly noisy) is necessary to identify the causal graph, making it an interesting framework for our problem.
Our contributions First, we show that given samples from a mixture of unknown interventions within the framework of Linear-SEM with additive Gaussian noise, there exists an efficient algorithm to uniquely recover the individual components of the mixture. The sample complexity of our procedure scales polynomially with the dimensionality of the problem and inversely polynomially with the accuracy parameter and the magnitude of changes induced by each intervention. Our findings indicate that the recovery error for each individual interventional distribution approaches zero as the number of samples increases. Therefore, in the infinite sample regime, we can recover the true interventional distributions, even when the targets of the interventions are unknown, Second, if the input distributions satisfy strong interventional faithfulness assumption (as defined in Squires et al. (26)), we can utilize the results from [26] to identify the targets of the interventions, thereby enabling causal discovery using these accurately recovered interventional distributions. Finally, we conduct simulation study to validate our theoretical findings. We show that as sample size increases, one can recover the mixture parameters, identify the unknown intervention targets, and learn the underlying causal graph with high accuracy.
2 Prior Work
Mixture of DAGs and Interventions. There has been a lot of interest in understanding the mixture distribution arising from a collection of directed acyclic graphs (DAGs) 27 23 29 14 28). Saeed al. (33 studied the distribution arising from mixture of multiple DAGs with common topological order, thus a generalization of our problem. Their method identifies the variables whose conditional distribution across DAGs varies. However, there is theoretical guarantee for the identifiability of the mixture's is components. Like us, Kumar and Sinha [14] also studied the mixture arising from interventions on a causal graph and gives an algorithm to identify the mixture component. However, they assume knowledge of the correct topological order and sample access to the observational distribution. Thiesson et 28 also studied the problem of learning a mixture of DAGs using the Expectation- Expectation-Maxinnzzttin (EM) framework. However, there is no theoretical guarantee about the identifiability of individual components.
Learning Mixture of Gaussians. Learning a mixture of Gaussians is heavily studied problem (2] ИТ There exist efficient algorithms both in terms of runtime and sample complexity for fixed number of components in the mixture [1 15 2 Ge et al. (7] gave an efficient algorithm for the case when the number of components almost /n where n is the dimension of the variables. However, this method only guarantees identifiability in the perturbative setting, where the true parameters are randomly perturbed before the samples are generated.
Causal Discovery with Unknown Interventions. Recent years have seen the development of methods that perform causal discovery with observational and multiple unknown interventional data [16] 26, 10] Squires et al. [26] takes multiple but segregated datasets from unknown interven- tional distributions and aims to identify the unknown interventions and learn the underlying causal graph up to its interventional MEC (I-MEC). Jaber et al. [10] considers the same problem of causal discovery with unknown soft interventions in Mon-Markovian systems (i.e., latent common cause models). However, they also assume that the interventional and/or observational data is already segregated. To our knowledge, no prior works consider directly learning the causal graph from mixture of interventions.
2

---

3 Notation and Preliminaries
Notation. We use the upper-case letter X to denote random variable and lower-case "x" to denote the value taken by the random variable X. Let, the uppercase bold-face letter X denote a set of random variables and the lowercase bold-face letter denote the corresponding value taken by X. Let the conditional probability function IP(X x) Y y) be denoted by P(xxy)). We use the calligraphic letter S to denote set and |S] to denote the cardinality of the set S. Let [n] denote the set of natural numbers {1,.... nn.. For any vector v, we use the notation [v], to denote it's jth entry and for any matrix M we use [M] to denote the entry in the 7th row and jth column of M. We use R. to denote positive scalars.
Structural Equation Model (SEM) Following Definition 7.1.1 in Pearl [18. let a causal model (or SEM) be defined by a 3-tuple .M = (V. F),, where [VV..... Vn denotes the set of observed (endogenous) variables and U = -Ui,... Jn} denotes the set of unobserved (exogenous) variables that represent noise, anomalies or assumptions. Next, F denotes a set of n functions (fi...., Jn), each describing the causal relationships between the random variables having the form:
V: = (((pa(())) u.,),
where U, S U and pa(VV)
Vi) S V are such that the associated causal graph (defined next) is acyclic. A causal graph GM is a directed acyclic graph (DAG), where the nodes are the variables V and the edges U with edges pointing from pa(V,) VV) to V for all i [m].
Linear-SEM (with causal sufficiency) In this work, we study a special class of such causal models (Gaussian Linear-EMss where the function class of each fi is restricted to be linear and of the form
V = fi(pa(V.). u.) = Σ
aujy1 + UUg,
Vy (VP))(V)
where Oi * O, VV, E pa)V. The causal Sufficiency assumption states that U, = (Ut), i.e., U; is the only exogenous variable that causally affects the endogenous variable V. This is equivalent to the absence of any latent confounder (Chapter in (20). In our work, we consider causally-sufficien Linear-SEMs; with a slight abuse of nomeclature, we will call them Linear-SEM. The functional relationship between the exogenous and endogenous variables is deterministic, and the system's s stochasticity comes from a probability distribution over the exogenous noise variables U. Thus, the probability distribution over the exogenous variable P(U) defines a probability distribution over the endogenous variable P(V). Without loss of generality, let the nodes (V1.... Vn) } of the underlying causal graph be topologically ordered. Then, we can equivalently write the above set of equations as:
(I) where A, with Auj contains the causal effects between the endogenous variables. Thus, the matrix A, hereafter described as the adjacency matrix, characterizes the causal relationships between the endogenous variables (V), where Aij f 0 denotes edge between the variable V; and Vú, in G.
v Av + u
v (I A)-
Linear-SEM with additive Gaussian Noise We further specialize the exogenous variable us (henceforth referred to as noise variable) to be Gaussian with mean μı and variance d;, i.c. uy (f, a,). Thus, the joint distribution of the exogenous variables is given by multivariate Gaussian distribution u ~ (H,, D) where [μ4] = μ4; and the covariance is given by diagonal matrix D with [D]a de Thus, the endogenous variables also follow multivariate Gaussian distribution with P(v) = N(m, S), where m & Bμ, 5 A BDBT and B A (I - A)-1, Causal discovery aims to identify the unknown adjacency matrix A given observational or other auxiliary data.
Interventions. Following Definition 7.1 from Pearl [18], the new causal model describing the interventional distribution, where the variables in a set I are set to a particular value, is given by M, VU,VFFr F1). where F₁- = {f, V, & I} U {K V,2 E I} and the functional relationship of every node V; E I with their parents and corresponding exogenous variable U, is changed from fo to f.. In particular, the functional relationship of node V, is changed to
U
aij Raj'oy + u,'
(2)
Uy (V)
We will drop the subscript M when it is clear from context
3

---

where uz' ~ (pss, ( Such interventions are broadly referred to as "soft". Several other kinds of interventions are also defined in the literature, e.g., do, uncertain, soft etc. [3] We consider three different types of widely studied specializations of soft interventions in our work:
(1) shift: the mean of the noise distribution is shifted by a particular value, i.e., u4ا = (4s + K for some R. and everything else remains the same, i..., of o; and 0ij" = aij. vj [n].
(2) stochastic do (henceforth referred as stochastic): where all the incoming edges from parents are broken, i.c., ass' = O, and u,' ~ Niu'' ..)).
(3) do: in addition to breaking all incoming edges, i.e. Onj = O, we also set the variance of the noise distribution to O and the mean to any value of choice, i.e., uq ((s',)) 0).
Atomic Interventions In this work, we consider soft interventions where only one node is inter- vened at a time, i.e., I = Thus after soft intervention on node V,, the adjacency matrix is modified such that A, _ - e; - a = A - e P where cf _ (a: - a!)², af is the 7th row of matrix A and a; T is the new row after intervention such that [ailæ = 0, Ak 2 i, and e; is the unit vector with entry 1 at the jth position and 0 otherwise. Thus, the linear SEM from Eq. is:
2i (1 11-1-10 (1- A. = A e.c,) ''u) Ui
where u, ~ (p, D.). p4 p- ne for some 7/4 E R. D, = -.--d,eee where 6, A (a. -,) is a diagonal matrix with the 7th diagonal entry as o; and rest is same as D. Thus, the interventional distribution of the endogenous variables is also a multivariate Gaussian distribution, i.e., PV(V) = N(m,, S;) where m, Bi S; a B,D, and B, a (I- e,,,),
d)).
4 Problem Formulation and Main Results
In $4.1 we begin by formulating the problem of learning the mixture of interventions and then state our main result on the identifiability of parameters of the mixture. As a consequence of our identifiability result, under an interventional faithfulness assumption (Squires et al. (26)). we show in $4.2 that the underlying true causal graph can be identified up to its I-MEC using a mixture of unknown interventions, thereby obtaining the same identifiability results as in the unmixed setting.
4.1 Learning a Mixture of Interventions
We begin by formally defining the mixture of interventions over Linear-SEM with additive Gaussian noise and then state the main result of our paper mixture of interventions be uniquely identified under a mild assumption discussed below.
Definition 4.1 (Mixture of Soft Atomic Interventions). Let M == (V.UUU be an unknown Gaussian Linear SEM where the distribution of the endogenous variables is given by P(V) (see $3). Lat== (i1....,ix } hereafter referred to as intervention target set, be a set of unknown soft atomic interventions where each generates new interventional distribution VV. Then, the mixture of soft atomic intervention is defined as:
P miz (V) E ETeP Pi (V)
GNE
Tie 1, is E [m] U (0) where n = IV is the number of endogenous variables. We also allow in which denotes the setting when none of the nodes is intervened, i.e., Po(V) & IPV)). Using Eq. 3 mixture defined over a linear SEM with additive Gaussian noise is mixture of Gaussians with parameters 0 = {(m Sig, T bizz where P.g. (V) = NN
where Tip E BR., henceforth referred as mixing weight, a positive scalar such that Eier
then aim answer the following questions: (1) Does there exist an algorithm that can uniquely identify the parameters (0) of the mixture of interventions under an infinite sample limit? (2) What is the run time and sample complexity of such algorithm? It is immediate that if the intervention doesn't 't change the causal mechanism in any way, then the
Having defined mixture of interventions,
We have used the subscript "i" notation in A; to denote the adjacency matrix of the intervened distribution.
We will use similar subscript notation to represent other variables related to intervened distributions

---

interventional distribution is equal to the observational distribution, and we would not be able to distinguish between them. This discussion suggests that it necessary to put an additional constraint on the interventions performed. Below, we formally state the assumption that will ensure this and that it is sufficient for the identifiability of mixture distribution.
Assumption 4.1 (Effective Intervention). Let P. (mm,, S:) be an interventional distribution after intervening on node Us where m, = Bi Bi + Tee;), B, (I - A + e,c,) and C, = -a, - - S = B, and D, = D - ó,e,e, (see atomic intervention paragraph in 3 Then, at least one of the following holds: TR + 0 or ||c|l| # or 8; + 0.
Now, we are ready to state the main result of our work that will help us answer the above questions. For an exact expression of sample complexity and runtime, see Lemma 5.]]
Theorem 4.1 (Identifiability of Mixture Parameters). Let P min (V) y be mixture of soft atomic interventionss defined over a Linear-SEM with additive Gaussian noise with "n" endogenous variables (Definition 4.1) such that the number of components [Z] is fixed. Given Assumption 4.1 satisfied and the causal graph corresponding to M doesn't violate faithfulness, then there exists an efficient algo-
rithm that runs in time polynomial in n, requires poly nh, 1.4
min (opooo(les, l. (llpe/llleelll....... TALE (gz
samples where A is the adjacency matrix of underlying graph and with probability greater than (1 - 60 recovers the mixture parameters = {{fin,, S1, (1,,1)...... (m 21: SyZ), t 21) such that
Σ EZ
[mn. - -mp((e)) 1? + ||:i.- - (p(t + Ti. - # S s
for some permutation (1,2,.... |2| + (1, | and arbitrarily small >> 0.
4.2 Causal Discovery with Mixture of Interventions
Theorem 4.1
helps us separate the mixture of interventions Pmic (V) and provides us with the parameters [[m, St) of the distribution of all the components in the mixture. However, it does not reveal which nodes were intervened, corresponding to the different components recovered from the mixture. There has been recent progress in performing causal discovery with a disentangled set of unknown interventional distributions 26 16). Specifically, Squires et al. 26 proposes algorithm (UT-IGSP) that greedily searches over the space of permutations to determine the I-MEC and the unknown intervention target of each component. UT-IGSP is consistent, i.e., it will output the correct I-MEC as the sample size goes to infinity. Thus, combining Theorem (.1 with the UT-IGSP algorithm implies that, as sample size goes to infinity, we can recover the underlying causal graph up to its I-MEC given a mixture of interventions over Linear-SEM with additive Gaussian noise:
Corollary 4.1.1 MMixtureMEEC) Given samples from a mixture of interventions Prsse (V) over linear-SEM with additive Gaussian noise and samples from the observational distribution P(V), there exists a consistent algorithm that will identify the I-MEC of the underlying causal graph under the I-faithfulness assumption (defined in Squires al. (26)) (and restated in $A.1).
Proof. The proof follows from the identifiability of the parameters of the mixture distribution (Theorem 4.1 and the consistency of UT-IGSP given by Squires al. (26).
n
Remark. The I- I-faithfulness assumption imposes certain restrictions on both observational and interventional distributions. However, as noted by Squires et al. (26), in the case of Linear Gaussian distributions, the set of distributions excluded by this assumption is of measure zero. This is because the Linear Gaussian distributions, defined by a matrix A, that do not meet this assumption are subject to multiple polynomial construints of the form p(A)= =0)=0 O. It is well-known result that for a random matrix A, the set of matrices that satisfy such polynomial equalities has measure zero 177y.
Proof Sketch of Theorem 4.1
Here we provide an overview of the proof of Theorem 4.1 Definition 4. tells us that the mixture
of interventions defined over a Linear-SEM with additive Gaussian noise is a mixture of Gaus- sians. Learning mixtures of Gaussian is well-studied in the literature 2 15 77. Since most of
5

---

these approaches require some form of separability between the distribution of components or the parameters of the distributions, in the following lemma we will first show that the covariance matrix and the mean of any interventional or observational distribution taken pairwise is well-separated when Assumption 4.1 holds. In particular, this seperation of parameters will ensure that the Gaussian mixture can be uniquely identified using the results from Belkin and Sinha (2)
Lemma 5.1. [Parameter Separation] Let Po (V(V) denote the observational distribution of linear SEM with additive Gaussian noise "M" (see $3 @wth "n" endogenous variables. For some i.j [n] U {0}, let (VVV) = [ and F3 (V) = S,) be two interventional distributions (observational if one "i" or "j" =0). Then the separation between covariance S, and Sy and mean m, and m, is lower bounded by:
||s: - -,yl + I|m m,,13 2 J(B, D) ||ci112 + 1les11) + M(B,D. + +73)
+ + [6g] min (msi,)) + 16,51 min (15ş1, Amin
where after intervention node k E 5i ||cx|| is the norm of the perturbation (or change) in the kth row of the adjacency matrix, "Ik is the perturbation in the mean and [ōy| is the perturbation in the variance of the noise distribution of node k (as defined in the Atomic Intervention paragraph of $3). Also, B = (I A)-1, and D and I are the covariance matrix and mean of the noise distribution in M, respectively. Furthermore, "f", "g" and "h" are positive valued polynomial functions of B, p and smallest eigenvalue of D (see the proof in for the exact expressions).
Remark. one of the distributions is observational, i.e, say i = 0, then the above bound holds with |c.l = 0, Y 0, and |ō,1 = O.
Remark. Different types of interventions will allow us to change certain parameters in the above bound. Let the exogenous noise variables u, ~ NN,,,, σ.) when not intervened. Now, if we intervene on node Us then the new noise variable has distribution vi ~ NNpp + +.4,0 (.) given as follows for different intervention types:
(1) do intervention: ||a:ll + 0 if Us is not a root node, 18.1 +0 + O, and to # 0 if the value of node o; is set to any value other than pi.
(2) stochastic intervention: ||c||| # O if oe is not root node.
(3) shift intervention: # O.
(4) soft intervention is the most general case, and nothing is guaranteed to be non-zero.
Next, we restate a definition from Belkin and Sinha [2) that defines the radius of identifiability (R()))
of probability distribution. If (0) > O, this implies that we can uniquely identify the distribution.
Definition 5.1. Let Po. A E θ be a family of probability distributions. For each @ we define the radius of identifiabiity R(0) as the supremum of the following set:
{r > 0| V01 * 02. (110 01| < r, |02 0|| < <) - (Pe, Po.).
In other words, R(0) is the largest number, such that the open ball of radius R(0) around 9 intersected with θ is an identifiable (sub) family of the probability distribution. If no such ball exists, R())
Next, we restate a result from 2 adapted to our setting, which shows that there exists an efficient algorithm for disentangling a mixture of Gaussians as long as the parameters are separated, which will ensure that the radius of identifiability R(0)= > 0.
Theorem 5.2 (Theorem 3.1 in Belkin and Sinha (1). Let Prii (V) be a mixture of Gaussians
with parameters 0 {(m1, (1,,))..... (m z): Sizz. x m θ where O is the of parameters
within a ball of radius Q. Then, there exists an algoritium which given e > O and 0 < 8 < 1
and poly (n, max(? { (( ), t. Q) samples from IF Fiie (V), with probability greater than (1 6).
outputs parameter vector f = á = (mi, St, #z)..... (mizz S (I))) E such that there exists a permutation p: (1,..., [Z]] + {I,..., [I]} satisfying:
Σ (1 - m mppp)) 112 22= + ||St, 3p(re)l + |m - * #p(ce)))) S 2
KLEI
where the radius of identifiability R(0) is lower bounded by:
(R(0))² > min T if)
min(I|m, mm,ll + |S, - -s,l1), ,,]l?),minm.) min
6

---

Algorithm 1: Mixture-UTIGSP
input :mixed dataset (Pmix), observational data (Pots), number of nodes (n)), cutoff ratio (T)
output : Mixture Distribution Parameters (0), Intervention Targets (Z), causal graph (9)
1. Esstimate 0₁ _ { ((1,, S1), (βt,, Sk)] MoussianniituurMMoee(([ (Dmis for each possible number of component in the mixture i.e k E [n + 1]. Define θ _ .f...... 0x+1) be the set of estimated parameters and L {41,.... ..i....,,n+11 .I++1} mixture data corresponding to the models with different number of components.
be the tog-likelihood of the
2. To estimate the number of components in the mixture (k.) iterate over A: = (n + 1) to 2:
(a) stop where the relative change in the likelihood increases above a cutoff ratio i.e i - 1t
(b) k. = k if the stopping criteria is met otherwise l; = 1.
3. I, 9 UT-IGSP(2 (D obs Ok.) 26
return O I.
Our Theorem along with Assumption 4.1 states that for every pair i, (In) U (0)) we have ||S S + |m,-- m > 0. Also, by construction of the mixture of interventions (in Definition 4.1p. we have ग. 0, Vi E (0). This implies that the radius of convergence R(0) > 0 and thus the parameters of the mixture of interventions P(V) can be identified uniquely
given samples from the mixture distribution with sample size inversely proportional to R()).
6 Empirical Results
6.1 Experiment on Simulated Datasets
Proposition 4.1.I establishes that given samples from the mixture distribution, one can identify the underlying causal graph up to its I-MEC. To learn the causal graph, we first disentangle the mixture. Theorem 4.1 and 5.2 show that the sample complexity of our mixture disentangling algorithm is inversely proportional to various parameters of the underlying system and the intervention parameters (7, |8] and ||c]]. Our simulation study further validates our theoretical results and characterizes the end-to-end performance of identifying the causal graph with such mixture data and its dependence on the above-mentionel parameters.
Simulation Setup We consider data generated from a Linear-SEM with additive Gaussian noise, = (I-A)=1 'n (see $3), with endogenous variables and corresponding exogenous (noise) variables. Here 77 (0, D). where the noise covariance matrix diagonal with entries and α = 1 unless otherwise specified. A is the (lower-triangular) weighted adjacency matrix whose weights are sampled in the range [- 1, -0 0.55] | [0.5. 1] bounded away from O. Let g" denote the causal graph corresponding to this linear SEM with edge i - j + Aji > O. By sampling from the resulting multivariate Gaussian distribution, we obtain observational data. Next, for each causal graph, we generate separate interventional data by intervening time (atomic interventions), which is again Gaussian distribution but with different parameters (see Atomic Intervention paragraph in 3 We experiment with two settings:
diag(o* @ ..... o²)
given set of nodes in the graph one at
(1) all: where we perform an atomic intervention on all nodes in the graph.
(2) half: where we perform an atomic intervention on randomly selected half of the nodes. Then, the mixed data generated by pooling all the individual atomic interventions and observational data with equal proportions into single dataset. The decision to use equal proportions of samples from all components is solely intended simplify the design choices for the experiment setup. In our experiment, we vary the total number of samples in the mixed dataset as N E (2 2 ..... ,,'7. }. In particular, we perform two kinds of atomic interventions: "do" and "stochastic" (see Interventions paragraph in for a formal definition). The initial noise distribution for all the nodes is univariate Gaussian distribution (0, 1). In our experiments for do interventions, instead of setting the final variance of noise distribution to O, we set it to very small value of 10-9 for numerical stability. Unless otherwise specified, we perform 10 runs for each experimental setting and plot the 0.05 and 0.95 quantiles. Sce for additional details on the experimental setup.
7

---

FATY (ode::551
Parameter Estimation Errer
foersae Siillarity
DTAD ECTAPE, FOADONAR)
882
802-
RAPL
prodersa nSSe-1E)
Run rece-1K1
2010
4000
8742
20300
12108
Atore:
2001
52000
8192
2488
2023
2018
sample size
sample size
sample size
(a) num intervention all (1)
(b) num intervention all (1)
(c) intervention all (I)
Par Parameter Estimation Error
beccard Similarity
ESTARE, POOGHC4)
NATU F2
FARY pode 26.1
200
SOICTETTE Fodd
SHD
200
0.4
RATL rede- H.1
10
0.-
02
orode PARK n93eH1R)
14304
Intora
1000
2000
anse
awe
2010
staal
are
Laters
pizzed
1oare
sample size
sample
sample size
(d) num intervention half (L)
num intervention half (t)
(f) num intervention half (L)
Figure 1: Performance of Alg. 1 as we vary sample size and number of nodes: The first row
(a-c) shows the performance when the mixed data contains atomic intervention all the nodes and observational data. The second row (d-f) shows the performance when the number of atomic interventions (chosen randomly) in mixed data is taken to be half of the number of nodes along with observational data. The column shows different evaluation metrics, i.e., Parameter Estimation Error, Average Jaccard Similarity, and SHD, The symbols (?) represent higher is better, and (+) represents the opposite (see Evaluation metric paragraph in ( In summary, performance improves for both cases the number of samples increases. However, the graph with more nodes requires a larger sample to perform similarly. For a detailed discussion, see $
Method Description and Evaluation Metries Given the mixed data generated from the underlying true causal graph 9", the goal to estimate the underlying causal graph G. We break down the task into two steps. First, we disentangle the mixture data and identify the parameters of the individual interventional and/or observational distributions. Our theoretical result (Theorem 4.J) uses [2] for identifiability of the parameters of a mixture of Gaussians. Since they only show the existence of such an algorithm, we use the standard sklearn python package (19] that implements an EM algorithm to estimate the parameters of the mixture. Importantly, our experiment doesn't 't require prior knowledge about the number of components (k) in the mixture. We train separate mixture models varying the number of components. Then we select the optimal number of components using the likelihoddo curve the fitted Gaussian mixture model using a simple thresholding heuristic (see step in Alg. [ We leave the exploration of better model selection criteria for future work. For all simulation experiments, unless otherwise specified, we use a cutoff threshold of 0.07, chosen arbitrarily. In $ we experiment with different values of this threshold and show that Mixture-UTIGSE is robust to this choice. The intervention targets present in the mixture are still unknown at this step. Next, we provide the estimated mixture parameters intervention targets (UT-IGSS (6)). which internally estimates the unknown intervention targets and outputs one of the possible graphs from the estimated I-MEC. We assume that observational data is given as an input to the UT-IGSP algorithm. The proposed algorithm is provided in Alg. [ See B for our hyperparameter choice and other experimental details.
existing causal discovery algorithm with unknown
Evaluation Metrics We evaluate the performance of MixtureUTTIGSP (Alg. 1 on three metrics:
Parameter Estimation Error: This metric measures the least absolute error between the estimated parameters (mean and covariance matrix defining each individual distribution) after the first step
8

---

Table I: Performance of Alg. on Protein Signalling Dataset [22]: We evaluate the performance of Mixture-UTIGSII as we vary the cutoff ratio select the number of component in the mixture. The second column shows the number of estimated components where the actual number of components in the mixture 6. The third and fourth columns show the Jaccard Similarity of the identified intervention target of Piixture-UTIGSS and oracle versions of the UT-IGSP algorithm. The fourth and last column shows the SHD between the estimated and true causal graphs for both methods respectively. Overall we observe that at a lower cutoff threshold Mixture-UTIGSY is able to perform as well as the oracle UT-IGSP algorithm on all the metrics. See $B.2 for detailed discussion.
cutoff ratio
Estimated Component
JS
Oracle JS
SHD
Oracle SHD
0.01
4/6
0.07
0.05
0.07
2/6
0.04
0.05
18
17
0.15
1/6
0,00
0.05
16
18
0.30
1/6
0.00
0.05
18
17
avg
2/6
0.03
0.05
16.75
17.75
of Mixture-UTIGSSP matched with the ground truth parameters considering all possible matchings between the components averaged over all runs. See for details.
Average Jaccard Similarity (JS): We measure the average Jaccard similarity between the estimated intervention target and the corresponding ground truth (atomic) intervention target. We use the matching between the estimated and ground truth components found while calculating the parameter estimation error averaged over all runs. See $B.5 for details.
Average Structural Hamming Distance (SHD): Given the estimated and ground truth graphs, compute the SHD between the two graphs averaged over all runs.
Results Fig. shows the performance of Alg. iin the two settings, "all" in the first row and "half" in the second row (see Simulation setup above). The first column shows the performance of the first step of Alg. where the mixture parameters are identified. We observe that parameter estimation error decreases as the number of samples increases in both settings. As expected, larger graphs require a larger sample size to perform similarly to smaller-sized graphs within each setting.
Step 1 of our Alg. 1 only recovers the parameters (f(m;, S,) () of the components present in the mixture distribution. step 2 of our Alg. [] we call UT-IGSP (26) that identifies the individual intervention targets from the estimated distribution parameters and also returns causal graph from the estimated I-MEC. Fig. lb and Te show the average Jaccard Similarity between the ground truth and the estimated intervention targets. The colored lines denote experiments graphs with different numbers of nodes. The corresponding dotted lines show the oracle performance of UT-IGSP when the separated ground truth mixture distributions (Fig. Tb and Ie]. the oracle version performs much better compared to its non-oracle counterpart for small sample sizes 12 to 2 but performs similarly as sample size increases.
given input. As expected, in both the settings
Finally, in the third column (Fig. Ic and If), we calculate the SHD between the estimated causal graph and the ground truth causal graph G*. The SHD of the graph estimated by MixtureUTTIGSP and the oracle version are similar for different node settings and all sample sizes. This suggests that small errors in the estimation of the parameters of the mixture distribution don't 't't affect the estimation of the underlying causal graph.
Additional Experiments: In $B. we provide details on the experimental setup and additional results. In 22 we plot two additional metrics for the simulation experiments. The first metric is the number of esttmmatd components in the mixture and the second metric is the the error in estimation of the mixing coefficient. In Fig, we study the sensitivity of the cutoff ratio used by Mixture- select the number of components
to the mixture. Next, in Fig. 4 we evaluate the performance of our Alg. T as we vary the density, i.e., the expected number of edges in the graph. In Fig. 6 we show how the sparsity of the graph and other intervention parameters like the value of the new mean and variance of the noise distribution after intervention affects the performance of Alg.

---

6.2 Experiment on Biological Dataset
We evaluate our method on the Protein Signaling dataset 22 to demonstrate real-world applicability. The dataset is collected from flow cytometry measurement of 11 phosphorylated proteins and phospholipids and is widely used in causal discovery literature [31 26 The dataset consists of 5846 measurements with different experimental conditions and perturbations. Following Wang et al. [3I], we define the subset of the dataset as observational, where only the receptor enzymes were perturbed in the experiment. Next, we select other 5 subsets of the dataset where a signaling protein is also perturbed in addition to the receptor enzyme. The observational dataset consists of 1755 samples, and the interventional datasets have 911, 723, 810, 799, and 848 samples, respectively. The mixed dataset is created by merging all the observational and interventional datasets.
The total number of nodes in the underlying causal graph is 11. Thus, the maximum number of possible components in the mixture is 12 (11 single-node interventional distribution and one observational). In the mixture dataset described above, we have components observational and interventional). The second column in Table I shows that Mixture- UTIGSP recovers 4 components close to the ground truth 6 when the cutoff ratio 0.01 (step 2 of Alg. DT. Next, we give the disentangled dataset from the first step of our algorithm to identify the unknown target. Though the Jaccard similarity of the recovered target not very high (average of 0.03 shown in the last row of the third column, where the maximum value is 1.0), it is similar to that of the oracle performance of UT-IGSP when the disentangled ground truth mixture distributions were given as input. This shows that it is difficult to identify the correct intervention targets even with correctly disentangled data. Also, the SHD between the recovered graph and the widely accepted ground truth graph for Eexture-UTISSP (ours) and UT-IGSP (oracle) is very close. Overall, at a lower cutoff ratio, the performance of Mixture-UTICEE UTIGS''' performance is sensitive to the choice of the cutoff ratio on
is close to the Oracle UT-IGSP algorithm. Unlike the simulation
case (see Fig. 3 this dataset. In Fig. 5 we plot the ground truth graph curated by the domain expert alongside the estimated causal graph for visualization.
7 Conclusion
We studied the problem of learning the mixture distribution generated from observational and/or multiple unknown interventional distributions generated from the underlying causal graph. We show that the parameters of the mixture distribution can be uniquely identified under the mild assumption that ensures that any intervention changes the distribution of the observed variables. As a consequence of our identifiability result, under an interventional faithfulness assumption (Squires et al. (26)), we show that the underlying true causal graph can be identified up its I-MEC based on mixture of unknown interventions, thereby obtaining the same identifiability results as in the unmixed setting. Finally, we conduct simulation study validate our findings empirically. We demonstrate that as the sample size increases, we obtain parameter estimates of the mixture distribution that are closer to the ground truth and, result, we eventually recover the correct underlying causal graph.
8 Limitations and Future Work
Since our work is the first to study the problem of a mixture of causal interventions without assuming knowledge of causal graphs, we have restricted our attention to one particular family of causal with additive Gaussian noise. In the future, it would be interesting to study this problem for a more general family of causal models. Further, our work uses Belkin and Sinha 2 for identifying the parameters of mixture of Gaussians, which assumes that the number of components in the mixture is fixed. Recent progress in 7 gives an efficient algorithm for recovering the parameters when the number of components is almost /na where n is the number of variables. However, they only work perturbative settings, and proving the result for non-perturbative settings is out of the scope of the current paper. Finally, to identify the parameters of the mixture distribution in our empirical study, we use heuristics to estimate the number of components. It would be interesting to explore other methods to automatically select the number of components.
models--Lneer-SSE
10

---

References
[1] Joshua Angrist and Victor Lavy. Does teacher training affect pupil learning? evidence from matched comparisons in jerusalem public schools. Journal of Labor Economics, 19(2):333699 2001. URL htttps://econaapers repep coopec.ogg/.eee. ucp: jaabe::..::
p:343-69
[2] Mikhail Belkin and Kaushik Sinha. Polynomial learning of distribution families. 2010 JEEE 5/st Annual Symposium on Foundations of Computer Science, pages 103-112, 2010. URL
https: semanticscholast D : 3089712
[3] Daniel Eaton and Kevin Murphy, Exact bayesian structure learning from uncertain interven- tions. In Marina Meila and Xiaotong Shen, editors, Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, volume 2 of Proceedings of Machine Learning Research, pages 107-114, San Juan, Puerto Rico, 21-24 Mar 2007. PMLR. URL fstps://proceedingg mlr wwwps/essrveee eato///a htmml
[4] Markus I. Eronen. Causal discovery and the problem of psychological in- terventions. New Ideas in Psychology, 59:100785, 2020. ISSN 0732-118X. doi hoil:ttps://do.or///000000. www.wiieaassccc..00000000// sciencedirect com/ htt.://w........ooooo......////.
URL https://ww/
[5] Nir Friedman, Michal Linial, Iftach Nachman, and Dana Pe'er. Using bayesian networks to analyze expression data. In Proceedings of the Fourth Annual International Conference Computational Molecular Biology, RECOMB '00, page 127-135, New York, NY, USA, 2000.
Association for Computing Machinery. ISBN 1581 13660, doi [00.1145/332006333333333 URL httpp:://oi. http:://ddoooooo//////
org/10. 10. 1145/332306 3323555
[6] Yanfang Fu, Jennifer Foden, Cyd Khayter, Morgan Maeder, Deepak Reyon, J Joung, and Jeffry Sander. high-frrequeny off- target mutagenesis induced by crispr-cas nucleases in human cells. Nature biotechnology. 31, 06 2013. doi 10. 1038/nbt..622
[7] Rong Ge, Qingqing Huang, and Sham M. Kakade. Learning mixtures of gaussians in high dimensions. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. STOC 115 page 761-770, New York, NY, USA, 2015. Association for Computing URL https://:///oi org/
Machinery. ISBN 978 450335366. 1411100144//24453922746666 10.1145/2746639 2746616
[8] Lucas Girard and Yannick Guyonvarch. Bridging methodologies: Angrist and imbens' contribu- tions to causal identification. 2024. URL https:/tts////ppp Somnaaniiiccchooaarrrorr//ooooop
267760356
[9] Spencer I.. Gordon, Erik Jahn, Bijan Mazaheri, Yuval Rabani, and Leonard J. Schulman. Identification of mixtures of discrete product distributions near-optimal sample and time complexity, 2023.
[10] Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Causal dis- covery from soft interventions with unknown targets: Characterization and learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9551-9561. Curran Associates, Inc., 2020. URL htpphttttt///rreeeennges htwp://ceeeiinng..eeiieeeeeeeeee newrips.... cc/ haccc/ppe__ttee files/ieee/e Daaper_fillespppee////0000 /tpps/pppp//////ieee/ (c00sfaabeef500aa34400555522-2-3
pdf
[11] Adam Tauman Kalai, Alex Samorodnitsky, and Shang- Teng. analysis. In 2009 50th Annual JEEE Symposium on Foundations of Computer Science, pages 395-404, 2009. doi 100.0.110/0/0C000000000
Learning and smoothed
[12] Jack Kelly, Carlo Berzuini, Bernard Keavney, Maciej Tomaszewski, and Hui Guo. A review of causal discovery methods for molecular network analysis. Molecular Genetics and Genomic Medicine, 10(10), October 2022. ISSN 2324-9269.
Funding Informa- tion: This work was jointly supported by the British Heart Foundation and The Alan Turing Institute (which receives core funding under the EPSRC grant EP/N510129/1 part of the Cardiovascular Data Science Awards (Round 2, SP/19/10/34813) Publisher Copyright: C 2022 The Authors. Molecular Genetics and Genomic Medicine published by Wiley Periodicals LLC.

---

[13] K. S. Kendler and J. Campbell. sitioning the mind-body problem. Psychological Medicine, 39(6):881-887, 2009.
Interventionist causal models in psychiatry: repo-
100010017000329170800000
[14] Abhinav Kumar and Gaurav Sinha. Disentangling mixtures of unknown causal interventions. In Cassio de Campos and Marloes H. Maathuis, editors, Proceedings of the Thirty-Sevents Conference on Uncertainty in Artificial Intelligence. volume 161 of Proceedings of Machine Learning Research, pages 2093-2102. PMLR, 27-30 Jul 2021. URL https:://proceeedaiiii
mlr. ppress/v16//uumarla.... html
[15] Ankur Moitra and Gregory Valiant. Settling the polynomial learnability of mixtures of gaussians. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 93 102, 2010. URL http::///ppl.eemtttccccoooo..o. Sang/CorpusID.. 3250359
[16] Joris M. Mooij, Sara Magliacane, and Tom Claassen. Joint causal inference from multiple contexts. J. Mach. Learn. Res., (1). jan 2020. ISSN 1532-4435.
[17] Masashi Okamoto. Distinetness of the Eigenvalues of Quadratic form in Multivariate Sample. The Annals of Statistics, 1 - 765, 1973. d6110.22144o/117744422 URL https: //doi. org/10. 10. 1214 /014///s//ii /ttp//////111113/// 1176342472
[18] Judea Pearl. Causality: Models, Reasoning and Inference. Cambridge University Press, USA, 2nd edition, 2009. ISBN 052189560X.
[19] Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning in Python, Journal of Machine Learning Research, 12:2825-2838 2011.
[20] Jonas Peters, Dominik Janzing, and Bernhard Schlkopf. Elements of Causal Inference: Founda- tions and Learming Algorithms. The MIT Press, 2017. ISBN 0262037319.
[21] Donald D. Price, Damien G. Finniss, and Fabrizio Benedetti. A comprehensive review of the placebo effect: recent advances and current thought. Annual review of psychology, 59:565-90, 2008. https://///apppp swwanti semantccscoolrr
Mrrg/CorpusID::100 11316014
[22] Karen Sachs, Omar Perez, Dana Pe' er, Douglas A Lauffenburger, and Garry P Nolan. Causal protein-signaling networks derived from multiparameter single-cell data. Science (New York, N.Y.), 300551)33333 529, April 2005. ISSN 0036-8075. 1if110..1//ccincee. 105809 URL https://doi.org/ 11t....2/sscieneeeeee 11058009
[23] Basil Saced, Snigdha Panigrahi, and Caroline Uhler. Causal structure discovery from dis- tributions arising from mixtures of DAGs. In Hal Daumé III and Aarti Singh, editors, Pro- ceedings of the 37th International Conference on Machine Learning, volume 119 of Pro- ceedings of Machine Learning Research, pages mlr satec//v19//saaee220 html
PMLR, 13-18 Jul 2020. URL
[24] Ayush Sawarni, Rahul Madhavan, Gaurav Sinha, and Siddharth Barman. Learning good interventions in causal graphs via covering. In Robin J. Evans and Ilya Shpitser, editors, Proceedings of the -hith Conference on Uncertainty in Arrificial Intelligence, volume 216 of Proceedings of Machine Learning Research, pages 1827-1834 PMLR, 31 Jul-04 Aug 2023. URL
mlr, wpwess/v11// wtt.:///wwannii. 23a 23mmmml html
[25] Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvarinen, and Antti Kerminen. A linear non- non-gaussian acyelic model for causal discovery. Journal of Machine Learning Reseurch, -00000000--0030 2006. URLphttp //jmrr. wwt./ooor//.eeeee.e http://vvv//iiiii....a. html
[26] Chandler Squires, Yuhao Wang, and Caroline Uhler. Permutation- based causal structure learning with unknown intervention targets. In Ryan P. Adams and Vibhav Gogate, editors, Proceedings of the Thirly-Sixth Conference on Uncertainty in Artificial Intelligence, UAI 2020, virtual online, August 3-6, 2020, volume 124 of Proceedings of Machine Learning Research, pages 1039-1048. AUAI Press, 2020. URL http: htpp::///rocceiingg www. wtt.:p/wssss//eeeeeeeee http:///w11ee/rrreee.... html
12

---

[27] Eric V. Strobl. Causal discovery with a mixture of dags. Mach. Learn.. 112(11)4401-4222 mar 2022. ISSN 0885-6125, (60/100..007/0009440220011111114 /tt/t//ts/////
[28] Bo Thiesson, Christopher Meek, David Maxwell Chickering, and David Heckerman. Learning mixtures dag models. Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, UAI'98, page 504-513, San Francisco, CA. USA, 1998. Morgan Kaufmann Publishers Inc. ISBN 155860555X.
[29] Burak Varici, Dmitriy Katz, Dennis Wei, Prasanna Sattigeri, and Ali Tajer. Separability analysis for causal discovery mixture of DAGs. Transactions on Machine Learning Research, 2024.
ISSN 2835-8856. URL
nww/forum? A.-.LroTTT
[30] Xiaoling Wang. Yebo Wang, Xiwei Wu, Jinhui Wang, Yingjia Wang, Zhaojun Qiu, Tammy Chang, He Huang. Ren-Jang Lin, and Jiing Jiing-Kuan Yee. Unbiased detection of off off-target cleavage by crispr-cas9 and talens using pregrase-defective lentiviral vectors, Nature biotechnology, 33, 01 2015. dO 1038/nbt.3127
[31] Yuhao Wang. Liam Solus, Karren Dai Yang, and Caroline Uhler. Permutation-basse causal inference algorithms with interventions. In Proceedings of the 3 International Conference on Neural Information Processing Systems, NIPS' 17, page 5824-5833, Red Hook, NY, USA,
2017. Curran Associates Inc. ISBN 978151086096
[32] Jiaqi Zhang, Louis Cammarata, Chandler Squires, Themistoklis Sapsis, and Caroline Uhler. Active learning for optimal intervention design in causal models. Nature Machine Intelligence, 5:1-10, 10 2023. 0001000033///225--30-00199999
13

---

A Missing Proofs
A.1 I-faithfulness in UT-IGSP algorithm.
Here, we restate the assumption from Squires et al. [26 that needed for consistency of the UT-IGSP algorithm:
Assumption A.1 (Z-faithfulness assumption). Let I be list of intervention targets. The set of distributions (sobo) U (f")1z is I-faithful with respect to a DAG G if fobs is faithful with respect to and for any 1s and disjoint A, C. [p]. we have that (A SE C&|C (I((K)) if and only if (xAlEC)) = =
A.2 Proof of Lemma
Lemma 5.1. [Parameter Separation] Let Po(V) denote the observational distribution of linear SEM with additive Gaussian noise "M" (see $3 with "n" endogenous variables. For some i.j [n] U (0), , let PV(V) [mm,, Si) and 3 (V) NMm,, S.m..S) be two interventional distributions (observational if one of "1" or "j" =0). Then the separation between covariance S; and Sg and mean m, and m, is lower bounded by:
|| - S + I|m myl1 2 f(B, D) ||<||| + |1e;1l) + h(B, D. + +33)
+ (B( [6d] min (lo:), Amin (D)) + 16,1 min (1551e Amin(())
where after intervention on node l E j. ||ca|] is the norm of the perturbation (or change) in the hthh row of the adjacency malrix, "th is the perturbation in the mean and [ōy, is the perturbation in the variance of the noise distribution of node k (as defined in the Atomic Intervention paragraph of $3). Also, B = - A) and D and ş are the covariance matrix and mean of the noise distribution in M, respectively. Furthermore, " "f" "g", and "h" are positive valued polynomial functions of B. p and smallest eigenvalue of D (see the proof in $A.2 for the exact expressions).
Proof. First, we state lemma that will give us lower bound on the separation between the covariance matrix of two intervention distributions (or one could be observational.. The proof is given $A.3
Lemma A.1 (Minimum Covariance Separation). Let St and Sj be the covariance matrix of the Gaussian distribution corresponding to intervention on node V, and V, in the causal graph. Let, without loss of generality, V: topologically greater than Vj in the causal graph. Let = -I- A)-1 be the covariance matrix of the noise distribution, let BDB be the covariance matrix of the observed distribution P(V), and let c, =a; a² be the soft intervention performed on node V₁ (see for definitions). Then we have:
D Biag(or,.....
||S: S511 2 ((B, (1caa11 +1c,,13) (1cl(/+++11))))
+g(B) (10) min (164), Amin (D)) + 18,1 min (18,1, Amin (D))
one of the covariance matrices is from the observational distribution, i.e., say Sy S then the above lower bounds still holds with |cy]ll = 0 and ô, O.
Using the above Lemma A.1 and substituting the explicit form of f(B, from Eq. 19 obtain:
|| - S, 2 fBB, D) [|c|1l + +||c,11²)
+ ( [.1 min (10%), Amin (D)) + 18y| min (15g), Amin (D))
Aw
2 (D)
(D) (1c11 12 |1c;
[(B,D)
(Ic.112 + [1e;|13) + w
2
B B-11
14

---

Next, we state another lemma that will give us a lower bound on the separation of the mean of two interventional distributions (or one of them could be observational). The proof of the lemma below is given in A.5
Lemma A.2 (Minimum Mean Separation), Let my and m, denote the mean of the Gaussian distribution corresponding the intervention on node V₁ and Vj in the causal graph. Then we have:
vt 2j active
4|
1
411
wi v active and
7
S
||c/|1
m, mm-mm111 2
41|--11 7
41 B
45 . are active and
x
S ||c:12
B
B||B
0,
,47 are active and
A||Bp||2 I ||_:|1
of
4||B S 1lcy11
where v7
(cc (IcTBBul Bpl
hTd or |cT
shd 2 v -
3hal and similarly for 2
4 and vjj- If one of the means say my is from the observational distribution, i.e., m, =m = Bp. then setting 7 0 above will give the appropriate bounds and only case 2 and are applicable.
Now, From Case of the above Lemma
A.2 (Eq.
2b is active) and above equation have: 42 ,
X min (D)
cc
11 11c))11))
|| - S, + m, my 2
B 1-B1-111 11
4
B-
B
(6)
z
From Case 2 of the above Lemma A.2 (Eq. 42
vtatt Dy is active) and using
4 Byl
S
||el
1|
we
have:
min
2
(D)
c.
22
2 (D)
|S
S,1l + m| m,,1?
g+
(7)
81
4
32
B 11 B
From Case 3 of the above Lemma A.2 (Eq. 42
25 is active) and using 4 Ball
7i
I
||c/|| we
have:
min (D)lle 1
X (D)
||S: - S, + llm; m 2 <+
+ 32
(8)
8|
B-B-1
B||
|1 Bui
Similarly, for Case 4 and using
S ||c:|
and
S ||e, 1|2
have:
2
(D)?
min (D)
|| S,ll + [|m
m,
c+
(9)
32 B
B
BuI
32 B
B
Next, combining Eq. 6 7 g
we have:
72 +
||S
- + m, m 5
max
[4[ 112
32| 11
X (D)
(10)
S(B,D) D)
||:il| + ||c]]l²) + g(B D) (1881+11 +15g))
2
+ MB, D. 1) + 73))
For the case when one of the distributions is observational, say w.l.o.g. Sy and m, m, then the same analysis holds since Cj = 0 and 8, = 0 (from Lemma A. and only the analyses of case and case 4 are applicable (from Lemma A.2 thereby completing the proof.
A.3 Proof of Lemma A.1
Proof. Without loss of generality, throughout our analysis, we will assume that the endogenous variables Vi,..., Vn are topologically ordered based on the underlying causal graph. Thus, the
15

---

corresponding adjacency matrix A is lower triangular. The value of ||S; -551lll will be unaffected by any permutation of the node order in the matrix A as shown next. Let A = PAPT be the adjaceney matrix when the nodes are permuted by the permutation matrix where PPT = I. Also, let the corresponding permuted covariance matrix be $ BDB" where B = (1 - A)- = P(I - AJ PBP = 5 = PBP PDP PB pT = PBDB" pT = PSP Similarly, we have S, = P" and S, = =P PS,P". Now we have:
SS, -, [P((S - 5,) 1 |S - -
(11)
since the permutation matrix only permutes the row and column the above equation, the Frobenius norm remains the same.
First, state lemma that characterizes the covariance matrix S, of the interventional distribution. The proof of this lemma can be found in $A.4
Lemma A.3 (Covariance Matrix Update). Let (V) (mm;; be an interventional distri- bution and let the endogenous nodes VI,... V, be topologically ordered based on the underlying causal graph, then we have:
S. 1
for root node B.D.. 6,,,I. otherwise
where r; = 0; d, B, B- - B. (1 A1= is the covariance matrix of the observational distribution and D is the covariance matrix of the observational noise distribution (see Atomic Intervention paragraph in $
Thus from the above Lemma A.3 we have S; = B.DB ó,0,0q" Substituting the value of B from the above lemma again we get:
S = BDBB-B - BD v.u, DB + n و,a,
(12)
= = 1 BDBB c,e, BT -Be,c, BDB Be,e BT - o,Be, B",
where u, BB c.. v; Be, 11- = u² Du, c Sc,, Next, multiplying the LHS and RHS of the above equation with B-1 and B we get:
B B (S - B = met. DBT cee e,c, BD S,e,e.
(13)
The absolute value of k) (k E [n)) entry of this matrix is given by:
DDuce Be 111 -D =
k k+i
B S)B ex
(14)
8,.
k ==i
where in the second case of Be, and DEs ok the htth diagonal entry of the matrix D. Similarly, the (j, th entry of this matrix is given by:
[0,
kti
B SSBBS-SBB--- S)B-Tee-----
1-D B k=i
(15)
Similarly, the covariance matrix of node V, and j # i is given by:
-- 3,e,BBB Be,c, BDB + Be BT B Be,e, Bd
B -155--5BB- --
DB" cjee -,c, BD 6,e,e].
(16)
Thus the absolute value of the (i, th entry of the above matrix is given by:
e B (S, -) eul Das, Ba cy(e ex)l 0,
(17)
since we had assumed without loss of generality that V, x V e,BTc, c, 0. Similarly, the (j, th entry of this matrix is given by:
-Dicc Be
k # j k =
of B -)B-Fes es
{1) 2 BT e - 8, 1Ι
(18)
6,
16

---

where in the second case e
B" Cj O. Thus, taking the difference of the ith and 5th row of both the
matrix (from Eq. 14 15 17 and 18 and using the fact that cf Be, 0, c Be, and c/ Be;
since without loss of generality we have Vj < Vi) we obtain the following lower bound:
[B: -S)BBB 2
Σ
-S: ex +
Drac Bex)² + (n - 6:)2
Diacy Bex)² + (Dijez B² Bes + (11 8,)2
Di ee B" c, + (n - 6,)²
Dig Bele T B" eg + (nj 0j)² 2))²++ (DijeB c,)²
k=1
2 Amin (D)c B
Σ Dunese B - -8,²
Aman (D)c, B Σ Dueene BT c, + (n, - 8,)²
k=1
Amin (D)e BDB 03 + (m - -8,2
Amin (D)c BDB Cj (nj 8z)²
Amin (D)c Se; + (1) - 6.)² + Amin (D)c _h Se, + (1i - 8,)²
Amin (D)T, + (1) 6,)2 + Ami (D) + (1) 6,)
(1h + m7))
|6g|
2 Amin (D)
+
min
[0:], Amin (D)
4
4
|6
[85l. Amin (D) Am)n(D))
+
min
4
(19)
after substituting 7h Lemma that that gives us a lower bound for the second and third term. Thus, we obtain:
of Amin (S]l ny ee, Se,
Amin(S) [s),l and using
Amain (D) (Amin (1 + (11cc)13)
S, S
+
16
min (18s), (onn((D)
B 18-1113 11
4 B l
16,
min (18,), Amin(())
+
B||
(20)
2 (D) [1c/|11 ||cg 112)
16
min (105), Aman(())
+
B-1
4 B 11
|6,|
min Amin (min),)mi((D)) (D))
+
4 B
1|
and Amin ( = Amin ( since it is lower triangular matrix where all diagonal entries are 1) and || S || F || For the case when one of the covariance matrices is S corresponding to no intervention and the other is S; corresponding to intervention node V,, then from Eq. 14 and
where Xmii (S) > Amin (D)
Amin (D) (:: (ST) (S)
17

---

the following similar analysis we have:
(DRn Bex)² (11= 6,)²
mmn (D) 7t 16g1
min (6s)) Aman An))(())
(21)
man (D][c: |6:| min (Ool) Amen (D)
|| - S
thereby completing proof of this lemma.
Lemma A.4. Given X 2 0 and rj 2 0, the following inequality holds true:
Xnj
|6]
min (181.2).
Xn + (17 5)² z
+
(22)
4
4
Proof. Case 1: (6 < 0) Let a An + (1 5)2 then we have T 2 + 17 82
xy + 8
Case 2: 8 > 0 and
[0 < 8/2 or 36 38/21) Again this case 2 + + 8
Case 3: 8 > 0 and 8/2 S n v 36/2) In this case, we have T 2 An.. Also, we have 1) 8/2
T 2 A6/2 which together implies:
2 max (2n, X
(23)
An
A5
2
Thus, combining the above three cases we have the following lower bound on the value of
82
Xn
T 2
min
Xm
+
2
Xn
82
\|ō
min
(24)
[8]
(16).a).
min
which completes the proof.
A.4 Proof of Lemma
Proof. From Eq. 3 we have S; = B.D,B where B, = (I- - e;,")-= and D; = D - (a:
d.eece," D d. Since e:c is rank-1 update the (I-A) matrix, using the Sherman-
Morrison identity we obtain:
B, (1-A+ - =
(I - A)
= -1I-) A)-
1 c A)
Be,c T B
(25)
B 1+ c Be;
B Be,c, B
4 B r.q..
where r; A Be, scalar d, 2 1 + of Be, and qi A BTC, c, The scalar d, since of e, cf Be; given by the following lemma:
18

---

Lemma A.5. Let and B be a lower triangular matrix and C₁ be a vector such that c; = -0:-0 and [c)r = 0, Vi 2 (see Atomic Interventions paragraph of $ for definition), then q e, = c/ Be, = 0. Also, if c; + 0, then q: = B" + O.
The proof of the above lemma be found below after the proof of the current lemma. Next, S, is given by:
S BB,DB
BB(DD - 6,eçe, BBT
(26)
B.DBB -d B.e,e,
lerm
If the intervened node V, is one of rool nodes of the underlying unknown causal graph, then
C3 = qi = Bd c = B, = B (from Eq. 25 and thus:
B,D BDB S,
(27)
where S is the covariance matrix of the observational distribution. Otherwise, for non-root nodes, term I in the above equation is:
B,DB; = (B - -r:q )DB ((B-r:sh -r:
=DDBT -BDqrr -(BDqr) + + Dq:r?
(28)
= S -.:.. - r. +
where w; = BDq, and scalar 1/j = - Dq. Next simplifying term 2 in Eq.
26
we get:
T
Bre,(B,es)*= Be; dlee-righ' e. (Be,-riq e.)
(29)
Be,e, BT = =r
since c Be; 0 from Lemma A.5 and r; A Be, (from Eq. 25 matrix of the endogenous variables the intervened distribution given by:
Thus the covariance
- B.DB S otherwise
for root node
S
(30)
thereby completing our proof.
Proof of Lemma A.S
Showing q: * 0: We given that B is lower triangular matrix with non-
zero diagonal entries. Also, C; a, a, F 0 and [ci]e 0, Vt 2 i be that last index where C; is non-zero. Now lets look at the IB" c:le = C.. [B" ]r o 0 since B is upper triangular matrix and [c:]:- * O.
31 s.t. [ca]e # 0 and let t
Showing q. e; = 0: Be, is the 7th column of the lower triangular matrix of Be, since [cile- = 0, Vt 2
[Be,] = 0,
i
A.5 Proof of Lemma A.2
Proof. Similar to the proof of Lemma A.1 endogenous variables are topologically ordered based on the underlying causal graph such that the adjacency matrix A is lower triangular. The permutation matrix will only permute the rows of the mean vectors m, and my; hence, there will be no effect on the value of ||m: 1I
without loss of generality, we will assume that the
Now, let the mean of the Gaussian distribution corresponding to intervention on node V;, be given by (see Atomic Intervention paragraph in 3 for definition):
m, B,p, (B - Be,c, B) mee)
(31)
B B- = e,c, B) 7,e,),
where B; = (1- (1- cf B (from Lemma A.3 μ4i is the new mean vector for the noise distribution, μ is the mean vector of the observational noise distribution and we, is the update
19

---

to the mean of the noise distribution when intervening on node V, Similarly, the mean corresponding the intervened distribution on node V, given by:
m; = B, = (B - (B-Be,, B) + tee)
(32)
B (T e, (1 + 7zee).
Looking at the nth entry of the vector B B-1m;, we get:
e B m. = = c/ Bu + 7/- Be
(33)
and the 7th entry of the vector B 1 mm given by:
e B B = e
mj
(34)
Similarly, the 5th entry of the vector B m, is given by:
B m: e/ u
(35)
and the jt entry of the vector B B-; is given by:
7 aup+n) e B m, = = - B, Bu
Be,
(36)
Thus, the difference in the mean of both distributions can be lower bounded by:
|B 'm: m2; (7+ Bn)² + (7g cς Bu)²
(37)
Now based on the value of 1r/s and |o] BuJ, we have:
+ c Bul 1xsl
or Ic Bul
(7s - Bp)
(38)
0,
Bu
3lml 2
where eitt and v are used to denote two different mutually exclusive different events for ease of exposition later. In the case when v,. true, we have:
y s (c. Bu) = ||
Schchy-Schwwrz)
4
(39)
2
- |.,.122
4|| 2 2
Similarly, we have:
T 4 Bul
2
< 1ad
or c Bul 31
(7H - Bu)² >
2
(40)
0,
45
hil
s lef
Bp < 2
3/1l
2
and in the event when uij true, we have:
3 < (cF s ||,|1B||B||@
(Cauchy-Schwarc
4
(41)
7/
< ||e ?|
B
Combining Eq. 38 and
40 and using B -m, (m,
mz)ll= S 1|B |m] mylle we have:
vi : 15 are active
All
B
vi by are active, Eq. holds
m, - 1-m m1 2
4 13
(42)
B 2
o of are active, Eq.
39 holds
11
0,
d by are active, Eq
39 and 41 holds.
20

---

For the case when one of the mean say m, is observational then:
m, m Bu
(43)
B B-1m, μ..
Thus the 1th and nthh entry of my is ef μ and e] μe, respectively. Thus using Eq. 33 and 35 get:
|B- (m: m, >1 2 (+i c/ Bp)²
(44)
Then again, following a similar analysis as in Eq. 38 and 39 we have the following cases:
v. is active
m: m
(45)
0.
v is active, Eq. 39 holds,
which equivalent to say that only case and 4 are applicable in Eq. 42 This completes the proof.
B
Setup and Additional Empirical Result
B.1
Experimental Setup Discussion Simulation
Random Graph Generation: As mentioned the Simulation setup in $6 we randomly generate the adjacency matrix A of the causal graphs used simulate the mixture distribution. All the weights in the adjacency matrix are sampled in the range [-1, 0.55 U [0.5, bounded away from zero. This gives us a complete graph of all nodes. Thus, introduce sparsity in the graph, we only keep an edge with probability Ç by setting the corresponding value in the adjacency matrix to zero if the edge is removed. Unless otherwise specified, set Ç 0.8 for all our experiments.
Step of Alg. T:
We use the Mixture class from the scikit-learn Python package to disentangle the components of the mixture. For all our experiments, use the default tol 10-3 used by GaussianMixture to decide on convergence of the underlying EM algorithm.
Step 2 of Alg. T We run the UT-IGSP algorithm in Step 2 of our Alg. Tiih the standard parameter mentioned the documentation. Specifically, we use a = 10-3 3 for both MemoizedC[fester and Memoizedlnvaaianceeeee functions used by UT-IGSP.
Specific to results Appendix Unless otherwise specified, for all the results in the appendix we run all the experiments for 5 random settings. We ignore the error bars in the appendix for clarity in exposition. Also for all the experiments, the half-intervention setting i.e. where the mixture contains intervention on half of the randomly selected nodes is considered.
B.2 Experimental Setup Discussion Biology Dataset
Dataset: the interventional data the signaling protein is also perturbed along with the receptor enzymes. The different perturbed signaling proteins (along with the number of samples corresponding) are: Akt (911), PKC (723), PIP2 (810), Mek (799), PIP3 (848). The observational data contained 1755 samples so overall 5846 samples were used for our experiments. For details see Wang et al. [3] and Sachs al. 22
B.3 Code
The source code to all the experiments can be found in the following GitHub repository: http://gghhbb.com/ggggaaagg////p
B.4 Computational Resources
We use an internal cluster of CPUs to run all our experiments. run 10 random runs for each the experimental configurations and report the mean (as points) and 5th and 95th quantiles as error bars for all our experiments in the main paper, and we report only mean the mean for the experiments in the appendix to declutter the figures.
21

---

num (4)c-(4.)
Mixing Weight Estimation Erro
0.7
(odo-(4.)
#Estimated Component
(um_node--6.)
num_ (G)
num (8))-(8))
0.6
(B)e
0.5
0.4
0.2
0.0
1024
2040
40986
8192
16184
32768
65536
131072
262144
524288
1049576
3024
2048
40/66
B192
16384
32768
45536
131072
262144
524288
1048576
sample size
sample size
(a) num interventions all
(b) num interventions
6.5
num node-(4.)
Mixing Weight Estimation Error
num node-(4.)
numunode-(6.)
0.25
(um_node-16.)
#Estimated Component
num (ode-(8.)
(8.e
5.5
0.20
0.15
0.5
0.10
1.5
1024
2048
4098
8192
16364
32768
65536
131072
202144
$24200
1648576
1924
2048
4096
6192
18384
32768
45536
131072
202144
524238
1648576
sample size
sample size
(c) num interventions = half
(d) num interventions = half
Figure 2: Other Evaluations Metries for the simulation experiments in Fig. 1 The top row denotes the corresponding metries for all interventions in the mixture setting and the bottom row to the half setting. The first column shows the number of components estimated by algorithm Mixture- UTIGSP. For the all setting, the actual number of components corresponding to the system with nodes 4,6 and are 5,7,9 respectively (one intervention each node observe that MixtureUUTIGSP is able to correctly estimate the number of components even with small number of samples. Similarly, for half setting, the actual number of components corresponding to the system with nodes 4,6 and 8 are 3,4,5 respectively (intervention on half of node and one observational distribution). Even for this case Mixture-UTIGSP UTIGSP is able correctly estimate the number of components. The second column shows the error in the estimation of the mixing coefficient (TH''s 's, see Definition 4.1). For both cases, we observe that the error in the estimation of the mixing coefficient goes to zero as the sample size increases.
observational distribution). We
B.5 Evaluation Metric
Parameter Estimation Error Given the mixture distribution, the first step of our Alg. eestmaates the parameters of every interventional and observational distribution present in the mixture (mixing weight T. mean m, and covariance matrix S,). Alg. [ returrs the maximum number of possible components, i.e. A searching over the number of components for future work. To calculate the parameter estimation error, we first find the best match of the estimated parameters with the ground truth parameters based on the minimum error between the mean and covariance matrix. More specifically, let ke be the ground truth number of components in the mixture. Then, we iterate over all possible k- sized subsets of the estimated parameters and choose one with the smallest absolute error sum between the mean and covariance matrix. Formally:
+ 1, by default. For all our experiments, we used this default value and left
Parameter Estimation Error min
Σ
(m: m -p SS: perm([n+1]) (46)
22

---

Parameter Estimation Error
Average Jaccard Simil arlyy
0.7
Culert natoora 65
cutettrate-13 A
3.4
culert natlowdd.e..
20
2.5
20
0.4
and catantt
SHD
0.3
9.2
1026
2040
4090
01g
18.94
327145
69:36
122073
201444
104877
8.
1024
2049
4006
18284
82766
6530
13302
142
5043as
1040176
2006
4095
81g2
18,04
52784
09716
231079
202164
$14226
1040776
sample size
sample Size
sample Size
Figure 3: Performance of Alg. as we change the cutoff ratio used for automatic component
selection: We consider graphs with 6 nodes in this experiment with half intervention setting. In step 2 of Mixture-UTIGSE we select the number of components using the log- likelikoooodd curve. We scan the curve starting from the mixture model with the largest number of components to the smallest and stop where the relative change the likelihood increases above a cutoff ratio (to select the elbow point of the curve). The cutoff ratio in the algorithm is chosen to be an arbitrary number close to zero. Here we compare the performance of Mixture-UTIGSP on all three metrics for the half setting of Fig. a we vary the cutoff ratio. We observe that for the cutoff ratio close to zero i.e. 0.01, 0.15,0.3 the performance remains similar showing that the model selection criteria are robust to the selected cutoff ratio. The number of nodes
where perm((r + 1I) represents all possible permutations of the indices [0, I,...., n] and p² is the corresponding permutation with the minimum error.
Average Jaccard Similarity (JS) In step 2 of our Alg. | UT-IGSS estimates the unknown inter- ventional targets for each of the individual components disentangled in Step 1. We the same matching (p*) found in the parameter estimation error step (as mentioned above) to calculate the Jaccard similarity between the estimated and ground truth intervention target for that component. Formally:
K JS( bp(t))
1 k.
t E
Avg. Jaccard Similarity
A
(47)
1
14 ut G
where t, is the ground truth intervention target set and &y is the estimated target set. For the case when both 4 = f = Φh then [t f.)= &
23

---

Parameter Estimation Error
aerogge Jaccard Simi Similarity
20
4098
24384
2270d
adttte
121072
20144
$24288
1048776
2008
Kode
M122
14208
20780
13002
202164
524208
1048076
2024
2018
8192
20104
9270n
sample size
sample
sample
Figure 4: Performance of Alg. as we change the density of the underlying true causal graph:
The mixture data contains atomic interventions on all nodes well as observational data (half setting as described in the results in 3 The column shows different evaluation metrics, i.e., Parameter Estimation Error, Average Jaccard Similarity, and SHD (see Evaluation metric paragraph $ In this experiment, we vary the density of the underlying causal graph by keeping the edges in fully connected graph with fixed probability, labeled as density the legend of the above plots (see random graph generation paragraph in $B.1 for details). The maximum possible density is 1, i.e., the probability of keeping an edge is 1, corresponding to a fully connected graph, and the lowest possible density is O. We observe that the density of the graph increases, require more samples to achieve similar performance to less dense graphs on all three metrics. Our Theorem 4.I shows that the sample complexity required for estimating the parameters of the mixture is proportional the norm the adjacency matrix || and as the density of the graph increases ||A|] increases. Thus, as the density increases, require more samples to achieve similar performance in estimating the parameters of the mixture, as seen the parameter estimation error plot above.
PLCs
PLCP
PLCS
Mik
Mel
Mck
Raf
Raf
Rar
INK
JNK
JNK
p38
p38
pis
PKC
PKC
PKC
(a) Domain Expert Graph
(b) Mixture- -UXtUPe-UTIGSP UTIGSP (Ours)
UTIGSP (Oracle)
Figure 5: Ground truth and estimated causal graph for Protein signaling dataset 22 Fig 5a
:
the graph created with the help of domain experts for this problem [1I. 5b shows the graph estimated by our Mixture- PUtture-UTIGSP and [cc is the graph estimated by oracle UT-IGSP when they given the ground truth disentangled mixture. The blue colored arrow in 1b and Ic shows the correctly recovered edges in the domain expert graph. Green shows the edges with the same skeleton in the domain expert graph but in reversed direction. The red shows the edges that incorrectly added in the estimated graph. We observe that MixtureUTTGGS correctly identifies two more edges (PKA->ERK and PKA-> Akt) compared an oracle which could be due randomness in the UTIGSP algorithm. For this estimation, the best-performing cutoff of 0,01 was selected (see Table [
24

---

300
Parameter Estimation Error
TEn robe 1221
Similariay
0.7
TEn roba Sreae 1330
250
0.5
12300.)
SHD
150
0.3
100
Average
0.2
50-
1024
2048
4004
0.92
14:34
52700
03336
121072
201144
324
1040776
2014
2045
1022
12705
63336
191072
20214
$24/20
1014
2018
18306
2270d
e3.346
121072
202144
$24/24
1040777
sample size
sample size
sample size
(a) Varying the mean of noise distribution (%x(): The initial mean of noise distribution is 0.0 for the nodes. Upon intervening on a node to generate the interventional distribution, we change the mean of the noise to a different value. The variance of the noise distribution of the intervened node is kept the same as the initial distribution Le. 1.0. From Theorem 4.1 we expect that the new increases further from the initial mean 0.0. the parameter estimation error should lower given sample size and lead to better performance intervention target estimation and causal discovery. As expected, the setting with the smallest change in the mean of the noise distribution (blue curve) has the worst performance, The case when the new noise mean is unexpected increase in parameter estimation error.
10.0 (orange curve) unusual where
Parameter Estimation Error
14000-
8E00.1
Average Jaccard Similarity
0.7
0.6
ricked seredto0... Eaw ricke ((UA0
Eom Fickae o33
Fible spr-thh 38932
10
molee warv Dut nole Iaku (000)
role warii (E0L. ton bater pariEELL
(02-11-338..1
0.5
10000
0.4
2.3
5000
2000
1034
2015
409
6102
3016
65500
131072
20224
524285
1848570
1034
2006
1030
92168
45036
121073
302144
526088
7046576
1014
2014
now
8302
1014
121072
202244
Sucia
1o4157
sample size
sample size
sample size
(b) Varying the variance of noise distribution ()o:): The initial variance of noise distribution 1.0 for all nodes, and we change the variance of the new noise distribution upon intervention in this experiment. The mean of the noise distribution of the intervened distribution is kept the same as the initial distribution i.c. 0.0. From Theorem 1.
that sample complexity recover the parameters of the mixture distribution is inversely proportional to the change in the noise variance [6.). Thus, we expect that the performance Alg. 1 should improve as the new noise variance moves away from the initial noise variance 1.0. We can see in the above plot that the performance of the green curve (6; = 0) is worst in terms of the Jaccard similarity and SHD of the recovered graph, validating our expectation. Parameter estimation cannot be directly compared since as the variance increases, the norm of the covariance matrix increases, and thus, the overall error in the estimation error increases. observe that compared to changing the mean (Fig. 6a increasing the variance gives slightly lower performance gains.
Figure 6: Performance of Alg. 1 as we change different parameters of interventions: We consider graphs with 6 nodes in this experiment. The mean of all noise distributions without any intervention is 0.0, and the variance is 1.0. The mixture data contains atomic interventions on all nodes and observational data (half setting as described results in $6. The column shows different evaluation metrics, i.e., Parameter Estimation Error, Average Jaccard Similarity, and SHD (see evaluation metric paragraph in $6). From Theorem |.1] we observe that the sample complexity for recovering the parameters of the mixture is inversely proportional to the change in the mean of the noise distribution of and change the variance of the noise distribution | In this experiment, we vary these two parameters one at time and empirically validate this observation.
25

---

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

---

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

---

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

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
See $B
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:p/pw...eeeoooooo/oooo/o/aaa
Answer: [Yes]
Justification: Yes, we do.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We theoretically study the problem in simple setting that might not be directly applicable in real-world scenarios.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
29

---

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

---

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


Reviews:
[{"review_id": "UTsxH0JsVJ", "reviewer": "Reviewer_583w", "summary": "This paper considers a setup where an intervention results in obtaining iid data from a mixture of multiple interventional data and observational data and the goal is to learn the mixing weights and the resulting interventional distributions. Particular focus is on the linear SEM setting with Gaussian noise where interventions are allowed to be soft with some restrictions. The goal is to then learn the mixing weights and the interventional distribution (all multivariate Gaussians) parameters without knowledge of the causal graph. Given the large amount of literature on learning mixtures of Gaussians, it only remains to be shown that the individual components are well-separated in terms of changes in the interventional distributions.", "questions": "1. Theorem 4.1 is an existence theorem and in the experimental section, EM is used to learn the parameters. Given that the polynomial time guarantee includes information about A, how would we claim to not requiring knowledge of the causal graph?\n2. While misspecifying k for the 'half' interventions case is indeed a feature, is there an improvement if k is correctly specified. Currently, it's not completely clear to me that the error goes down in (d). \n3. Is there any intuition for why when SHD and Jaccard similarity metrics improve, the parameter estimation error still does not? See nodes = 8 in half interventions case.", "limitations": "The authors have addressed limitations in a separate section.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Interventions in the real world turn out to be messy and this paper continues on the thread of research that deals with unknown interventions. The paper is well-written with a clear flow of ideas. The numerical evaluations are also thorough.", "weaknesses": "While I understand that this is the first step in learning mixtures of interventions, I believe that it has limited novelty both conceptually and technically since it largely follows from existing work on learning Gaussian mixtures. The considered setup also assumes unconfoundedness on top of linear SEMs and Gaussian noise. Few more detailed questions follow in the next section.\n\nThe experimental evaluation is also limited to simulation data which don't completely endorse the validation of the algorithm. See next section on suggestions/questions. \n\nThe writing can be more careful. There are typos in the main assumption (4.1) and there's some confusing notation about the high probability delta and the difference in variance delta_i.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and thoughtful comments. Below, we answer the weaknesses and questions raised by the reviewer.\n\n> **Weakness**:\n\n**Limited Novelty**:  While we agree that our work builds on top of existing work but doesn’t follow immediately from them. To invoke these existing results on learning Gaussian mixtures, we do indeed make some non-trivial contributions, which we highlight below:\n1. To invoke existing learning Gaussian mixture results, one needs to show the separation between distributions corresponding to the mixture components. In our case, the mixture components correspond to interventional distributions, and it is non-trivial to show separation between them. We wish to emphasize that this separation depends on the type of interventions one performs. Through careful analysis, our work shows that the mean and covariance of interventional distributions are well separated for a more general class of soft interventions. \n2. In addition to the above, one of our other major contributions comes in modeling a real-world setting. Although the contributions in our work are a first step towards solving the practical problem, nevertheless, we believe it is an important first step. \n\n**Experimental Evaluation**: Please see the answer to Question 2. We have also added a new experiment in which we automatically select the number of components that improves the parameter estimation error in Fig 1d of the main paper (see answer to Question 3 below). \n\n\n**Writing Comment**: We thank the reviewer for pointing this out. Yes, the variance $\\delta_i$ and the probability $\\delta$ are different. We will update the main paper to incorporate the reviewer’s suggestion.\n\n\\\n\\\n> **Questions**:\n\n**Question 1**: \nPlease note that Theorem 4.1 states that the **sample complexity** of the algorithm is polynomial in the norm of the adjacency matrix (A) but not the runtime as you stated. **The algorithm doesn’t explicitly use the knowledge of the adjacency matrix “A”**. The dependence of sample complexity on \"A\" characterizes the problem difficulty, i.e., depending on the problem, we will require a different number of samples to get the desired accuracy. Also, the algorithm is consistent, i.e., it will recover the correct parameters under an infinite sample limit. \n\\\n\\\n**Question 2**:\n1. Fig 1a-c shows the setting when the number of components is correctly specified, i.e., k=num_node +1, and the number of components in the mixture is also num_nodes +1. In this case, we see a clear improvement in the parameter estimation error (Fig 1a). Fig 1d-f corresponds to the setting where the number of components is misspecified, i.e., k=num_node+1 and number of components = num_node/2+1. This is mainly due to mispecified number of components in the mixture. Below, we fix this.\n2. **Automated Component Selection**: We have added results with a new version of our algorithm (Mixture-UTIGSP), where we automatically search for the number of components in the mixture (please see global comment **Automated Component Selection** for details). Evaluating the “half-setting,” where the number of components in the mixture is (num nodes +1)/2, we observe that:\n    1. The number of components found by this method is also close to the correct value. \n    2. The parameter estimation error goes down to zero for all the nodes, unlike Fig 1d in the main paper. The other metrics, like SHD, still have the same decreasing trend.\n   3. Please refer to Figure 2 in the **additional pdf document** attached to the global comment for the parameter estimation and SHD plot before (Fig1d and 1f from the main paper) and after this improvement. \n\n\n**Question 3**: \nThe parameter estimation error is high in the second setting (num intervention = half, Fig 1d-f of main paper) due to the misspecified number of components (k=num nodes+1). To remove this problem, we have modified our algorithm to automatically select the correct number of components in the mixture (please see **Automatic component selection** paragraph in Global comments and answer to Question 2). In summary, with the modified algorithm, the parameter estimation error goes to zero, Jaccard similarity increases, and SHD decreases to zero as the sample size increases.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BVsCu1HGEC", "reviewer": "Reviewer_mSnK", "summary": "The paper proposes linear structural equation models with additive Gaussian noise to address the challenge of disentangling mixed interventional and observational data. The problem is highly relevant to real-world applications with mixed data.", "questions": "See Weaknesses.", "limitations": "* The method focuses on linear structural equation models with additive Gaussian noise only, and the theoretical guarantees rely on the linear- SEM assumptions, which may limit the method's applicability in practice.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The theoretical framework is robust, with clear assumptions and derivations. The paper provides theoretical guarantees on the identifiability of mixture parameters.\n\n* The key idea is clearly explained and easy to follow.", "weaknesses": "* The use of linear structural equation models is well-established in recent literature. Implementing SEMs with unknown interventions is not a novel approach.\n\n* The identifiability guarantees rely on the assumption of soft interventions. This assumption may restrict the broader applicability of the model.\n\n* The proposed method lacks sufficient experimental support. And it seems that the proposed method is primarily validated through simulations in the experiments, is it possible to provide real-world data examples?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and thoughtful comments. Below, we answer the weaknesses raised by the reviewer.\n\n\n**Weakness 1**: \n\nWhile we agree that the linear SEMs with unknown interventions are a relatively well-studied problem, we wish to highlight that our setting is different as we work with a mixture of multiple unknown interventions. Given such a mixture, our goal is to disentangle this mixture and recover the parameters corresponding to the mixture components. **To the best of our knowledge, no other work exists that aims to solve this problem of disentangling the mixture of unknown interventional distributions in the setting of linear SEMS with Gaussian noise**. Furthermore, in this setting, our work lays out the first theoretical foundation on the identifiability of the individual components in the mixture. \n\nWe would like to restate the fundamental importance of this setup in the causal discovery literature (also stated in the Introduction, Lines 40-46 of the main paper). Shimizu et al. [1] showed that observational data is sufficient for learning the underlying causal graph when the data-generating process is a linear SEM with additive non-Gaussian noise with no latent confounders. However, in the same setting with Gaussian noise, the causal graph is only identifiable up to its Markov Equivalence Class (MEC). Thus, performing interventions (possibly noisy) is necessary to identify the causal graph, making it an interesting framework for our problem.\n\nWe also wish to remark that some prior works do study a more general problem of disentangling the mixture of multiple unknown directed acyclic graphs. However, there are no theoretical guarantees about the identifiability of individual components in this setting (please refer to the Mixture of DAGs and Intervention paragraph in Section 2 of the main paper). \n\n\\\n\\\n**Weakness 2**: \n\nSoft interventions are a very general form of intervention that subsumes most of the widely studied interventions in the literature, such as shift, stochastic do, and do (please also see Lines 134 to 139 for this specialization). Therefore, we believe that studying soft interventions would indeed have a much broader applicability. \n\n\\\n\\\n**Weakness 3**:\n\n We have run our algorithm on a real-world protein signaling network dataset. In summary, our method performs equivalently on all the metrics compared to the Oracle algorithm, which has access to the disentangled data (please refer to the **Evaluation on real-world dataset** paragraph in the Global comment for details). Also, in the **additional pdf document** attached to the global comment, we provide the ground truth graph and the estimated graph for both the algorithms. The causal graph estimated by our algorithm is very similar to the graph estimated by the oracle. \n \n\nAlso, we have added results with a new version of our algorithm (Mixture-UTIGSP), where we automatically search for the number of components in the mixture (please see global comment **Automated Component Selection** for details). Evaluating the “half-setting,” where the number of components in the mixture is (num nodes +1)/2, we observe that:\n1. The number of components found by this method is also close to the correct value. \n2. The parameter estimation error goes down to zero for all the nodes, unlike Fig 1d in the main paper. The other metrics, like SHD, still have the same decreasing trend.\n3. Please refer to Figure 2 in the **additional pdf document** attached to the global comment for the parameter estimation and SHD plot before (Fig1d and 1f from the main paper) and after this improvement. \n\n\n**Limitations 1**: \n\nWe agree that the linear SEM with Gaussian noise is restrictive and may not apply to many real-world settings.  \nHowever, even with these assumptions, the problem we study in our work is non-trivial and poses several challenges. \nExtending our results beyond the linear SEM setting would help broaden the applicability of our results. We believe that studying these questions is a very important future research direction, and we would like to consider our work as a first step in this direction. Also, in answer to the **Weakness 1** above, we motivated our choice to study Linear SEM with Gaussian noise.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2tXK9YqPT7", "reviewer": "Reviewer_nhPx", "summary": "The paper proposes a method to disentangle the observational and interventional data under linear SEM with Gaussian noise.", "questions": "1) Could you please elaborate on how realistic the problem setting is? Especially concerning the noisy intervention setting [6, 28], how compatible is the paper's problem setup with these real-world scenarios?\n\n2) Could you please elaborate on the connection between your proposed method and existing literature on learning mixture of Gaussians?", "limitations": "Yes", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The algorithm proposed in this paper efficiently disentangles components of mixtures arising from unknown interventions, accommodating both soft and hard interventions. The proposed method is supported by thorough theoretical analysis. Additionally, the paper is well-written and easy to follow.", "weaknesses": "The experiments are not comprehensive enough to thoroughly assess the effectiveness of the proposed method. More experiments on real-world datasets are required. This is especially necessary since the problem setup for the mixture of interventions is a bit restrictive. Also, it would be interesting to analyze how the method empirically performs on datasets that are not generated from Linear SEM or do not have Gaussian noises.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and thoughtful comments. Below, we answer the weaknesses and questions raised by the reviewer.\n\n>Weakness\n\n**Weakness 1: Experiment on the real-world dataset:** \n\nWe have run our algorithm on a real-world protein signaling network dataset. Our method performs equivalently on all the metrics compared to the Oracle algorithm, which has access to the disentangled data, unlike us (please refer to the **Evaluation on real-world dataset** paragraph in the Global comment for details). Also, In the **additional pdf document** attached to the global comment, we provide the ground truth graph and the estimated graph from both algorithms. \n\n\\\n\\\n**Weakness 2: Experiment with Linear SEM with non-gaussian noise:** \n\nThe main motivation for our work comes from the problem of causal discovery. In general, one can only identify the causal graph up to their Markov Equivalence Class using only observational data. Thus, we need interventional data to fully identify the causal graph.  The intervention targets are sometimes noisy, so we can only obtain a mixture of interventional data.\n\nHowever, Shimizu et al. [1] showed that observational data is **sufficient for learning the underlying causal graph when the data-generating process is a linear SEM with additive non-Gaussian noise** with no latent confounders.  They also proposed an algorithm (LINGAM)  that uses Non-Linear ICA over observational data to identify the causal graph. Thus, Linear SEM with non-gaussian noise doesn't require interventional data to identify the underlying causal graph. Hence, studying the mixture of interventional distribution for this framework is an interesting problem outside the scope of current work.\n\n\\\n\\\n>Questions\n\n**Question 1**: \n\nThe work from [6,28] has shown that CRISPR gene editing technology has an off-target effect. Also, the off-target effect can be random, i.e., every off-target effect could be different. For example, Aryal et al. [2] have shown that the same gene editing experiment on mice embryos exhibited different off-target cleavage for different mice. Thus, the observed data can be a mixture of multiple off-target interventions as modeled in our work. To perform any downstream task, one needs to identify the unknown intended target and disentangle the mixture distribution, which is also the main goal of our work. \n\n\\\n\\\n**Question 2**: \n\nIn our work, we study the problem of disentangling a mixture of unknown interventions on Linear SEM with Gaussian noise, a special case of learning Gaussian mixtures. We remark that learning Gaussian mixtures is a well-studied problem with a rich literature (check Section 2), and our work builds upon these existing results. To invoke existing learning Gaussian mixture results, one needs to show the separation between distributions corresponding to the mixture components which is non-trivial. In our case, the mixture components correspond to interventional distributions, and one of our main contributions is to show the separation between them. We wish to emphasize that this separation also depends on the type of interventions one performs, and in our work, through careful analysis, we show the mean and covariance of interventional distributions are well separated for a more general class of soft interventions. As a consequence of our separation result, we show that the intervention targets and parameters of the international distribution can be recovered.   \n\\\n\\\n[1] Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvärinen, and Antti Kerminen. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(72):2003–2030, 2006\n\n[2] N.K. Aryal, A.R. Wasylishen, and G. Lozano. Crispr/cas9 can mediate high-efficiency off- target mutations in mice in vivo. Cell Death and Disease, 9, 2018", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6WKXjRoogL", "reviewer": "Reviewer_SSWb", "summary": "This paper explores the challenge of disentangling and identifying causal relationships in situations where interventional data is noisy and mixed with both intended and unintended effects. It focuses on applying interventions within linear SEMs with Gaussian noise without prior knowledge of the true causal graph.  It presents an efficient algorithm that can learn and separate individual components of a mixture of unknown interventions, allowing for the recovery of true interventional distributions even when intervention targets are unknown.", "questions": "1. I suggest improving readability by properly describing insights related to theorems, even though some of the proofs focus on matrix computations.\n2. In the experimental setup, what would be the effect of different variances in Gaussian noise?\n3.There might be some symbols used incorrectly:\nIn line 104, \"the edge U\" should be checked.\nIn line 128, the definition of M_I needs verification.\nIn line 134, the letter \\(\\kappa\\) is used when mentioning shift interventions, but \\(\\gamma\\) is used below. I know that do-interventions also change \\(\\gamma\\), but I suggest keeping the notation consistent.\nIn line 279, \"A_{ij} > 0\" should possibly be \"|A_{ij}| > 0\".", "limitations": "The author has explained the limitations of the study. This paper has no possible negative social impact.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper addresses a relatively unexplored problem of disentangling mixed interventional and observational data within linear SEMs without prior knowledge of the causal graph. This is a challenging problem with significant implications for causal inference, making the study innovative and important for the field.\nThe authors propose an efficient algorithm that leverages the properties of linear SEMs with Gaussian noise to recover individual components of the mixture. The methodological approach is rigorous, with detailed theoretical support including proofs of identifiability and sample complexity. This thorough theoretical treatment provides a solid foundation for the claims made in the paper.\nThe paper is well-structured with clear explanations of the problem, methodology, and results.", "weaknesses": "The methods developed in the paper are specific to linear SEMs with Gaussian noise, which might limit their applicability in scenarios where these assumptions do not hold. Non-linear relationships or non-Gaussian noise structures, which are common in many real-world datasets, may not be adequately addressed by the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and thoughtful comments. Below, we answer the weaknesses and questions raised by the reviewer.\n\n>Weakness\n\n**Weakness 1: Experiments**\n\n*Experiment on the real-world dataset:* We have run our algorithm on a real-world protein signaling network dataset. Our method performs equivalently on all the metrics compared to the Oracle algorithm, which has access to the disentangled data (please refer to the **Evaluation on real-world dataset** paragraph in the Global comment for details). Also, In the **additional pdf document** attached to the global comment, we provide the ground truth graph and the estimated graph from both algorithms. \n\n*Experiment with Linear SEM with non-gaussian noise*: \nThe main motivation for our work comes from the problem of causal discovery. In general, one can only identify the causal graph up to their Markov Equivalence Class using only observational data. Thus, we need interventional data to fully identify the causal graph. The intervention targets are sometimes noisy, so we can only obtain a mixture of interventional data.\nHowever, Shimizu et al. [1] showed that observational data is **sufficient for learning the underlying causal graph when the data-generating process is a linear SEM with additive non-Gaussian noise** with no latent confounders.  They also proposed an algorithm (LINGAM)  that uses Non-Linear ICA over observational data to identify the causal graph. Thus, Linear SEM with non-gaussian noise doesn't require interventional data to identify the underlying causal graph. Hence, studying the mixture of interventional distribution for this framework is an interesting problem outside the scope of current work.\n\n\n\\\n\\\n>Questions\n\n**Questions 1**: We thank the reviewer for this comment. We will add the intuition behind the proofs in the final version of the paper.\n\\\n\\\n**Question 2: (Effect of different variance in Gaussian noise)**\n \nWe have an ablation experiment in Fig 5b of Appendix B.4, where we study the effect of changing the variance of the noise distribution post-intervention. The initial variance of the noise distribution of every node is 1.0, and post-intervention, we set the variance of the intervened node to take values from the set $\\{0.1,1.0,4.0,8.0\\}$. If the final noise variance (after intervention) is close to the initial noise variance (1.0), then the Jaccard similarity and SHD of the estimated targets and causal graphs are worse. This is also expected from our theoretical result (Theorem 4.1), which states that the sample complexity to recover the parameters of the mixture distribution is inversely proportional to the change in the noise variance ($\\delta_i$ = |final variance - initial variance|).\n\\\n\\\n**Typos**: We thank the reviewer for pointing out the typos and other writing suggestions in the text. We will incorporate them into the final version of the paper.\n\n\n\\\n\\\n[1] Shohei Shimizu, Patrik O. Hoyer, Aapo Hyvärinen, and Antti Kerminen. A linear non-gaussian acyclic model for causal discovery. Journal of Machine Learning Research, 7(72):2003–2030, 2006", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Below, we answer some of the common weaknesses or questions raised by multiple reviewers:



> Reviewer 583w

**Automatic component selection**: 

In our Algorithm-1 (Mixture-UTIGSP), we allow for the misspecification of the correct number of components in a mixture. By default, the number of components is set as num node+1. However, this default setting could lead to errors in identifying the component's parameters, as shown in Fig 1d of the main paper. To address this issue, we have included results from a new version of our algorithm (Mixture-UTIGSP) that automatically searches for the number of components in the mixture. We do so by: 
1. First, a different Gaussian mixture model should be fitted for all possible numbers of components, i.e., 1 to "num node+1".
2. num_fwd_component = Start from the model with 1 component, iterate to the model with the "num node +1" component, and stop where the change in the log-likelihood of the mixture model drops below a cutoff percentage.
3. num_bwd_component = Start from the “num node + 1” component model, iterate to the model with 1 component, and stop where the change in the likelihood of mixture increases above a cutoff percentage. 
4. Number of component = (num_fwd_component+num_bwd_component)//2

Multiple other strategies, such as the BIC criterion or different variations of the above algorithm, could automatically select the number of components in the mixture, but we leave that exploration to future work.


We have rerun our experiment on the “half"-setting (where the true number of components in the mixture is (num nodes +1)/2) with this new automated selection method. Unlike Fig 1d in the main paper, where the parameter estimation doesn't improve much due to misspecified parameters, we observe that the parameter estimation errors go down to zero for all the nodes. Moreover, the other metrics, like Jaccard Similarity and SHD, still respectively show the same increasing and decreasing trend. Also, the estimated number of components becomes more accurate as the sample size increases. Please see Figure 2 in the **additional PDF document** attached for a comprehensive comparison of the parameter estimation and SHD plot before and after this improvement. For this experiment, we only utilized Step 3 of the modified algorithm mentioned earlier to determine the number of components.

\
\
> Reviewer 583w, mSnK, nhPx, SSWb

**Evaluation on real-world dataset**:

To demonstrate real-world applicability, we evaluate our method on the Protein Signaling dataset [1]. The dataset is collected from flow cytometry measurement of 11 phosphorylated proteins and phospholipids and is widely used in causal discovery literature [2,3]. The dataset consists of 5846 measurements with different experimental conditions and perturbations. Following Wang et al. [2], we define the subset of the dataset as observational, where only the receptor enzymes were perturbed in the experiment. Next, we select other 5 subsets of the dataset where a signaling protein is also perturbed in addition to the receptor enzyme. The observational dataset consists of 1755 samples, and the 5 interventional datasets have 911, 723, 810, 799, and 848 samples, respectively.  The table below summarizes the performance of our algorithm with the oracle (UTGSP), which already has access to disentangled data. For this experiment, our algorithm uses the automatic selection criteria for selecting the number of components in the mixture (*see Automatic component selection paragraph above*)

|  				| **Estimated vs Actual #component**  | **Jaccard Similarity** | **SHD** |
|--------------|----------------------------------|--------------------------------| -----------------|
|Ours (Mixture-UTIGSP)         |	7 (estimated) vs 6 (actual) | 0.08 | 17.6 +/- 1.0 | 
|Oracle (UTIGSP) 	  	| NA | 0.09 | 17.4 +/- 1.0 |

The total number of nodes in the underlying causal graph is 11. Thus, the maximum possible component in the mixture is 12 (11 interventional and one observational). In the mixture dataset described above, we have 6 components (1 observational and 5 interventional). Our method automatically recovers 7 components from the mixture, close to the ground truth 6. Next, we give the disentangled dataset from the first step of our algorithm to identify the unknown target. Though the Jaccard similarity of the recovered target is not very high (0.08, where the maximum value is 1.0), it is similar to that of Oracle (UTGSP). This shows that it is difficult to identify the correct intervention targets even with correctly disentangled data. Also, the SHD between the recovered graph and the widely accepted ground truth graph for Mixture-UTIGSP (ours) and UTIGSP (oracle) is very close. 

In the **additional pdf document** attached to the global comment, we provide the ground truth graph and the estimated graph from both algorithms. The causal graph estimated by our algorithm is very similar to the graph estimated by the oracle. 

\
\
[1] K. Sachs, O. Perez, D. Pe’er, D. A. Lauffenburger and G. P. Nolan. Causal protein-signaling networks derived from multiparameter single-cell data. Science 308.5721 (2005): 523-529.

[2] Y. Wang, L. Solus, K. Yang, and C. Uhler. Permutation-based causal inference algorithms with interventions. In Advances in Neural Information Processing Systems, pages 5822–5831, 2017.

[3] Chandler Squires, Yuhao Wang, and Caroline Uhler. Permutation-based causal structure learning with unknown intervention targets. Proceedings of the Thirty-Sixth Conference on Uncertainty in Artificial Intelligence, UAI 2020

Meta-review: The reviewers are recommending acceptance after the rebuttal, although some had reservations about the contribution being on the minor end since the method heavily draws from disentangling a mixture of Gaussians. The additive noise assumption is also seen as a weakness of the analysis. However, I believe the sample-complexity results are much needed in the causal discovery literature and might justify the needed ANM assumption. Reviewer SSWb gave an 8 with a confidence of 5, but I do not think their review content justifies this high score/confidence pair. Looking at the other scores, this paper is a bit above borderline in its current form in my opinion.
Decision: Accept (poster)