# Disentangling Mixtures of Unknown Causal Interventions111Published as an
oral paper [KS21] at the $37^{th}$ Conference on Uncertainty in Artificial
Intelligence (UAI), 2021.

Abhinav Kumar
Microsoft Research, Bangalore
Karnataka, India
<EMAIL_ADDRESS>Gaurav Sinha
Microsoft Research, Bangalore
Karnataka, India
<EMAIL_ADDRESS>
###### Abstract

In many real-world scenarios, such as gene knockout experiments, targeted
interventions are often accompanied by unknown interventions at off-target
sites. Moreover, different units can get randomly exposed to different unknown
interventions, thereby creating a mixture of interventions. Identifying
different components of this mixture can be very valuable in some
applications. Motivated by such situations, in this work, we study the problem
of identifying all components present in a mixture of interventions on a given
causal Bayesian Network. We construct an example to show that, in general, the
components are not identifiable from the mixture distribution. Next, assuming
that the given network satisfies a _positivity_ condition, we show that, if
the set of mixture components satisfy a mild _exclusion_ assumption, then they
can be uniquely identified. Our proof gives an efficient algorithm to recover
these targets from the exponentially large search space of possible targets.
In the more realistic scenario, where distributions are given via finitely
many samples, we conduct a simulation study to analyze the performance of an
algorithm derived from our identifiability proof.

##  1 Introduction

Motivation: Causal Bayesian Networks (CBN) ([Pea09, Spi10]), have become the
popular choice to model causal relationships in many real-world systems. These
models can simulate the effects of external interventions that forcibly fix
target system variables to desired target values. The simulation is done via
the $do()$ operator ([Pea09]) wherein the CBN is altered by breaking incoming
edges of the target variables and fixing them to desired target values. Pre-
estimating the effect of interventions can help in decision making, for
example, interventions on a CBN describing gene interactions can guide gene
editing experiments.

However, real-world interventions are not always precise and mistakenly end up
intervening other unintended targets. For example, gene knockout experiments
via the CRISPR-Cas$9$ gene-editing technology perform unintended cleavage at
unknown genome sites ([FFK+13, WWW+15]). Moreover, the unintended intervention
targets can themselves be noisy i.e. different individuals targeted by the
same intervention might undergo completely different off-target interventions.
For example, [AWL18] demonstrated that same gene editing experiment (using
CRISPR-Cas$9$) on mice embryos exhibited different unintended cleavage for
different mice. In such situations, units (samples) that underwent different
unintended interventions are not segregated and therefore the generated
distribution becomes a mixture of individual interventional distributions. We
ask the following natural question.

######  Question 1.1.

Given access to a mixture of interventional distributions, under what
conditions can one identify all the intervention targets?222from here on wards
we use the terms targets and components interchangeably

Our Contributions: First, we model the situation of identifying hidden off-
target interventions as the problem of identifying individual components of a
mixture of interventions. We assume an underlying CBN and model interventions
via the $do()$ operator described above. Second, by constructing examples, we
show that, in general for a given CBN and an input mixture distribution,
components of the mixture might not be unique. Using this, we motivate the
need for a mild _positivity_ assumption (Assumption 3.2) on the distribution
generated by the CBN and a mild and reasonable _exclusion_ assumption
(Assumption 3.1) on the structure of the intervention components present in
the mixture. Third, we prove that, given access to a CBN satisfying
_positivity_ and any input mixture having intervention components satisfying
_exclusion_ , such intervention components generating the mixture can be
uniquely identified from the mixture distribution. Fourth, given oracle access
to marginals of the distributions generated by the CBN and the mixture, our
identifiability proof gives an efficient algorithm to recover target
components from an exponentially large space of possible components. Finally,
in Section 5, we conduct a simulation study to analyze the performance of an
algorithm (Algorithm 2) directly inspired from our identifiability proof, but
with access to only finitely many samples. Even though the goal of our paper
is to prove identifiability of these intervention targets, our simulation
study indicates that our algorithm is promising in the realistic situation of
finitely many samples.

Related Prior Work: Recently [SWU20] considered the problem of causal
discovery using unknown intervention targets, and, as a crucial intermediate
step, prove identifiability of these targets. They also design two algorithms
UT-IGSP and JCI-GSP (based on the Joint Causal Inference framework in [MMC20])
to recover these targets from data. As discussed in our motivation, in many
real situations, such as [AWL18], the off-target effects are themselves noisy
and end up creating mixtures of multiple unknown interventions. Since [SWU20]
assumes separate access to each unknown intervention, their algorithm cannot
be used in our situation. Another line of work related to ours is the study of
mixtures of Bayesian Networks. Perfect interventions i.e. $do()$ operators on
the CBNs create new interventional CBNs (Definition $1.3.1$ in [Pea09]) and
therefore the input mixture in our setup is actually a mixture of Bayesian
Networks. This is a more general problem and was tackled first in [TMCH98].
They developed an Expectation-Maximization (EM) based heuristic to find
individual Bayesian Network components. However, they do not investigate
identifiability of the components. In our setting, we care about
identifiability since the components correspond to the unknown interventions.
Along with recovering the individual components of a mixture, there is also
growing interest in developing techniques to understand conditional
independence (CI) relationships among the variables in the mixture data. For
example, some recent works try to build other graphical representations, from
which the CI relationships in the mixture can be easily understood ([Spi94,
RSG11, Str19b, Str19a, SPU20]). Even though these new representations can
identify some aspects of the components, none of these works prove or discuss
the uniqueness and identifiability of the components, which is the main
interest of our work. Finally, we would like to mention that the general area
of causal discovery and inference using different kinds of unknown
interventions has received a lot of attention lately ([EM07, SWU20, JKSB20,
MMC20, RHPM15]). Even though many of these do not align with goal of our
paper, the growing interest in this area highlights seriousness of the issue
of unintended stochasticity in targeted interventions and the desire to design
algorithms robust to them.

##  2 Preliminaries

Notation We use capital letters (e.g. $X$) to represent random variables and
the corresponding lower case letter $x$ to denote the assignment $X=x$. The
set of values taken by random variable $X$ will be denoted by $C_{X}$. Unless
otherwise specified, all random variables in this paper are discrete and have
finite support i.e. $|C_{X}|<\infty$. A tuple or set of random variables is
denoted by capital bold face letter (e.g. $\bm{X}$) and the corresponding
lower case bold faced letter $\bm{x}$ will denote the assignment
$\bm{X}=\bm{x}$. Let, $C_{\bm{X}}=\prod_{X_{i}\in\bm{X}}C_{X_{i}}$ denote the
set of all possible values that can be taken by $\bm{X}$. Probability of
$\bm{X}$ taking the value $\bm{x}$ is denoted by $\mathbb{P}(\bm{X=x})$ or
equivalently as $\mathbb{P}(\bm{x})$ and probability of $\bm{X=x}$ given
$\bm{Y=y}$ is denoted as $\mathbb{P}(\bm{X=x|Y=y})$ or equivalently with
$\mathbb{P}(\bm{x|y})$. We will use $[n]$ to denote the set $\\{1,2,...,n\\}$,
$[m,n]$ to denote set $\\{m,m+1,\ldots,n\\}$, calligraphic capital letters
e.g. $\mathcal{S}$ to denote sets. Size of any set $\mathcal{S}$ is denoted by
$|\mathcal{S}|$. $\mathbb{R},\mathbb{R}_{+}$ and $\mathbb{R}_{\geq 0}$ will
denote the set of real numbers, positive real numbers and non-negative real
numbers respectively.

Bayesian Network Let $\mathcal{G}=\\{\bm{V},\mathcal{E}\\}$ be a directed
acyclic graph (DAG) with node set $\bm{V}=\\{V_{1},\ldots,V_{n}\\}$ where each
node $V_{i}$ represents a random variable. $\mathcal{G}$ is called a Bayesian
Network if the following factorization of the joint probability of $\bm{V}$
holds.

$\mathbb{P}(\bm{V})=\prod_{V_{i}\in\bm{V}}\mathbb{P}(V_{i}|\bm{pa}(V_{i}))$

where $\bm{pa}(V_{i})$ are parent nodes of $V_{i}$.

A _causal Bayesian Network_ is a Bayesian Network where all edges denote
direct causal relationships. It allows for modeling effect of external actions
called “interventions”, by appropriate modification of the Bayesian Network. A
formal definition of causal Bayesian Networks can be found in Definition
$1.3.1$, [Pea09].

Interventions: As mentioned above, these capture external actions on a system
under consideration, for example, dosage of medicines administered to a
patient, providing subsidies to poorer sections of the population, etc. A
natural way to model them in causal Bayesian Networks is to perform the act of
_causal surgery_ , wherein, incoming edges into the node(s) to be intervened
are removed and the node(s) is forcibly fixed to the desired value. As
described in Definition $1.3.1$, [Pea09], the new network thus obtained is
treated as the Bayesian Network modelling effect of the intervention.
Formally, following the notation in [Pea09], if we perform intervention on
nodes $\bm{X}\subseteq\bm{V}$ with a desire to set it to value $\bm{x}^{*}\in
C_{\bm{X}}$, then the effect of this intervention (also known as
_interventional distribution_) is a probability distribution on $\bm{V}$
denoted as $\mathbb{P}(\bm{v}|do(\bm{x}^{*}))$ (or
$\mathbb{P}_{\bm{x}^{*}}(\bm{v})$). In the intervened Bayesian Network,
conditional probability distributions (CPD) $\mathbb{P}(X_{i}|\bm{pa}(X_{i}))$
of all $X_{i}\in\bm{X}$ that are intervened and set to $x_{i}^{*}$, changes to
the Kronecker delta function $\delta_{x_{i},x_{i}^{*}}$ i.e.
$\mathbb{P}(X_{i}=x_{i}|\bm{pa}(X_{i}))=1$ if $x_{i}=x_{i}^{*}$ else it is
$0$. The CPD of the non-intervened nodes i.e. $\bm{V}\setminus\bm{X}$ remains
unchanged. Hence the interventional distribution factorizes as:

$\mathbb{P}_{\bm{x}^{*}}(V=\bm{v})=\prod_{V_{i}\notin\bm{X}}\mathbb{P}(V=v_{i}|\bm{pa}(V_{i}))\prod_{V_{i}\in\bm{X}}\delta_{v_{i},x_{i}^{*}}$

Such interventions are called perfect interventions. They capture many real-
world situations like gene-editing-experiments, where a certain target gene is
spliced out and replaced with the desired gene. Other kinds of interventions
such as _imperfect, uncertain_ e.t.c. have been defined in literature (Section
2 in [EM07]). However, in this paper we only deal with perfect interventions.

##  3 Problem Formulation and Main Theorem

As motivated in Section 1, the intended interventions performed during an
experiment often have hidden off-target effects, which could themselves be
stochastic, leading to different hidden treatments on different individuals.
We can model such a situation as an unknown mixture of different
interventions. Here is a formal definition.

######  Definition 3.1 (Mixture of Interventions).

Let $\mathcal{G}=\\{\bm{V},\mathcal{E}\\}$ be a causal Bayesian Network. A
probability distribution $\mathbb{P}_{mix}(\bm{V})$ is called a mixture of
interventions if for some $m\in\mathbb{N}$, there exist subsets
${\bm{T}}_{1},\ldots,{\bm{T}}_{m}\subseteq{\bm{V}}$, corresponding values
$\bm{t}_{i}\in\mathcal{C}_{{\bm{T}}_{i}}$, and positive scalar weights
$\pi_{i}\in\mathbb{R}_{+}$, $i\in[m]$, such that

$\mathbb{P}_{mix}({\bm{V}})=\sum\limits_{i=1}^{m}\pi_{i}\mathbb{P}_{{\bm{t}_{i}}}({\bm{V}})$

where $\bm{t}_{i}\neq\bm{t}_{j}$ for all $i\neq j\in[m]$333if $t_{i}=t_{j}$,
then $(\pi_{i}+\pi_{j})\mathbb{P}_{{\bm{t}_{i}}}(\bm{V})$ is one component..
We allow $\bm{T_{i}}=\varnothing$, in which case,
$\mathbb{P}_{{\bm{t}_{i}}}(\bm{V})$ is defined as $\mathbb{P}(\bm{V})$. Note
that for $\mathbb{P}_{mix}$ to be a valid distribution
$\sum_{i=1}^{m}\pi_{i}=1$. We refer to the set
$\mathcal{T}=\\{(\bm{t}_{i},\pi_{i}),i\in[m]\\}$ as a set of intervention
tuples generating the mixture.

