# Causal Discovery in Linear Structural Causal Models with Deterministic
Relations

Yuqin Yang School of Mathematics, Georgia Institute of Technology.
<EMAIL_ADDRESS>Mohamed Nafea Electrical & Computer Engineering
Department, University of Detroit Mercy<EMAIL_ADDRESS>AmirEmad
Ghassami Department of Computer Science, Johns Hopkins University.
<EMAIL_ADDRESS>Negar Kiyavash College of Management of Technology, École
Polytechnique Fédérale de Lausanne (EPFL<EMAIL_ADDRESS>
###### Abstract

Linear structural causal models (SCMs)– in which each observed variable is
generated by a subset of the other observed variables as well as a subset of
the exogenous sources– are pervasive in causal inference and casual discovery.
However, for the task of causal discovery, existing work almost exclusively
focus on the submodel where each observed variable is associated with a
distinct source with non-zero variance. This results in the restriction that
no observed variable can deterministically depend on other observed variables
or latent confounders. In this paper, we extend the results on structure
learning by focusing on a subclass of linear SCMs which do not have this
property, i.e., models in which observed variables can be causally affected by
any subset of the sources, and are allowed to be a deterministic function of
other observed variables or latent confounders. This allows for a more
realistic modeling of influence or information propagation in systems. We
focus on the task of causal discovery form observational data generated from a
member of this subclass. We derive a set of necessary and sufficient
conditions for unique identifiability of the causal structure. To the best of
our knowledge, this is the first work that gives identifiability results for
causal discovery under both latent confounding and deterministic
relationships. Further, we propose an algorithm for recovering the underlying
causal structure when the aforementioned conditions are satisfied. We validate
our theoretical results both on synthetic and real datasets.

##  1 Introduction

Causal discovery, which refers to the problem of learning causal relationships
among the variables of a system, has received extensive attention with
applications ranging from social sciences, economics, all the way to biology.
The gold standard of causal discovery is performing interventions (i.e.,
controlled experiments). But such experiments could be costly, infeasible, or
even at times unethical. This necessitates developing statistical methods
based on purely observational data, where further assumptions on the data
generating process are needed.

Linear structural causal models (SCMs) have been extensively considered in the
literature perhaps as the most pervasive causal data generating model (Pearl,,
2009; Spirtes et al.,, 2000; Peters et al.,, 2017). In this model, the system
is comprised of a set of observed (endogenous) variables and

$x_{1}$$x_{2}$$x_{3}$$s_{1}$$s_{2}$$s_{3}$(a)

Linear G-SCMLinear DS-SCM Linear DS-P-SCM Linear P-SCM(b)

Figure 1: (a) A linear P-SCM with observed variables $(x_{1},x_{2},x_{3})$ and
independent sources $(s_{1},s_{2},s_{3})$. This model cannot be represented as
a linear DS-SCM, since $x_{3}$ is fully determined by $(x_{1},x_{2})$. (b)
Relations among linear causal models. The intersection DS-P-SCM represents the
linear causal models under distinct source assumption, jointly independent
sources and linear latent confounding.

a set of source (exogenous) variables. Each observed variable $x$ is generated
as a linear combination of a subset of the other observed variables $Pa(x)$
(called direct causes of $x$) plus a function of a subset of the source
variables $S(x)$. We refer to this model as the linear general SCM (G-SCM).

Literature on linear G-SCM for causal discovery almost exclusively focuses on
a subset of G-SCM, in which for each observed variable $x$, at least one
source in $S(x)$ is distinct and has non-zero variance (Peters et al.,, 2017).
Here, a distinct source of observed variable $x$ means a source $s\in S(x)$
that does not belong to any other subsets $S(x^{\prime})$, $x^{\prime}\neq
x$.111A more common representation of this subclass is that each observed
variable $x$ is only associated with one source, and the source of each
observed variable is not a deterministic function of other sources. Then the
non-distinct (i.e., shared) sources can be explained as latent confounders in
the system. We refer to this submodel of G-SCM as _distinct source SCM_ (DS-
SCM). This restriction implies that no observed variable can be a
deterministic function of any other observed variables and/or any latent
confounders in the system. However, in a G-SCM, an observed variable is
allowed to have no distinct sources (or equivalently can have a distinct
source with zero-variance). Hence, deterministic relations are allowed.
Deterministic relations are problematic in causal discovery as they introduce
additional dependencies among variables (Peters et al.,, 2017). Specifically,
when deterministic relations exist, d-separation is not complete anymore
(although it remains sound). Such complications are perhaps the reason that
deterministic relations are avoided for the most part in the literature.

Furthermore, G-SCMs without distinct sources can have practical significance
in problems beyond causal modelling. This subset of G-SCMs can be used to
model influence propagation through networks, where the observed nodes are
influenced directly or indirectly by a set of external factors (sources).
Examples of such factors include sources of news or rumors, or sources of
diseases. Specifically, G-SCMs without distinct sources can be used to model
scenarios with less factors than observed nodes; this situation arises when a
few sources influence a group of observed variables in the system. For
instance, in a setting of spread of news, a large group of individuals may
have their news exclusively from a limited set of news sources (Guille et
al.,, 2013; Quinn et al.,, 2015). Other examples include spread of epidemics
(Nowzari et al.,, 2016), political campaigns (González-Bailón and Wang,,
2016), message passing in human brain networks (Karwowski et al.,, 2019).

In this paper, we focus on another subclass of linear G-SCMs which relaxes the
distinct source assumption of DS-SCM and hence, allows for deterministic
relations among the observed variables. In our proposed model, we consider a
set of jointly independent source variables. Each observed variable is
generated as a linear combination of the other observed variables plus a
linear combination of the sources. We relax the distinct source assumption of
DS-SCM by assuming instead that each observed variable contains strictly more
sources than any of its direct causes. Figure 1(a) depicts an example which
satisfies our assumption but violates the assumption of DS-SCM. As previously
mentioned, sharing sources introduces latent confounding among the variables.
Hence our introduced model allows for both latent confounders as well as
deterministic relations. We refer to this model as the linear _propagation
SCM_ (P-SCM). Majority of works in the literature on linear causal models in
fact consider an intersection of P-SCM and DS-SCM, which we refer to as DS-P-
SCM. Therefore, our work strictly expands the considered model space compared
to those works. See Figure 1(b) for a schematic representation of the
relations among the linear models.

We study the problem of causal discovery when the data generating model is a
linear P-SCM, that is, to learn the directions and strengths of the causal
influences among the observed variables, as well as the direct connections
from the sources to the observed variables. We derive a set of necessary and
sufficient conditions for unique identifiability of the causal structure from
observational data. To the best of our knowledge, this is the first work that
gives identifiability results for causal discovery under both latent
confounding and deterministic relationships. We further propose an algorithm
which uniquely identifies the causal structure when the conditions are
satisfied. Also, we derive an equivalent condition when the generating model
is a linear DS-P-SCM. We examine our algorithm on synthetic and real datasets,
and compare with existing causal discovery methods, developed for linear DS-
SCMs with or without latent confounders. Our results show that our proposed
algorithm outperforms those methods in recovering the underlying structure.

Related work. Under causal sufficiency, Shimizu et al., (2006) showed that a
linear non-Gaussian additive model (LiNGAM), in which source variables have
non-Gaussian distributions, allows for unique identifiability of the causal
structure from observations. Causal sufficiency is a common assumption in
causal discovery which means there exist no latent confounders for any pair of
observed variables. Yet, without considering the effect of latent confounders,
one may infer wrong causal relations among observed variables. Hoyer et al.,
(2008) and Salehkaleybar et al., (2020) considered an extension of LiNGAM in
the presence of latent variables (lvLiNGAM). Our model generalizes lvLiNGAM to
the case when observed variables are allowed to deterministically depend on
other observed variables or latent confounders. We further comment on the
connection of our model to lvLiNGAM in Appendix C.4.

SCMs with deterministic relations have been considered in a few work. In
(Geiger et al.,, 1990; Spirtes et al.,, 2000), D-separation condition (with
capital letter D) is proposed for graphically determining conditional
independencies when deterministic relations are allowed. Yet, it remained
unclear whether D-separation condition can capture all conditional
independencies induced from the distribution. Daniušis et al., (2010)
considered a system with only two variables, one variable deterministically
causing the other, and showed that the correct causal direction can be learnt
if the deterministic function contains no information about the cause variable
and vice versa. Their analysis does not hold for linear relations though.
Scheines et al., (1996) considered recovering a reduced model in which all
deterministic variables are removed. Luo, (2006); Mabrouk et al., (2014);
Lemeire et al., (2012) adapted conventional causal discovery methods such as
PC and greedy-search algorithms (Pearl,, 2009; Tsamardinos et al.,, 2006;
Chickering,, 2002), where deterministic relations are detected either by
additional independence tests, or by calculating conditional entropy among
variables. The aforementioned methods suffer from identifiability problem. In
particular, majority of these methods do not discuss the capability of
identifying the underlying structure by their algorithm (e.g., the equivalence
classes of the recovery result). Besides, these methods do not consider the
presence of latent confounders in the system. Please refer to Appendix A for a
detailed background on causal discovery methods.

##  2 System model

Notation. We use upper-case letters for vectors and bold upper-case letters
for matrices. We use $[n]\triangleq\\{1,2,\cdots,n\\}$. If
$X=[x_{1},\cdots,x_{p}]$, $X_{[i:j]}$ is the sub-vector
$[x_{i},x_{i+1},\cdots,x_{j}]$; $1\leq i<j\leq p$. We use
$x_{i}\rightsquigarrow x_{j}$ to refer to a directed path from node $x_{i}$ to
node $x_{j}$ (in the corresponding graph).

###  2.1 Generating model

As we mentioned in the introduction, linear G-SCM is one of the main data
generating models assumed in the literature. A G-SCM (Pearl,, 2009, Definition
7.1.1) is a 4-tuple
$\langle\mathcal{S},\mathcal{X},\mathcal{F},P(\mathcal{S})\rangle$, where
$\mathcal{S}$ is a set of source variables; $\mathcal{X}$ is a set of observed
variables; $\mathcal{F}=\\{f_{x}\\}_{x\in\mathcal{X}}$ is a set of functions
such that for each $x\in\mathcal{X}$, $x=f_{x}(Pa(x),S(x))$, where
$Pa(x)\subseteq\mathcal{X}\setminus\\{x\\}$ and $S(x)\subseteq\mathcal{S}$ ;
$P(\mathcal{S})$ is a joint probability distribution over $\mathcal{S}$. In
the case of linear functions, the model is restricted as follows:

######  Definition 1 (Linear G-SCM)

A linear G-SCM is the subclass of G-SCM in which each observed variable $x$ is
generated as $x=f_{x}(Pa(x))+g_{x}(S(x))$, where $f_{x}$ is a linear function
and $g_{x}$ is a function indicating the effects from the sources. We refer to
$g_{x}(S(x))$ as the source mixture corresponding to variable $x$.

Previous works on causal discovery mostly focus on a subclass of linear G-SCM
which satisfies the distinct source assumption defined below.

######  Assumption 1 (Distinct source assumption)

A linear G-SCM satisfies the distinct source assumption if each $S(x)$
contains at least one distinct source, that is, a source with non-zero
variance that does not appear in any other $S(x^{\prime})$ for $x^{\prime}\neq
x$.

We refer to the subclass of linear G-SCMs satisfying the distinct source
assumption as linear DS-SCM. The non-distinct (i.e., shared) sources represent
latent confounders in the system. Assumption 1 can be interpreted as that the
source mixture for one variable cannot be a deterministic function of the
source mixture of the rest of the variables. Equivalently, no observed
variable can be a deterministic function of any other observed variables
and/or any latent confounders in the system.

In this paper, we introduce another subclass of linear G-SCMs, which we refer
to as the linear propagation SCM (P-SCM). Consider a set of observed variables
$\mathcal{X}=\\{x_{1},\cdots,x_{p}\\}$ arranged in a causal order (no latter
variable causes any earlier variable), and another set of jointly independent
source variables $\mathcal{S}=\\{s_{1},\cdots,s_{m}\\}$. In the generating
model of a linear P-SCM, each observed variable consists of a linear
combination of earlier observed variables plus another linear combination of
the sources. Specifically,

$\displaystyle x_{i}$
$\displaystyle={{\sum}}_{j=1}^{i-1}\;a_{ij}x_{j}+\tilde{s}_{i},\qquad\tilde{s}_{i}=g_{x_{i}}(S(x_{i}))={{\sum}}_{j=1}^{m}b_{ij}s_{j}.$
(1)

$a_{ij}$ is the strength of the direct causal effect from $x_{j}$ to $x_{i}$.
$\tilde{s}_{i}$, $i\in[p]$ represents the mixture of sources exogenously
causing $x_{i}$. $b_{ij}$ is the strength of the direct exogenous effect from
$s_{j}$ to $x_{i}$. We refer to $\\{\tilde{s}_{1},\cdots,\tilde{s}_{p}\\}$ as
source mixtures or simply mixtures. Note that since (1) allows observed
variables to share sources, our model allows for latent confounding.222Note
that prohibiting latent confounders, i.e., causal sufficiency, requires
independent source mixtures. However, the latent confounding can only be
linear, i.e., it is due to the source mixtures being linear combinations of
elements in $\mathcal{S}$. In our model we require the following assumption on
the generating model which is weaker than Assumption 1 of DS-SCM.

###### Assumption 2

If $x_{i}$ is a direct cause of $x_{j}$, then there is at least one source in
$x_{j}$ that is not in $x_{i}$.

Unlike the distinct source assumption in DS-SCMs, Assumption 2 does not
necessarily require each observed variable to be associated with a distinct
source (see Figure 1(a) for an example). Therefore, our model allows for
deterministic relations. We provide a detailed comparison of our model with
DS-SCM in Section 4.

We define the causal diagram of the model as a directed graph in which the
vertex set consists of the observed variables $\mathcal{X}$ and the source
variables $\mathcal{S}$. There is a directed edge from observed variable
$x_{i}$ to $x_{j}$ if and only if $a_{ji}\neq 0$ (we refer to such an edge as
a causal connection), and a directed edge from source $s_{i}$ to observed
variable $x_{j}$ if and only if $b_{ji}\neq 0$ (we refer to such an edge as an
exogenous connection). Due to the assumed causal order, the causal diagram is
acyclic, and hence the model is a directed acyclic graph (DAG). The model in
(1) can be written in the matrix form as

$\displaystyle
X=\mathbf{A}X+\tilde{S};\qquad\tilde{S}=\mathbf{B}S,\vspace{-2mm}$ (2)

where $X\triangleq[x_{1},\cdots,x_{p}]^{\top}$,
$\tilde{S}\triangleq[\tilde{s}_{1},\cdots,\tilde{s}_{p}]^{\top}$,
$S\triangleq[s_{1},\cdots,s_{m}]^{\top}$. $\mathbf{A}$ is a $p\times p$
strictly lower triangular matrix with the coefficient $a_{ij}$ on the
$(i,j)$-th entry. $\mathbf{B}$ is a $p\times m$ matrix with the coefficient
$b_{ij}$ on the $(i,j)$-th entry. The strictly lower triangular matrix
$\mathbf{A}$ attests the existence of a causal order among the observed
variables (the generating process is recursive (Bollen,, 1989)). Mixtures
$\tilde{s}_{i}$, $i\in[p]$ represent additive exogenous noises.

###  2.2 Identifiability assumptions

In (2), each $x_{i}$ can be written as a linear combination of the sources.
Let $\mathbf{W}$ be a mixing matrix s.t.

$\displaystyle
X=\mathbf{W}S,\qquad\text{where}\quad\mathbf{W}=(\mathbf{I}-\mathbf{A})^{-1}\mathbf{B},\vspace{-2mm}$
(3)

Define the component set of a variable $x_{i}=\sum_{j}w_{ij}s_{j}$ (or a
mixture $\tilde{s}_{i}=\sum_{j}b_{ij}s_{j}$) as
${\rm{Comp}}(x_{i})=\left\\{s_{j}\in\mathcal{S}~{}|w_{ij}\neq 0\;(\text{or
}b_{ij}\neq 0)\right\\}.$ We require the following assumptions for
identifiability.

######  Assumption 3 (P-SCM faithfulness)

  1. (a)

If $x_{i}$ is an ancestor of $x_{j}$, then all source components in $x_{i}$
must also appear in $x_{j}$.

  2. (b)

Let $\mathbf{B}_{p}$ be an arbitrarily permuted version of matrix $\mathbf{B}$
(either row or column permutations). Any submatrix of $\mathbf{B}_{p}$ (with
non-zero rows or columns) is of full rank.

######  Assumption 4 (Separability)

We assume the linear P-SCM is separable– its corresponding mixing matrix
$\bf{W}$, cf. (3), can be correctly recovered using observations $X$, up to
scaling and permutation of its columns.

P-SCM faithfulness assumption is extended from the common faithfulness
assumption in studying causal models (Spirtes et al.,, 2000; Pearl,, 2009).
This assumption is satisfied almost surely if all model coefficients
$\\{a_{ij}\\}$ and $\\{b_{ij}\\}$ are drawn randomly and independently from
continuous distributions (Meek,, 1995). Separability, on the other hand, can
be achieved using blind source separation (BSS) methods (Comon and Jutten,,
2010), given certain assumption on the sources. For example, when the sources
are non-Gaussian random variables, the mixing matrix $\bf{W}$ can be recovered
using Independent Component Analysis (ICA) or overcomplete ICA methods
(Comon,, 1994; Hyvarinen et al.,, 2002; Lewicki and Sejnowski,, 2000). Other
BSS methods include Statistical Blind Source Separation Regression (SBSSR)
model and Non-negative Matrix Factorization (NMF). See Appendices B and C for
a background on faithfulness assumption and BSS methods and how they apply to
our model. Note that the result of BSS may suffer from permutation and
scalability indeterminacies, due to lack of prior information about the
sources. In Appendix C.4 we show that these indeterminacies do not affect the
recovery performance of our algorithm. Specifically, we show that, even in the
presence of these indeterminacies, our recovered model is identical to the
true model.

##  3 Conditions for unique identifiability

In this section, we present the necessary and sufficient conditions for unique
identifiability of a linear P-SCM, which consists of two parts, the unique
components condition and marriage condition. Both conditions are imposed on
the “possible parent set” of each observed variable which is a superset of its
ancestors that can be recovered from the mixing matrix (from observational
data). We first define the possible parent set, and then present the
combinatorial version of the conditions. Equivalent algebraic (matrix)
representations of the conditions are provided in Appendix E.1.

The necessary and sufficient condition we derive for unique identifiability of
a linear P-SCM, as well as our proposed algorithm, require a search over the
possible parent set of an observed variable $x_{k}$ which is defined as
follows.

###### Definition 2

The _possible parent set_ of an observed variable $x_{k}$ is defined as the
set of observed variables in $\mathcal{X}$ whose component set is a strict
subset of the component set of $x_{k}$. That is,
$\mathcal{P}_{k}=\\{x_{i}\in\mathcal{X}|{\rm{Comp}}(x_{i})\subsetneq{\rm{Comp}}(x_{k})\\}$.

We refer to the elements of this set as the “possible parents” of $x_{k}$
since each element is a candidate to be a parent of $x_{k}$, according to
P-SCM faithfulness assumption. The possible parent set of $x_{k}$ (i) can be
deduced from the mixing matrix and (ii) can be strictly smaller than the set
of observed variables preceding $x_{k}$ in the causal order; see Appendix D.2
for an example.

In linear DS-SCMs, since each observed variable has a distinct source,
$\mathcal{P}_{k}$ only includes the ancestors of $x_{k}$ in the generating
model (see Section 4.1 for more explanation). This property allows to identify
all the observable ancestors of each variable $x_{k}$ from the mixing matrix.
Subsequently, an algorithm, such as lvLiNGAM in (Salehkaleybar et al.,, 2020),
can recover the directed causal paths among variables. By contrast, in our
linear P-SCM, the possible parent set $\mathcal{P}_{k}$ can include observed
variables which are not ancestors of $x_{k}$. The reason behind this is that
there may exist an observed variable which does not have a distinct source,
hence this variable can mimic an ancestor of $x_{k}$ by its exogenous
connections to the sources.

From (3), the observed variables are given by
$X\\!=\\!(\mathbf{I}\\!-\\!\mathbf{A})^{-1}\mathbf{B}S\\!=\\!(\mathbf{I}\\!-\\!\mathbf{A})^{-1}\tilde{\mathbf{B}}S^{\prime}$,
where $\tilde{\mathbf{B}}$ is a version of $\mathbf{B}$ with the columns
arbitrarily permuted and rescaled such that
$\tilde{\mathbf{B}}S^{\prime}=\mathbf{B}S$. Note that the $(i,j)$-th entry of
$(\mathbf{I}-\mathbf{A})^{-1}$ represents the total causal effect from
observed variable $x_{j}$ to observed variable $x_{i}$ (Spirtes et al.,,
2000). Our task is to uniquely recover $(\mathbf{I}-\mathbf{A})^{-1}$, i.e.,
the total causal effects among observed variables, and to recover $\mathbf{B}$
up to permutation and scaling of its columns, i.e., the exogenous connections
from the sources to the observed variables. Note that the permutation
indeterminacy of $\mathbf{B}$ is immaterial since there exists no ordering
between the exogenous connections, and we are not concerned about the
scalability indeterminacy in recovering their effect. Next, we introduce the
necessary and sufficient conditions for recovering
$(\mathbf{I}-\mathbf{A})^{-1}$ and $\tilde{\mathbf{B}}$.

###  3.1 Unique components condition

When recovering the total causal effect from possible parents of $x_{k}$
(i.e., variables in $\mathcal{P}_{k}$) to $x_{k}$, the question is whether
each existing component in $x_{k}$ (i.e.,
$s\in\bigcup_{x_{i}\in\mathcal{P}_{k}}{\rm{Comp}}(x_{i})$) comes from a
possible parent ($x_{i}\in\mathcal{P}_{k}$), or comes from the exogenous
connections to $x_{k}$ (i.e., $\tilde{s}_{k}=\sum_{l=1}^{m}\;b_{kl}s_{l}$), or
maybe both. To address this question, we propose the concept of unique
components. For a possible parent $x_{i}\in\mathcal{P}_{k}$, if
$\tilde{s}_{i}$ has a component that is not shared by the source mixture of
any other possible parent in $\mathcal{P}_{k}$ (i.e., any $\tilde{s}_{j}$;
$j\neq i$, $x_{j}\in\mathcal{P}_{k}$), then we can use this unique component
to compute the total causal effect from $x_{i}$ to $x_{k}$ (by dividing the
coefficient of this unique component in $x_{k}$ by its coefficient in
$x_{i}$).

We can recursively use the unique components idea to find the total causal
effects from all possible parents in $\mathcal{P}_{k}$ to $x_{k}$: After using
the unique components to recover total causal effects from the corresponding
possible parents to $x_{k}$, we remove those variables and search for unique
components with respect to the remainder subset of $\mathcal{P}_{k}$. Thus, we
extend the concept of unique components to subsets of $\mathcal{P}_{k}$ by
considering only the possible parents in these subsets. We define the unique
components over the mixtures
$\tilde{\mathcal{S}}_{k}=\\{\tilde{s}_{i}:x_{i}\in\mathcal{P}_{k}\\}$ in an
iterative manner as follows.

###### Definition 3

Fix an observed variable $x_{k}$. For each possible parent of $x_{k}$, i.e.,
$x_{i}\in\mathcal{P}_{k}$, we define the _unique component set_ of $x_{i}$,
denoted by $U_{k}(i)$, as follows.
(i) Let $J^{(0)}=\\{i:x_{i}\in\mathcal{P}_{k}\\}$, i.e., the index set of the
possible parent set of $x_{k}$.
(ii) For $n=1,2,\cdots$ ($n$ is the iteration index):
\- For $i\in J^{(n-1)}$, define
$\tilde{U}_{k}^{(n)}(i)={\rm{Comp}}\left(\tilde{s}_{i}\right)\big{\backslash}\bigcup_{j\in
J^{(n-1)},j\neq i}{\rm{Comp}}\left(\tilde{s}_{j}\right).$
\- Let $J^{(n)}=\\{i\in J^{(n-1)}|~{}\tilde{U}^{(n)}_{k}(i)=\emptyset\\}$.
\- Repeat until $|J^{(N+1)}|=|J^{(N)}|$ for some $N\in\mathbb{N}$. Define
$\mathcal{I}_{k}=\\{x_{l}:l\in J^{(N)}\\}$.
For each $x_{i}\in\mathcal{P}_{k}$, $U_{k}(i)=\tilde{U}_{k}^{(n)}(i),~{}i\in
J^{(n-1)}\backslash J^{(n)},~{}n=1,\cdots,N$; $U_{k}(i)=\emptyset,~{}i\in
J^{(N)}$.

In Definition 3, when $n=1$, $\tilde{U}_{k}^{(1)}(i)$ represents the
components in $\tilde{s}_{i}$ but not in any other $\tilde{s}_{j}$, where
$x_{j}\in\mathcal{P}_{k}$ (or equivalently $j\in J^{(0)}$). $J^{(1)}$
represents the index set of $\mathcal{P}_{k}^{(1)}$ which is the subset of
$\mathcal{P}_{k}$ composed of observed variables with no unique components in
the first iteration. In the next iteration, $\tilde{U}_{k}^{(2)}(i)$ is
defined similarly but only for $i\in J^{(1)}$. $J^{(2)}$ is the index set of
the subset of $\mathcal{P}_{k}^{(1)}$ with no unique components. This
procedure is repeated until no more unique components are found;
$\mathcal{I}_{k}\subseteq\mathcal{P}_{k}$ is the remaining subset of possible
parents with no unique components after the procedure terminates. Appendix D.3
provides an example to demonstrate this iterative definition.

We use Definition 3 as follows. We (i) identify the possible parents in
$\mathcal{P}_{k}$ with unique components, (ii) compute their total causal
effects to $x_{k}$ using these unique components, and (iii) subtract the
learnt causal effects from $x_{k}$. Next, we consider only the possible
parents with no unique components in the first iteration
($x_{i}\in\mathcal{P}_{k}^{(1)}$), and find which of these have unique
components among variables in $\mathcal{P}_{k}^{(1)}$. We then use these
unique components to compute total causal effects from the corresponding
variables in $\mathcal{P}_{k}^{(1)}$ to $x_{k}$. Based on Definition 3, we
state the unique components condition as follows.

######  Condition 1 (Unique components condition)

(i) For each possible parent $x_{i}$ of $x_{k}$ (i.e.,
$x_{i}\in\mathcal{P}_{k})$ with a non-empty unique component set (i.e.,
$|U_{k}(i)|\neq 0$), the unique components of $x_{i}$ are not exogenously
connected to $x_{k}$. That is, ${\rm{Comp}}(\tilde{s}_{k})\cap
U_{k}(i)=\emptyset,\;\forall x_{i}\in\mathcal{P}_{k}\text{ s.t.
}U_{k}(i)\neq\emptyset.$
(ii) Further, for any $x_{i}\in\mathcal{P}_{k}$ with an empty unique component
set ($|U_{k}(i)|=0$), the exogenous connections to $x_{i}$ and $x_{k}$ are
disjoint. That is,
${\rm{Comp}}(\tilde{s}_{k})\cap{\rm{Comp}}(\tilde{s}_{i})=\emptyset,\;\forall
x_{i}\in\mathcal{P}_{k}\text{ s.t. }U_{k}(i)=\emptyset.$

The first part of Condition 1 states that if a source $s$ is a unique
component of any possible parent of $x_{k}$, then $s$ should not have an
exogenous connection to $x_{k}$. The second part states that any possible
parent of $x_{k}$ with no unique components should not overlap in any
exogenous connections with $x_{k}$ 333Note that when an observed variable has
multiple unique components, we only need one unique component not to be
exogenously connected to $x_{k}$ to infer the total causal effect. However,
there is no prior information about which of these unique components is not
exogenously connected to $x_{k}$, hence none of the unique components can be
exogenously connected to $x_{k}$. For more details, see the necessity proof in
Appendix E.3.. In general, $x_{k}$ can only be exogenously connected to (i)
source components that are shared only among its possible parents that have
unique component(s), (ii) new source components that are not connected to any
of its possible parents. Please refer to Example 6 in Appendix D.4 to see why
this condition is necessary for unique identifiability.

Input: Recovered mixing matrix $\tilde{\mathbf{W}}$ from BSS. Initialize:
$\tilde{\mathbf{A}}=\mathbf{I}$, $\mathbf{B}=\mathbf{0}$.

1 Repermute $\tilde{\mathbf{W}}$ such that the number of non-zero entries in
each row is in an increasing order (rows with equal number of non-zero entries
are permuted at random) ;

2 for  _$k=1:p$_ do

3 Find possible parent set $\mathcal{P}_{k}$ using $\tilde{\mathbf{W}}$;
Select the row $W_{k}=\tilde{\mathbf{W}}[k,:]$; Initialize
$\bar{\mathcal{P}}_{k}=\mathcal{P}_{k}$ ;

4 Find the set $\mathcal{U}$ of possible parents in $\bar{\mathcal{P}}_{k}$
that have unique components ;

5 if  _$|\mathcal{U}|\neq 0$_ then

6 Compute the total causal effect $\tilde{a}_{ki}$ for each
$x_{i}\in\mathcal{U}$ using its unique components ;

7 $W_{k}\leftarrow
W_{k}-\sum_{x_{i}\in\mathcal{U}}\tilde{a}_{ki}\mathbf{B}[i,:]$;
$\bar{\mathcal{P}}_{k}\leftarrow\bar{\mathcal{P}}_{k}\setminus\mathcal{U}$; Go
back to Step 1 using updated $\bar{\mathcal{P}}_{k}$ ;

8

9 else

10 Select the rows of $\mathbf{B}$ corresponding to the possible parents in
$\bar{\mathcal{P}}_{k}$, denote by $\mathbf{B}_{I}$;

11 Compute $\tilde{a}_{ki}$ by solving an overdetermined linear system, using
the non-zero columns of $\mathbf{B}_{I}$ and the corresponding entries in
$W_{k}$; Set the selected entries of $W_{k}$ as 0 ;

12

13 $\mathbf{B}[k,:]=W_{k}$;

14

15$\mathbf{A}=\mathbf{I}-\tilde{\mathbf{A}}^{-1}$;

Output: Repermuted matrices $\mathbf{A}$, $\mathbf{B}$ according to the
reversed order from Step 1.

Algorithm 1 P-SCM Recovery

###  3.2 The marriage condition

The second part of the necessary and sufficient conditions for unique
identifiability of a linear P-SCM is identical to the marriage condition of
Hall’s marriage theorem (Cameron,, 1994). The combinatorial formulation of
this theorem considers a collection of finite sets and provides a necessary
and sufficient condition (the marriage condition) for the feasibility of
selecting a distinct element from each set.

######  Lemma 1 (Hall’s marriage theorem and marriage condition)

Let $X$ be a collection of finite subsets of a set $S$. The members of $X$ can
be counted with multiplicity (two or more members are identical). Define the
mapping $f(x):X\mapsto S$ s.t. $f$ selects a distinct element from each set
$x\in X$. The collection $X$ satisfies the marriage condition if for every
sub-collection $C\subseteq X$, $|C|\leq|\bigcup_{x\in C}x|$, i.e., every
$C\subseteq X$ covers at least $|C|$ different elements of $S$. Hall’s
Marriage Theorem states that, the mapping $f$ exists if and only if $X$
satisfies the marriage condition.

In our framework, the collection $X$ corresponds to the family of component
sets of possible parents of a variable $x_{k}$. Specifically, members of the
collection $X$ are the finite subsets
${\rm{Comp}}(x_{i})\subseteq\mathcal{S}$, $x_{i}\in\mathcal{P}_{k}$,
$\mathcal{S}$ is the set of sources. The marriage condition translates to the
following:

######  Condition 2 (The marriage condition)

For each observed variable $x_{k}$ with possible parent set $\mathcal{P}_{k}$,
every subset of the possible parent set, $X_{C}\subseteq\mathcal{P}_{k}$,
satisfies $|X_{C}|\leq\big{|}\bigcup_{x_{i}\in
X_{C}}{\rm{Comp}}(x_{i})\big{|}$. That is, every subset
$X_{C}\subseteq\mathcal{P}_{k}$ includes at least $|X_{C}|$ different source
variables.

Since each variable $x_{k}$ can be written as a linear combination of the
source mixtures in its possible parent set
($\tilde{\mathcal{S}}_{k}=\\{\tilde{s}_{i}:x_{i}\in\mathcal{P}_{k}\\}$) plus
$\tilde{s}_{k}$, the marriage condition can be equivalently imposed on the
collection $\tilde{\mathcal{S}}_{k}$: For
$\tilde{S}_{C}\subseteq\tilde{\mathcal{S}}_{k}$,
$|\tilde{S}_{C}|\leq\left|\bigcup_{\tilde{s}_{i}\in\tilde{S}_{C}}{\rm{Comp}}(\tilde{s}_{i})\right|$.
See Appendix F.3 for the proof. Recall that Condition 1 is also imposed on
$\tilde{\mathcal{S}}_{k}$ (the unique components are defined over the source
mixtures in $\mathcal{P}_{k}$). Please refer to Example 7 in Appendix D.4 to
see the necessity of the marriage condition for unique identifiability of a
linear P-SCM.

###  3.3 Main result

Our main result states the necessary and sufficient conditions for unique
identifiability of the total causal effects among the observed variables and
the exogenous connections from the sources.

###### Theorem 1

Let
$\mathcal{A}=\\{a_{ij},b_{ik}:i,j\in\\{1,\cdots,p\\},k\in\\{1,\cdots,m\\}\\}$.
$\mathcal{A}$ fully parameterizes a linear P-SCM. Let $\pi$ denote the
Lebesgue measure over $\mathcal{A}$. The causal effects and exogenous
connections of a linear P-SCM are uniquely identifiable from observations
almost surely (w.r.t. the measure $\pi$) if and only if, for any observed
variable $x_{k}$, both Conditions 1 and 2 are satisfied.

The proof of Theorem 1 appears in Appendix E. Necessity of the conditions is
proved using similar reasoning as in Examples 6 and 7: If either condition is
not satisfied, it is impossible to distinguish the true generating model from
certain different generating model(s). For sufficiency of the conditions, we
propose the P-SCM Recovery algorithm (Algorithm 1) and prove its correctness,
i.e., the algorithm recovers the true causal structure when the conditions are
satisfied. For each observed variable $x_{k}$ with possible parent set
$\mathcal{P}_{k}$, Algorithm 1 computes the total causal effects from
$x_{i}\in\mathcal{P}_{k}$ to $x_{k}$ using the unique components in $U_{k}(i)$
in the same iterative manner as described in Definition 3, until no more
unique components can be found in the last subset $\mathcal{I}_{k}$. The
algorithm computes the total causal effect from all $x_{i}\in\mathcal{I}_{k}$
to $x_{k}$ by solving an overdetermined linear system. After computing total
causal effects from all possible parents to $x_{k}$, the remaining parts in
$x_{k}$ are considered as exogenous connections.

##  4 Comparison with linear DS-SCM

There are two main differences between our proposed linear P-SCM and linear
DS-SCM. The first difference regards the type of latent confounders they
allow. From (1), in linear P-SCM, the source mixture associated with each
observed variable is comprised of a linear combination of jointly independent
sources, which can lead to linear latent confounding. That is, the dependency
between two source mixtures is due to the fact that they are both linear
combinations of the same set of sources. This is not necessarily the case for
linear DS-SCM, i.e., the source mixtures can be non-linear combinations of the
sources. The second difference between P-SCM and DS-SCM regards the
restriction of distinct sources. Linear P-SCM relaxes the distinct source
assumption to the requirement in Assumption 2 which assumes that each observed
variable contains strictly more sources than any of its direct causes. This
means that unlike DS-SCM, in our model, an observed variable can be a
deterministic function of its direct causes and the latent confounders.

Note that all the works in the literature on linear DS-SCM that we are aware
of– with the exception of (Wang and Drton,, 2020)– in fact consider an
intersection of P-SCM and DS-SCM, in which all three assumptions of linear
latent confounding, jointly independent sources (not necessarily independent
source mixtures), and Assumption 1 hold (Hoyer et al.,, 2008; Entner and
Hoyer,, 2010; Tashiro et al.,, 2014; Salehkaleybar et al.,, 2020). In this
case, the subclass of P-SCMs representing this subclass are those with matrix
$\mathbf{B}$ in (2) of the form $\mathbf{B}=[\mathbf{I}\;\;\mathbf{B}_{s}]$.
We refer to this subclass of linear G-SCM as linear DS-P-SCM. Therefore, our
work strictly expands the considered model space compared to those works. To
demonstrate the practical significance of linear P-SCM over linear DS-P-SCM in
causal discovery, we show that there are models that can be correctly
explained by a linear P-SCM, while linear DS-P-SCMs either are inapplicable or
give misleading results (hence the model cannot be recovered using causal
discovery methods for linear DS-P-SCMs). These examples appear in Appendix
D.1.

###  4.1 Reduction of the conditions for linear DS-P-SCM

To show how our conditions for unique identifiability of linear P-SCMs can be
reduced for linear DS-P-SCMs, consider the setting in which each observed
variable is associated with a distinct source. Under this setting, the model
can be equivalently written as a linear DS-SCM with linear latent confounding
and jointly independent sources (see Appendix F.1 for more details). This
setting reduces Conditions 1 and 2 in Theorem 1 as follows. First, all
possible parents of an observed variable $x_{k}$ have unique components, i.e.,
$U_{k}(i)\neq\emptyset$ for all $x_{i}\in\mathcal{P}_{k}$. This further
implies that the marriage condition is automatically satisfied. Second, for
each $x_{k}$, the possible parent set $\mathcal{P}_{k}$ is equivalent to the
ancestor set of $x_{k}$. This follows because, for each
$x_{i}\in\mathcal{P}_{k}$ with a distinct source $s_{j}$, since $s_{j}$ is not
connected to any other observed variables including $x_{k}$, the $s_{j}$
component in $x_{k}$ must result from $x_{i}$. Hence, there must be a causal
connection/path from $x_{i}$ to $x_{k}$. Theorem 2 below provides the
equivalent necessary and sufficient conditions for this setting. See Appendix
F.4 for the proof, as well as a graphical representation of the condition.

###### Theorem 2

Suppose every observed variable in the linear P-SCM is associated with a
distinct source. The causal effects and exogenous connections of a linear
P-SCM are uniquely identifiable from observations almost surely (in the sense
described in Theorem 1) if and only if the following condition holds: For a
source $s_{j}$ that is exogenously connected to an observed variable $x_{k}$,
either there are no causal paths from any observed variable containing $s_{j}$
to $x_{k}$, or there are at least two distinct causal paths from the observed
variable(s) with $s_{j}$ in their source mixtures to $x_{k}$.

###### Remark 1

The condition in Theorem 2 for a linear P-SCM with distinct source implies the
condition for unique identifiability of a linear DS-P-SCM in (Salehkaleybar et
al.,, 2020, Theorem 16), but the reverse is not true. Thus, a linear DS-P-SCM
can be uniquely identifiable in (Salehkaleybar et al.,, 2020) but not uniquely
identifiable (as a linear P-SCM) in our setting. The reason is that the search
space in Theorem 2, which is the whole class of linear P-SCMs, is strictly
larger than the search space in (Salehkaleybar et al.,, 2020), which is linear
DS-P-SCMs. See Appendix F.5 for the proof, and Figure 2 for a schematic
representation of the conditions.

Linear P-SCMLinear DS-P-SCM Uniquely identifiable in linear DS-P-SCM Uniquely
identifiable in linear P-SCM (A) Uniquely identifiable in linear P-SCM (B)
Figure 2: Theoretical results derived in this paper. Dashed circle represent
the (sufficient) condition for unique identifiability of a linear DS-P-SCM in
(Salehkaleybar et al.,, 2020, Theorem 16). Theorem 1 translates to: A linear
P-SCM $\mathcal{G}\in A\cup B\Leftrightarrow\mathcal{G}$ satisfies Conditions
1 and 2. Theorem 2 translates to: A linear DS-P-SCM $\mathcal{G}\in
A\Leftrightarrow\mathcal{G}$ satisfies the condition in Theorem 2.

###  4.2 Choice of the representation of linear P-SCM

Note that equivalently we can say P-SCM also requires distinct sources but
those sources can have zero variance (i.e., zero). In this case, as shown in
Appendix F.2, instead of the form in (2), our model can be equivalently
written as

$\displaystyle X=\mathbf{A}_{ol}X_{l}+\mathbf{A}X+S_{d},$ (4)

where $X_{l}$ is the vector of latent confounders; $S_{d}$ is the vector of
(possibly zero) jointly independent distinct sources; $\mathbf{A}_{ol}$
represents the latent confounding. This representation is perhaps more
familiar to the reader (as it is considered in most works on linear DS-P-SCM),
yet we claim that the representation in (2) is more suitable for the task of
identification when zero variance sources exist in the model: First, in order
to fully learn the structure of the model in (4), the number of latent
confounders must be known in advance (Hoyer et al.,, 2008; Salehkaleybar et
al.,, 2020), which cannot be deduced from the mixing matrix $\mathbf{W}$ when
deterministic relations are present. In this case, we can only learn the sum
of the number of latent confounders (i.e., cardinality of $X_{l}$) and non-
zero distinct sources (i.e., support of $S_{d}$). On the contrary, by
considering both latent confounders and non-zero distinct sources as $S$ in
(2), we do not need to know the number of latent confounders or the number of
non-zero distinct sources in the recovery. Second, our conditions for
identifiability of linear P-SCM depend on the exogenous connection matrix
$\mathbf{B}$, which includes both latent confounding and non-deterministic
relationships in (4) (i.e., matrix $\mathbf{A}_{ol}$ and the non-zero entries
in $S_{d}$). As a result, the identifiability results derived in this work
would be more complicated if translated on the model in (4), and we are not
aware of a straightforward way to do this translation.

##  5 Numerical experiments

We first provide estimates for the likelihood of satisfiability of the
conditions in Theorem 1. Specifically, we randomly generate linear P-SCMs and
linear DS-P-SCMs with fixed expected degrees among observed variables and
sources, and investigate what portion of them satisfy the conditions. We refer
to the generating model as a linear DS-P-SCM when each observed variable in
the generated P-SCM has a distinct source. Next, we evaluate the performance
of Algorithm 1 for P-SCM recovery on synthetic models under different
settings. Finally, for real data, we consider the closing prices of five world
stock indices, and model the corresponding returns as a linear P-SCM.

N100N225SSECHSIDJI

Figure 3: (Left) Satisfiability of our conditions on models generated
according to a linear P-SCM or DS-P-SCM. (Right) Recovered causal graphs among
five world stock indices.

Satisfiability of the conditions. We test the satisfiability of our derived
conditions on linear P-SCM and linear DS-P-SCM with different pairs of
$(d_{e},d_{o})$, where $d_{e}(d_{o})$ is the expected number of causal
(exogenous) connections for each observed (source) variable. Figure 3 (left)
shows the average number of generated models (attempts) required to obtain a
model that satisfies our conditions, plus/minus half the standard deviations
w.r.t. the source to observed node ratio (the number of sources divided by the
number of observed variables). The result shows that our conditions are likely
to be satisfied on (1) linear P-SCMs when the number of sources is large and
the average degrees are small, and (2) linear DS-P-SCMs when both the number
of sources and average degrees are small. We believe that satisfiability of
our conditions depends on (1) the existence and similarity of exogenous
connections among observed variables, (2) the ratio of overlap among exogenous
connections (how many sources are shared among observed variables) and (3) the
structural complexity of the causal connections among observed variables. See
Appendix G.1 for more details.

Figure 4: Performance of algorithms in terms of SHD/Edge metric (lower value
means better performance). P-SCMR_A, P-SCMR_B represent the recoveries of
$\mathbf{A}$, $\mathbf{B}$ by our algorithm.

Performance of recovery. We evaluate the performance of our recovery algorithm
on models generated under each of the following settings: (1) P-SCM with equal
number of observed variables and sources (P-SCM_Equal); (2) P-SCM with fewer
sources than observed variables (P-SCM_Fewer) (this indicates that
deterministic relation must exist); (3) DS-P-SCM with more sources than
observed variables (DS-P-SCM); (4) Same as Setting (1) but the model does not
satisfy our conditions (P-SCM_NonUnique). We only select the generating models
which satisfy Conditions 1 and 2 in the first three settings. The sources are
independently drawn from uniform distributions; we use FastICA (Hyvarinen,,
1999) and ReconstructionICA (Le et al.,, 2011) for BSS.

We compare our proposed algorithm with ICA-LiNGAM (Shimizu et al.,, 2006),
DirectLiNGAM (Shimizu et al.,, 2011), ParceLiNGAM (Tashiro et al.,, 2014),
Pairwise lvLiNGAM (Entner and Hoyer,, 2010), in terms of the differences
between recovered and true adjacency matrix $\mathbf{A}$, and recovered and
true exogenous connection matrix $\mathbf{B}$ (after normalization and
repermutation)444A well-known class of methods for causal structure learning
in the presence of latent confounders is FCI algorithm (Spirtes et al.,, 2000)
and its variants. Yet, due to the non-compatibility of the requirements of
these methods with our model, we did not compare our approach with these
methods (see Appendix G.2 for more details).. Evaluating $\mathbf{B}$ is only
applicable to our algorithm since other methods do not return $\mathbf{B}$. We
report the results for the normalized Structural Hamming Distance over true
edges (SHD/Edges); comparisons with additional metrics appear in Appendix G.2.
We compare the performance under (i) all ICA recoveries and (ii) only the
successful recoveries ($\tilde{\mathbf{W}}$ recovered by ICA is highly
accurate). Figure 4 shows the performance of recoveries for all algorithms
(whenever applicable), averaged over models randomly generated under Settings
(1)-(4). The number of observed nodes ranges from 5 to 10.

We observe that when the generating model is a P-SCM, our algorithm can learn
the model more accurately than existing algorithms, even if the conditions are
not satisfied. This is because existing algorithms may misinterpret the shared
sources among observed variables as confounding or direct causal connections,
which results in adding additional edges to the recovered graph. When the
generating model is a linear DS-P-SCM, the performance of our method is also
comparable to existing algorithms. Besides, our algorithm performs
significantly better than others when the ICA recovery is successful. Our
algorithm assumes that the true mixing matrix $\mathbf{W}$ can be recovered up
to permutation and scaling of its columns, hence depends heavily on the
accuracy of BSS recovery.

Performance on real data. We test the performance of our recovery algorithm on
the daily closing prices of the following five world stock indices: DJI, N225,
N100, HSI, SSEC (Hyvärinen et al.,, 2010; Salehkaleybar et al.,, 2020). We
consider the corresponding return (relative daily change) of each index as an
observed variable, and model these observed variables to be generated by a
linear P-SCM with five sources, where the sources are non-Gaussian random
variables. Using P-SCM Recovery algorithm, the directed graph among these
observed variables can be recovered as the right plot in Figure 3. We observe
that DJI is a root node of this DAG. Further, DJI, N225 N100 all have causal
effects on HSI. Both observations are known to be true either from common
belief in economy, or from previous results in (Hyvärinen et al.,, 2010).

##  6 Conclusion

We proposed the linear propagation SCM (P-SCM), which establishes a way of
allowing observed variables in a linear structural causal model to
deterministically depend on other observed variables or latent confounders. We
considered the problem of finding the necessary and sufficient conditions to
uniquely identify a linear P-SCM based on observational data. We proposed an
algorithm to recover the underlying causal model when a linear P-SCM is
assumed to be the data generating process. As mentioned earlier, the
performance of our proposed algorithm relies on the accuracy of blind source
separation (BSS) recovery. Future directions include investigating algorithms
that are robust to BSS errors. Further, it is of interest to investigate
whether relaxing the unique identifiability requirement could result in
simpler necessary and sufficient conditions that can be efficiently verified.

## References

  * Behr et al., (2018) Behr, M., Holmes, C., Munk, A., et al. (2018).  Multiscale blind source separation.  The Annals of Statistics, 46(2):711–744.
  * Bollen, (1989) Bollen, K. A. (1989).  Structural equations with latent variables.  John Wiley & Sons.
  * Cameron, (1994) Cameron, P. J. (1994).  Combinatorics: Topics, Techniques, Algorithms.  Cambridge University Press.
  * Chickering, (2002) Chickering, D. M. (2002).  Optimal structure identification with greedy search.  Journal of machine learning research, 3(Nov):507–554.
  * Comon, (1994) Comon, P. (1994).  Independent component analysis, a new concept?  Signal processing, 36(3):287–314.
  * Comon and Jutten, (2010) Comon, P. and Jutten, C. (2010).  Handbook of Blind Source Separation: Independent component analysis and applications.  Academic press.
  * Daniušis et al., (2010) Daniušis, P., Janzing, D., Mooij, J., Zscheischler, J., Steudel, B., Zhang, K., and Schölkopf, B. (2010).  Inferring deterministic causal relations.  In Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, pages 143–150.
  * Donoho and Stodden, (2004) Donoho, D. and Stodden, V. (2004).  When does non-negative matrix factorization give a correct decomposition into parts?  In Advances in neural information processing systems, pages 1141–1148.
  * Edmonds, (1967) Edmonds, J. (1967).  Systems of distinct representatives and linear algebra.  J. Res. Nat. Bur. Standards Sect. B, 71(4):241–245.
  * Efron and Tibshirani, (1994) Efron, B. and Tibshirani, R. J. (1994).  An introduction to the bootstrap.  CRC press.
  * Entner and Hoyer, (2010) Entner, D. and Hoyer, P. O. (2010).  Discovering unconfounded causal relationships using linear non-gaussian models.  In JSAI International Symposium on Artificial Intelligence, pages 181–195. Springer.
  * Eriksson and Koivunen, (2004) Eriksson, J. and Koivunen, V. (2004).  Identifiability, separability, and uniqueness of linear ICA models.  IEEE signal processing letters, 11(7):601–604.
  * Geiger et al., (1990) Geiger, D., Verma, T., and Pearl, J. (1990).  Identifying independence in bayesian networks.  Networks, 20(5):507–534.
  * González-Bailón and Wang, (2016) González-Bailón, S. and Wang, N. (2016).  Networked discontent: The anatomy of protest campaigns in social media.  Social networks, 44:95–104.
  * Guille et al., (2013) Guille, A., Hacid, H., Favre, C., and Zighed, D. A. (2013).  Information diffusion in online social networks: A survey.  ACM Sigmod Record, 42(2):17–28.
  * Hoyer et al., (2009) Hoyer, P. O., Janzing, D., Mooij, J. M., Peters, J., and Schölkopf, B. (2009).  Nonlinear causal discovery with additive noise models.  In Advances in neural information processing systems, pages 689–696.
  * Hoyer et al., (2008) Hoyer, P. O., Shimizu, S., Kerminen, A. J., and Palviainen, M. (2008).  Estimation of causal effects using linear non-gaussian causal models with hidden variables.  International Journal of Approximate Reasoning, 49(2):362–378.
  * Hyvarinen, (1999) Hyvarinen, A. (1999).  Fast and robust fixed-point algorithms for independent component analysis.  IEEE transactions on Neural Networks, 10(3):626–634.
  * Hyvarinen et al., (2002) Hyvarinen, A., Karhunen, J., and Oja, E. (2002).  Independent component analysis.  Studies in informatics and control, 11(2):205–207.
  * Hyvärinen and Oja, (2000) Hyvärinen, A. and Oja, E. (2000).  Independent component analysis: algorithms and applications.  Neural networks, 13(4-5):411–430.
  * Hyvärinen et al., (2010) Hyvärinen, A., Zhang, K., Shimizu, S., and Hoyer, P. O. (2010).  Estimation of a structural vector autoregression model using non-gaussianity.  Journal of Machine Learning Research, 11(5).
  * Karwowski et al., (2019) Karwowski, W., Vasheghani Farahani, F., and Lighthall, N. (2019).  Application of graph theory for identifying connectivity patterns in human brain networks: a systematic review.  frontiers in Neuroscience, 13:585.
  * Le et al., (2011) Le, Q. V., Karpenko, A., Ngiam, J., and Ng, A. Y. (2011).  Ica with reconstruction cost for efficient overcomplete feature learning.  In Advances in neural information processing systems, pages 1017–1025.
  * Lee and Seung, (1999) Lee, D. D. and Seung, H. S. (1999).  Learning the parts of objects by non-negative matrix factorization.  Nature, 401(6755):788–791.
  * Lemeire et al., (2012) Lemeire, J., Meganck, S., Cartella, F., and Liu, T. (2012).  Conservative independence-based causal structure learning in absence of adjacency faithfulness.  International Journal of Approximate Reasoning, 53(9):1305–1325.
  * Lewicki and Sejnowski, (2000) Lewicki, M. S. and Sejnowski, T. J. (2000).  Learning overcomplete representations.  Neural computation, 12(2):337–365.
  * Luo, (2006) Luo, W. (2006).  Learning bayesian networks in semi-deterministic systems.  In Conference of the Canadian Society for Computational Studies of Intelligence, pages 230–241. Springer.
  * Mabrouk et al., (2014) Mabrouk, A., Gonzales, C., Jabet-Chevalier, K., and Chojnacki, E. (2014).  An efficient bayesian network structure learning algorithm in the presence of deterministic relations.  In ECAI, volume 14, pages 567–572.
  * Meek, (1995) Meek, C. (1995).  Strong-completeness and faithfulness in belief networks.  In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. Citeseer.
  * Nowzari et al., (2016) Nowzari, C., Preciado, V. M., and Pappas, G. J. (2016).  Analysis and control of epidemics: A survey of spreading processes on complex networks.  IEEE Control Systems Magazine, 36(1):26–46.
  * Pearl, (2009) Pearl, J. (2009).  Causality.  Cambridge university press.
  * Peters and Bühlmann, (2014) Peters, J. and Bühlmann, P. (2014).  Identifiability of gaussian structural equation models with equal error variances.  Biometrika, 101(1):219–228.
  * Peters et al., (2017) Peters, J., Janzing, D., and Schölkopf, B. (2017).  Elements of causal inference: foundations and learning algorithms.  MIT press.
  * Quinn et al., (2015) Quinn, C. J., Kiyavash, N., and Coleman, T. P. (2015).  Directed information graphs.  IEEE Transactions on information theory, 61(12):6887–6909.
  * Salehkaleybar et al., (2020) Salehkaleybar, S., Ghassami, A., Kiyavash, N., and Zhang, K. (2020).  Learning linear non-gaussian causal models in the presence of latent variables.  Journal of Machine Learning Research, 21(39):1–24.
  * Scheines et al., (1996) Scheines, R., Spirtes, P., Glymour, C., Meek, C., and Richardson, T. (1996).  Tetrad 3: Tools for causal modeling–user’s manual.  CMU Philosophy.
  * Shimizu et al., (2006) Shimizu, S., Hoyer, P. O., Hyvärinen, A., and Kerminen, A. (2006).  A linear non-gaussian acyclic model for causal discovery.  Journal of Machine Learning Research, 7(Oct):2003–2030.
  * Shimizu et al., (2011) Shimizu, S., Inazumi, T., Sogawa, Y., Hyvärinen, A., Kawahara, Y., Washio, T., Hoyer, P. O., and Bollen, K. (2011).  DirectLiNGAM: A direct method for learning a linear non-gaussian structural equation model.  Journal of Machine Learning Research, 12(Apr):1225–1248.
  * Spirtes et al., (2000) Spirtes, P., Glymour, C. N., Scheines, R., and Heckerman, D. (2000).  Causation, prediction, and search.  MIT press.
  * Tashiro et al., (2014) Tashiro, T., Shimizu, S., Hyvärinen, A., and Washio, T. (2014).  Parcelingam: a causal ordering method robust against latent confounders.  Neural computation, 26(1):57–83.
  * Tsamardinos et al., (2006) Tsamardinos, I., Brown, L. E., and Aliferis, C. F. (2006).  The max-min hill-climbing bayesian network structure learning algorithm.  Machine learning, 65(1):31–78.
  * Wang and Drton, (2020) Wang, Y. S. and Drton, M. (2020).  Causal discovery with unobserved confounding and non-gaussian data.  arXiv preprint arXiv:2007.11131.

##  Appendix A Related work: A review of causal discovery methods

Conventional methods for recovering causal directions from observational data
often make use of Bayesian graphical models (Pearl,, 2009; Spirtes et al.,,
2000). Bayesian networks allow for the use of efficient algorithms, such as
the constraint-based PC and Fast Causal Inference (FCI) algorithms (Pearl,,
2009; Spirtes et al.,, 2000), and the score-based Greedy Equivalent Search
(GES) algorithm (Chickering,, 2002). However, these methods suffer from an
identifiability problem. In particular, they only allow for estimating the
underlying causal structure from data up to its Markov equivalence class,
i.e., the set of structures representing the same conditional independence
assertions under causal sufficiency. It turns out the Markov equivalence of
the causal structure is a fundamental limit of identification for an
underlying data generating process that is a linear DS-SCM with additive
Gaussian noises.

Further assumptions on the data generating process can narrow down the set of
possible models compatible with the observed data. These assumptions can be
made on the functional form relating the observed variables and/or the
distributions of the sources (noises). For example, Shimizu et al., (2006)
showed that assuming a linear non-Gaussian additive model (LiNGAM), in which
the noises have arbitrary non-Gaussian distributions, enables unique
identifiability of the causal structure under causal sufficiency. Alternative
assumptions may lead as well to unique identifiability: (Peters and Bühlmann,,
2014) showed that if all the variances of the noises in a linear Gaussian DS-
SCM are equal, then one can uniquely identify the causal structure. Also,
Hoyer et al., (2009) assumed (i) specific types of non-linearity relationships
among the observed variables, and (ii) additive exogenous noises, and showed
that, for the case of two observed variables, that non-linearity allows for
identifying the causal structure.

These developments, including LiNGAM algorithm (Shimizu et al.,, 2006) and its
variant DirectLiNGAM (Shimizu et al.,, 2011) assume causal sufficiency.
Without considering the effect of latent confounders, one may infer wrong
causal relations among observed variables. Studying causal models with latent
confounders might be essential to infer the correct causal structure. Hoyer et
al., (2008) and Salehkaleybar et al., (2020) considered an extension of LiNGAM
in the presence of latent confounders (lvLiNGAM). Please refer to Appendix C.1
for detailed discussion about both methods.

LiNGAM algorithm is partly based on independent component analysis (ICA)
(Comon,, 1994; Hyvarinen et al.,, 2002). The identifiability proof and the
recovery algorithm both begin with using ICA to estimate the source mixing
matrix from observations. In lvLiNGAM, the number of sources is larger than
the number of observed variables since the latent confounders are associated
with additional sources. This results in an overcomplete basis for the mixing
matrix, and hence lvLiNGAM is based on overcomplete ICA (Lewicki and
Sejnowski,, 2000; Eriksson and Koivunen,, 2004).

Our linear P-SCM generalizes lvLiNGAM to the case when the number of sources
can be equal or less than the number of observed variables, since each
observed variable is not necessarily associated with a distinct source.
Instead, each observed variable is exogenously connected to a subset of the
jointly independent set of sources, which allows the observed variable to
deterministically depend on other observed variables and latent confounders.
We further assume separability of the sources from observations, which means
all sources composing each observed variable can be correctly estimated, up to
scaling and permutation of the coefficients.

SCMs with deterministic relations have been considered in a few work. In
(Geiger et al.,, 1990; Spirtes et al.,, 2000), D-separation555This is
different from the classical d-separation (with small letter d) described in
(Pearl,, 2009, Section 1.2). condition is proposed for graphically determining
conditional independencies when deterministic relations are allowed. Yet, it
remains unclear whether D-separation condition can capture all conditional
independencies induced from the distribution. Further, a few approaches have
been proposed for causal discovery. When the system only consists of two
variables with one variable deterministically causing the other, Daniušis et
al., (2010) showed that the correct causal direction can be learnt if there is
no correlation between the density of the cause variable and the slope of the
deterministic function (w.r.t. a reference measure). Their analysis however
does not hold for linear relations. In a system where both deterministic and
non-deterministic relations are present, Scheines et al., (1996) considered
recovering the reduced model where all deterministic variables are removed.
Luo, (2006) adapted the conventional constraint-based IC algorithm (Pearl,,
2009) and added new rules in the independence tests to detect deterministic
relations. Mabrouk et al., (2014) combined constraint-based methods with
greedy search (Tsamardinos et al.,, 2006), where the deterministic relation is
detected by calculating the conditional entropy among variables. Lemeire et
al., (2012) introduced information equivalence, where two variables are
information equivalent (w.r.t. a third variable) if knowing one variable is
equivalent to knowing the other, from the viewpoint of the third variable.
Information equivalence is thus a generalization of deterministic relations.
Lemeire et al., (2012) adapted the PC algorithm with additional tests to
detect information equivalence among variables. The aforementioned methods all
suffer from the same identifiability problem as in conventional causal
discovery methods, where the underlying causal structure can only be estimated
up to certain equivalence classes, and majority of these methods do not
discuss the capability of identifying the underlying structure by their
algorithm (i.e., the equivalence class of the recovery result). Further, these
methods do not consider the presence of latent confounders in the system.

##  Appendix B Detailed descriptions of model assumptions

###  B.1 P-SCM faithfulness assumption

For a G-SCM, faithfulness assumption means that all marginal and conditional
independencies in the underlying causal graph are captured (required) by the
Markov condition (i.e., a Markov factorization of the underlying probability
distribution such that each variable is conditionally independent on its non-
descendant variables given its parents). In the language of linear DS-SCMs,
faithfulness translates to the linear coefficients not canceling out causal
effects among variables. That is, when multiple causal effects exist from one
observed variable to another, their combined effect is not exactly equal to
zero.

P-SCM faithfulness assumption extends this idea to linear P-SCMs.
Specifically, Assumption 3(a) states that when multiple distinct causal paths
exist from observed variables, containing source $s_{j}$, to an observed
variable $x_{i}$, their combined effect do not cancel out one another, or
cancel out the exogenous connection from $s_{j}$ to $x_{i}$ (i.e., $s_{j}$
component in $x_{i}$ is not equal to zero). This is equivalent to the
conventional faithfulness assumption for linear DS-SCMs. Assumption 3(b)
considers the coefficients of matrix $\mathbf{B}$, and can be explained as:
Any source mixture $\tilde{s}_{i}$ cannot be written as a linear combination
of other source mixtures. Note that when all model coefficients $\\{a_{ij}\\}$
and $\\{b_{ij}\\}$ are independently drawn from continuous distributions,
Assumptions (a) and (b) are satisfied both with probability one (Meek,, 1995),
hence P-SCM faithfulness is a reasonable assumption.

###  B.2 Separability assumption

Separability can be achieved using blind source separation (BSS) methods,
which is to separate a set of sources from a set of their mixtures given
little to no information about the sources and the mixing process. For
example, when the sources are known to be non-Gaussian random variables, the
mixing matrix $\mathbf{W}$ can be recovered using Independent Component
Analysis (ICA) or overcomplete ICA methods (Comon,, 1994; Hyvarinen et al.,,
2002; Lewicki and Sejnowski,, 2000; Eriksson and Koivunen,, 2004).
Separability can also be achieved when the sources are piecewise constant
functionals satisfying a set of mild conditions (Behr et al.,, 2018). We
discuss BSS in more details in Appendix C.

To satisfy the separability property, we assume the availability of a large
number of data vectors $\\{X^{(i)}:i\in[n]\\}$, and that each is generated
according to the described process, and using the same coefficients
$\\{a_{ij}\\}$ and $\\{b_{ij}\\}$.

##  Appendix C Blind source separation methods

Blind source separation (BSS) is the problem of separating a set of source
signals (sources) from a set of mixed signals (mixtures) given little to no
information about the sources and the mixing process (Comon and Jutten,,
2010). In the linear setting where the mixtures are linear combinations of the
sources, the blindness often refers to not knowing the source realizations nor
the mixing weights. Without any further knowledge about the sources, the
problem is infeasible, and hence further assumptions on the sources are needed
to facilitate source separation. An example of BSS is the independent
component analysis framework in which the sources are assumed to be drawn from
independent non-Gaussian distributions. Other examples include the statistical
blind source separation regression (SBSSR) model in (Behr et al.,, 2018) and
non-negative matrix factorization in (Donoho and Stodden,, 2004). In this
section, we provide a brief description of these methods, and present how to
utilize them as seeds to our causal structure learning framework.

###  C.1 Independent component analysis

Independent component analysis (Comon,, 1994) is a statistical technique to
separate independent, non-Gaussian random variables (sources) from their
observed linear mixtures. Specifically, consider a vector of $p$ observed
variables (mixtures) $X=[x_{1},\cdots,x_{p}]^{\top}$ which is generated as

$\displaystyle X=\mathbf{W}S,$ (5)

where $S=[s_{1},\cdots,s_{m}]^{\top}$ are $m$ unknown real-valued independent
non-degenerate random variables (sources), and $\mathbf{W}$ is a constant
$p\times m$ unknown mixing matrix. $(\mathbf{W},S)$ is called the
representation of $X$.

If the observed data is invertible mixtures of non-Gaussian components, i.e.,
the mixing matrix $\mathbf{W}$ is invertible, Comon, (1994) showed that the
representation of $X$ can be uniquely identified up to scaling and permutation
of the columns of $\mathbf{W}$, given enough observed data vectors $X$.
Further, if $\mathbf{W}$ is of full column rank and at most one source in $S$
is Gaussian, the representation of $X$ is still identifiable up to scaling and
permutation indeterminacies (Eriksson and Koivunen,, 2004). For detailed
explanation about ICA, the reader can refer to (Hyvärinen and Oja,, 2000;
Comon and Jutten,, 2010).

When the number of observed variables is less than the number of sources,
Eriksson and Koivunen, (2004) showed that if all the $m$ sources are non-
Gaussian and the representation of $X$ is irreducible, the matrix $\mathbf{W}$
can be identified up to scaling and permutation of its columns. Irreducibility
means that the columns of the mixing matrix $\mathbf{W}$ are pairwise linearly
independent. If two columns in $\mathbf{W}$ are linearly dependent, with
corresponding sources $s_{i}$ and $s_{j}$, then it is impossible to to
distinguish between the true representation of $X$ and another representation
with $m-1$ sources in which the two linearly dependent columns are merged into
a single column.

We now describe LiNGAM algorithm, which uniquely recovers the causal structure
of the underlying model when the mixing matrix is invertible and the sources
are non-Gaussian (Shimizu et al.,, 2006). The underlying DS-SCM is written as

$\displaystyle X=\mathbf{A}X+S=\mathbf{W}S$ (6)

where $S$ is a vector of length $m=p$, consisting of jointly independent non-
Gaussian sources, and $\mathbf{W}=(\mathbf{I}-\mathbf{A})^{-1}$.

Note that (6) fits into the standard ICA framework in (5). Thus, $\mathbf{W}$
can be identified up to scaling and permutation of its columns. Without prior
knowledge about the scale and ordering of the sources, the following general
ICA model for $X$ holds:

$\displaystyle X=\tilde{\mathbf{W}}S^{\prime},$ (7)

where $\tilde{\mathbf{W}}$ is the recovered mixing matrix (with scaling and
permutation indeterminacies). $\tilde{\mathbf{W}}$ can be written as

$\displaystyle\tilde{\mathbf{W}}=\mathbf{W}\mathbf{P}\mathbf{\Gamma},$ (8)

where $\mathbf{P}$ is a permutation matrix and $\mathbf{\Gamma}$ is a diagonal
scaling matrix. $S^{\prime}$ contains the corresponding set of sources with
reordering and rescaling that correspond to $\mathbf{P}$ and
$\mathbf{\Gamma}$.

The corresponding causal model, represented by matrix $\mathbf{A}$, can be
uniquely identified because of the acyclicity assumption. In particular, by
some scaling and permutation of its columns and rows, the inverse of
$\tilde{\mathbf{W}}$ can be converted uniquely to a lower triangular matrix
with all ones on its main diagonal.

In the presence of latent variables, Hoyer et al., (2008) and Salehkaleybar et
al., (2020) utilized overcomplete ICA to extend LiNGAM algorithm. Given the
output of the overcomplete ICA, the recovered mixing matrix
$\tilde{\mathbf{W}}$ is unique up to scaling and permutation of its columns,
under the assumption of irreducibility. The number of latent variables in the
system is assumed to be known. The task is to identify the columns of
$\tilde{\mathbf{W}}$ which correspond to exogenous noises associated with
observed variables, and subsequently apply LiNGAM algorithm after eliminating
the columns corresponding to latent variables. Hoyer et al., (2008) proposed
an algorithm which brute-forces all possible classifications of the columns of
$\tilde{\mathbf{W}}$ (whether each of the columns corresponds to distinct
source associated with an observed variable, or to a latent confounder). The
algorithm then identifies the possible selections that are compatible with
faithfulness and acyclicity assumptions. More recently, Salehkaleybar et al.,
(2020) proposed a more efficient algorithm that identifies the set of columns
corresponding to observed variables. The idea is to learn the skeleton of the
underlying graph via pairwise comparisons of the observed variables (based on
their corresponding rows in $\tilde{\mathbf{W}}$). This is possible due to
faithfulness and acyclicity assumptions. Using the learnt skeleton, the
algorithm selects only the columns whose non-zero entries are compatible with
the observable descendants of each observed variable.

###  C.2 Statistical blind source separation regression model

Statistical blind source separation regression (SBSSR) model is a finite
alphabet BSS method proposed in (Behr et al.,, 2018) to separate piecewise
constant source functions from their linear mixtures. Suppose we have a set of
$m$ source functions $\mathcal{S}=\\{s_{1},s_{2},\cdots,s_{m}\\}$, each of
which consists of an array of constant segments (i.e., a step function) on
$[0,1]$. The function values are selected from a known finite alphabet, yet
the jump sizes, numbers, and locations of change points for each function are
unknown. Specifically, let
$\mathcal{U}=\\{u_{1},u_{2},\cdots,u_{k}\\}\subset\mathbb{R}$ be a known
finite and totally ordered alphabet, i.e., $u_{1}<u_{2}<\cdots<u_{k}$. Each
source function belongs to the class

$\mathcal{S}=\left\\{\sum_{j=0}^{K}\theta_{j}\mathbf{1}_{\left[\tau_{j},\tau_{j+1}\right)}:\theta_{j}\in\mathcal{U},0=\tau_{0}<\cdots<\tau_{K}<\tau_{K+1}=1,K\in\mathbb{N}\right\\}.$

$K$ is the unknown number of changes, which is assumed to be finite.
$\theta_{1},\cdots,\theta_{K}$ are the function values selected from the
alphabet $\mathcal{U}$ such that $\theta_{j}\neq\theta_{j+1}$ for
$j=0,1,\cdots,K$. $\tau_{1},\cdots,\tau_{K}$ are the change points. We observe
samples of $p$ linear mixtures $\\{x_{k}(t),~{}k=1,\cdots,p\\}$ at $n$
uniformly selected location points $t_{i}$ in $[0,1]$:

$x_{k}(t_{i})=\sum_{j=1}^{m}w_{kj}s_{j}(t_{i})+\sigma\epsilon_{ki}=W_{k}^{\top}S(t_{i})+\sigma\epsilon_{ki};\qquad
i=1,\cdots,n;~{}k=1,\cdots,p.$ (9)

$W_{k}=[w_{k1},\cdots,w_{km}]^{\top}$ is the vector of mixing weights for
mixture $x_{k}$ with

$W_{k}\geq 0,~{}\sum_{j=1}^{m}w_{kj}=1,\qquad k=1,\cdots,p.$

$S(t_{i})=[s_{1}(t_{i}),\cdots,s_{m}(t_{i})]^{\top}$ is the vector of values
of the source functions at point $t_{i}$ for all $i\in[n]$. $\epsilon_{ki}$ is
an additive Gaussian noise with zero mean and unit variance, and $\sigma>0$ is
the known noise variance. Behr et al., (2018) showed that, under mild
separability conditions among weights and source functions, both the source
functions and the mixing weights can be identified up to permutations,
including the number of change points, change point locations, and the
function values on each segment for all source functions.

Unlike ICA, the mixing matrix $\mathbf{W}$ in SBSSR does not necessarily need
to satisfy the irreducibility assumption, due to the prior knowledge about the
sources alphabet. In fact, the recovered mixing matrix $\tilde{\mathbf{W}}$
using SBSSR can include two linearly independent columns, while the method is
able to separate the corresponding sources. However, even with the ability to
separate such sources, we require to merge them into one combined source,
since the two corresponding generating models are observationally equivalent,
as we will shortly explain.

###  C.3 Non-negative matrix factorization

Non-negative matrix factorization (NMF) is another BSS method to decompose
large matrices into the multiplication of low-rank, non-negative smaller
matrices (Lee and Seung,, 1999). Suppose each observed variable is an
$n_{1}\times n_{2}$ matrix $\mathbf{X}_{k}$ with rank $r_{k}$. Using NMF,
$\mathbf{X}_{k}$ can be decomposed into

$\mathbf{X}_{k}=\mathbf{W}_{k}\mathbf{F}_{k}^{\top}=\sum_{i=1}^{r_{k}}W_{ki}F_{ki}^{\top}.$
(10)

$\mathbf{W}_{k}$ is a non-negative $n_{1}\times r_{k}$ weight matrix.
$\mathbf{F}_{k}$ is a non-negative $n_{2}\times r_{k}$ feature matrix.
$W_{ki}$, $F_{ki}$ are the column vectors of $\mathbf{W}_{k}$,
$\mathbf{F}_{k}$ for all $i=1,\cdots,r_{k}$. If we consider the feature
vectors $F_{ki}$ as sources, then we can write each observed matrix
$\mathbf{X}_{k}$ into a linear combination of sources (here, both sources and
weights are column vectors). Donoho and Stodden, (2004) showed that under
certain conditions on $\mathbf{W}_{k}$ and $\mathbf{F}_{k}$, the factorization
(10) is unique up to permutation and scaling of the feature column vectors,
i.e., the sources.

###  C.4 Application to our model

Under various assumptions on the sources and the mixing matrix, we can use the
aforementioned BSS methods to estimate the correct representation of the
observed variables, i.e., estimate the mixing matrix $\mathbf{W}$ and the
corresponding sources $S$.

In the BSS methods described in Appendices C.1-C.3, the permutation and
scalability indeterminacies always exist, except for SBSSR, where we do not
have scalability indeterminacy due to the prior information about the sources
alphabets and the mixing weights. In general, more prior information about the
sources may eliminate the scalability indeterminacy. Another example where the
scalability indeterminacy relaxes is when the sources in the ICA framework are
all known to have unit variance. In the same spirit, having prior information
about the ordering may eliminate the permutation indeterminacy.

The output of BSS is the factorization of $X$ as in (7), where under
permutation and scalability indeterminacies, $\tilde{\mathbf{W}}$ is given by
(8) , and $S^{\prime}$ is given by

$S^{\prime}=\mathbf{\Gamma}^{-1}\mathbf{P}^{\top}S.$

$\mathbf{P}$ is the $m\times m$ permutation matrix with
$\mathbf{P}\mathbf{P}^{\top}=\mathbf{I}$, and $\mathbf{\Gamma}$ is the
diagonal scaling matrix. Recall that in LiNGAM, the mixing matrix
$\mathbf{W}=(\mathbf{I}-\mathbf{A})^{-1}$ is lower triangular with all ones on
the main diagonal, since $\mathbf{A}$ is strictly lower triangular due to the
DAG-ness assumption of the underlying graph. By contrast, in our model, the
mixing matrix in (3) does not possess these structural restrictions since
$\mathbf{W}=(\mathbf{I}-\mathbf{A})^{-1}\mathbf{B}$, where $\mathbf{B}$ can
have an arbitrary structure.

As in LiNGAM, our recovery algorithm is robust to permutation and scaling
ambiguities. From (3) and (8), the recovered mixing matrix in our model can be
written as

$\displaystyle\tilde{\mathbf{W}}=\mathbf{W}\mathbf{P}\mathbf{\Gamma}=(\mathbf{I}-\mathbf{A})^{-1}\mathbf{B}\mathbf{P}\mathbf{\Gamma}.$

By writing $\tilde{\mathbf{B}}$ as

$\displaystyle\tilde{\mathbf{B}}=\mathbf{B}\mathbf{P}\mathbf{\Gamma},$ (11)

we have

$\displaystyle\tilde{\mathbf{W}}=(\mathbf{I}-\mathbf{A})^{-1}\tilde{\mathbf{B}}.$
(12)

Our recovery algorithm is in fact able to recover
$(\mathbf{I}-\mathbf{A})^{-1}$ and $\tilde{\mathbf{B}}$ using
$\tilde{\mathbf{W}}$, where $\tilde{\mathbf{B}}$ is a column-repermuted and
rescaled version of $\mathbf{B}$. The permutation indeterminacy of the matrix
$\mathbf{B}$ is immaterial because there exists no ordering among the
exogenous connections from the sources to each observed variable, and we are
not concerned about the scalability indeterminacy in recovering the strengths
of these exogenous connections. Therefore, permutation and scalability
indeterminacies do not affect the recovery performance of our algorithm. In
the following, we provide an example for the aforementioned indeterminacies.

###### Example 1

Consider the generating model in Figure 5. In the matrix form, the generating
model is given by

$x_{1}$$x_{2}$$x_{3}$$s_{1}$$s_{2}$$s_{3}$ Figure 5: Generating model for
Example 1.

$\displaystyle\begin{bmatrix}x_{1}\\\ x_{2}\\\ x_{3}\\\
\end{bmatrix}=\begin{bmatrix}0&0&0\\\ 0&0&0\\\ a_{31}&a_{32}&0\\\
\end{bmatrix}\begin{bmatrix}x_{1}\\\ x_{2}\\\ x_{3}\\\
\end{bmatrix}+\begin{bmatrix}b_{11}&b_{12}&0\\\ b_{21}&0&b_{23}\\\
b_{31}&0&0\\\ \end{bmatrix}\begin{bmatrix}s_{1}\\\ s_{2}\\\ s_{3}\\\
\end{bmatrix}.$ (13)

The observed variables can be represented as linear combinations of the
sources as follows:

$\displaystyle X=\mathbf{W}S=\begin{bmatrix}b_{11}&b_{12}&0\\\
b_{21}&0&b_{23}\\\ w_{31}&a_{31}b_{12}&a_{32}b_{23}\\\
\end{bmatrix}\begin{bmatrix}s_{1}\\\ s_{2}\\\ s_{3}\\\ \end{bmatrix},$

where $w_{31}=a_{31}b_{11}+a_{32}b_{21}+b_{31}$.

Given samples of the observed variables $X$, we can apply BSS methods to learn
the representation of $X$ up to permutation and scaling of the columns of
$\mathbf{W}$. Suppose the recovered mixing matrix is

$\displaystyle\tilde{\mathbf{W}}=\mathbf{W}\mathbf{P}\mathbf{\Gamma}=\begin{bmatrix}\alpha
b_{12}&\gamma b_{11}&0\\\ 0&\gamma b_{21}&\beta b_{23}\\\ \alpha
a_{31}b_{12}&\gamma w_{31}&\beta a_{32}b_{23}\\\ \end{bmatrix}.$

The permutation matrix and the scaling matrix are

$\displaystyle\mathbf{P}=\begin{bmatrix}0&1&0\\\ 1&0&0\\\ 0&0&1\\\
\end{bmatrix},\quad\mathbf{\Gamma}=\begin{bmatrix}\alpha&0&0\\\ 0&\beta&0\\\
0&0&\gamma\\\ \end{bmatrix},$

and the corresponding sources are

$\displaystyle S^{\prime}=\begin{bmatrix}s^{\prime}_{1}\\\ s^{\prime}_{2}\\\
s^{\prime}_{3}\\\ \end{bmatrix}=\begin{bmatrix}\alpha^{-1}s_{2}\\\
\gamma^{-1}s_{1}\\\ \beta^{-1}s_{3}\\\ \end{bmatrix}.$

$\alpha,\beta,\gamma\neq 0$ are the scaling coefficients.

Given the recovered mixing matrix $\tilde{\mathbf{W}}$, our P-SCM recovery
algorithm uniquely recovers $\mathbf{A}$ and
$\tilde{\mathbf{B}}=\mathbf{B}\mathbf{P}\mathbf{\Gamma}$, which is explained
in Section 3.3. Thus the recovered model is

$\displaystyle
X=\mathbf{A}X+\tilde{\mathbf{B}}S^{\prime}=\begin{bmatrix}0&0&0\\\ 0&0&0\\\
a_{31}&a_{32}&0\\\ \end{bmatrix}\begin{bmatrix}x_{1}\\\ x_{2}\\\ x_{3}\\\
\end{bmatrix}+\begin{bmatrix}\alpha b_{12}&\gamma b_{11}&0\\\ 0&\gamma
b_{21}&\beta b_{23}\\\ 0&\gamma b_{31}&0\\\
\end{bmatrix}\begin{bmatrix}s^{\prime}_{1}\\\ s^{\prime}_{2}\\\
s^{\prime}_{3}\\\ \end{bmatrix}.$ (14)

Note that $\tilde{\mathbf{B}}S^{\prime}=\mathbf{B}S$, hence the recovered
model in (14) is identical to the generating model in (13). However, we do not
learn the representation $\mathbf{B}S$ uniquely, instead we learn
$\tilde{\mathbf{B}}S^{\prime}$, which is irrelevant as we explained above.

It is worth noting that the irreducibility assumption in our linear P-SCM is
without loss of generality. Under P-SCM faithfulness assumption, reducibility,
i.e., existence of a pair of columns $W_{i},~{}W_{j},~{}i\neq j$ in the mixing
matrix $\mathbf{W}$ that are linearly dependent, occurs if and only if the
corresponding sources $s_{i}$ and $s_{j}$ are directly connected to a common
observed variable, and are not directly connected to any other observed
variables. This follows because we can write the corresponding columns in
$\mathbf{W}=(\mathbf{I}-\mathbf{A})^{-1}\mathbf{B}$ (cf. (3)) as

$[W_{i}\quad W_{j}]=(\mathbf{I}-\mathbf{A})^{-1}[B_{i}\quad B_{j}],$

where $B_{i}$ and $B_{j}$ are the columns in $\mathbf{B}$ corresponding to
sources $s_{i}$ and $s_{j}$. Since $(\mathbf{I}-\mathbf{A})^{-1}$ is an
invertible square matrix, $W_{i}$ and $W_{j}$ are linearly dependent if and
only if $B_{i}$ and $B_{j}$ are linearly dependent. Under P-SCM faithfulness
assumption (b), this happens if and only if $[B_{i}~{}~{}B_{j}]$ have only one
non-zero row, which means $s_{i}$ and $s_{j}$ are directly connected to a
common observed variable, and to this variable only. Therefore, when $W_{i}$
and $W_{j}$ are linearly dependent, i.e., $W_{i}=\alpha W_{j},\alpha\neq 0$,
the corresponding sources $s_{i},s_{j}$ appear at each node $x_{k}$ as
$w_{kj}(s_{j}+\alpha s_{i})$, where $w_{kj}\in\mathbb{R}$. Since $s_{i}$ and
$s_{j}$ are connected to the same variable, replacing the exogenous
connections from $s_{i},s_{j}$ by a combined source
$s_{i}^{\prime}=s_{j}+\alpha s_{i}$ in the generating model results in a model
that has the same distribution as the original generating model, i.e., an
observationally equivalent model.

In conclusion, under different problem settings and assumptions, given
observations of variables $X$, we can use BSS methods to recover the mixing
matrix $\mathbf{W}$ up to permutation and/or scalability indeterminacies,
which have no impact in recovering the true generating model. We call these
models separable, as mentioned in Section 2.2.

Connection to LiNGAM. According to the above analysis and the comparison
between DS-SCM and P-SCM in Section 4, both LiNGAM and lvLiNGAM models are
included in our linear P-SCM. Specifically, our model reduces to LiNGAM when
each observed variable is directly influenced by a single source, and the
sources are jointly independent non-Gaussian random variables with non-zero
variances. Here, separability holds by using ICA. Similarly, lvLiNGAM
corresponds to the case when the sources are non-Gaussian, and each of the
source mixtures $\tilde{s}_{i}$ has at least one distinct source. Note that,
in lvLiNGAM, the number of source variables is larger than the number of
observed variables since the latent confounders are associated with additional
distinct sources. This results in an overcomplete basis for the mixing matrix,
and hence separability holds using overcomplete ICA. Further, a sufficient
condition for unique identifiability in lvLiNGAM is that the mixing matrix
$\mathbf{W}$ in (3) is irreducible in the sense that its columns are pairwise
linearly independent. This is in fact a sufficient condition for overcomplete
ICA to return a unique solution up to scaling and permutation of the columns
(Eriksson and Koivunen,, 2004). In this work, we impose a more general
assumption on the separability of the source variables from observations. This
framework includes ICA and overcomplete ICA as special cases, but is not
restricted to both methods.

##  Appendix D Examples

###  D.1 Examples showing the distinction between linear P-SCM and linear DS-
P-SCM

In this subsection, we demonstrate the practical significance of linear P-SCM
over a linear DS-P-SCM. Specifically, we answer the following question: Using
the more general linear P-SCM, can we correctly identify models that are not
identifiable using linear DS-P-SCMs? In the following, we provide two examples
where linear P-SCMs can explain the underlying causal model, while linear DS-
P-SCMs, with or without latent confounders, either are inapplicable or give
misleading results. Therefore, the model cannot be recovered using causal
discovery methods for linear DS-P-SCMs, but can be correctly recovered by our
P-SCM Recovery algorithm.

###### Example 2

In this example, we begin with the ground truth (i.e., the underlying model),
and show that linear DS-P-SCMs fail to explain the model, while our linear
P-SCM explains the model. Consider the graph on the left in Figure 6, which
represents the true generating model for this example. We have five observed
variables $(x_{1},\cdots,x_{5})$ and four jointly independent sources
$(s_{1},\cdots,s_{4})$. Since there are less sources than observed variables,
the model cannot be represented by a linear DS-P-SCM with or without latent
confounders. Recall that each observed variable in linear DS-P-SCMs must be
associated with an distinct source that is not shared with other observed
variables. Hence the number of independent sources has to be greater than or
equal to the number of observed variables in linear DS-P-SCMs.

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$s_{1}$$s_{2}$$s_{3}$$s_{4}$

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$s_{1}$$s_{2}$$s_{3}$$s_{4}$

Figure 6: (Left) The ground truth (the true generating model) for Example 2.
(Right) The ground truth cannot be modeled as a linear DS-P-SCM with latent
confounders. The exogenous connections shared among $x_{1}$, $x_{2}$ and
$x_{3}$ in the ground truth are explained here by two additional latent
confounders $x_{6}$ and $x_{7}$. However, $x_{2}$, $x_{4}$, $x_{5}$ all have
no distinct sources, hence deterministically depend on their direct causes and
the latent confounder. Red arrows represent the differences.

On the other hand, it is easy to see that the ground truth in Figure 6 can be
modeled by our linear P-SCM, which allows for observed variables not to have
exogenous connections, and explains “latent confounding” simply by “shared”
exogenous connections from the sources (for instance, $s_{2}$ has exogenous
connections to both $x_{1}$ and $x_{2}$).

Lastly, it is worth mentioning that the generating model in this example has a
hierarchical structure that entails practical significance: $x_{1}$, $x_{2}$
and $x_{3}$ are exogenously connected to different pairs of sources, while
$x_{4}$ and $x_{5}$ are composed of different triplets of sources (through
different pairs of causal connections from $x_{1}$, $x_{2}$ and $x_{3}$). We
thus can treat $\\{x_{1},x_{2},x_{3}\\}$ as one layer, and $\\{x_{4},x_{5}\\}$
as another layer below $\\{x_{1},x_{2},x_{3}\\}$. This hierarchical structure
may arise naturally in influence propagation problems through networks of
nodes. For instance, one layer of twitter users tweet news directly from the
news sources (NY-times, Washington-Post, etc), then another layer of users
retweet from the first layer, and so on. In conclusion, this example show that
our linear P-SCM is more suited to model such a setting than a linear DS-P-
SCM.

###### Example 3

We begin with a ground truth graph and show that– as in the previous example–
linear DS-P-SCMs with latent confounders fail to explain the model. Further,
we show that linear DS-P-SCMs without latent confounders can explain the
model, yet the recovery under this assumption results in misinterpreted edges
(low accuracy). A linear P-SCM, on the other hand, explains the model and
results in the recovery of a correct network.

Consider the graph on the left in Figure 7, which represents the true
generating model. We have four observed variables $(x_{1},\cdots,x_{4})$ and
four jointly independent sources $(s_{1},\cdots,s_{4})$. Notice that $s_{3}$
is exogenously connected to two observed variables. To explain the model by a
linear DS-P-SCM, a latent confounder $x_{5}$ must be added to the model as
shown in the middle in Figure 7 (to explain the shared sources), which leaves
observed variable $x_{3}$ with no distinct sources. Therefore the ground truth
cannot be explained by an DS-P-SCM with latent confounders. On the contrary,
the ground truth can be explained by a linear P-SCM, which allows each
observed variable to be exogenously connected to a subset of the sources.

Note that, since we have four observed variables and four sources, the model
can be modeled by a linear DS-P-SCM without latent confounders (i.e., both
models have the same joint distribution over the observed variables), where
each observed variable is exogenously connected to one distinct source, and to
this source only. This however leads to incorrect recovery as explained in the
plot on the right in Figure 7. Specifically, in the true generating model,
$s_{3}$ is exogenously connected to both $x_{3}$ and $x_{4}$, while $x_{4}$
has a distinct source $s_{4}$. Thus, assuming a linear DS-P-SCM as the
generating model, $s_{3}$ will be the distinct source of $x_{3}$, and the
exogenous connection from $s_{3}$ to $x_{4}$ will be interpreted as a causal
connection from $x_{3}$ to $x_{4}$. This will in turn necessitate the
erroneous causal connection from $x_{1}$ to $x_{4}$ to cancel out the causal
effect of $x_{1}$ on $x_{4}$ through $x_{3}$. Notice here that these
additional connections break the marginal independency between $x_{1}$ and
$x_{4}$, therefore the recovered model is unfaithful to the true generating
model.

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$s_{1}$$s_{3}$$s_{2}$$s_{4}$

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$s_{1}$$s_{3}$$s_{2}$$s_{4}$

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$s_{1}$$s_{3}$$s_{2}$$s_{4}$

Figure 7: (Left) The ground truth (the true generating model) for Example 3.
(Middle) The ground truth can not be modeled as a linear DS-P-SCM with latent
confounders: $s_{3}$ is exogenously connected to two observed variables
$x_{3}$ and $x_{4}$. A latent confounder $x_{5}$ is added to the model, which
leaves observed variable $x_{3}$ with no distinct sources. (Right) The ground
truth is modeled incorrectly as a linear DS-P-SCM without latent confounders.

###  D.2 Example explaining the possible parent set

###### Example 4

Suppose we have 3 observed variables $(x_{1},x_{2},x_{3})$ and 4 source
variables $(s_{1},s_{2},s_{3},s_{4})$, and the generating model is given by
$x_{1}=b_{11}s_{1}+b_{12}s_{2}$; $x_{2}=b_{21}s_{1}+b_{23}s_{3}$;
$x_{3}=a_{31}x_{1}+b_{34}s_{4}$. The observed variables can be written as a
linear combination of the sources as follows:

$\displaystyle X=\mathbf{W}S=\begin{bmatrix}b_{11}&b_{12}&0&0\\\
b_{21}&0&b_{23}&0\\\ a_{31}b_{11}&a_{31}b_{12}&0&b_{43}\\\
\end{bmatrix}\begin{bmatrix}s_{1}\\\ s_{2}\\\ s_{3}\\\ s_{4}\\\
\end{bmatrix}.$

The recovered mixing matrix $\tilde{\mathbf{W}}$ is a column-permuted and
rescaled version of $\mathbf{W}$. Using $\tilde{\mathbf{W}}$, one possible
causal order of the observed variables is $(x_{1},x_{2},x_{3})$, where one may
further conclude that $x_{1}$ and $x_{2}$ have no parents and $x_{3}$ has
$x_{1}$ as a parent. Note that both $x_{1}$ and $x_{2}$ precede $x_{3}$ in
this causal order, hence both need to be considered when recovering the causal
structure of $x_{3}$.

However, the possible parent set of $x_{3}$ is $\mathcal{P}_{3}=\\{x_{1}\\}$
(as defined in Section 3): $x_{2}$ cannot be a parent of $x_{3}$ since $x_{3}$
does not have $s_{3}$ as a component. To conclude, the possible parent set of
$x_{3}$, i.e., $\mathcal{P}_{3}$, is a strict subset of the observed variable
preceding $x_{3}$ in the casual order deduced from $\tilde{\mathbf{W}}$.

###  D.3 Example explaining the definition of unique component

###### Example 5

Consider a generating model with seven observed variables
$(x_{1},\cdots,x_{7})$ and eight source variables $(s_{1},\cdots,s_{8})$. Let
us fix $x_{7}$. Suppose all the other six variables are possible parents of
$x_{7}$, i.e., $\mathcal{P}_{7}=\\{x_{1},\cdots,x_{6}\\}$. The exogenous
connections from the source variables to the observed variables in
$\mathcal{P}_{7}$ are

$\displaystyle\tilde{s}_{1}$
$\displaystyle=b_{11}s_{1}+b_{13}s_{3}+b_{14}s_{4}+b_{17}s_{7};$
$\displaystyle\tilde{s}_{2}$
$\displaystyle=b_{22}s_{2}+b_{23}s_{3}+b_{25}s_{5};$
$\displaystyle\tilde{s}_{3}$ $\displaystyle=b_{34}s_{4}+b_{36}s_{6};$
$\displaystyle\tilde{s}_{4}$
$\displaystyle=b_{45}s_{5}+b_{46}s_{6}+b_{48}s_{8};$
$\displaystyle\tilde{s}_{5}$ $\displaystyle=b_{57}s_{7}+b_{58}s_{8};$
$\displaystyle\tilde{s}_{6}$ $\displaystyle=b_{67}s_{7}+b_{68}s_{8}.$

Let us first consider the possible parent set of $x_{7}$, i.e.,
$\mathcal{P}_{7}$. The index set of $\mathcal{P}_{7}$ is
$J^{(0)}=\\{1,\cdots,6\\}$. According to the equations, $s_{1}$ is connected
only to $x_{1}$, and $s_{2}$ is connected only to $x_{2}$. Thus, the unique
component set of $x_{1}$ is $U_{7}(1)=\\{s_{1}\\}$, and the unique component
set of $x_{2}$ is $U_{7}(2)=\\{s_{2}\\}$. The other observed variables in
$\mathcal{P}_{7}$ do not have unique components. Thus, the subset of
$\mathcal{P}_{7}$ with no unique components is
$\mathcal{P}_{7}^{(1)}=\\{x_{3},x_{4},x_{5},x_{6}\\}$. The corresponding index
set is $J^{(1)}=\\{3,4,5,6\\}$.

Next, we consider only the observed variables in $\mathcal{P}_{7}^{(1)}$ with
indices in $J^{(1)}$. $s_{4}$ is connected only to $x_{3}$, and hence
$U_{7}(3)=\\{s_{4}\\}$. Similarly, $U_{7}(4)=\\{s_{5}\\}$, and
$J^{(2)}=\\{5,6\\}$.

Finally, each of the observed variables with indices in $J^{(2)}$
($x_{5},x_{6}$) is connected to both sources $s_{7}$ and $s_{8}$. Thus,
neither $x_{5}$ nor $x_{6}$ has a unique component, and the procedure
terminates. To conclude, the set of observed variables with no unique
components is $\mathcal{I}_{7}=\\{x_{5},x_{6}\\}$.

###  D.4 Examples showing the necessity of the conditions

In this subsection, we provide examples on how Conditions 1 and 2 are
necessary for the unique identifiability of a linear P-SCM. More specifically,
in Example 6 below, we show that, for a given observed variable $x_{k}$, if
any source variable that is a unique component of a possible parent
$x_{i}\in\mathcal{P}_{k}$ has an exogenous connection to $x_{k}$, then we can
not uniquely identify the total causal effect from $x_{i}$ to $x_{k}$ in the
corresponding generating model. In other words, for unique identifiability of
the causal effects to $x_{k}$, $\tilde{s}_{k}$ must not contain a unique
component of any $x_{i}\in\mathcal{P}_{k}$.

Notice that since we consider a fixed observed variable, $x_{k}$, and aim to
recover/estimate the total causal effects from the observed variables in
$\mathcal{P}_{k}$, we do not consider the causal connections among these
possible parents.

###### Example 6

Consider the following generating model:

$\displaystyle\begin{bmatrix}x_{1}\\\ x_{2}\\\ x_{3}\\\
\end{bmatrix}=\begin{bmatrix}0&0&0\\\ 0&0&0\\\ a_{31}&a_{32}&0\\\
\end{bmatrix}\begin{bmatrix}x_{1}\\\ x_{2}\\\ x_{3}\\\
\end{bmatrix}+\begin{bmatrix}b_{11}&b_{12}&0\\\ b_{21}&0&b_{23}\\\
0&b_{32}&0\\\ \end{bmatrix}\begin{bmatrix}s_{1}\\\ s_{2}\\\ s_{3}\\\
\end{bmatrix}.$ (15)

The observed variables can be represented as linear combinations of the
sources as follows:

$\displaystyle X=\mathbf{W}S=\begin{bmatrix}b_{11}&b_{12}&0\\\
b_{21}&0&b_{23}\\\ a_{31}b_{11}&a_{31}b_{12}+b_{32}&a_{32}b_{23}\\\
\end{bmatrix}\begin{bmatrix}s_{1}\\\ s_{2}\\\ s_{3}\\\ \end{bmatrix}.$ (16)

Given the observations $X=(x_{1},x_{2},x_{3})^{\top}$, the mixing matrix
$\mathbf{W}$ in (16) can be recovered up to permutation and scaling
indeterminacies as described in Appendix C.4. For simplicity, we assume that
the recovered mixing matrix $\tilde{\mathbf{W}}$ is the same as $\mathbf{W}$.
The intricacies resulting from permutation and scaling indeterminacies is
resolved in our proposed P-SCM Recovery algorithm.

We assume that the causal structure of $x_{1}$ and $x_{2}$ have been correctly
recovered as in (15), and consider observed variable $x_{3}$. From the blind
source separation output, i.e., the recovered mixing matrix $\mathbf{W}$ in
(16), we deduce that $x_{1}$ and $x_{2}$ are possible parents of $x_{3}$.

We can rewrite the generating model of $x_{3}$ in (15) as follows:

$x_{3}=a_{31}x_{1}+a_{32}x_{2}+\tilde{s}_{3},\quad\text{where
}\tilde{s}_{3}=b_{32}s_{2}.$ (17)

Notice that $s_{2}$ is a unique component of $x_{1}$. The $s_{2}$ component in
$x_{3}$ (cf. (16)) consists of two parts: $a_{31}b_{12}s_{2}$ which results
from a causal connection from $x_{1}$, and $b_{32}s_{2}$ which results from an
exogenous connection from $s_{2}$. In order to learn the causal structure of
$x_{3}$, we ought to be able to differentiate between these two parts from
their mixture in the mixing matrix $\mathbf{W}$, which is not possible in this
example. Specifically, from the recovered mixing matrix
$\tilde{\mathbf{W}}=\mathbf{W}$, we can not distinguish the true generating
model in (17) from the two following generating models:

$\textbf{Model 1}:\quad
x_{3}^{(1)}=\left(a_{31}+\frac{b_{32}}{b_{12}}\right)x_{1}+a_{32}x_{2}+\tilde{s}_{3}^{(1)},\quad\text{where
}\tilde{s}_{3}^{(1)}=-\frac{b_{11}b_{32}}{b_{12}}s_{1},$

which corresponds to the $s_{2}$ component in $x_{3}$ being caused only by a
causal connection from $x_{1}$; and

$\textbf{Model 2}:\quad
x_{3}^{(2)}=a_{32}x_{2}+\tilde{s}_{3}^{(2)},\quad\text{where
}\tilde{s}_{3}^{(2)}=a_{31}b_{11}s_{1}+(a_{31}b_{12}+b_{32})s_{2}.$

which corresponds to the $s_{2}$ component being caused only by an exogenous
connection from $s_{2}$.

Similarly, if the generating model in (17) is such that
$\tilde{s}_{3}=b_{33}s_{3}$, the causal effects cannot be uniquely identified,
since $s_{3}$ is a unique component for $x_{2}$. In conclusion, to uniquely
recover the causal structure of $x_{3}$, neither $s_{2}$ nor $s_{3}$ can be
included in $\tilde{s}_{3}$.

Next, we present an example about the necessity of the marriage condition for
unique identifiability a in linear P-SCM. Recall that the marriage condition
is: For a given observed variable $x_{k}$ and its possible parent set
$\mathcal{P}_{k}$, every subset of the possible parents
$X_{C}\subseteq\mathcal{P}_{k}$ must include at least $|X_{C}|$ different
source variables.

######  Example 7 (Marriage condition)

Consider the following generating model:

$\displaystyle x_{1}$
$\displaystyle=\tilde{s}_{1}=b_{11}s_{1}+b_{12}s_{2};\qquad
x_{2}=\tilde{s}_{2}=b_{21}s_{1}+b_{23}s_{3};$ (18) $\displaystyle x_{3}$
$\displaystyle=\tilde{s}_{3}=b_{32}s_{2}+b_{33}s_{3};\qquad
x_{4}=\tilde{s}_{4}=b_{42}s_{2}+b_{44}s_{4};$ $\displaystyle x_{5}$
$\displaystyle=\tilde{s}_{5}=b_{53}s_{3}+b_{54}s_{4};\qquad
x_{6}=a_{62}x_{2}+a_{64}x_{4}+a_{65}x_{5}+\tilde{s}_{6},\quad\tilde{s}_{6}=b_{65}s_{5}.$

The observed variables can be written as follows:

$\displaystyle X=\mathbf{W}S=\begin{bmatrix}b_{11}&b_{12}&0&0&0\\\
b_{21}&0&b_{23}&0&0\\\ 0&b_{32}&b_{33}&0&0\\\ 0&b_{42}&0&b_{44}&0\\\
0&0&b_{53}&b_{54}&0\\\ w_{61}&w_{62}&w_{63}&w_{64}&w_{65}\\\
\end{bmatrix}\begin{bmatrix}s_{1}\\\ s_{2}\\\ s_{3}\\\ s_{4}\\\ s_{5}\\\
\end{bmatrix}.$ (19)

We recover the mixing matrix $\mathbf{W}$ using BSS. As in the previous
example, we assume that $\tilde{\mathbf{W}}=\mathbf{W}$. Consider the observed
variable $x_{6}$. From $\mathbf{W}$, the possible parents of $x_{6}$ are
$\mathcal{P}_{6}=\\{x_{1},\cdots,x_{5}\\}$. Notice that the marriage condition
is not satisfied in this example:
$\left|\bigcup_{x_{i}\in\mathcal{P}_{6}}{\rm{Comp}}(x_{i})\right|=4$ while
$|\mathcal{P}_{6}|=5$, therefore,
$|\mathcal{P}_{6}|\nleq\left|\bigcup_{x_{i}\in\mathcal{P}_{6}}{\rm{Comp}}(x_{i})\right|$.
In the following, we show how this renders the unique identifiability to be
impossible.

Consider $X_{[1:4]}=(x_{1},x_{2},x_{3},x_{4})^{\top}$. These observed
variables only contain the source variables
$S_{[1:4]}=(s_{1},\cdots,s_{4})^{\top}$, and thus can be written as
$X_{[1:4]}=\mathbf{W}_{0}S_{[1:4]}$, where $\mathbf{W}_{0}$ is the upper left
$4\times 4$ submatrix of $\mathbf{W}$ in (19). $\mathbf{W}_{0}$ is invertible
due to P-SCM faithfulness assumption. Now, $x_{5}$ contains only the sources
$(s_{3},s_{4})$, and hence can be written as a linear combination of
$X_{[1:4]}$ as follows:

$\displaystyle
x_{5}=[0\;0\;b_{53}\;b_{54}]\mathbf{W}^{-1}_{0}X_{[1:4]}=\sum_{i=1}^{4}c_{i}x_{i},$
(20)

where $c_{i},i=1,\cdots,4$ can be calculated using the exogenous connections.
The fact that $x_{5}$ is linearly dependant on (i.e., can be represented as a
linear combination of) $x_{1},\cdots,x_{4}$ results in impossibility of
learning the causal connections to $x_{6}$ from observations. Specifically, it
is impossible to distinguish the true generating model of $x_{6}$ in (18) from
the following model, in which $x_{5}$ in the true generating model is replaced
by (20):

$x_{6}=c_{1}a_{65}x_{1}+(c_{2}a_{65}+a_{62})x_{2}+c_{3}a_{65}x_{3}+(c_{4}a_{65}+a_{64})x_{4}+\tilde{s}_{6}.$
(21)

Therefore, the generating model is not uniquely identifiable.

As we have seen in this example, unique identifiability of causal effects to
$x_{6}$ fails because, in the representation of $X$ recovered by BSS (cf.
(19)), $x_{5}$ is linearly dependent on the remaining possible parents of
$x_{6}$, i.e., $X_{[1:4]}$. In Appendix F.3, we show that linear independence
among possible parents in $\mathcal{P}_{k}$ holds if and only if the marriage
condition is satisfied.

##  Appendix E Proof of main theorem

###  E.1 Matrix representation of the necessary and sufficient conditions

Let us first define the existing component set $\mathcal{E}_{k}$ for each
observed variable $x_{k}$ as follows.

###### Definition 4

The _existing component set_ of $x_{k}$, denoted by $\mathcal{E}_{k}$, is the
set of all components in the possible parents of $x_{k}$, i.e.,
$\mathcal{E}_{k}=\bigcup_{x_{i}\in\mathcal{P}_{k}}{\rm{Comp}}(x_{i})$.

Recall that matrix $\mathbf{B}$ in (2) consists of all the exogenous
connections from sources to observed variables. Let $\mathbf{B}_{k}$ denote
the submatrix of $\mathbf{B}$ with rows corresponding to the possible parents
of $x_{k}$, i.e., $\mathcal{P}_{k}$, and columns corresponding to the existing
component set of $x_{k}$, i.e., $\mathcal{E}_{k}$. That is,

$\displaystyle\mathbf{B}_{k}=\left[\mathbf{B}_{ij}\right]_{i,j:\;x_{i}\in\mathcal{P}_{k},\;s_{j}\in\mathcal{E}_{k}}$
(22)

We repermute the rows and columns of $\mathbf{B}_{k}$, and label the columns,
as follows:

  1. (i)

We find the columns in $\mathbf{B}_{k}$ with only one non-zero entry and label
these columns as type-1. We repermute the columns of $\mathbf{B}_{k}$ such
that all type-1 columns are at the leftmost of $\mathbf{B}_{k}$.

  2. (ii)

We repermute the rows of $\mathbf{B}_{k}$ such that all nonzero entries in
type-1 columns appear in the upper rows. Note that two type-1 columns can have
their non-zero entry in the same row.

  3. (iii)

Among the columns that are not type-1 (have two or more non-zero entries), we
find those columns with their non-zero entries appearing in the non-zero part
of type-1 columns (i.e., the upper non-zero rows). We label these columns as
type-2. We repermute the columns of $\mathbf{B}_{k}$ such that type-2 columns
are next to type-1 columns. The matrix $\mathbf{B}_{k}$ can be now written as

$\displaystyle\mathbf{B}_{k}=\begin{bmatrix}\mathbf{U}_{1}&\mathbf{X}_{1}&\mathbf{Y}_{1}\\\
\mathbf{0}&\mathbf{0}&\mathbf{Z}_{1}\\\ \end{bmatrix}.$ (23)

$[\mathbf{U}_{1};\mathbf{0}]$ are the type-1 columns,
$[\mathbf{X}_{1};\mathbf{0}]$ are the type-2 columns, and
$[\mathbf{Y}_{1};\mathbf{Z}_{1}]$ are the remaining columns. Each column of
$\mathbf{Z}_{1}$ has at least one non-zero entry.

  4. (iv)

We repeat steps (i) to (iii) to permute the columns and rows of
$\mathbf{Z}_{1}$ such that

$\displaystyle\mathbf{Z}_{1}=\begin{bmatrix}\mathbf{U}_{2}&\mathbf{X}_{2}&\mathbf{Y}_{2}\\\
\mathbf{0}&\mathbf{0}&\mathbf{Z}_{2}\\\ \end{bmatrix}.$ (24)

The columns of $\mathbf{B}_{k}$ corresponding to the columns of
$\mathbf{U}_{2}$ and $\mathbf{X}_{2}$ (which were unlabeled in (23)) are now
labeled as type-1 and type-2 respectively.

  5. (v)

For $\mathbf{Z}_{n}$, $n=2,3,\cdots$, we repeat steps (i) to (iii) and label
the corresponding columns in $\mathbf{B}_{k}$ as in (iv); until this
factorization does not hold for $\mathbf{Z}_{N}$ for some $N\in\mathbb{N}$. We
label the columns of $\mathbf{B}_{k}$ that correspond to the columns of
$\mathbf{Z}_{N}$ as type-3 columns.

The column and row permutations in (i)-(v) are analogous to the iterative
process in Definition 3. Type-1 columns in (i) correspond to the unique
components in the first iteration, i.e., among possible parents in
$\mathcal{P}_{k}$. The rows selected in (ii) correspond to the possible
parents in $\mathcal{P}_{k}\setminus\mathcal{P}_{k}^{(1)}$. Type-2 columns
correspond to the sources that are shared only among the possible parents in
$\mathcal{P}_{k}\setminus\mathcal{P}_{k}^{(1)}$. $\mathbf{Z}_{1}$ in (23)
represents the exogenous connections of observed variables in
$\mathcal{P}_{k}^{(1)}$. For the iteration in (i)-(v), $\mathbf{Z}_{n}$,
$n=1,2,\cdots,N$, can be written as

$\mathbf{Z}_{n}=[\mathbf{B}_{ij}]_{i,j:\;x_{i}\in\mathcal{P}_{k}^{(n)},\;s_{j}\in\bigcup_{i\in
J^{(n)}}{\rm{Comp}}(\tilde{s}_{i})}.$

Lastly, the rows in $\mathbf{Z}_{N}$ correspond to the possible parents in
$\mathcal{I}_{k}$, and the sources shared among these variables correspond to
type-3 columns.

Given the matrix permutation and labeling in (i)-(v), the unique components
condition translates to: Each observed variable $x_{k}$ can only be
exogenously connected to either source variables corresponding to type-2
columns in $\mathbf{B}_{k}$, or new source components that are not in
$\mathcal{E}_{k}$ (i.e., do not correspond to columns in $\mathbf{B}_{k}$).
Further, the marriage condition translates to the matrix $\mathbf{B}_{k}$
being of full row rank, which is equivalent to $\mathbf{Z}_{N}$ being of full
row rank. The equivalence between the marriage condition and the full-row rank
of $\mathbf{B}_{k}$ is explained in Appendix F.3.

###  E.2 Proof of sufficiency

For any data generating model that satisfies Conditions 1 and 2 in Sections
3.1 and 3.2, we show that using the recovered mixing matrix
$\tilde{\mathbf{W}}$, we can construct an algorithm that uniquely recovers
both the causal effects among observed variables and the exogenous connections
from the sources. Specifically, we show that P-SCM Recovery Algorithm
(Algorithm 1) recovers the exact matrix of total causal effects, i.e.,
$(\mathbf{I}-\mathbf{A})^{-1}$, and the exogenous connection matrix
$\mathbf{B}$ up to permutation and scaling, i.e., $\tilde{\mathbf{B}}$ in
(11). The row permutation in Step 1 of Algorithm 1 has the property that for
each observed variable $x_{k}$, the possible parents of $x_{k}$ are all
preceding $x_{k}$ in the row ordering. This follows because for every
$x_{i}\in\mathcal{P}_{k}$, ${\rm{Comp}}(x_{i})\subsetneq{\rm{Comp}}(x_{k})$
according to Definition 2. Without loss of generality, assume that the
ordering among observed variables after the permutation in Step 1 is a natural
ordering. In this case, we have
$\mathcal{P}_{k}\subseteq\\{x_{1},\cdots,x_{k-1}\\}$ for all $x_{k}$.

We provide the proof by induction on the index of the observed variables $k$,
where the induction base is $k=1$. For $k=1$, there are no observed variables
in $\mathcal{P}_{1}$, hence all the source components of $x_{1}$ must result
from exogenous connections, which are learnt from the recovered mixing matrix.
For the induction hypothesis, we assume that the total causal effects among
$\\{x_{1},\cdots,x_{k-1}\\}$ and their exogenous connections from the sources
are given. We show that we can recover the total causal effects as well as the
exogenous connections to $x_{k}$.

From the induction hypothesis, we know the exogenous connections (source
mixtures) to the possible parents of $x_{k}$, i.e.,
$\tilde{\mathcal{S}}_{k}=\\{\tilde{s}_{i}:x_{i}\in\mathcal{P}_{k}\\}$. Our
algorithm follows a similar iterative procedure as in Definition 3, in order
to identify the unique components of each $x_{i}\in\mathcal{P}_{k}$, while
simultaneously solve for the total causal effect from $x_{i}$ to $x_{k}$.

First, the algorithm finds the observed variables with unique components among
all possible parents in $\mathcal{P}_{k}$, i.e.,
$x_{i}\in\mathcal{P}_{k}\setminus\mathcal{P}_{k}^{(1)}$ (see Section 3.1). For
each $x_{i}\in\mathcal{P}_{k}\setminus\mathcal{P}_{k}^{(1)}$ with a unique
component $s_{j}$, it follows from the unique component condition that $s_{j}$
is not exogenously connected to $x_{k}$. Thus, the $s_{j}$ component in
$x_{k}$ must result from the causal connection/path from $x_{i}$. The strength
of the causal effect can be correctly recovered via dividing $s_{j}$ component
in $x_{k}$ by $s_{j}$ component in $\tilde{s}_{i}$, i.e.,
$\tilde{w}_{kj}/\tilde{b}_{ij}$. Subsequently, we correctly recover the total
causal effect from all $x_{i}\in\mathcal{P}_{k}\setminus\mathcal{P}_{k}^{(1)}$
to $x_{k}$.

###### Remark 2

Note that $s_{j}$ component in $x_{i}$ only results from an exogenous
connection from $s_{j}$ to $x_{i}$, since the parents of $x_{i}$ are also in
$\mathcal{P}_{k}$ and $s_{j}$ is a unique component. Hence the $s_{j}$
component in $\tilde{s}_{i}$ is the same as the $s_{j}$ component in $x_{i}$.
This explains our use of “dividing by $s_{j}$ coefficient in $x_{i}$”, instead
of in $\tilde{s}_{i}$, in Section 3.1.

Next, we find the total causal effects from $x_{i}\in\mathcal{P}_{k}^{(1)}$.
Similarly, consider
$x_{i}\in\mathcal{P}_{k}^{(1)}\setminus\mathcal{P}_{k}^{(2)}$ with a unique
component $s_{j}$. It follows from the unique components condition that
$s_{j}$ is not exogenously connected to $x_{k}$. Thus, $s_{j}$ component in
$x_{k}$ results from the following effects: (i) causal connection/path from
$x_{i}$ and/or (ii) causal connections/paths from observed variables in
$\mathcal{P}_{k}\setminus\mathcal{P}_{k}^{(1)}$. The latter causal effects are
recovered in the last step and subtracted from $x_{k}$, and hence we calculate
the total causal effect from $x_{i}$ to $x_{k}$ by the residual of $s_{j}$
component in $x_{k}$ divided by $s_{j}$ component in $\tilde{s}_{i}$.
Therefore, we correctly recover the total causal effects from all
$x_{i}\in\mathcal{P}_{k}^{(1)}\setminus\mathcal{P}_{k}^{(2)}$ to $x_{k}$.

Repeat the last step for
$x_{i}\in\mathcal{P}_{k}^{(n)}\setminus\mathcal{P}_{k}^{(n+1)}$ for
$n=2,\cdots,N-1$, i.e., all observed variables with unique components. Next,
we find the total causal effects from $x_{i}\in\mathcal{I}_{k}$ (with no
unique components) to $x_{k}$. The unique components condition implies that
$x_{k}$ cannot be exogenously connected to any source variable that belongs to
$\bigcup_{i\in J^{(N)}}{\rm{Comp}}(\tilde{s}_{i})$ (recall that $J^{(N)}$ is
the index set of $\mathcal{I}_{k}$). That is, the exogenous connections to
$x_{k}$ can not overlap with the exogenous connections to any
$x_{i}\in\mathcal{I}_{k}$. Then, we recover the total causal effects from
$x_{i}\in\mathcal{I}_{k}$ to $x_{k}$ using the residuals of the set of sources
$\bigcup_{i\in J^{(N)}}{\rm{Comp}}(\tilde{s}_{i})$ in $x_{k}$ (after all
subtractions in the previous steps). This results in an overdetermined linear
system of the total causal effects:

$\displaystyle\mathbf{w}=\mathbf{Z}^{\top}_{N}\tilde{\mathbf{a}}_{k},\quad\mathbf{Z}_{N}=[\tilde{\mathbf{B}}_{ij}]_{i,j:\;x_{i}\in\mathcal{I}_{k},\;s_{j}\in\bigcup_{i\in
J^{(N)}}{\rm{Comp}}(\tilde{s}_{i})}.$ (25)

$\mathbf{w}$ is the vector of the residuals of the source components in
$x_{k}$ that correspond to $\bigcup_{i\in J^{(N)}}{\rm{Comp}}(\tilde{s}_{i})$;
$\tilde{\mathbf{a}}_{k}$ is the vector of total causal effects from the
observed variables in $\mathcal{I}_{k}$ to $x_{k}$; $\mathbf{Z}_{N}$
represents the exogenous connections to observed variables in
$\mathcal{I}_{k}$ (see Appendix E.1).

According to the marriage condition, $\mathbf{Z}_{N}$ is of full row rank, see
Appendix E.1. Thus, the overdetermined linear system in (25) has at most one
solution which corresponds to the true total causal effects from each
$x_{i}\in\mathcal{I}_{k}$. Note that $\tilde{\mathbf{B}}_{k}$ has the same
rank as $\mathbf{B}_{k}$ since permuting the columns does not change the rank.
To sum up, Algorithm 1 correctly recovers the total causal effects from the
possible parents of $x_{k}$ ($x_{i}\in\mathcal{P}_{k}$) to $x_{k}$. The
remaining source components in $x_{k}$ represent the exogenous connections
from the corresponding sources to $x_{k}$, which can be recovered up to
permutation and scalability indeterminacies. The recovered matrix
$\tilde{\mathbf{B}}$ has the same column-permutation and scaling as the output
of BSS $\tilde{\mathbf{W}}$. That is, Algorithm 1 is able to recover the exact
adjacency matrix $\mathbf{A}$ using the unique components and/or matrix
inversion, by shifting all the indeterminacies into the residual values to
recover $\tilde{\mathbf{B}}$. Recall, for matrix $\mathbf{B}$, the column
permutation indeterminacy is irrelevant; the scalability indeterminacy is
unavoidable in our setting unless we have prior information about the sources.

The column permutation is maintained for $\tilde{\mathbf{B}}$ because the
order of the sources, given in $\tilde{\mathbf{W}}$, is not changed throughout
Algorithm 1. For scalability of the causal effects, we assume that the learnt
exogenous connections from a source $s_{l}$ to all $x_{i}\in\mathcal{P}_{k}$
(i.e., the column of $\tilde{\mathbf{B}}_{k}$ corresponding to $s_{l}$) share
the same scale as the corresponding column in $\tilde{\mathbf{W}}$. Algorithm
1 first recovers the correct total causal effect
$\tilde{a}_{ki}=\tilde{w}_{kj}/\tilde{b}_{ij}$ (cf. Step 1) using the unique
components for $x_{i}\in\mathcal{P}_{k}\setminus\mathcal{P}_{k}^{(1)}$. The
residual of $s_{l}$ in $x_{k}$ after subtracting the effect of $x_{i}$ (Step
1), which is $\tilde{w}_{kl}-\tilde{a}_{ki}\tilde{b}_{il}$, shares the same
scale as $\tilde{w}_{kl}$. Similarly, for all $x_{i}$ with unique components,
i.e., $x_{i}\in\mathcal{P}_{k}\setminus\mathcal{I}_{k}$, Algorithm 1 recovers
the correct total causal effect $\tilde{a}_{ki}$, and the residual shares the
same scale as $\tilde{w}_{kl}$. For $x_{i}\in\mathcal{I}_{k}$, Algorithm 1
still recovers the correct total causal effect using (25) (cf. Step 1), since
each column of $\mathbf{Z}_{N}$ in (25) shares the same scale as the
corresponding entry of $\mathbf{w}$. Finally, the remaining $s_{l}$ component
in $x_{k}$, shares the same scale as $\tilde{w}_{kl}$, which is then
considered as the direct connection $\tilde{b}_{kl}$. Therefore, the learnt
exogenous connections from $s_{l}$ to all observed variables $x_{k}$, which
are in the column of $\tilde{\mathbf{B}}$ corresponding to $s_{l}$, share the
same scale as the corresponding column in $\tilde{\mathbf{W}}$.

In conclusion, given the causal structure and exogenous connections to the
possible parents of $x_{k}$, we are able to recover the exact total causal
effects to $x_{k}$ along with its exogenous connections. This establishes the
induction step and completes our sufficiency proof.

###### Remark 3

As we mentioned earlier, for each observed variable $x_{k}$, the possible
parents of $x_{k}$, i.e., $\mathcal{P}_{k}$, are all preceding $x_{k}$ in the
row ordering deduced in Step 1 of Algorithm 1. Since the ancestors of $x_{k}$
are also included in $\mathcal{P}_{k}$, this implies that by sorting the
observed variables according to the number of source components in the
recovered mixing matrix $\tilde{\mathbf{W}}$, we can find a causal order among
the observed variables which is consistent with the correct order. This method
is faster than the pairwise comparison in (Salehkaleybar et al.,, 2020, Lemma
5).

###  E.3 Proof of necessity

We show that for any generating model $\mathcal{G}$ that violates either the
unique component condition or the marriage condition, given the corresponding
$\tilde{\mathbf{W}}$, we cannot distinguish between the true generating model
$\mathcal{G}$ and another generating model $\mathcal{G}^{\prime}$. Without
loss of generality, assume that the observed variables are ordered such that
for any $x_{k}$, $\mathcal{P}_{k}\subseteq\\{x_{1},\cdots,x_{k-1}\\}$. This
ordering can be achieved by permuting the rows of $\tilde{\mathbf{W}}$ to the
corresponding order.

Now, consider a generating model $\mathcal{G}$ that does not satisfy either or
both of the conditions. Suppose $x_{k}$ has the smallest index among the
observed variables such that the conditions are not satisfied. That is, the
submodel $\\{x_{1},\cdots,x_{k-1}\\}$ does satisfy the unique component and
marriage conditions. We can write the generating model $\mathcal{G}$ of
$x_{k}$ as:

$x_{k}=\sum_{i:x_{i}\in\mathcal{P}_{k}}\tilde{a}_{ki}\tilde{s}_{i}+\tilde{s}_{k},\quad\tilde{s}_{k}=\sum_{s_{j}\in{\rm{Comp}}(\tilde{s}_{k})}b_{kj}s_{j}.$
(26)

where we redefine $\tilde{a}_{ki}$ to be the total causal effect from observed
variable $x_{i}$ to $x_{k}$, and $b_{kj}$ is the strength of the exogenous
connection from $s_{j}$ to $x_{k}$. We consider one of the following cases for
non-satisfiability of the theorem conditions:

  1. (i)

$\exists x_{i_{0}}\in\mathcal{P}_{k}$ with a non-empty unique component set,
such that at least one unique component of $x_{i_{0}}$ is exogenously
connected to $x_{k}$.

  2. (ii)

$\exists x_{i_{0}}\in\mathcal{P}_{k}$ with an empty unique component set such
that at least one component of $\tilde{s}_{i_{0}}$ is exogenously connected to
$x_{k}$.

  3. (iii)

The collection of component sets of the source mixtures
$\tilde{\mathcal{S}}_{k}=\\{{\rm{Comp}}(\tilde{s}_{i}):x_{i}\in\mathcal{P}_{k}\\}$
does not satisfy the marriage condition.

Case (i).  Suppose there exists an index $i_{0}$ such that
$U_{k}(i_{0})\cap{\rm{Comp}}(\tilde{s}_{k})\neq\emptyset$. Let $s_{j_{0}}\in
U_{k}(i_{0})\cap{\rm{Comp}}(\tilde{s}_{k})$, i.e., $s_{j_{0}}$ is a unique
component of $x_{i_{0}}$ and is also exogenously connected to $x_{k}$. In the
following, we show we cannot determine if the component $s_{j_{0}}$ in $x_{k}$
results from a causal connection/path or an exogenous connection to $x_{k}$,
or both.

We first take out the term with respect to $\tilde{s}_{i_{0}}$ and $s_{j_{0}}$
from $x_{k}$ in (26), and rewrite (26) as

$\displaystyle x_{k}=\sum_{\begin{subarray}{c}i:x_{i}\in\mathcal{P}_{k}\\\
i\neq
i_{0}\end{subarray}}\tilde{a}_{ki}\tilde{s}_{i}+\tilde{a}_{ki_{0}}\tilde{s}_{i_{0}}+\sum_{\begin{subarray}{c}s_{j}\in{\rm{Comp}}(\tilde{s}_{k})\\\
j\neq j_{0}\end{subarray}}b_{kj}s_{j}+b_{kj_{0}}s_{j_{0}},\quad b_{kj_{0}}\neq
0.$ (27)

Next, consider the exogenous connections to $x_{i_{0}}$ (i.e.,
$\tilde{s}_{i_{0}}$), which can be expressed as

$\displaystyle\tilde{s}_{i_{0}}=\sum_{\begin{subarray}{c}s_{j^{\prime}}\in{\rm{Comp}}(\tilde{s}_{i_{0}})\\\
j^{\prime}\neq
j_{0}\end{subarray}}b_{i_{0}j^{\prime}}s_{j^{\prime}}+b_{i_{0}j_{0}}s_{j_{0}},\quad
b_{i_{0}j_{0}}\neq 0.$ (28)

By substituting $\tilde{s}_{i_{0}}$ in (27) by (28), we get

$\displaystyle x_{k}$
$\displaystyle=\sum_{\begin{subarray}{c}i:x_{i}\in\mathcal{P}_{k}\\\ i\neq
i_{0}\end{subarray}}\tilde{a}_{ki}\tilde{s}_{i}+\sum_{\begin{subarray}{c}s_{j}\in{\rm{Comp}}(\tilde{s}_{k})\\\
j\neq
j_{0}\end{subarray}}b_{kj}s_{j}+b_{kj_{0}}s_{j_{0}}+\tilde{a}_{ki_{0}}\left(\sum_{\begin{subarray}{c}s_{j^{\prime}}\in{\rm{Comp}}(\tilde{s}_{i_{0}})\\\
j^{\prime}\neq
j_{0}\end{subarray}}b_{i_{0}j^{\prime}}s_{j^{\prime}}+b_{i_{0}j_{0}}s_{j_{0}}\right)$
$\displaystyle=\sum_{\begin{subarray}{c}i:x_{i}\in\mathcal{P}_{k}\\\ i\neq
i_{0}\end{subarray}}\tilde{a}_{ki}\tilde{s}_{i}+\sum_{\begin{subarray}{c}s_{j}\in{\rm{Comp}}(\tilde{s}_{k})\\\
j\neq
j_{0}\end{subarray}}b_{kj}s_{j}+\sum_{\begin{subarray}{c}s_{j^{\prime}}\in{\rm{Comp}}(\tilde{s}_{i_{0}})\\\
j^{\prime}\neq
j_{0}\end{subarray}}\tilde{a}_{ki_{0}}b_{i_{0}j^{\prime}}s_{j^{\prime}}+(\tilde{a}_{ki_{0}}b_{i_{0}j_{0}}+b_{kj_{0}})s_{j_{0}}.$
(29)

Given the recovered mixing matrix $\tilde{\mathbf{W}}$, $x_{k}$ can be written
as a linear combination of sources. Suppose the total causal effects from all
observed variables $x_{i}\in\mathcal{P}_{k}\setminus\\{x_{i_{0}}\\}$ are
recovered as in (29). Now, our task is to recover the total causal effect from
$x_{i_{0}}$ to $x_{k}$.

Let us consider the $s_{j_{0}}$ component in (29). It consists of two parts:
$\tilde{a}_{ki_{0}}b_{i_{0}j_{0}}s_{j_{0}}$ which results from the causal
connection/path from $x_{i_{0}}$, and $b_{kj_{0}}s_{j_{0}}$ which results from
the exogenous connection from $s_{j_{0}}$. In order to learn the causal
structure, we ought to be able to differentiate between these two parts from
their mixture in (29) (i.e., based on the mixing matrix $\tilde{\mathbf{W}}$),
which is not possible. More specifically, we can not distinguish the true
model from the following two generating models:

Model 1:

$\displaystyle
x_{k}^{(1)}=\sum_{\begin{subarray}{c}i:x_{i}\in\mathcal{P}_{k}\\\ i\neq
i_{0}\end{subarray}}\tilde{a}_{ki}\tilde{s}_{i}+(\tilde{a}_{i_{0}}+\frac{b_{kj_{0}}}{b_{i_{0}j_{0}}})\tilde{s}_{i_{0}}+\tilde{s}^{(1)}_{k};~{}\tilde{s}^{(1)}_{k}=\sum_{\begin{subarray}{c}s_{j}\in{\rm{Comp}}(\tilde{s}_{k})\\\
j\neq
j_{0}\end{subarray}}b_{kj}s_{j}-\sum_{\begin{subarray}{c}s_{j^{\prime}}\in{\rm{Comp}}(\tilde{s}_{i_{0}})\\\
j^{\prime}\neq
j_{0}\end{subarray}}\frac{b_{kj_{0}}b_{i_{0}j^{\prime}}}{b_{i_{0}j_{0}}}s_{j^{\prime}},$
(30)

which corresponds to the $s_{j_{0}}$ component in $x_{k}$ being caused only by
the causal effect from $x_{i_{0}}$.

Model 2:

$\displaystyle
x_{k}^{(2)}=\sum_{\begin{subarray}{c}i:x_{i}\in\mathcal{P}_{k}\\\ i\neq
i_{0}\end{subarray}}\tilde{a}_{ki}\tilde{s}_{i}+\tilde{s}^{(2)}_{k};\quad\tilde{s}^{(2)}_{k}=\sum_{\begin{subarray}{c}s_{j}\in{\rm{Comp}}(\tilde{s}_{k})\\\
j\neq
j_{0}\end{subarray}}b_{kj}s_{j}+\sum_{\begin{subarray}{c}s_{j^{\prime}}\in{\rm{Comp}}(\tilde{s}_{i_{0}})\\\
j^{\prime}\neq
j_{0}\end{subarray}}\tilde{a}_{ki_{0}}b_{i_{0}j^{\prime}}s_{j^{\prime}}+(\tilde{a}_{ki_{0}}b_{i_{0}j_{0}}+b_{kj_{0}})s_{j_{0}},$
(31)

which corresponds to the $s_{j_{0}}$ component being caused only by the
exogenous connection from $s_{j_{0}}$. On the contrary, if the unique
component $s_{j_{0}}$ is not exogenously connected to $x_{k}$, then we can use
this unique component to compute the total causal effect from $x_{i_{0}}$ to
$x_{k}$ (i.e., $\tilde{a}_{ki_{0}}$) and use this to figure out if there exist
exogenous connections from the remaining components in $\tilde{s}_{i_{0}}$ to
$x_{k}$.

Notice that an observed variable $x_{i}$ may have multiple unique components
in the unique component set $U_{k}(i)$. This does not violate the
irreducibility assumption, because when we are recovering the causal structure
of $x_{k}$, we are only considering the submatrix of $\tilde{\mathbf{W}}$
corresponding to the observed variables in $\mathcal{P}_{k}$. Suppose there
exists another source $s_{l_{0}}$ which is a unique component of $x_{i_{0}}$
and is not exogenously connected to $x_{k}$, while the unique component
$s_{j_{0}}$ of $x_{i_{0}}$ is exogenously connected to $x_{k}$. Since we have
no prior information about which of the two unique components is not
exogenously connected to $x_{k}$, there are two candidate models that we
cannot distinguish between: In each of these two models, the total causal
effect from $x_{i_{0}}$ to $x_{k}$ is calculated using one of the two unique
components in $x_{i_{0}}$, and there is an extra exogenous connection from the
other unique component. Thus none of the unique components in $U_{k}(i)$ can
be exogenously connected to $x_{k}$.

Case (ii).  Suppose there exists an index $i_{0}$ such that
${\rm{Comp}}(\tilde{s}_{i_{0}})\cap{\rm{Comp}}(\tilde{s}_{k})\neq\emptyset$.
Let
$s_{j_{0}}\in{\rm{Comp}}(\tilde{s}_{i_{0}})\cap{\rm{Comp}}(\tilde{s}_{k})$,
i.e., $s_{j_{0}}$ is exogenously connected to both $x_{i_{0}}$ and $x_{k}$,
where $x_{i_{0}}$ does not have unique components.

Notice that (27)-(29) hold for this case as well; (27)-(29) do not depend on
whether $x_{i_{0}}$ has unique components. When $x_{i_{0}}$ has no unique
components, and one of its components $s_{j_{0}}$ is exogenously connected to
$x_{k}$, this results in a similar indistinguishably problem as in the
previous case. In particular, we are not able to distinguish between the part
of $s_{j_{0}}$ component in $x_{k}$ that results from the causal
connection/path from $x_{i_{0}}$, and the part that results from the exogenous
connection from $s_{j_{0}}$. Thus, given $\tilde{\mathbf{W}}$, we can not
distinguish the true model from the two generating models in (30) and (31).

The only difference from case (i) is that $x_{i_{0}}$ does not have unique
components. In this case, we cannot have any of the components in
$\tilde{s}_{i_{0}}$ to be exogenously connected to $x_{k}$. In particular, all
the shared (non-unique) components of $\tilde{s}_{i_{0}}$ are pivotal to
recover the total causal effect from $x_{i_{0}}$ to $x_{k}$ and including any
of them in $\tilde{s}_{k}$ will always result in indistinguishably of the
generating model.

Case (iii).  Suppose the marriage condition is not satisfied on the collection
$\tilde{\mathcal{S}}_{k}$. Then as described in Appendix E.1, the matrix
$\mathbf{B}_{k}$ is not of full row rank, where $\mathbf{B}_{k}$ is defined as
$\mathbf{B}_{k}=[\mathbf{B}_{ij}]_{i,j:\;x_{i}\in\mathcal{P}_{k},\;s_{j}\in\mathcal{E}_{k}}$.

Given the recovered mixing matrix $\tilde{\mathbf{W}}$, suppose that the
exogenous connections to $x_{k}$, i.e., $\tilde{s}_{k}$, are recovered as in
(26). Then the remaining source components in $x_{k}$ that result from the
causal connections/paths from the possible parents in $\mathcal{P}_{k}$ can be
written as

$\displaystyle\sum_{s_{j}\in{\rm{Comp}}(x_{k})}\tilde{w}_{kj}s_{j}-\tilde{s}_{k}=\sum_{s_{j}\in\mathcal{E}_{k}}\tilde{w}^{\prime}_{kj}s_{j}=\sum_{i:x_{i}\in\mathcal{P}_{k}}\tilde{a}_{ki}\tilde{s}_{i},$

where $\\{\tilde{w}_{kj}\\}_{j:s_{j}\in{\rm{Comp}}(x_{k})}$ are the entries
corresponding to $x_{k}$ in $\tilde{\mathbf{W}}$ (i.e.,
$x_{k}=\sum_{s_{j}\in{\rm{Comp}}(x_{k})}\tilde{w}_{kj}s_{j}$).
$\\{\tilde{w}^{\prime}_{kj}\\}$ are also known, as they result from
subtracting the components of $\tilde{s}_{k}$ (known by assumption) from
$x_{k}$. Our task is to recover the total causal effect $\tilde{a}_{ki}$ from
each possible parent $x_{i}\in\mathcal{P}_{k}$ to $x_{k}$, which translates to
finding the solution of