Uniqueness and Identifiability : In our mixture model, each of the targets
$\bm{t}_{i}$, corresponds to an intervention that intentionally or
unintentionally transpired in the experiment. Since our ultimate goal is to
recover them from the mixture distribution (see Question 1.1), the problem
only makes sense if they “uniquely” define the mixture. Formally, there should
not exist two distinct sets of intervention tuples
$\mathcal{T}_{1}=\\{({\bm{t}}_{1}^{1},\pi_{1}^{1}),\ldots,({\bm{t}}_{n}^{1},\pi_{n}^{1})\\}$
and
$\mathcal{T}_{2}=\\{({\bm{t}}_{1}^{2},\pi_{1}^{2}),\ldots,({\bm{t}}_{m}^{2},\pi_{m}^{2})\\}$
which generate the same mixture distribution, i.e.,

$\mathbb{P}_{mix}({\bm{V}})=\sum\limits_{i=1}^{n}\pi_{i}^{1}\mathbb{P}_{{\bm{t}}_{i}^{1}}({\bm{V}})=\sum\limits_{j=1}^{m}\pi_{j}^{2}\mathbb{P}_{{\bm{t}}_{j}^{2}}({\bm{V}})$

An immediate next question is that of “identifiability”. Given access to a
causal Bayesian Network and the joint distribution $\mathbb{P}(\bm{V})$ it
captures, does there exist an algorithm, that takes as input the mixture
distribution $\mathbb{P}_{mix}(\bm{V})$ and exactly recovers the unknown set
of intervention tuples that generated $\mathbb{P}_{mix}(\bm{V})$? In the
general case, the answer to both these questions is no! Using a very simple
network, with just one node, we show that mixture distributions need not be
unique, motivating the need for more assumptions. More complicated examples
with multiple nodes can be easily created in the same way, but, for a cleaner
presentation we stick to this example since its purpose is to only motivate an
assumption we make next.

######  Example 3.1.

Consider a causal Bayesian Network with a single binary variable
$\bm{V}=\\{V_{1}\\}$, i.e. $C_{V_{1}}=\\{0,1\\}$ and denote
$\mathbb{P}(V_{1}=0),\mathbb{P}(V_{1}=1)$ by $p_{0},p_{1}$ respectively.
Define the mixture,

$\mathbb{P}_{mix}(V_{1})=\pi_{0}\mathbb{P}_{0}(V_{1})+\pi_{1}\mathbb{P}_{1}(V_{1})+(1-\pi_{0}-\pi_{1})\mathbb{P}(V_{1})$

On setting $V_{1}=0$ and then $V_{1}=1$ in the above equation, and rearranging
the terms, we obtain

$\begin{bmatrix}\begin{array}[]{cc}1-p_{0}&-p_{0}\\\ p_{0}-1&p_{0}\\\
\end{array}\end{bmatrix}\begin{bmatrix}[l]\pi_{0}\\\
\pi_{1}\end{bmatrix}=\begin{bmatrix}[l]\begin{array}[]{cc}&\mathbb{P}_{mix}(V_{1}=0)-p_{0}\\\
&\mathbb{P}_{mix}(V_{1}=1)-p_{1}\\\ \end{array}\end{bmatrix}$

The above $2\times 2$ matrix is singular and has rank $1$ i.e. the system does
not have a unique solution. In fact, when $0<p_{0}<1$,

$\pi_{0}=\frac{\mathbb{P}_{mix}(V_{1}=0)-p_{0}+p_{0}t}{1-p_{0}},\hskip
10.00002pt\pi_{1}=t$

are all valid solutions whenever $t\leq 1-\mathbb{P}_{mix}(V_{1}=0)$ and
$t\geq\max\\{\frac{p_{0}-\mathbb{P}_{mix}(V_{1}=0)}{p_{0}},0\\}$. Therefore,
uniqueness of intervention tuples does not hold in general.

Even though the example looks very simple, it captures the main reason behind
the non-identifiability of the set of intervention tuples. Exactly like the
above example, for any mixture, we can obtain systems of linear equations by
evaluating marginal probabilities of $\mathbb{P}_{mix}$ for different settings
of $\bm{V}$. Our goal then would be to find settings which help us solve these
systems uniquely and recover the set of intervention tuples. Unfortunately, in
this process, similar to the above example, the linear systems will have
dependent equations and therefore infinitely many solutions. To get over this
issue, we focus our attention on sets of intervention tuples, where, for each
variable there exists some value that is missing from all of it’s intervention
targets. In, our main theorem, we show that any mixture generated by such a
set cannot be generated by any other set of this kind. Next, we formally state
the assumption and then discuss why it is extremely mild and reasonable in
most real situations.

######  Assumption 3.1 (Exclusion).

Let $\mathcal{T}$ be a set of intervention tuples as defined in Definition
3.1. We say that $\mathcal{T}$ satisfies _exclusion_ , if for all
$V_{i}\in\bm{V}$, there exists $\bar{v}_{i}\in C_{V_{i}}$ such that
$\bar{v}_{i}\notin\bm{t}$ for any target $\bm{t}$ belonging to any tuple in
$\mathcal{T}$. We say that a mixture of interventions
$\mathbb{P}_{mix}(\bm{V})$ satisfies _exclusion_ if some set of intervention
tuples $\mathcal{T}$ generating it satisfies exclusion.

######  Remark 3.1.

This assumption puts only a mild constraint on the set of mixtures we
consider. For example, in a network with $n$ nodes and each node having $\leq
k$ possible values, excluding a fixed value of each node, can still generate
arbitrary mixtures over $\Omega(k^{n})$ allowed targets. Without exclusion,
there are $O((k+1)^{n})$ possible targets that generate the mixtures.
Therefore the reduction is minimal compared to the size of the space of
targets we are searching in. In real-world applications, it’s common for nodes
to have a large number of possible values. Therefore, for each node, the
possibility of off-target interventions impacting all values becomes unlikely.
We also emphasize that the values missing from the targets can be different
for different input mixtures and are not known to our algorithms. Our
identifiability algorithm only uses existence of such missing values making
its interpretation even more general.

Even though the above assumption helps us tackle the singularity problem
outlined in Example 3.1, it is not enough to guarantee uniqueness of
intervention tuples in general. We also assume a simple “positivity”
assumption on the causal Bayesian Network, which demands that the joint
probability $\mathbb{P}(\bm{v})>0$ for any setting $\bm{V=v}$. In fact, using
the same example as above (Example 3.1), we show that not assuming
$p_{0},p_{1}>0$, can lead to multiple set of intervention tuples satisfying
Assumption 3.1 and generating the same mixture. To see this, we consider the
input mixture $\mathbb{P}_{mix}(\bm{V})=\mathbb{P}(\bm{V})$. The set of
intervention tuples $\mathcal{T}_{1}=\\{(\varnothing,1)\\}$ for it clearly
satisfies Assumption 3.1 as intervention targets $(V_{1}=a)$ and $(V_{1}=b)$
are excluded. Now, if $p_{1}=0$, then
$\mathbb{P}_{0}(V_{1})=\mathbb{P}(V_{1})$ and for any $\pi_{0}\in[0,1]$, we
can trivially write

$\mathbb{P}_{mix}(V_{1})=\pi_{0}\mathbb{P}_{0}(V_{1})+(1-\pi_{0})\mathbb{P}(V_{1})$

implying that
$\mathcal{T}_{2}=\\{(V_{1}=0,\pi_{0}),(\varnothing,1-\pi_{0})\\}$ is another
set of intervention tuples for $\mathbb{P}_{mix}$, implying non-uniqueness.
Here is the statement of our assumption.

######  Assumption 3.2 (Positivity).

Let $\bm{V}$ be the set of nodes in our causal Bayesian Network and
$\mathbb{P}(\bm{V})$ be the corresponding joint probability distribution. We
assume that $\mathbb{P}(\bm{v})>0$ for all $\bm{v}\in C_{\bm{V}}$.

######  Remark 3.2.

As a straight forward consequence of this assumption, for every random
variable $V_{i}\in\bm{V}$, we can show that the conditional probability
distributions are positive as well i.e. $\mathbb{P}(v_{i}|\bm{pa}(v_{i}))>0$
for all $v_{i}\in C_{V_{i}}$ and setting $\bm{pa}(v_{i})$ of the parents. This
positivity assumption is commonly assumed in many works related to causal
graphs. For example, [HB12] assume positivity throughout their discussion when
characterizing the Interventional Markov Equivalence class.

Having stated these assumptions, we are now ready to state the main theorem of
this paper. A detailed proof is provided in Section 4.

######  Theorem 1.

Let $\mathcal{G}=\\{\bm{V},\mathcal{E}\\}$ be a causal Bayesian Network and
$\mathbb{P}(\bm{V})$ be the associated joint probability distribution
satisfying Assumption 3.2. Let $\mathbb{P}_{mix}(\bm{V})$ (Definition 3.1) be
any mixture of interventions that satisfies Assumption 3.1. The following are
true.

  1. 1.

There exists a unique set of intervention tuples
$\mathcal{T}=\\{(\bm{t_{1}},\pi_{1}),\ldots,(\bm{t_{m}},\pi_{m})\\}$
satisfying Assumption 3.1, such that

$\mathbb{P}_{mix}(\bm{V})=\sum\limits_{i=1}^{m}\pi_{i}\mathbb{P}_{\bm{t_{i}}}(V).$

  2. 2.

Given access to $\mathcal{G}$, $\mathbb{P}(\bm{V})$ and
$\mathbb{P}_{mix}(\bm{V})$, there exists an algorithm, that runs in time
$n*(m*k_{max})^{O(1)}$, and, outputs the set of intervention tuples
$\mathcal{T}$ (satisfying Assumption 3.1) generating it. Here $n$ is the
number of nodes in $\mathcal{G}$, $m$ is the size of set $\mathcal{T}$ and
$k_{max}$ is the maximum number of distinct values that any node can take.

######  Remark 3.3.

Though Assumption 3.2 is a sufficient conditions for Theorem 1, it is not
necessary. In Example B.1, we give an example that does not satisfy this
assumption but is uniquely generated by a set of intervention tuples
satisfying Assumption 3.1.

##  4 Proof of Main Theorem

In this section, we provide rigorous proof to both parts of Theorem 1
together. Our uniqueness proof (for Part $1$) is constructive and gives an
algorithm as described in Part $2$. Our proof goes via an induction argument
on the number of nodes $n$ present in the given Bayesian Network. There are
many lemmas stated throughout the proof. For a cleaner exposition, all of
their proofs are provided in Appendix A.

###  4.1 Base Case ($n=1$)

Consider a causal Bayesian Network $\mathcal{G}=(V,\mathcal{E})$ with only one
vertex $V$ and no edges (i.e. $\mathcal{E}=\varnothing$), such that
$\mathbb{P}(V)$ satisfies Assumption 3.2. Let $C_{V}=\\{v^{1},\ldots,v^{k}\\}$
be the set of values that $V$ can take. Therefore, by Assumption 3.2,
$\mathbb{P}(v^{i})>0$ for all $i\in[k]$. Next, consider any mixture of
interventions $\mathbb{P}_{mix}(V)$ that satisfies Assumption 3.1. Writing the
most general form of $\mathbb{P}_{mix}$, i.e. allowing for scalar weights to
be $\geq 0$, we can write,

$\mathbb{P}_{mix}(V)=\pi_{0}\mathbb{P}_{t_{0}}(V)+\pi_{1}\mathbb{P}_{t_{1}}(V)+\ldots+\pi_{k}\mathbb{P}_{t_{k}}(V),$

where $t_{0}=\varnothing,t_{1}=v^{1},\ldots,t_{k}=v^{k}$. By the notation in
Definition 3.1, $\mathbb{P}_{\varnothing}(V)=\mathbb{P}(V)$. Subtracting
$\mathbb{P}(V)$ from both sides and setting $\pi_{0}=1-\sum_{i=1}^{k}\pi_{i}$,
we get,

$\mathbb{P}_{mix}(V)-\mathbb{P}(V)=\sum\limits_{i=1}^{k}\pi_{i}(\mathbb{P}_{v^{i}}(V)-\mathbb{P}(V)).$

Recall, from the definition of interventions in Section 2, for any $v^{j}\in
C_{V}$, $\mathbb{P}_{v^{i}}(v^{j})=\delta_{v^{i},v^{j}}$. Substituting
$V=v^{1},\ldots,v^{k}$ and using
$\mathbb{P}_{v^{i}}(v^{j})=\delta_{v^{i},v^{j}}$, gives us $k$ linear
equations which can be written in the following matrix form:

$\left.\left.\begin{bmatrix}1-a_{1}&-a_{1}&.&.&-a_{1}\\\
-a_{2}&1-a_{2}&.&.&-a_{2}\\\ .&.&.&.&.\\\ -a_{k}&-a_{k}&.&.&1-a_{k}\\\
\end{bmatrix}\right.\begin{bmatrix}\pi_{1}\\\ \pi_{2}\\\ .\\\ \pi_{k}\\\
\end{bmatrix}\right.=\begin{bmatrix}b_{1}\\\ b_{2}\\\ .\\\ b_{k}\\\
\end{bmatrix}$ (1)

where $b_{i}=\mathbb{P}_{mix}(v^{i})-\mathbb{P}(v^{i})$ and
$a_{i}=\mathbb{P}(v^{i})>0$ (Assumption 3.2). Any set of intervention tuples
$\mathcal{T}$ generating $\mathbb{P}_{mix}(V)$ can be obtained as a solution
to the above system. Since, in Part $1$ of the theorem we restrict our focus
to $\mathcal{T}$ that satisfy Assumption 3.1, we know there exists some
$i\in[k]$, such that $\pi_{i}=0$. In the following lemma, we show that such a
system under these assumptions has a unique solution when
$\pi_{1},\ldots,\pi_{k}\in\mathbb{R}_{\geq 0}$. Proof of this lemma is
presented in Appendix A.1.

######  Lemma 4.1.

Consider the following linear system.

$\left.\left.\begin{bmatrix}c-a_{1}&-a_{1}&.&.&-a_{1}\\\
-a_{2}&c-a_{2}&.&.&-a_{2}\\\ .&.&.&.&.\\\ -a_{k}&-a_{k}&.&.&c-a_{k}\\\
\end{bmatrix}\right.\begin{bmatrix}x_{1}\\\ x_{2}\\\ .\\\ x_{k}\\\
\end{bmatrix}\right.=\begin{bmatrix}b_{1}\\\ b_{2}\\\ .\\\ b_{k}\\\
\end{bmatrix}$

Assume that $a_{1},\ldots,a_{k}>0$, $\sum_{j=1}^{k}a_{j}=c$ and it has at
least one solution. Then, rank of the above matrix is $k-1$ and there are
infinitely many solutions. Under the assumption that
$\bm{x}\in\mathbb{R}_{\geq 0}$ and $x_{i}=0$ for some $i\in[k]$, the solution
becomes unique. Given access to $a_{j}$s, $b_{j}$s and $c$, there exists an
algorithm that computes this solution in $k^{O(1)}$ time.

It’s easy to see that Equation 1 satisfies all requirements of Lemma 4.1,
implying the base case of our induction proof.

Inductive hypothesis $(n=N)$: Assume, Theorem 1 is true for all causal
Bayesian Networks on $N$ nodes, that satisfy Assumption 3.2 and input mixtures
that satisfy Assumption 3.1.

###  4.2 Induction step $(n=N+1)$:

Assuming the above inductive hypothesis, we show that Theorem 1 is true for
all causal Bayesian Networks on $N+1$ nodes, and mixture of interventions on
it, satisfying Assumptions 3.2 and 3.1 respectively. Let
$\bm{V}=\\{V_{1},\ldots,V_{N+1}\\}$, $\mathbb{P}(\bm{V})$ be the distribution
of $\bm{V}$ and $\mathbb{P}_{mix}(\bm{V})$ be any mixture of interventions
that satisfies Assumption 3.1. We wish to show that there is a unique set of
intervention tuples satisfying Assumption 3.1 that generates
$\mathbb{P}_{mix}(\bm{V})$. Without loss of generality let
$V_{1}\prec\ldots\prec V_{N+1}$ be a topological order for $\mathcal{G}$. We
will now marginalize on $V_{N+1}$ to reduce our problem to the $n=N$ case, so
that we can use the inductive hypothesis. The following lemma is required to
make this argument. We present it’s proof in Appendix A.2.

######  Lemma 4.2.

Let $\bm{V}_{N}=\\{V_{1},\ldots,V_{N}\\}$,

  1. 1.

$\mathbb{P}(\bm{V}_{N})$ is generated by the CBN $\mathcal{G}_{N}$ obtained by
deleting vertex $V_{N+1}$ (and all its incoming edges) from $\mathcal{G}$, and
satisfies Assumption 3.2.

  2. 2.

$\mathbb{P}_{mix}(\bm{V}_{N})$ can be written as a mixture of interventions on
$\mathcal{G}_{N}$ that satisfies Assumption 3.1.

  3. 3.

Given access to $\mathbb{P}(\bm{V})$ and $\mathbb{P}_{mix}(\bm{V})$, in
$O(k_{max})$ time we can create access to $\mathbb{P}(\bm{V}_{N})$ and
$\mathbb{P}_{mix}(\bm{V}_{N})$, by marginalizing on $V_{N+1}$.

Using the inductive hypothesis with this claim, we get that there exists a
unique set of intervention tuples
$\mathcal{S}=\\{(\bm{s}_{1},\mu_{1}),\ldots,(\bm{s}_{q},\mu_{q})\\}$444For
$i\in[q]$, $\bm{s}_{i}$ are values taken by variables
$\bm{S}_{i}\subset\bm{V}$ satisfying Assumption 3.1 that generates
$\mathbb{P}_{mix}(\bm{V}_{N})$, i.e.,

$\mathbb{P}_{mix}(\bm{V}_{N})=\sum\limits_{j=1}^{q}\mu_{j}\mathbb{P}_{\bm{s}_{j}}(\bm{V}_{N}),$

The induction hypothesis also implies that $\mathcal{S}$ can be computed in
$N*(q*k_{max})^{O(1)}$ time using access to $\mathbb{P}(\bm{V}_{N})$ and
$\mathbb{P}_{mix}(\bm{V}_{N})$. The next step in our proof then is to show
that, for a given $\mathcal{G}$, $\mathbb{P}(\bm{V})$ and
$\mathbb{P}_{mix}(\bm{V})$, the set of intervention tuples $\mathcal{S}$ can
be uniquely _lifted_ to a set $\mathcal{T}$ of intervention tuples that
satisfies Assumption 3.1 and generates $\mathbb{P}_{mix}(\bm{V})$. We also
show that using access to $\mathcal{G}$, $\mathbb{P}(\bm{V})$ and
$\mathbb{P}_{mix}(\bm{V})$, the lifting process runs in $(m*k_{max})^{O(1)}$
time implying that $\mathcal{T}$ can be computed in $(N+1)*(m*k_{max})^{O(1)}$
time.

####  4.2.1 Lifting $\mathcal{S}$

In this section we lift the set of intervention tuples $\mathcal{S}$
generating $\mathbb{P}_{mix}(\bm{V}_{N})$ uniquely to a set of intervention
tuples satisfying Assumption 3.1 generating $\mathbb{P}_{mix}(\bm{V})$. Let
$\mathcal{T}=\\{(\bm{t}_{1},\pi_{1}),\ldots,(\bm{t}_{m},\pi_{m})\\}$ be any
arbitrary set of intervention tuples satisfying Assumption 3.1 that generates
$\mathbb{P}_{mix}(\bm{V})$, i.e.

$\mathbb{P}_{mix}(\bm{V})=\sum\limits_{i=1}^{m}\pi_{i}\mathbb{P}_{\bm{t}_{i}}(\bm{V}).$
(2)

First, we give a lemma that connects targets $\bm{t}_{1},\ldots\bm{t}_{m}$
inside $\mathcal{T}$ with targets $\bm{s}_{1},\ldots\bm{s}_{q}$ inside
$\mathcal{S}$. We present it’s proof in Appendix A.3.

######  Lemma 4.3.

For every $\bm{t}_{i},i\in[m]$, there is some $\bm{s}_{j},j\in[q]$ such that,
either $\bm{t}_{i}=\bm{s}_{j}$ or $\bm{t}_{i}=\bm{s}_{j}\cup\\{v\\}$ for some
$v$ in $C_{V_{N+1}}$.

For $j\in[q]$, we define sets
$\mathcal{S}_{j}=\\{\bm{s}_{j},\bm{s}_{j}\cup\\{v^{1}\\},\ldots\bm{s}_{j}\cup\\{v^{k}\\}\\}$
where $C_{V_{N+1}}=\\{v^{1},\ldots,v^{k}\\}$. Since the targets
$\bm{s}_{j},j\in[q]$ are distinct, the sets $\mathcal{S}_{j},j\in[q]$ are
disjoint. Lemma 4.3 implies that

$\\{\bm{t}_{1},\ldots,\bm{t}_{m}\\}\subset\mathcal{S}_{1}\cup\ldots\mathcal{S}_{q}$

Since $\mathcal{T}$ was arbitrary, for every such $\mathcal{T}$, there exist
non-negative scalars $\pi_{\bm{s}}$,
$\bm{s}\in\mathcal{S}_{1}\cup\ldots\cup\mathcal{S}_{q}$ such that Equation 2
can be written as,

$\mathbb{P}_{mix}(\bm{V})=\sum\limits_{j=1}^{q}\sum\limits_{\bm{s}\in\mathcal{S}_{j}}\pi_{\bm{s}}\mathbb{P}_{\bm{s}}(\bm{V})$
(3)

Any solution of Equation 3 with $\pi_{\bm{s}}\geq 0$ gives a set of
intervention tuples for $\mathbb{P}_{mix}$. We show that there is a unique
such set which satisfies Assumption 3.1.

######  Lemma 4.4.

Let $\pi_{\bm{s}}$, $\bm{s}\in\mathcal{S}_{1}\cup\ldots\cup\mathcal{S}_{q}$ be
some non-negative solution to Equation 3 and the set
$\mathcal{T}=\\{(\bm{s},\pi_{\bm{s}}):\pi_{\bm{s}}>0\\}$ be the corresponding
set of intervention tuples. There exists a unique $\mathcal{T}$ that satisfies
Assumption 3.1.

###### Proof.

We show that enforcing Assumption 3.1 uniquely determines all $\pi_{\bm{s}}$
as solutions to a sequence of system of linear equations, implying that there
is a unique $\mathcal{T}$ that satisfies Assumption 3.1. To construct this
sequence, we need an ordering on $\bm{s}_{1},\ldots,\bm{s}_{q}$. So, without
loss of generality, we assume that for $j_{1}\leq j_{2}$,
$\bm{s}_{j_{2}}\not\subseteq\bm{s}_{j_{1}}$. The linear equations are created
by using specific settings for $\bm{V}$ in Equation 3 which enable us to
decompose the linear system into a sequence of simpler systems i.e. one for
each $\mathcal{S}_{i}$. We propose these settings next and explain why and how
they work. Since $\mathcal{S}$ satisfies Assumption 3.1, there exists
$\bar{v}_{i}\in V_{i},i\in[N]$ such that for all $j\in[q]$,
$\bar{v}_{i}\notin\bm{s}_{j}$. For $j\in[q]$, we define
$\bm{s}_{-j}=\\{\bar{v}_{i}:V_{i}\notin\bm{S}_{j}\\}$555$\bm{s}_{j}$
corresponds to set of variables $\bm{S}_{j}\subset\bm{V}$. and for every
$l\in[k]$, create settings

$\bm{v}_{j,l}=\bm{s}_{j}\cup\bm{s}_{-j}\cup\\{v^{l}\\}$

where $C_{V_{N+1}}=\\{v^{1},\ldots,v^{k}\\}$. The following lemma is used to
decompose the system of equations into simpler systems. Proof is presented in
Appendix A.4.

######  Lemma 4.5.

For $i\in[q]$, $l\in[k]$ and
$\bm{s}\in\mathcal{S}_{i+1}\cup\ldots\cup\mathcal{S}_{q}$,

$\mathbb{P}_{\bm{s}}(\bm{v}_{i,l})=0$

Using this in Equation 3, leaves us with the following simpler system for
every $i\in[q]$,

$\mathbb{P}_{mix}(\bm{v}_{i,l})-\sum\limits_{j=1}^{i-1}\sum\limits_{\bm{s}\in\mathcal{S}_{j}}\pi_{\bm{s}}\mathbb{P}_{\bm{s}}(\bm{v}_{i,l})=\sum\limits_{\bm{s}\in\mathcal{S}_{i}}\pi_{\bm{s}}\mathbb{P}_{\bm{s}}(\bm{v}_{i,l})$
(4)

Suppose all $\pi_{\bm{s}}$,
$\bm{s}\in\mathcal{S}_{1}\cup\ldots\cup\mathcal{S}_{i-1}$, have been
determined. Then the left had side of this equation is completely known and
has no unknown variables. We denote it by $\Delta$ going forward. Therefore,
by varying $l\in[k]$, we have $k$ equations in $k+1$ variables
$\pi_{\bm{s}},\bm{s}\in\mathcal{S}_{i}$. In the next lemma, we will obtain a
linear equation satisfied by these $k+1$ variables and reduce the system to
$k$ equations in $k$ variables. On marginalizing over $V_{N+1}$ in Equation 3,
we get

######  Lemma 4.6.

For all $i\in[q]$ and $(\bm{s}_{i},\mu_{i})\in\mathcal{S}$, the following
holds.

$\mu_{i}=\sum\limits_{\bm{s}\in\mathcal{S}_{i}}\pi_{\bm{s}}$

Proof of Lemma 4.6 is presented in Appendix A.5. By making the substitution
from this lemma above into Equation 4, we get the equation

$\Delta-\mu_{i}\mathbb{P}_{\bm{s}_{i}}(\bm{v}_{i,l})=\sum\limits_{l^{\prime}\in[k]}\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}(\mathbb{P}_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}(\bm{v}_{i,l})-\mathbb{P}_{\bm{s}_{i}}(\bm{v}_{i,l}))$
(5)

that gives a system of $k$ equations in $k$ variables when we vary
$l^{\prime}\in[k]$. Clearly we are looking for non-negative solutions for
$\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}$, $l^{\prime}\in[k]$. When we
enforce Assumption 3.1, there is some $l^{\prime}\in[k]$ such that
$\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}=0$. In Lemma 4.7, we show that we
can uniquely solve Equation 5 for such
$\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}$, $l^{\prime}\in[k]$.

######  Lemma 4.7.

For every $i\in[q]$, Equation 5 has a unique solution when we enforce that
$\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}$, $l^{\prime}\in[k]$ are non-
negative and at least one of them is $0$.

We present a proof of this Lemma in Appendix A.6. This lemma implies that
under enforcement of Assumption 3.1, all targets $\in\mathcal{S}_{i}$ (and
their respective mixing coefficients) that appear in
$\mathbb{P}_{mix}(\bm{V})$ get uniquely identified. Using this technique from
$i=1$ to $q$, any set of intervention tuples satisfying Assumption 3.1 that
generates $\mathbb{P}_{mix}(\bm{V})$ gets uniquely identified. Therefore,
there is a unique set of intervention tuples $\mathcal{T}$ that generates
$\mathbb{P}_{mix}$ and satisfies Assumption 3.1. ∎

The lifting of targets in $\mathcal{S}_{i}$ is done in Lemma 4.7 using
technique from Lemma 4.1 which takes $(k_{max})^{O(1)}$ time. This is repeated
for all $i\in[q]$, therefore, we spend $(q*k_{max})^{O(1)}$ time. It’s easy to
see that $q\leq m$ and so using the induction hypothesis the set of
intervention tuples is computed in $(N+1)*(m*k_{max})^{O(1)}$ time, completing
the induction step. We describe our complete algorithm in Algorithm 1. It’s
correctness and time complexity follows from the discussion in this section.
For better understanding, in Examples C.1 and C.2, we provide two worked out
examples on small problem instances, that illustrate important aspects of our
algorithm.

1

input : Variables $\bm{V}=(V_{1},\ldots,V_{N+1})$, CBN $\mathcal{G}$,
Distributions $\mathbb{P}(\bm{V}),\mathbb{P}_{mix}(\bm{V})$

output : Set of intervention tuples $\mathcal{T}$

2

  1. 1.

When $|\bm{V}|=1$, setup the linear system in Equation 1 and solve it using
technique described in Lemma 4.1 to obtain a set $\mathcal{T}$ of intervention
tuples. return $\mathcal{T}$.

  2. 2.

Let $V_{1}\prec\ldots\prec V_{N+1}$ denote a topological order in
$\mathcal{G}$. Marginalize on $V_{N+1}$ to create access to
$\mathbb{P}_{mix}(\bm{V}_{N})$ and $\mathbb{P}(\bm{V}_{N})$ where
$\bm{V}_{N}=(V_{1},\ldots,V_{N})$. Construct
$\mathcal{G}_{N}=\mathcal{G}\setminus\\{V_{N+1}\\}$. Recursively call this
algorithm with inputs $\mathcal{G}_{N}$, $\mathbb{P}(\bm{V}_{N})$,
$\mathbb{P}_{mix}(\bm{V}_{N})$, to compute the unique set of intervention
tuples $\mathcal{S}=\\{(\bm{s}_{1},\mu_{1}),\ldots,(\bm{s}_{q},\mu_{q})\\}$
that satisfies Assumption 3.1 and generates $\mathbb{P}_{mix}(\bm{V}_{N})$.
Let $\bm{s}_{1},\ldots,\bm{s}_{q}$ be ordered such that $i\leq j$ implies that
$\bm{s}_{j}\not\subseteq\bm{s}_{i}$. For each $i\in[N]$, by inspecting
$\bm{s}_{j},j\in[q]$, identify $\bar{v}_{i}\in C_{V_{i}}$ such that
$\bar{v}_{i}\notin\bm{s}_{j}$ for any $j\in[q]$. Define
$\bm{s}_{-j}=\\{\bar{v}_{i}:V_{i}\notin S_{j}\\}$. Let
$C_{V_{N+1}}=\\{v^{1},\ldots,v^{k}\\}$. For each $i\in[q]$ and $l\in[k]$,
create setting $\bm{v}_{i,l}=\bm{s}_{i}\cup\bm{s}_{-i}\cup\\{v^{l}\\}$.

  3. 3.

For each fixed $i\in[q]$, evaluate distributions for different $\bm{v}_{i,l}$,
$l\in[k]$, to setup the system of equations described in Equation 5. Solve the
system using the technique outlined in proof of Lemma 4.7 (which in turn uses
Lemma 4.1). At the end of this process collect all the intervention tuples
thus obtained (for all $i\in[q]$), in the set $\mathcal{T}$. return
$\mathcal{T}$.

Algorithm 1 DISENTANGLE-INFINITE

##  5 Simulation Study

The main purpose of this simulation study is to experimentally analyze the
performance of Algorithm 2 which modifies Algorithm 1 to make it work with
finite number of samples from distributions $\mathbb{P}_{mix}(\bm{V})$ and
$\mathbb{P}(\bm{V})$.

Simulation Setup: For each simulation setting $(N,M)$666$N$ is number of
nodes, $M$ is number of samples we randomly sample a directed acyclic graph on
$N$ nodes (each having $3$ categorical values), from the Scale-Free (SF) model
([BA99]), with number of edges chosen uniformly randomly from the set of
integers $[N,5N]$. Given this graph, we model the conditional probability
distribution of each node as a multinoulli distribution with Dirichlet priors
having fixed parameter $\alpha=2$ for all categories. This is done to conform
with Assumption 3.2. This generates our causal Bayesian Network $\mathcal{G}$.
We estimate marginal probabilities of the joint distribution defined by
$\mathcal{G}$ by generating $M$ samples using ancestral sampling on the
network. Now, to create input instances, we first choose an integer $m$
uniformly randomly from the set $[4,16]$ and use this as the number of
intervention tuples in the mixture. Then we iterate from $1$ to $m$ to build
each intervention target of the mixture. First, we choose the size of the
target by picking an integer $r$ uniformly randomly from the set
$\\{0,\ldots,N\\}$. Then we uniformly randomly choose an $r-$sized subset of
$[N]$, defining the variables in the current target. For each of these
variables, we first choose a category uniformly randomly and remove it from
consideration (in order to satisfy Assumption 3.1). From the remaining
categories, we uniformly randomly select one for each of the variables in the
target. Finally, we generate $m$ scalar weights for the mixing coefficients
such that they sum to $1$. In order to make sure that these coefficients are
not too small, we generate them with Dirichlet priors with all parameter
values fixed to $2$. The settings for number of nodes $N$ and sample size $M$
used in the experiment are
$(N,M)\in\\{4,8,12\\}\times\\{2^{4},2^{5},\ldots,2^{20}\\}$ where $\times$ is
the direct product of sets.

(a) Recall

(b) RMSE

(c) False-Positive RMSE

(d) False-Negative RMSE

Figure 1: Performance of Algorithm 2 as sample size and number of nodes
increase

Results Discussion: Figure 1 presents four plots that demonstrate performance
of our algorithm as sample size $M$ varies in
$\\{2^{4},2^{5},\ldots,2^{20}\\}$. We also vary the number of nodes $N$ in
$\\{4,8,12\\}$ and show separate plots for each $N$ in each of the figures.
The four plots in Figure 1, demonstrate four different accuracy metrics we
describe in Appendix F. In Figure 1(a), we plot the average recall of
intervention targets as $M$ increases. Recall for a single input instance is
the number of intervention targets in the input that are identified in the
output, as defined in Appendix F. Average recall is the average of this over
all random instances generated in the simulation. We observe a general trend
of increase in the recall as we increase the number of samples. Also, a
relatively larger number of samples are required to achieve the same level of
recall for mixtures generated from CBN with a large number of nodes as
compared to smaller ones. This trend is expected as Algorithm 2 estimates the
intervention targets by sequentially adding nodes to them. Hence for larger-
sized CBNs, the error accumulated is larger as compared to smaller ones.

In Figure 1(b), we plot the average root-mean-squared error (RMSE) between the
estimated and actual mixing coefficients. For each input, RMSE is calculated
using the definition supplied in Appendix F. Then it is averaged over all the
random input instances. We observe a fast decrease in the average RMSE as $M$
increases. We also observe that the average RMSE is higher for higher $N$.
This is also expected since for distributions on larger number of variables,
more samples will be needed to estimate marginal probabilities accurately.

In Figure 1(c), we plot average False-Positive RMSE (Section Appendix F) or
FP-RMSE as $M$ increases. For each input instance, FP-RMSE computes the RMSE
in mixing proportions for components which are not present in actual target
set but predicted by our algorithm. This is then averaged over all the random
input instances. For each value of $N$, we observe a similar decreasing trend
in this plot showing that incorrect targets in our output have very small
mixing proportions (as sample size increases) and therefore even if they are
present in the output their contribution is insignificant.

In Figure 1(d), we plot average False-Negative RMSE (Section Appendix F) or
FN-RMSE as $M$ increases. For each input instance, FN-RMSE computes the RMSE
in mixing proportions for components present in the actual target but not
present in the output targets. This is then averaged over all the random input
instances. Even though we observe a clear decreasing trend in this situation
as well, the rate is much slower as $N$ increases. This implies that the
sample complexity of our algorithm is high and it might need too many samples
to correctly identify the coefficients of targets present in the input.
Reducing the sample complexity is an interesting research direction which we
plan to pursue in a future work.

In Figure 3, we demonstrate and compare performance of our Algorithm (as $M,N$
increase), for CBNs generated using different random graph models (Scale-Free
and Erdös-Rényi). We observe no significant difference in performance and make
a conjecture that only high level graph parameters (such as number of nodes,
edges, in-degree etc.) might be having an impact on performance and the
topology (given these parameters) might not be that crucial.

To further understand the performance of our algorithm with respect to the
number of nodes, in Figure 2, we plot the Average Recall and Average RMSE as
number of nodes varies from $4$ to $32$, for a fixed sample size of $\sim
10^{6}$. We observe that recall decreases and RMSE increases very quickly as
number of nodes increase. Even though this is expected since error is
accumulated as we successively add nodes and find new intervention targets,
such performance for a very large sample size indicates bad dependence of
sample complexity on the number of nodes. Improving this needs more
exploration and is left for future work.

Limitations and Future Directions: The increasing trend in recall and
decreasing trend in RMSE of mixing coefficients shows promise. But the current
algorithm appears to be expensive in terms of sample complexity, especially
for mixture generated from larger graphs as seen in Figures 1(a), 1(d) and
Figure 2. Hence, it will be interesting to explore directions which could
reduce sample complexity. We leave this for future work. Another limitation is
the absence of baseline works to compare to. Since, ours is the first paper
that proves identifiability of such mixtures and gives the first such
algorithm, there are no prior works to compare against. In future, we plan to
compare our algorithm on a related or downstream task that might have been
explored in other works such as [TMCH98, SWU20, JKSB20].

##  6 Conclusion

In this paper, we investigated the problem of identifying individual
intervention targets from a mixture of interventions on a causal Bayesian
Network. This problem is well motivated from the real-world scenario wherein
experiments/interventions are accompanied by stochastic hidden off-target
effects. We modeled this problem as a mixture of intervention distributions
and constructed examples to show that, in general, it is impossible to
identify all targets in it. Then, we proposed a mild _positivity_ assumption
on the underlying network and a very reasonable _exclusion_ assumption on the
intervention targets that can appear in the mixture distribution. Using these
assumptions we proved that given access to the underlying CBN and the mixture
distribution, there is a unique set of intervention targets that satisfies our
_exclusion_ assumption and also generates the mixture. Our uniqueness proof
also provides an algorithm that uses access to the underlying distributions
and efficiently identifies all the targets along with their coefficients in
the mixture. In order to work with finitely many samples from the
distributions, we created a small modification to our algorithm and validated
it’s performance using simulated experiments. We tested our algorithm and
bench-marked its performance as the number of samples and nodes increased. As
future work, we plan to investigate algorithms to recover targets in such
mixtures using a smaller number of samples. Another interesting direction is
to use limited access to the underlying CBN while recovering the targets. This
can be very useful in situations where sufficient data or prior knowledge
might not be available to pin down the CBN. Solving the identifiability
problem when the CBN has unobserved confounders might be a good first step in
this direction.

##  7 Acknowledgements

This work was done during an internship of the first author (Abhinav Kumar)
under the guidance and mentorship of the second author (Gaurav Sinha), during
the period January-August 2020. Abhinav Kumar would like to thank Adobe
Research India for hosting him during this period and providing facilities for
a fruitful and enjoyable research experience. Abhinav Kumar did this
internship as part of his undergraduate thesis offered by his undergraduate
institution BITS Pilani, Hyderabad. He would like to thank the institution for
this opportunity. Gaurav Sinha would like to thank his mentees Aurghya Maiti,
Pulkit Goel, Naman Poddar and Ayush Chauhan who were part of an older
internship where the seed of this work was planted. The authors would like to
thank anonymous reviewers for their very helpful comments which helped in
greatly improving the presentation of this paper.

## References

  * [AP15] Ankur Ankan and Abinash Panda.  pgmpy: Probabilistic graphical models using python.  In Proceedings of the 14th Python in Science Conference (SCIPY 2015). Citeseer, 2015.
  * [AWL18] 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.
  * [BA99] Albert-László Barabási and Réka Albert.  Emergence of scaling in random networks.  Science, 286(5439):509–512, 1999.
  * [EM07] Daniel Eaton and Kevin Murphy.  Exact bayesian structure learning from uncertain interventions.  In Marina Meila and Xiaotong Shen, editors, PMLR, volume 2 of Proceedings of Machine Learning Research, pages 107–114, San Juan, Puerto Rico, 21–24 Mar 2007. PMLR.
  * [FFK+13] Yanfang Fu, Jennifer Foden, Cyd Khayter, Morgan Maeder, Deepak Reyon, J Joung, and Jeffry Sander.  High-frequency off-target mutagenesis induced by crispr-cas nucleases in human cells.  Nature biotechnology, 31, 06 2013.
  * [HB12] Alain Hauser and Peter Bühlmann.  Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs.  J. Mach. Learn. Res., 13(1):2409–2464, August 2012.
  * [JKSB20] Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim.  Causal discovery 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.
  * [KS21] Abhinav Kumar and Gaurav Sinha.  Disentangling mixtures of unknown causal interventions.  In Cassio de Campos and Marloes H. Maathuis, editors, Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 2093–2102. PMLR, 27–30 Jul 2021.
  * [MMC20] Joris M. Mooij, Sara Magliacane, and Tom Claassen.  Joint causal inference from multiple contexts.  Journal of Machine Learning Research, 21(99):1–108, 2020.
  * [Pea09] Judea Pearl.  Causality: Models, Reasoning and Inference.  Cambridge University Press, USA, 2nd edition, 2009.
  * [RHPM15] Dominik Rothenhäusler, Christina Heinze, Jonas Peters, and Nicolai Meinshausen.  Backshift: Learning causal cyclic graphs from unknown shift interventions.  In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 1513–1521. Curran Associates, Inc., 2015.
  * [RSG11] Joseph Ramsey, Peter Spirtes, and C Glymour.  On meta-analyses of imaging data and the mixture of records.  NeuroImage, 57:323–30, 07 2011.
  * [Spi94] P. Spirtes.  Conditional independence in directed cyclic graphical models for feedback.  In Carnegie Mellon University, 1994.
  * [Spi10] Peter Spirtes.  Introduction to causal inference.  Journal of Machine Learning Research, 11(54):1643–1662, 2010.
  * [SPU20] Basil Saeed, Snigdha Panigrahi, and Caroline Uhler.  Causal structure discovery from distributions arising from mixtures of dags.  CoRR, abs/2001.11940, 2020.
  * [Str19a] Eric V. Strobl.  The global markov property for a mixture of dags.  arXiv: Statistics Theory, 2019.
  * [Str19b] Eric V. Strobl.  Improved causal discovery from longitudinal data using a mixture of dags.  In Thuc Duy Le, Jiuyong Li, Kun Zhang, Emre Kıcıman Peng Cui, and Aapo Hyvärinen, editors, PMLR, volume 104 of Proceedings of Machine Learning Research, pages 100–133, Anchorage, Alaska, USA, 05 Aug 2019\.
  * [SWU20] Chandler Squires, Yuhao Wang, and Caroline Uhler.  Permutation-based causal structure learning with unknown intervention targets.  In Jonas Peters and David Sontag, editors, Proceedings of Machine Learning Research, volume 124, pages 1039–1048, Virtual, 03–06 Aug 2020\. PMLR.
  * [TMCH98] Bo Thiesson, Christopher Meek, David Maxwell Chickering, and David Heckerman.  Learning mixtures of dag models.  In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, UAI’98, page 504–513, San Francisco, CA, USA, 1998\. Morgan Kaufmann Publishers Inc.
  * [WWW+15] Xiaoling Wang, Yebo Wang, Xiwei Wu, Jinhui Wang, Yingjia Wang, Zhaojun Qiu, Tammy Chang, He Huang, Ren-Jang Lin, and Jiing-Kuan Yee.  Unbiased detection of off-target cleavage by crispr-cas9 and talens using integrase-defective lentiviral vectors.  Nature biotechnology, 33, 01 2015.

##  Appendix A Proofs from Section 4

In this section, we provide missing proofs of the lemmas stated in Section 4.

###  A.1 Proof of Lemma 4.1

Note that we have assumed $a_{i}>0$ for all $i\in[k]$. We iterate from $i=1$
to $k-1$ and apply the following row transformations on our matrix.

$\begin{split}R_{i}&\mapsto R_{i}-(\frac{a_{i}}{a_{k}})R_{k}\\\ \end{split}$

This results in the following linear system.

$\left.\left.\begin{bmatrix}c&0&.&-\frac{a_{1}}{a_{k}}c\\\
0&c&.&-\frac{a_{2}}{a_{k}}c\\\ .&.&.&.\\\ .&.&.&.\\\
-a_{k}&-a_{k}&.&c-a_{k}\\\ \end{bmatrix}\right.\begin{bmatrix}x_{1}\\\
x_{2}\\\ .\\\ .\\\ x_{k}\\\
\end{bmatrix}\right.=\begin{bmatrix}\tilde{b}_{1}\\\ \tilde{b}_{2}\\\ .\\\
.\\\ \tilde{b}_{k}\\\ \end{bmatrix}$

where $\tilde{b}_{i}=(b_{i}-\frac{a_{i}}{a_{k}}b_{k})$ for all $i\in[k-1]$ and
$\tilde{b}_{k}=b_{k}$. Since $c>0$, this matrix is easily seen to have rank
$\geq k-1$. Using $c=\sum_{i=1}^{k}a_{i}$ we can easily check that the last
row $R_{k}$ is $\frac{-a_{k}}{c}(R_{1}+\ldots+R_{k-1})$, implying that it has
rank $k-1$. Since the system is assumed to have at least one solution, it
actually has infinitely many solutions. The null space of this matrix is the
one dimensional space spanned by
$\bm{w}=(\frac{a_{1}}{a_{k}},\ldots,\frac{a_{k}}{a_{k}})^{T}$ which has all
positive entries since $a_{i}>0,i\in[k]$. Assume there are two distinct
solutions $\bm{u}=(u_{1},\ldots,u_{k})^{T}$ and
$\bm{v}=(v_{1},\ldots,v_{k})^{T}$ in $\mathbb{R}_{\geq 0}^{k}$ such that both
have at least one of their co-ordinates $0$, then $\bm{u}-\bm{v}$ belongs to
the null space i.e. $\bm{u}-\bm{v}=\lambda\bm{w}$ for some non-zero scalar
$\lambda$. If the same co-ordinate of $\bm{u},\bm{v}$ are $0$ i.e. for some
$i\in[k]$, $u_{i}=v_{i}=0$, then since $\frac{a_{i}}{a_{k}}$ is non-zero
$\lambda=0\Rightarrow\bm{u}=\bm{v}$, a contradiction. If different co-
ordinates of $\bm{u},\bm{v}$ are $0$, say $u_{1}=v_{2}=0$, then since
$\bm{u},\bm{v}\in\mathbb{R}_{\geq 0}^{k}$, $u_{1}-v_{1}$ is negative and
$u_{2}-v_{2}$ is positive. This is not possible since both these quantities
should have the same sign as $\lambda$, as all co-ordinates of $\bm{w}$ are
strictly positive. Therefore we arrive at a contradiction and there is a
unique solution.

Having proved this uniqueness, finding the solution is easy. We perform the
above-mentioned row transformations and obtain the general solution. Then for
each $i\in[k]$, we set $x_{i}=0$ and try to solve for the other variables
$x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{k}\in\mathbb{R}_{\geq 0}$. By the
above argument, we will get a valid solution for only one such $i$, which we
return as the unique solution. Clearly it takes $k^{O(1)}$ time.

###  A.2 Proof of Lemma 4.2

  1. 1.

Since $V_{1}\prec\ldots\prec V_{N+1}$ is a topological order, marginalizing
over $V_{N+1}$ in the factorization
$\mathbb{P}(\bm{V})=\prod_{i=1}^{N+1}\mathbb{P}(V_{i}|\bm{pa}(V_{i}))$ will
give the factorization
$\mathbb{P}(\bm{V}_{N})=\prod_{i=1}^{N}\mathbb{P}(V_{i}|\bm{pa}(V_{i}))$ which
is the factorization over $\mathcal{G}_{N}$.

  2. 2.

Let $\mathcal{T}=\\{(\pi_{1},\bm{t}_{1}),\ldots,(\pi_{m},\bm{t}_{m})\\}$ be a
set of intervention tuples generating $\mathbb{P}_{mix}(\bm{V})$ and
$C_{V_{N+1}}=\\{v^{1},\ldots,v^{k}\\}$. Marginalizing with respect to
$V_{N+1}$ for a single target $\bm{t}_{i},i\in[m]$ looks like,

$\sum\limits_{l=1}^{k}\mathbb{P}_{\bm{t}_{i}}(\bm{V}_{N},v^{l})=\left\\{\begin{array}[]{@{}l@{\thickspace}l}\mathbb{P}_{\bm{t}_{i}}(\bm{V}_{N})&:V_{N+1}\notin
T_{i}\\\
\mathbb{P}_{\bm{t}_{i}\setminus\\{v^{j}\\}}(\bm{V}_{N})&:v^{j}\in\bm{t}_{i}\end{array}\right.$
(6)

Applying this marginalization to Equation 2, i.e.,
$\mathbb{P}_{mix}(\bm{V})=\sum_{i=1}^{m}\pi_{i}\mathbb{P}_{\bm{t}_{i}}(\bm{V})$,
gives a convex linear combination of different
$\mathbb{P}_{\bm{s}}(\bm{V}_{N})$, where $\bm{s}$ are values of some set of
variables $\bm{S}\subset\bm{V}_{N}$, implying that
$\mathbb{P}_{mix}(\bm{V}_{N})$ is a mixture of interventions on
$\mathcal{G}_{N}$.

  3. 3.

This is straight-forward. To query $\mathbb{P}(v_{1},\ldots,v_{N})$, we query
$\mathbb{P}(v_{1},\ldots,v_{N},v_{N+1})$ for all $v_{N+1}\in C_{V_{N+1}}$ and
sum them up. The same can be done to create access for
$\mathbb{P}_{mix}(\bm{V}_{N})$. Since we are summing at most $k_{max}$ terms,
in $O(k_{max})$ time we can simulate access to both $\mathbb{P}(\bm{V}_{N})$,
$\mathbb{P}_{mix}(\bm{V}_{N})$.

###  A.3 Proof of Lemma 4.3

This follows by the marginalization equation (Equation 6 in Appendix A.2).

###  A.4 Proof of Lemma 4.5

Let $\bm{s}\in\mathcal{S}_{r}$ where $r>i$. This means that $\bm{s}$ is either
$\bm{s}_{r}$ or $\bm{s}_{r}\cup\\{v\\}$ for some $v\in C_{V_{N+1}}$. We show
that
$\mathbb{P}_{\bm{s}_{r}}(\bm{v}_{i,l})=\mathbb{P}_{\bm{s}_{r}}(\bm{s}_{i}\cup\bm{s}_{-i}\cup\\{v^{l}\\})=0$
for all $v^{l}\in C_{V_{N+1}}$. The proof for $\bm{s}=\bm{s}_{r}\cup\\{v\\}$
is identical. Since $i<r$, we get that $\bm{s}_{r}\not\subseteq\bm{s}_{i}$.
Now there are two cases, either the set of variables
$\bm{S}_{r}\subseteq\bm{S}_{i}$ or $\bm{S}_{r}\not\subseteq\bm{S}_{i}$. In the
first case, since $\bm{s}_{r}\not\subseteq\bm{s}_{i}$ we get that there is
some variable $V_{j}\in\bm{S}_{r},\bm{S}_{i}$ such that different values
$v_{j}^{r}$ and $v_{j}^{i}$ belong to $\bm{s}_{r}$ and $\bm{s}_{i}$
respectively implying that
$\mathbb{P}_{\bm{s}_{r}}(\bm{s}_{i}\cup\bm{s}_{-i}\cup\\{v\\})=0$. In the
second case, there is some variable $V_{j}\in\bm{S}_{r}$ ($j\in[N]$) that is
not in $\bm{S}_{i}$. Note that the “missing value” $\bar{v}_{j}\in C_{V_{j}}$
(i.e. the one that is missing from all targets $\bm{s}_{j},j\in[q]$) belongs
to $\bm{s}_{-i}$ (since $V_{j}\notin\bm{S}_{i}$) but it cannot belong to
$\bm{s}_{r}$ (since it is missing from all $\bm{s}_{1},\ldots,\bm{s}_{q}$)
$\Rightarrow\mathbb{P}_{\bm{s}_{r}}(\bm{s}_{i}\cup\bm{s}_{-i}\cup\\{v\\})=0$.

###  A.5 Proof of Lemma 4.6

Let $\bm{s}\in\mathcal{S}_{i}$. Note that $\bm{s}$ is either $\bm{s}_{i}$ or
$\bm{s}_{i}\cup\\{v\\}$ for some $v\in C_{V_{N+1}}$. Using Equation 6 we get
that for all $\bm{s}\in\mathcal{S}_{i}$, marginalization of $V_{N+1}$ in
$\pi_{\bm{s}}\mathbb{P}_{\bm{s}}(\bm{V})$ gives
$\pi_{\bm{s}}\mathbb{P}_{\bm{s}_{i}}(\bm{V}_{N})$. Marginalizing $V_{N+1}$ in
Equation 3, converts the left hand side to $\mathbb{P}_{mix}(\bm{V}_{N})$ and
right-hand side to
$\sum_{i=1}^{q}(\sum_{\bm{s}\in\mathcal{S}_{i}}\pi_{\bm{s}})\mathbb{P}_{\bm{s}_{i}}(\bm{V}_{N})$
giving a set of intervention tuples that generates
$\mathbb{P}_{mix}(\bm{V}_{N})$. By the inductive hypothesis,
$\mathbb{P}_{mix}(\bm{V}_{N})$ is generated by the unique set of intervention
tuples $\mathcal{S}$ satisfying Assumption 3.1. Since the intervention targets
in $\mathcal{S}$ and the ones in the set of intervention tuples we just
obtained are the same, using uniqueness of $\mathcal{S}$ we get that
$\mu_{i}=\sum\limits_{\bm{s}\in\mathcal{S}_{i}}\pi_{\bm{s}}$.

###  A.6 Proof of Lemma 4.7

Note that since $V_{N+1}$ is the last node in the topological order, using the
definition of interventions, we can conclude that,

$\mathbb{P}_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}(\bm{s}_{i}\cup\bm{s}_{-i}\cup\\{v^{l}\\})=\mathbb{P}_{\bm{s}_{i}}(\bm{s}_{i}\cup\bm{s}_{-i})\delta_{v^{l^{\prime}},v^{l}}$

where $v^{l},v^{l^{\prime}}\in C_{V_{N+1}}=\\{v^{1},\ldots,v^{k}\\}$. Recall
that $\bm{v}_{i,l}=\bm{s}_{i}\cup\bm{s}_{-i}\cup\\{v^{l}\\}$. Now, on
substituting for $\Delta$ using Equation 4 into Equation 5, we obtain,

$\begin{split}&\mathbb{P}_{mix}(\bm{v}_{i,l})-\mu_{i}\mathbb{P}_{\bm{s}_{i}}(\bm{v}_{i,l})-\sum\limits_{j=1}^{i-1}\sum\limits_{\bm{s}\in\mathcal{S}_{j}}\pi_{\bm{s}}\mathbb{P}_{\bm{s}}(\bm{v}_{i,l})=\\\
&\sum\limits_{l^{\prime}\in[k]}\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}\biggl{(}\mathbb{P}_{\bm{s}_{i}}(\bm{s}_{i}\cup\bm{s}_{-i})\delta_{v^{l^{\prime}},v^{l}}-\mathbb{P}_{\bm{s}_{i}}(\bm{v}_{i,l})\biggr{)}\end{split}$

Note that all the unknown variables are on the right-hand side of this
equation. Varying $l^{\prime}\in[k]$, gives us a linear system of equations
satisfied by scalars $\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}$.

$\left.\left.\begin{bmatrix}c-a_{1}&-a_{1}&.&.&-a_{1}\\\
-a_{2}&c-a_{2}&.&.&-a_{2}\\\ .&.&.&.&.\\\ -a_{k}&-a_{k}&.&.&c-a_{k}\\\
\end{bmatrix}\right.\begin{bmatrix}x_{1}\\\ x_{2}\\\ .\\\ x_{k}\\\
\end{bmatrix}\right.=\begin{bmatrix}b_{1}\\\ b_{2}\\\ .\\\ b_{k}\\\
\end{bmatrix}$

In the above system, we have renamed the known values as follows. For
$l\in[k]$, denote

$\begin{split}&a_{l}=\mathbb{P}_{\bm{s}_{i}}(\bm{v}_{i,l}),\\\
&b_{l}=\mathbb{P}_{mix}(\bm{v}_{i,l})-\mu_{i}\mathbb{P}_{\bm{s}_{i}}(\bm{v}_{i,l})-\sum\limits_{j=1}^{i-1}\sum\limits_{\bm{s}\in\mathcal{S}_{j}}\pi_{\bm{s}}\mathbb{P}_{\bm{s}}(\bm{v}_{i,l}),\\\
&c=\mathbb{P}_{\bm{s}_{i}}(\bm{s}_{i}\cup\bm{s}_{-i})\end{split}$

All $a_{l}$’s are probabilities from interventional distributions and can be
computed as product of conditional probabilities. Thus, by Assumption 3.2,
$a_{l}>0$ for all $l\in[k]$. It’s easy to see that $c=\sum_{l\in[k]}a_{l}$, by
the sum rule of probability. By statement of Lemma 4.3, for each $i\in[q]$ and
$l^{\prime}\in[k]$, $\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}\geq 0$. Since we
are only considering set of intervention tuples which satisfy Assumption 3.1,
there is some $l^{\prime}\in[k]$ such that
$\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}=0$. On constraining the variables
$x_{1},\ldots,x_{k}$ in the above system to these conditions (i.e.
$x_{l^{\prime}}\geq 0$ for all $l^{\prime}\in[k]$ and $x_{l^{\prime}}=0$ for
some $l^{\prime}\in[k]$), by Lemma 4.1 we are guaranteed a unique solution.
Therefore there is a unique tuple
$(\pi_{\bm{s}_{i}\cup\\{v^{1}\\}},\ldots,\pi_{\bm{s}_{i}\cup\\{v^{k}\\}})$
satisfying these requirements $\Rightarrow$ Equation 5 has a unique solution
which is easily computed in $k^{O(1)}$ time using the technique described in
proof of Lemma 4.1.

##  Appendix B Non-Necessity of Assumption 3.2

With the help of an example we argue that Assumption 3.2 is not necessary in
Theorem 1.

######  Example B.1.

Consider a causal Bayesian Network

$V_{1}\rightarrow V_{2}$

defined over two binary variable $\bm{V}=\\{V_{1},V_{2}\\}$ with
$C_{V_{i}}=\\{0,1\\}$, $i\in[2]$. Further, define CPDs,
$\mathbb{P}(V_{1}=1)=0.5$, $\mathbb{P}(V_{2}=1|V_{1}=0)=0.5$, and
$\mathbb{P}(V_{2}=1|V_{1}=1)=0$. Clearly $\mathbb{P}(V_{2}=1,V_{1}=1)=0$
implying that this CBN doesn’t satisfy Assumption 3.2.

Let $\mathbb{P}_{mix}(\bm{V})$ be a mixture distribution defined as

$\frac{1}{2}\mathbb{P}(\bm{V}|do(V_{1}=0))+\frac{1}{2}\mathbb{P}(\bm{V}|do(V_{1}=0,V_{2}=0))$

This mixture satisfies Assumption 3.1. Our algorithm first marginalizes on
$V_{2}$ and tries to find the unique set of intervention targets for
$\mathbb{P}_{mix}(V_{1})$. For this sub-problem, all steps of Algorithm 1 go
through (since the distribution $\mathbb{P}(V_{1})$ satisfies positivity), and
the correct components get identified. Note that, for this sub-problem the
algorithm identifies that
$\mathbb{P}_{mix}(V_{1})=\mathbb{P}(V_{1}|do(V_{1}=0))$. Now it tries to lift
this computed target $(V_{1}=0)$ to targets for the full mixture
$\mathbb{P}_{mix}(\bm{V})$.

Since the algorithm does not try to lift the target $(V_{1}=1)$ (as it was not
found as a target for $\mathbb{P}_{mix}(V_{1})$), it does not require
$\mathbb{P}(V_{2}|V_{1}=1)$ to be non-zero. This can be easily checked in the
lifting process described in Section 4.2.1. We do not repeat the steps of our
algorithm here and encourage the reader to work through the lifting steps
outlined in Section 4.2.1 and obtain unique solutions proving our point that
Assumption 3.2 is not necessary and can be weakened.

##  Appendix C Worked-Out Examples

In this section, we illustrate the workings of Algorithm 1 (in the main paper)
using two worked-out examples. Example C.1 is simpler and uses a mixture
distribution on a CBN with just two nodes. It does not really require all of
the crucial ideas from the lifting procedure described in Section 4.2.1.
However, we believe it is important since it gives a good broad understanding
of the entire algorithm. Example C.2 is complicated enough (using a mixture
distribution on a CBN with three nodes) to highlight some of the key novelties
of our lifting procedure in Section 4.2.1. We urge the reader to first work
through Example C.1 and then through Example C.2 to get a full understanding
of the critical ideas that make our proof of Theorem 1 work.

######  Example C.1.

Consider a causal Bayesian Network

$V_{1}\rightarrow V_{2}$

defined over two binary variable $\bm{V}=\\{V_{1},V_{2}\\}$ with
$C_{V_{i}}=\\{0,1\\}$, $i\in[2]$. Further, define CPDs,
$\mathbb{P}(V_{1}=1)=0.5$, $\mathbb{P}(V_{2}=1|V_{1})=0.5$ for both $V_{1}=0$
and $V_{1}=1$. Clearly, this CBN satisfies Assumption 3.2. Let
$\mathbb{P}_{mix}(\bm{V})$ be a mixture distribution defined as

$\frac{1}{2}\mathbb{P}(\bm{V}|do(V_{1}=0))+\frac{1}{2}\mathbb{P}(\bm{V}|do(V_{1}=0,V_{2}=0))$

This mixture satisfies Assumption 3.1. On marginalizing variable $V_{2}$, the
mixture becomes $\mathbb{P}_{mix}(V_{1})=\mathbb{P}(V_{1}|do(V_{1}=0))$ which
also satisfies Assumption 3.1, as a mixture of interventions on the CBN
comprising of the single variable $V_{1}$. A general mixture distribution on
variable $V_{1}$ looks like,

$\begin{split}\pi_{0}\mathbb{P}(V_{1}|do(V_{1}=0))+\pi_{1}\mathbb{P}(V_{1}|do(V_{1}=0))+(1-\pi_{0}-\pi_{1})\mathbb{P}(V_{1})\end{split}$

Varying $V_{1}$ in $\\{0,1\\}$ gives the system of equations,

$\begin{bmatrix}\begin{array}[]{cc}1-0.5&-0.5\\\ -0.5&1-0.5\\\
\end{array}\end{bmatrix}\begin{bmatrix}[l]\pi_{0}\\\
\pi_{1}\end{bmatrix}=\begin{bmatrix}[l]\begin{array}[]{cc}&\mathbb{P}_{mix}(V_{1}=0)-0.5\\\
&\mathbb{P}_{mix}(V_{1}=1)-0.5\\\ \end{array}\end{bmatrix}$

Lemma 4.1 highlights why such a system has a unique non-negative solution if
we assume that at least one of $\pi_{0},\pi_{1}$ is $0$, i.e. the set of
intervention tuples we are trying to construct satisfy Assumption 3.1. Lemma
4.1 also provides an efficient algorithm to find the unique solution giving
$\mathbb{P}_{mix}(V_{1})=\mathbb{P}(V_{1}|do(V_{1}=0))$. Now we have one
intervention target $(V_{1}=0)$ at hand, which we will try to lift. Note that,
the possible lifts of such a target are
$(V_{1}=0),(V_{1}=0,V_{2}=0),(V_{1}=0,V_{2}=1)$. Our next step will search
within this space of targets and try to complete the construction. A general
solution for mixtures within this space would look like

$\begin{split}\mu_{0}\mathbb{P}(\bm{V}|do(V_{1}=0))+\mu_{1}\mathbb{P}(\bm{V}|do(V_{1}=0,V_{2}=0))+\mu_{2}\mathbb{P}(\bm{V}|do(V_{1}=0,V_{2}=1))\end{split}$

where $\mu_{i}\geq 0,i\in\\{0,1,2\\}$. So we want to find
$\mu_{0},\mu_{1},\mu_{2}$ such that the above general solution becomes equal
to $\mathbb{P}_{mix}(\bm{V})$. Since we already know that
$\mathbb{P}_{mix}(V_{1})=\mathbb{P}(V_{1}|do(V_{1}=0))$, marginalizing on
$V_{2}$ implies that $\mu_{0}+\mu_{1}+\mu_{2}=1$. We substitute
$\mu_{0}=1-\mu_{1}-\mu_{2}$, equate the above general mixture to
$\mathbb{P}_{mix}(\bm{V})$, and re-arrange terms to get,

$\begin{split}\mathbb{P}_{mix}(\bm{V})-\mathbb{P}(\bm{V}|do(V_{1}=0))&=\mu_{1}(\mathbb{P}(\bm{V}|do(V_{1}=0,V_{2}=0))-\mathbb{P}(\bm{V}|do(V_{1}=0)))\\\
&+\mu_{2}(\mathbb{P}(\bm{V}|do(V_{1}=0,V_{2}=1))-\mathbb{P}(\bm{V}|do(V_{1}=0)))\end{split}$

We evaluate this mixture at settings $V_{1}=0,V_{2}=0$, and $V_{1}=0,V_{2}=1$,
to get a system of linear equations in $(\mu_{1},\mu_{2})$,

$\begin{bmatrix}\begin{array}[]{cc}1-0.5&-0.5\\\ -0.5&1-0.5\\\
\end{array}\end{bmatrix}\begin{bmatrix}[l]\mu_{1}\\\
\mu_{2}\end{bmatrix}=\begin{bmatrix}[l]\begin{array}[]{cc}&\mathbb{P}_{mix}(0,0)-0.5\\\
&\mathbb{P}_{mix}(0,1)-0.5\\\ \end{array}\end{bmatrix}$

Again, since we are solving for a set of intervention tuples satisfying
Assumption 3.1, one of $\mu_{1},\mu_{2}$ would be $0$. This used with Lemma
4.1 gives the unique solution $\mu_{1}=0.5,\pi_{2}=0\Rightarrow\mu_{0}=0.5$,
thereby identifying the correct set of intervention tuples.

We would like to note that the example we illustrated above is rather simple
and does not capture some main non-trivial aspects of our Algorithm. However,
we think it is important as a warm up exercise. A more involved example that
would bring out the crucial ideas of our proof is presented below in Example
C.2.

######  Example C.2.

Consider a causal Bayesian Network defined over three binary variables
$\bm{V}=\\{V_{1},V_{2},V_{3}\\}$ taking values in $C_{V_{i}}=\\{0,1\\}$,
$i\in[3]$, with $\bm{pa}(V_{1})=\varnothing$, $\bm{pa}(V_{2})=\\{V_{1}\\}$ and
$\bm{pa}(V_{3})=\\{V_{1},V_{2}\\}$. Let CPDs be such that Assumption 3.2 is
satisfied. Consider a mixture distribution

$\begin{split}\mathbb{P}_{mix}(\bm{V})=\mu_{0}\mathbb{P}(\bm{V}|do(V_{1}=0))+\mu_{1}\mathbb{P}(\bm{V}|do(V_{1}=0,V_{2}=0))+\mu_{2}\mathbb{P}(\bm{V}|do(V_{1}=0,V_{2}=0,V_{3}=0))\end{split}$

with positive scalars $\mu_{0},\mu_{1},\mu_{2}$ satisfying
$\mu_{0}+\mu_{1}+\mu_{2}=1$. Marginalizing on $V_{3}$, gives,

$\begin{split}\mathbb{P}_{mix}(V_{1},V_{2})=\pi_{0}\mathbb{P}(V_{1},V_{2}|do(V_{1}=0))+\pi_{1}\mathbb{P}(V_{1},V_{2}|do(V_{1}=0,V_{2}=0))\end{split}$

Our inductive hypothesis assumes that this mixture on smaller number of nodes
is generated by a unique set of intervention tuples that satisfies Assumption
3.1 and also that this set can be efficiently computed. This will give us
access to the two scalars $\pi_{0},\pi_{1}$ and to the two targets $(V_{1}=0)$
and $(V_{1}=0,V_{2}=0)$ (we call them the currently computed targets). We need
to lift these targets to targets for the original mixture distribution like we
did in Example C.1. However, the situation is not as simple here. Note that
$(V_{1}=0)$ can be lifted to one of the three targets
$(V_{1}=0),(V_{1}=0,V_{3}=0),(V_{1}=0,V_{3}=1)$. Similarly $(V_{1}=0,V_{2}=0)$
can be lifted to one of the three targets
$(V_{1}=0,V_{2}=0),(V_{1}=0,V_{2}=0,V_{3}=0),(V_{1}=0,V_{2}=0,V_{3}=1)$. So
there are $6$ possible targets in the original mixture and therefore a general
solution for our mixture can be written using $6$ new variables (say
$\delta_{0},\delta_{1},\delta_{2},\delta_{3},\delta_{4},\delta_{5}$) such
that,

$\begin{split}\mathbb{P}_{mix}(\bm{V})&=\delta_{0}\mathbb{P}(\bm{V}|do(V_{1}=0))+\delta_{1}\mathbb{P}(\bm{V}|do(V_{1}=0,V_{3}=0))+\delta_{2}\mathbb{P}(\bm{V}|do(V_{1}=0,V_{3}=1))\\\
&+\delta_{3}\mathbb{P}(\bm{V}|do(V_{1}=0,V_{2}=0))+\delta_{4}\mathbb{P}(\bm{V}|do(V_{1}=0,V_{2}=0,V_{3}=0))\\\
&+\delta_{5}\mathbb{P}(\bm{V}|do(V_{1}=0,V_{2}=0,V_{3}=1))\end{split}$ (7)

where all $\delta_{i}$ are non-negative. By marginalizing on $V_{3}$, and
using the solution we got from the inductive hypothesis (like we did in
Example C.1), we can show that,

$\pi_{0}=\delta_{0}+\delta_{1}+\delta_{2},\hskip
10.00002pt\pi_{1}=\delta_{3}+\delta_{4}+\delta_{5}$

Now the two main non trivial ingredients needed from here are:

  * •

Deciding the order in which the currently computed targets should be lifted,
and

  * •

Deciding the settings for $\bm{V}$ that would give linear systems where we can
argue about unique solutions like in Example C.1.

For the first one, we lift the currently computed targets in an order which
does not violate set inclusion for these targets, i.e. we first lift
$(V_{1}=0)$ and then lift $(V_{1}=0,V_{2}=0)$. This can be done by considering
any extension of the set inclusion partial order on these targets. Then for
lifting the target $(V_{1}=0)$, we choose to evaluate on the settings
$\bm{v}_{1}=(V_{1}=0,V_{2}=1,V_{3}=0),\bm{v}_{2}=(V_{1}=0,V_{2}=1,V_{3}=1)$.
Here, we pick the value of $V_{2}$ (i.e. $V_{2}=1$) that is missing from the
currently computed target under consideration i.e. $(V_{1}=0)$. There will
always be one such missing value (it follows from Assumption 3.1). Evaluating
on these settings simplifies our equation drastically. For $l\in[2]$, we get,

$\begin{split}\mathbb{P}_{mix}(\bm{v}_{l})=\delta_{0}\mathbb{P}(\bm{v}_{l}|do(V_{1}=0))+\delta_{1}\mathbb{P}(\bm{v}_{l}|do(V_{1}=0,V_{3}=0))+\delta_{2}\mathbb{P}(\bm{v}_{l}|do(V_{1}=0,V_{3}=1))\end{split}$

Basically all possible lifts of the other currently computed target i.e.
$(V_{1}=0,V_{2}=0)$ vanish and we have a much simpler system of equations at
hand. From here the solution follows exactly like the previous example. We
substitute $\delta_{0}=\pi_{0}-\delta_{1}-\delta_{2}$ and rearrange to get a
linear system in $2$ equations and $2$ variables $\delta_{1},\delta_{2}$.
Similar to the argument made in Example C.1, at least one of
$\delta_{1},\delta_{2}$ will be $0$ and therefore this system has a unique
solution (using Lemma 4.1) giving values of
$\delta_{0},\delta_{1},\delta_{2}$. These can then be substituted back in
Equation 7 reducing the number of variables to $3$ (i.e.
$\delta_{3},\delta_{4},\delta_{5}$). Again we substitute
$\delta_{3}=\pi_{1}-\delta_{4}-\delta_{5}$ and reduce the equation to just two
unknowns. Finally by using settings
$\bm{v}_{1}=(V_{1}=0,V_{2}=0,V_{3}=0),\bm{v}_{2}=(V_{1}=0,V_{2}=0,V_{3}=1)$ in
Equation 7 we will be left with $2$ equations in $2$ variables. Exactly like
our argument for lifting of $(V_{1}=0)$ (i.e. using Lemma 4.1), we can show
that, when at least one of $\delta_{4},\delta_{5}$ is $0$, this system has a
unique solution as well. Lemma 4.1 would efficiently give us the values of
$\delta_{4},\delta_{5}$ and therefore of $\delta_{3}$. Thus, we uniquely
identify a set of intervention tuples that satisfies Assumption 3.1 and
generates $\mathbb{P}_{mix}(\bm{V})$.

##  Appendix D Finite Sample Algorithm

In a real world scenario, we will only have finitely many samples from the
distributions $\mathbb{P}(\bm{V})$ and $\mathbb{P}_{mix}(\bm{V})$. In this
situation, we modify Algorithm 1 slightly to make it work with finitely many
samples. The resulting algorithm is presented in Algorithm 2. Let the sets
containing the samples be $\mathcal{B}=\\{\bm{b}_{1},\ldots,\bm{b}_{M}\\}$
where $\bm{b}_{i}\sim\mathbb{P}(\bm{V})$ and
$\mathcal{B}_{mix}=\\{\bm{b}_{1}^{mix},\ldots,\bm{b}_{M}^{mix}\\}$ where
$\bm{b}_{j}^{mix}\sim\mathbb{P}_{mix}(\bm{V})$. As a preprocessing step, we
estimate the distributions $\mathbb{P}(\bm{V})$ and $\mathbb{P}_{mix}(\bm{V})$
as $\hat{\mathbb{P}}(\bm{V})$ and $\hat{\mathbb{P}}_{mix}(\bm{V})$
(respectively) using samples in $\mathcal{B}$ and $\mathcal{B}_{mix}$
respectively. $\hat{\mathbb{P}}(\bm{V})$ is estimated by estimating all the
CPDs using maximum likelihood estimation (MLE). In our implementation, we use
a function from the pgmpy library ([AP15]), to compute these MLE estimates. We
enforce Assumption 3.2 on $\hat{\mathbb{P}}(\bm{V})$, by enforcing it on all
it’s CPDs, using a small positive parameter $\delta$ (chosen by us). When
$\hat{\mathbb{P}}(v_{i}|\bm{pa}(v_{i}))=0$ for some $v_{i}$ and some setting
of parents $\bm{pa}(v_{i})$, we update,

$\hat{\mathbb{P}}(V_{i}|\bm{pa}(v_{i}))\leftarrow\hat{\mathbb{P}}(V_{i}|\bm{pa}(v_{i}))+\delta$

for all values of $V_{i}$, and then re-normalize to make it a probability
distribution again. Marginal $\hat{\mathbb{P}}_{mix}(\bm{V}=\bm{v})$ is
calculated using relative frequency of the occurence of $\bm{V}=\bm{v}$ in the
samples inside $\mathcal{B}_{mix}$. These estimated distributions are then
used as inputs in Algorithm 2. We use another small positive parameter
$\epsilon$ as input to Algorithm 2 which prunes each recovered set of
intervention tuples computed during the algorithm, by only keeping mixing
coefficients greater that $\epsilon$. It’s easy to see that the time
complexity of Algorithm 2, including the estimation of probabilities from
samples is:

$\biggr{(}\frac{Nk_{max}^{d}M}{\epsilon}\biggr{)}^{O(1)}$

Here $N$ is number of nodes in the CBN $\mathcal{G}$, $d$ is the maximum in-
degree of any node in $\mathcal{G}$, $k_{max}$ is maximum number of values
that any node in $\mathcal{G}$ can take and $M$ is the number of samples
present in $\mathcal{B}$ and $\mathcal{B}_{mix}$.

######  Remark D.1.

Since our algorithm’s run-time depends on $\epsilon$, we need to carefully
select it’s value. Setting it too small could increase the run time whereas
setting it too big could lead to wrongfully pruning intervention targets (with
significant mixing proportions) present in the mixture.

1

input :
$\bm{V},\mathcal{G}\hat{\mathbb{P}}(\bm{V}),\hat{\mathbb{P}}_{mix}(\bm{V}),\epsilon$

2

output : Set of intervention tuples $\mathcal{T}$

3

  1. 1.

When $|\bm{V}|=1$, setup the linear system in Equation 1 (say
$\bm{Ax}=\bm{b}$) using the estimated distributions. Similar to the technique
described in Lemma 4.1, set one variable to $0$ at a time giving solution
$(\pi_{1},\ldots,\pi_{k})$ corresponding to targets
$(\bm{t}_{1},\ldots,\bm{t}_{k})$ as described in Section 4.1. For every
variable that is set to $0$, create a set
$\mathcal{T}=\\{(\bm{t}_{i},\pi_{i}):i\in[k]\\}$ containing the solution. For
every such $\mathcal{T}$, iterate through the tuples $(\bm{t}_{i},\pi_{i})$ in
it. If some $\pi_{i}<0$, set $\pi_{i}\leftarrow 0$. Compute the score
$r(\mathcal{T})=\|\bm{A\pi}-\bm{b}\|^{2}$, where
$\bm{\pi}=(\pi_{1},\ldots,\pi_{k})$. Next, select $\mathcal{T}$ with the
smallest value of $r(\mathcal{T})$. For this selected $\mathcal{T}$, check if
$1-\sum_{i=1}^{k}\pi_{i}<\epsilon$. If yes, renormalize
$\pi_{i}\leftarrow\pi_{i}/(\sum_{i=1}^{k}\pi_{i})$. If no, add the tuple
$(\varnothing,1-\sum_{i=1}^{k}\pi_{i})$ to $\mathcal{T}$. Only keep the tuples
with strictly positive mixing coefficients i.e.
$\mathcal{T}\leftarrow\\{(\bm{t}_{i},\pi_{i})\in\mathcal{T}:\pi_{i}>0\\}$.
return $\mathcal{T}$.

  2. 2.

Let $V_{1}\prec\ldots\prec V_{N+1}$ denote a topological order in
$\mathcal{G}$. Marginalize on $V_{N+1}$ to create access to
$\hat{\mathbb{P}}_{mix}(\bm{V}_{N})$ and $\hat{\mathbb{P}}(\bm{V}_{N})$ where
$\bm{V}_{N}=(V_{1},\ldots,V_{N})$. Construct
$\mathcal{G}_{N}=\mathcal{G}\setminus\\{V_{N+1}\\}$. Recursively call this
algorithm with inputs $\mathcal{G}_{N}$, $\hat{\mathbb{P}}(\bm{V}_{N})$,
$\hat{\mathbb{P}}_{mix}(\bm{V}_{N})$, and obtain a set of intervention tuples
$\mathcal{S}=\\{(\bm{s}_{1},\mu_{1}),\ldots,(\bm{s}_{q},\mu_{q})\\}$. Let
$\bm{s}_{1},\ldots,\bm{s}_{q}$ be ordered such that $i\leq j$ implies that
$\bm{s}_{j}\not\subseteq\bm{s}_{i}$. For all $i\in[N]$, by inspecting
$\bm{s}_{j}$, identify $\bar{v}_{i}\in C_{V_{i}}$ such that
$\bar{v}_{i}\notin\bm{s}_{j}$ for any $j\in[q]$. Define
$\bm{s}_{-j}=\\{\bar{v}_{i}:V_{i}\notin S_{j}\\}$. Let
$C_{V_{N+1}}=\\{v^{1},\ldots,v^{k}\\}$. For each $i\in[q]$ and $l\in[k]$,
create setting $\bm{v}_{i,l}=\bm{s}_{i}\cup\bm{s}_{-i}\cup\\{v^{l}\\}$.

  3. 3.

For each fixed $i\in[q]$, evaluate distributions for different $\bm{v}_{i,l}$,
$l\in[k]$, to setup the system of equations (say $\bm{Ax}=\bm{b}$) described
in Equation 5. Similar to the technique described in Lemma 4.7 (which in turn
uses Lemma 4.1), set one variable to $0$ at a time giving solution
$(\pi_{\bm{s}_{i}\cup\\{v^{1}\\}},\ldots,\pi_{\bm{s}_{i}\cup\\{v^{k}\\}})$
corresponding to targets
$(\bm{s}_{i}\cup\\{v^{1}\\},\ldots,\bm{s}_{i}\cup\\{v^{k}\\})$ as described in
Section 4.2. For every variable that is set to $0$, create a set
$\mathcal{T}=\\{(\bm{s}_{i}\cup\\{v^{l^{\prime}}\\},\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}):{l^{\prime}}\in[k]\\}$
containing the solution. For every such $\mathcal{T}$, iterate through the
tuples in it. If some $\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}<0$, set
$\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}\leftarrow 0$. Compute the score
$r(\mathcal{T})=\|\bm{A\pi}-\bm{b}\|^{2}$, where
$\bm{\pi}=(\pi_{\bm{s}_{i}\cup\\{v^{1}\\}},\ldots,\pi_{\bm{s}_{i}\cup\\{v^{k}\\}})$.
Next, select $\mathcal{T}$ with the smallest value of $r(\mathcal{T})$. For
this selected $\mathcal{T}$, check if
$\mu_{i}-\sum_{{l^{\prime}}=1}^{k}\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}<\epsilon$.
If yes, re-normalize
$\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}\leftarrow(\mu_{i}\times\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}})/(\sum_{{l^{\prime\prime}}=1}^{k}\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime\prime}}\\}})$.
If no, add the tuple
$(\bm{s}_{i},\mu_{i}-\sum_{{l^{\prime}}=1}^{k}\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}})$
to $\mathcal{T}$. At the end of this process, collect all the intervention
tuples thus obtained (for all $i\in[q]$), in the set $\mathcal{T}$.

  4. 4.

Find the excluded value of node $V_{N+1}$, i.e. the value which is not present
in any target in $\mathcal{T}$. If no such value exists, find $v\in
C_{V_{N+1}}$ which minimizes $\sum_{i=1}^{q}\pi_{\bm{s}_{i}\cup\\{v\\}}$. For
each $i\in[q]$, set $\pi_{\bm{s}_{i}\cup\\{v\\}}\leftarrow 0$. For each
$i\in[q]$, renormalize the mixing coefficients
$\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}\leftarrow(\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime}}\\}}\times\mu_{i})/(\sum_{{l^{\prime\prime}}=1}^{k}\pi_{\bm{s}_{i}\cup\\{v^{l^{\prime\prime}}\\}})$.
Only keep the tuples with strictly positive mixing coefficients in
$\mathcal{T}$ i.e.
$\mathcal{T}\leftarrow\\{(\bm{s},\pi_{\bm{s}})\in\mathcal{T}:\pi_{\bm{s}}>0\\}$.
return $\mathcal{T}$

Algorithm 2 DISENTANGLE-FINITE

##  Appendix E Additional Simulations

###  E.1 Effect of Graph Size

Figure 2: Performance of Algorithm 2 as a function of number of nodes in the
graph. The error bars show the $20\%$ and $80\%$ quantile respectively.

Figure 2 shows the variation of performance of Algorithm 2 keeping the number
of samples fixed at $\sim 10^{6}$. We observe that recall decreases and root-
mean-squared error in mixing coefficient increases very quickly as the number
of nodes increases in the graph. Even though this is expected since error is
accumulated as we successively add nodes and find new intervention targets,
such performance for a very large sample size indicates bad dependence of
sample complexity on the number of nodes. Improving this needs more
exploration and is left for future work.

###  E.2 Effect of Graph Type

Figure 3: Comparison of performance of Algorithm 2 for CBNs generated from
Erdös-Rényi (ER) and Scale Free (SF) models.

In Figure 3, we demonstrate performance of Algorithm 2 for CBNs generated from
two different family of random graphs (Erdös-Rényi (ER) and Scale-Free (SF)).
We observe no significant difference in performance for these models and make
a conjecture that only high level graph parameters (such as number of nodes,
edges, in-degree etc.) might be having an impact on performance and the
topology (given these parameters) might not be that crucial.

##  Appendix F Evaluation Metrics

Let $\mathcal{T}$ denote the actual set of intervention targets and
$\widehat{\mathcal{T}}$ denote the set of intervention targets computed by our
algorithm. Let $\pi_{\bm{t}}$, $\widehat{\pi}_{\bm{s}}$ denote mixing
coefficients of target $\bm{t}$, $\bm{s}$ in $\mathcal{T}$ and
$\widehat{\mathcal{T}}$ respectively. We use the following evaluation metrics
to evaluate the performance of our algorithm.

  1. 1.

Recall: Proportion of number of targets in $\mathcal{T}$ that were correctly
identified in $\mathcal{\widehat{T}}$

$\text{Recall}=\frac{|\mathcal{T}\cap\mathcal{\widehat{T}}|}{|\mathcal{T}|}.$

  2. 2.

Root Mean Squared Error: Root-mean-squared error (RMSE) in the mixing
coefficients.

$\text{RMSE}=\sqrt{\frac{\begin{aligned}
\sum_{\bm{t}\in\mathcal{T}\cap\mathcal{\widehat{T}}}(\pi_{\bm{t}}-\widehat{\pi}_{\bm{t}})^{2}+\sum_{\bm{t}\in(\mathcal{T}\setminus\mathcal{\widehat{T}})}(\pi_{\bm{t}})^{2}+\sum_{\bm{t}\in(\mathcal{\widehat{T}}\setminus\mathcal{T})}(\widehat{\pi}_{\bm{t}})^{2}\\\
\end{aligned}}{|\mathcal{T}\cup\mathcal{\widehat{T}}|}}$

  3. 3.

False-Positive RMSE: RMSE in the mixing coefficients of the incorrectly
identified targets.

$\text{FP-
RMSE}=\sqrt{\frac{\sum_{\bm{t}\in(\mathcal{\widehat{T}}\setminus\mathcal{T})}(\widehat{\pi}_{\bm{t}})^{2}}{|\mathcal{\widehat{T}}\setminus\mathcal{T}|}}$

  4. 4.

False-Negative RMSE: RMSE in the mixing coefficients of targets not
identified.

$\text{FN-
RMSE}=\sqrt{\frac{\sum_{\bm{t}\in(\mathcal{T}\setminus\mathcal{\widehat{T}})}(\pi_{\bm{t}})^{2}}{|\mathcal{T}\setminus\mathcal{\widehat{T}}|}}$