$\displaystyle=\dim\left(\mathrm{proj}_{\mathrm{span}\left\langle{\bm{h}}_{s_{j}}:j\leqslant
m^{\prime}\right\rangle^{\perp}}\mathrm{span}\left\langle{\bm{h}}_{t_{1}},{\bm{h}}_{t_{2}},\cdots,{\bm{h}}_{t_{\ell}}\right\rangle\right)$
$\displaystyle=\ell\quad\text{(by \lx@cref{creftypecap~refnum}{lemma:linalg-
proj-dim} and non-degeneracy of ${\bm{H}}$)}$

which proves (*). From (*) it is easy to see that
$m^{\prime}\in\overline{\mathrm{pa}}_{\mathcal{G}}(i)$ (and thus in
$\mathrm{pa}_{\mathcal{G}}(i)$ since $i\notin S$) if and only if
$r_{m^{\prime}}=r_{m^{\prime}-1}-1$. ∎

Now we conclude the proof of Theorem 3. Propositions 1 and 2 directly imply
that Algorithm 3 is able to exactly recover the ground-truth causal graph
$\mathcal{G}$. It remains to show that Algorithm 3 produces the correct
$\hat{{\bm{h}}}_{i}$’s. By Lemma 15 we know that
$E_{j}=\mathrm{span}\left\langle{\bm{h}}_{\ell}:\ell\in\overline{\mathrm{pa}}_{\mathcal{G}}(j)\right\rangle$,
so

$\cap_{j\in\overline{\mathrm{ch}}_{\mathcal{G}}(i)}E_{j}=\cap_{j\in\overline{\mathrm{ch}}_{\mathcal{G}}(i)}\mathrm{span}\left\langle{\bm{h}}_{\ell}:\ell\in\overline{\mathrm{pa}}_{\mathcal{G}}(j)\right\rangle=\mathrm{span}\left\langle{\bm{h}}_{\ell}:\ell\in\overline{\mathrm{dom}}_{\mathcal{G}}(i)\right\rangle.$

where the last step holds because ${\bm{H}}$ has full row rank and
$\cap_{j\in\overline{\mathrm{ch}}_{\mathcal{G}}(i)}\overline{\mathrm{pa}}_{\mathcal{G}}(j)=\overline{\mathrm{dom}}_{\mathcal{G}}(i)$
by definition. Hence, each $\hat{{\bm{h}}}_{i}$ is a linear combination of
${\bm{h}}_{\ell},\ell\in\overline{\mathrm{dom}}_{\mathcal{G}}(i)$, completing
the proof.

##  Appendix F Omitted Proofs from Theorem 4

###  F.1 Proof of Lemma 2

Let ${\bm{w}}_{k}(i)\in\mathbb{R}^{\left|\mathrm{pa}_{\mathcal{G}}(i)\right|}$
be the vector obtained by removing all zero entries in the $i$-th row of
${\bm{A}}_{k}$ and $\omega_{k,i,i}$ be the $i$-th diagonal entry in
$\bm{\Omega}_{k}$ , then for the $k$-th environment we have
${\bm{z}}_{i}={\bm{w}}_{k}(i)^{\top}{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)}+\omega_{k,i,i}^{\frac{1}{2}}\epsilon_{i}$,
so that

$\hat{p}_{k}\left({\bm{z}}_{i}\mid{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)=\omega_{k,i,i}^{-\frac{1}{2}}p_{\epsilon_{i}}\left(\omega_{k,i,i}^{-\frac{1}{2}}({\bm{z}}_{i}-\langle{\bm{w}}_{k}(i),{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)}\rangle)\right)$

where $p_{\epsilon_{i}}(\cdot)$ is the density of $\epsilon_{i}$. As a result,
we have

$\displaystyle\nabla\frac{\hat{p}_{1}}{\hat{p}_{k}}\left({\bm{z}}_{i}\mid{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)$
$\displaystyle=\frac{\hat{p}_{1}}{\hat{p}_{k}}\left({\bm{z}}_{i}\mid{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)\cdot\nabla\log\frac{\hat{p}_{1}}{\hat{p}_{k}}\left({\bm{z}}_{i}\mid{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)$
$\displaystyle=\frac{\hat{p}_{1}}{\hat{p}_{k}}\left({\bm{z}}_{i}\mid{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)\cdot\left[c_{i1}(1,-{\bm{w}}_{1}(i))-c_{ik}(1,-{\bm{w}}_{k}(i))\right]$

where for convenience we use $\nabla$ to denote the gradient with respect to
all variables ${\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}$, and
$c_{ik}=\omega_{k,i,i}^{-\frac{1}{2}}\cdot\frac{p_{\epsilon_{i}}^{\prime}}{p_{\epsilon_{i}}}\left(\omega_{k,i,i}^{-\frac{1}{2}}({\bm{z}}_{i}-\langle{\bm{w}}_{k}(i),{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)}\rangle\right)$
(we omit the dependency on ${\bm{z}}$ for simplicity).

Definition 6 implies that $\mathrm{span}\left\langle
c_{i1}(1,-{\bm{w}}_{1}(i))-c_{ik}(1,-{\bm{w}}_{k}(i)):2\leqslant k\leqslant
K\right\rangle=\mathbb{R}^{\left|\mathrm{pa}_{\mathcal{G}}(i)\right|+1}$, thus
it holds that
$\mathrm{span}\langle(1,-{\bm{w}}_{k}(i)):k\in[K]\rangle=\mathbb{R}^{\left|\mathrm{pa}_{\mathcal{G}}(i)\right|+1}$
as well. By definition of ${\bm{B}}_{k}$, this immediately implies that
$\dim\left(\mathrm{span}\left\langle({\bm{B}}_{k})_{i}:k\in[K]\right\rangle\right)=\left|\mathrm{pa}_{\mathcal{G}}(i)\right|+1$
as desired.

###  F.2 Proof of Theorem 4

Define
$\bm{\tau}:=\hat{{\bm{h}}}\circ{\bm{h}}^{-1}:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$,
then we have that ${\bm{v}}=\bm{\tau}({\bm{z}})$. Since both ${\bm{h}}$ and
$\hat{{\bm{h}}}$ are diffeomorphisms by assumption, so is $\bm{\tau}$. To
avoid confusion, in this section we use ${\bm{z}}$ (resp. ${\bm{v}}$) to
denote random variables while using $\hat{{\bm{z}}}$ (resp. $\hat{{\bm{v}}}$)
to denote (deterministic) vectors.

Let $\mathfrak{E}_{j}=\left\\{E_{k}^{(j)}:k\in[K_{j}]\right\\}$ be the $j$-th
collection of environments according to our assumption. We first prove the
following lemma:

######  Lemma 17.

${\bm{O}}_{{\bm{v}}}=\bm{\tau}({\bm{O}}_{{\bm{z}}})$.

###### Proof.

By the change of variable formula (schwartz1954formula), for
$\forall\hat{{\bm{z}}}\in\mathbb{R}^{d}$ and $\forall E\in\mathfrak{E}$ we
have
$p_{E}(\hat{{\bm{z}}})=q_{E}(\hat{{\bm{v}}})\left|\det{\bm{J}}_{\bm{\tau}}(\hat{{\bm{z}}})\right|$,
where $\hat{{\bm{v}}}=\bm{\tau}(\hat{{\bm{z}}})$. Since $\bm{\tau}$ is a
diffeomorphism, we must have
$\left|\det{\bm{J}}_{\bm{\tau}}(\hat{{\bm{z}}})\right|\neq 0$, so
$\hat{{\bm{z}}}\in{\bm{O}}_{{\bm{z}}}\Leftrightarrow\hat{{\bm{v}}}=\bm{\tau}(\hat{{\bm{z}}})\in{\bm{O}}_{{\bm{v}}}$,
concluding the proof. ∎

######  Lemma 18.

Let $\hat{{\bm{z}}}\in{\bm{O}}_{{\bm{z}}}$. For $\forall j\in[d]$ and
$2\leqslant k\leqslant K_{j}$, we have

$\frac{p_{j}^{E_{k}^{(j)}}}{p_{j}^{E_{1}^{(j)}}}\left(\hat{{\bm{z}}}_{j}\mid\hat{{\bm{z}}}_{\mathrm{pa}_{\mathcal{G}}(j)}\right)=\frac{q_{j}^{E_{k}^{(j)}}}{q_{j}^{E_{1}^{(j)}}}\left(\hat{{\bm{v}}}_{j}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\hat{\mathcal{G}}}(j)}\right),$
(23)

where $\hat{{\bm{v}}}=\bm{\tau}(\hat{{\bm{z}}})\in{\bm{O}}_{{\bm{v}}}$.

###### Proof.

Since ${\bm{v}}=\bm{\tau}({\bm{z}})$, by the change-of-measure formula
(schwartz1954formula) we have that for
$\forall\hat{{\bm{z}}}\in{\bm{O}}_{{\bm{z}}}$,

$\displaystyle\prod_{i=1}^{d}p_{i}^{E}\left(\hat{{\bm{z}}}_{i}\mid\hat{{\bm{z}}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)$
$\displaystyle=p_{E}(\hat{{\bm{z}}})=q_{E}(\hat{{\bm{v}}})\left|\det{\bm{J}}_{\bm{\tau}}(\hat{{\bm{z}}})\right|=\prod_{i=1}^{d}q_{i}^{E}\left(\bm{\tau}_{i}(\hat{{\bm{z}}})\mid\bm{\tau}_{\mathrm{pa}_{\hat{\mathcal{G}}}(i)}(\hat{{\bm{z}}})\right)\left|\det{\bm{J}}_{\bm{\tau}}(\hat{{\bm{z}}})\right|$
(24)

for all $E\in\mathfrak{E}_{j}$, where
$\hat{{\bm{v}}}=\bm{\tau}(\hat{{\bm{z}}})$. By Assumption ($ii$) and
Definition 3, we know that
$p_{i}^{E_{k}^{1}}=p_{i}^{E_{1}^{(1)}}\Leftrightarrow i\neq 1$ and
$q_{i}^{E_{k}^{1}}=q_{i}^{E_{1}^{(1)}}\Leftrightarrow i\neq 1$ for all $k>1$.
Thus, we have that

$\prod_{i=1}^{d}\frac{p_{i}^{E_{k}^{(j)}}\left(\hat{{\bm{z}}}_{i}\mid\hat{{\bm{z}}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)}{p_{i}^{E_{1}^{(j)}}\left(\hat{{\bm{z}}}_{i}\mid\hat{{\bm{z}}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)}=\frac{p_{j}^{E_{k}^{(j)}}}{p_{j}^{E_{1}^{(j)}}}(\hat{{\bm{z}}}_{j}\mid\hat{{\bm{z}}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(j)})$

and

$\prod_{i=1}^{d}\frac{q_{i}^{E_{k}^{(j)}}\left(\hat{{\bm{v}}}_{i}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\hat{\mathcal{G}}}(i)}\right)}{q_{i}^{E_{1}^{(j)}}\left(\hat{{\bm{v}}}_{i}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\hat{\mathcal{G}}}(i)}\right)}=\frac{q_{j}^{E_{k}^{(j)}}}{q_{j}^{E_{1}^{(j)}}}(\hat{{\bm{v}}}_{j}\mid\hat{{\bm{v}}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(j)}).$

Since the LHS of the above two equations are the same by 24, the RHS must also
be the same, concluding the proof. ∎

We assume WLOG that the vertices of $\mathcal{G}$ are labelled such that $i\to
j\Rightarrow i<j$, and that $\pi(i)=i,\forall i\in[d]$. Also we can assume the
nodes are fixed and only consider how they are connected, _i.e.,_
$\pi^{\prime}(i)=i,\forall i\in[d]$. 444This is also WLOG because we now have
groups of soft interventions where each group corresponds to a single node, so
we can just relabel the node in $\hat{\mathcal{G}}$ that corresponds to the
$i$-th group as node $i$.

######  Lemma 19.

We have
$\left(\bm{\tau}({\bm{N}}_{{\bm{z}}})\right)^{\mathrm{o}}=\left(\bm{\tau}^{-1}({\bm{N}}_{{\bm{v}}})\right)^{\mathrm{o}}=\emptyset$.

###### Proof.

The result immediately follows from the assumption that
${\bm{N}}_{{\bm{z}}}^{\mathrm{o}}={\bm{N}}_{{\bm{v}}}^{\mathrm{o}}=\emptyset$
and that $\tau$ is a diffeomorphism. ∎

For any vertex set $V$, we use $\mathcal{G}_{V}$ to denote its corresponding
induced subgraph of $\mathcal{G}$. We first prove the following statements by
induction on $j$:

  1. (1)

$\forall i\neq j$, $i\in\mathrm{pa}_{\mathcal{G}}(j)\Leftrightarrow
i\in\mathrm{pa}_{\mathcal{G}^{\prime}}\left(j\right)$;

  2. (2)

$\forall j\in[d]$, there exists a continuously differentiable function
$\phi_{i}$ such that
${\bm{v}}_{j}=\phi_{j}\left({\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(j)}\right)$.
Moreover, $\frac{\partial\phi_{j}}{\partial{\bm{z}}_{j}}\not\equiv 0$ (_i.e._
, not always zero).

  3. (3)

$\forall j\in[d]$, there exists a continuously differentiable function
$\Upsilon_{j}$ such that
${\bm{v}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(j)}=\Upsilon_{j}({\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(j)})$.

For $j=1$, by assumption $\mathrm{pa}_{\mathcal{G}}(j)=\emptyset$. Lemma 18
implies that for any $\hat{{\bm{z}}}\in{\bm{O}}_{{\bm{z}}}$,

$\frac{p_{1}^{E_{k}^{(1)}}}{p_{1}^{E_{1}^{(1)}}}(\hat{{\bm{z}}}_{1})=\frac{q_{1}^{E_{k}^{(1)}}}{q_{1}^{E_{1}^{(1)}}}\left(\hat{{\bm{v}}}_{1}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\hat{\mathcal{G}}}(1)}\right),\forall
2\leqslant k\leqslant K_{1}.$ (25)

Then for $\forall
i\in\overline{\mathrm{pa}}_{\hat{\mathcal{G}}}\left(1\right)$, taking the
partial derivative w.r.t ${\bm{v}}_{j}$ gives

$\frac{\partial}{\partial\hat{{\bm{v}}}_{i}}\frac{q_{1}^{E_{k}^{(1)}}}{q_{1}^{E_{1}^{(1)}}}\left(\hat{{\bm{v}}}_{1}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\hat{\mathcal{G}}}(1)}\right)=\left(\frac{p_{1}^{E_{k}^{(1)}}}{p_{1}^{E_{1}^{(1)}}}\right)^{\prime}(\hat{{\bm{z}}}_{1})\cdot\frac{\partial\hat{{\bm{z}}}_{1}}{\partial\hat{{\bm{v}}}_{i}}\Rightarrow\nabla_{{\bm{v}}_{\overline{\mathrm{pa}}_{\hat{\mathcal{G}}}(1)}}\frac{q_{1}^{E_{k}^{(1)}}}{q_{1}^{E_{1}^{(1)}}}\left(\hat{{\bm{v}}}_{1}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\hat{\mathcal{G}}}(1)}\right)=\left(\frac{p_{1}^{E_{k}^{(1)}}}{p_{1}^{E_{1}^{(1)}}}\right)^{\prime}(\hat{{\bm{z}}}_{1})\cdot\nabla_{{\bm{v}}_{\overline{\mathrm{pa}}_{\hat{\mathcal{G}}}(1)}}\hat{{\bm{z}}}_{1}.$

Thus,

$\mathrm{rank}\left[\nabla_{{\bm{v}}_{\overline{\mathrm{pa}}_{\hat{\mathcal{G}}}(1)}}\frac{q_{1}^{E_{k}^{(1)}}}{q_{1}^{E_{1}^{(1)}}}\left(\hat{{\bm{v}}}_{1}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\hat{\mathcal{G}}}(1)}\right):2\leqslant
k\leqslant K_{1}\right]\leqslant 1.$

Note that the above inequality holds for
$\forall\hat{{\bm{v}}}\in{\bm{O}}_{{\bm{v}}}$. If
$\mathrm{pa}_{\hat{\mathcal{G}}}(1)\neq\emptyset$, then this would contradict
the non-degeneracy assumption (iii) which implies that the above matrix should
have rank $\geqslant 2$ at some point $\hat{{\bm{v}}}\in{\bm{O}}_{{\bm{v}}}$.
Hence we must have $\mathrm{pa}_{\hat{\mathcal{G}}}(1)=\emptyset$, implying
that (1) holds for $j=1$.

Taking the derivative of both sides of 25 w.r.t ${\bm{z}}_{i},i\geqslant 2$
implies that
$\left(\frac{q_{1}^{E_{k}^{(1)}}}{q_{1}^{E_{1}^{(1)}}}\right)^{{}^{\prime}}(\hat{{\bm{v}}}_{1})\cdot\frac{\partial\hat{{\bm{v}}}_{1}}{\partial\hat{{\bm{z}}}_{i}}=0$.
By our assumption (iii), for
$\forall\hat{{\bm{v}}}\in{\bm{O}}_{{\bm{v}}}\setminus{\bm{N}}_{{\bm{v}}}$,
there exists $2\leqslant k\leqslant K_{1}$ such that
$\left(\frac{q_{1}^{E_{k}^{(1)}}}{q_{1}^{E_{1}^{(1)}}}\right)^{{}^{\prime}}(\hat{{\bm{v}}}_{1})\neq
0$, and thus we have
$\frac{\partial\hat{{\bm{v}}}_{1}}{\partial\hat{{\bm{z}}}_{i}}=0,\forall\hat{{\bm{z}}}\in\bm{\tau}^{-1}\left({\bm{O}}_{{\bm{v}}}\setminus{\bm{N}}_{{\bm{v}}}\right)$.
Since $\bm{\tau}$ is a diffeomorphism, we can deduce that
$\bm{\tau}^{-1}\left({\bm{O}}_{{\bm{v}}}\setminus{\bm{N}}_{{\bm{v}}}\right)={\bm{O}}_{{\bm{z}}}\setminus\bm{\tau}^{-1}\left({\bm{N}}_{{\bm{v}}}\right)$
and
$\left(\bm{\tau}^{-1}\left({\bm{N}}_{{\bm{v}}}\right)\right)^{\mathrm{o}}=\emptyset$
by Lemma 19. As a result, we actually have
$\frac{\partial\hat{{\bm{v}}}_{1}}{\partial\hat{{\bm{z}}}_{i}}=0,\forall\hat{{\bm{z}}}\in{\bm{O}}_{{\bm{z}}}$.
Hence in ${\bm{O}}_{{\bm{z}}}$ there exists a continuous differentiable
function $\phi_{1}$ such that ${\bm{v}}_{1}=\phi_{1}({\bm{z}}_{1})$, proving
(2). Finally, (3) directly follows from (2) since
$\mathrm{pa}_{\mathcal{G}}(1)=\emptyset$, concluding the proof for $j=1$.

Now suppose that the statement holds up to $j-1$, and we need to prove it for
$j$. Again by Lemma 18 we have for
$\forall\hat{{\bm{z}}}\in{\bm{O}}_{{\bm{z}}}$ that

$\frac{p_{j}^{E_{k}^{(j)}}}{p_{j}^{E_{1}^{(j)}}}\left(\hat{{\bm{z}}}_{j}\mid\hat{{\bm{z}}}_{\mathrm{pa}_{\mathcal{G}}(j)}\right)=\frac{q_{j}^{E_{k}^{(j)}}}{q_{j}^{E_{1}^{(j)}}}\left(\hat{{\bm{v}}}_{j}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\hat{\mathcal{G}}}(j)}\right),\quad\forall
2\leqslant k\leqslant K_{j}.$ (26)

For all $i\notin\overline{\mathrm{pa}}_{\mathcal{G}}(j)$, taking partial
derivative w.r.t. ${\bm{z}}_{i}$ gives

$0=\sum_{\ell\in\overline{\mathrm{pa}}_{\hat{\mathcal{G}}}\left(j\right)}\frac{\partial}{\partial\hat{{\bm{v}}}_{\ell}}\frac{q_{j}^{E_{k}^{(j)}}}{q_{j}^{E_{1}^{(j)}}}\left(\hat{{\bm{v}}}_{j}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\hat{\mathcal{G}}}(j)}\right)\cdot\frac{\partial\hat{{\bm{v}}}_{\ell}}{\partial\hat{{\bm{z}}}_{i}},\quad\forall
2\leqslant k\leqslant K_{j},$

_i.e._ ,

$\left[\nabla_{{\bm{v}}_{\overline{\mathrm{pa}}_{\hat{\mathcal{G}}}(j)}}\frac{q_{j}^{E_{k}^{(j)}}}{q_{j}^{E_{1}^{(j)}}}\left(\hat{{\bm{v}}}_{j}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\hat{\mathcal{G}}}(j)}\right):2\leqslant
k\leqslant
K_{j}\right]^{\top}\frac{\partial\hat{{\bm{v}}}_{\overline{\mathrm{pa}}_{\hat{\mathcal{G}}}(j)}}{\partial\hat{{\bm{z}}}_{i}}=0.$

Similar to the $j=1$ case, by assumption (iii), we know that the above
corfficient matrix has full row rank for
$\forall\hat{{\bm{v}}}\in{\bm{O}}_{{\bm{v}}}\setminus{\bm{N}}_{{\bm{v}}}$, so
for
$\forall{\bm{z}}\in\bm{\tau}^{-1}\left({\bm{O}}_{{\bm{v}}}\setminus{\bm{N}}_{{\bm{v}}}\right)={\bm{O}}_{{\bm{z}}}\setminus\bm{\tau}^{-1}\left({\bm{N}}_{{\bm{v}}}\right)$,
we have
$\frac{\partial\hat{{\bm{v}}}_{\overline{\mathrm{pa}}_{\hat{\mathcal{G}}}(j)}}{\partial\hat{{\bm{z}}}_{i}}=0$.
Since
$\left(\bm{\tau}^{-1}({\bm{N}}_{{\bm{v}}})\right)^{\mathrm{o}}=\emptyset$ by
Lemma 19, for all $\hat{{\bm{z}}}\in{\bm{N}}_{{\bm{z}}}$ we can choose a
sequence of points $\hat{{\bm{z}}}^{(i)},i=1,2,\cdots$ in
${\bm{O}}_{{\bm{z}}}$ such that $\hat{{\bm{z}}}^{(i)}\to\hat{{\bm{z}}}$. Since
$\bm{\tau}$ is a diffeomorphism, its derivatives are continuous and we can
deduce that
$\frac{\partial\hat{{\bm{v}}}_{\overline{\mathrm{pa}}_{\hat{\mathcal{G}}}(j)}}{\partial\hat{{\bm{z}}}_{i}}=\lim_{\ell\to+\infty}\frac{\partial\hat{{\bm{v}}}_{\overline{\mathrm{pa}}_{\hat{\mathcal{G}}}(j)}^{(\ell)}}{\partial\hat{{\bm{z}}}_{i}^{(\ell)}}=0$.
As a result,
$\frac{\partial\hat{{\bm{v}}}_{\overline{\mathrm{pa}}_{\hat{\mathcal{G}}}(j)}}{\partial\hat{{\bm{z}}}_{i}}=0$
actually holds for all ${\bm{z}}\in{\bm{O}}_{{\bm{z}}}$. Hence, there exists a
continuous differentiable function $\Upsilon_{j}$ such that
${\bm{v}}_{\overline{\mathrm{pa}}_{\hat{\mathcal{G}}}(j)}=\Upsilon_{j}\left({\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(j)}\right)$.

By our assumption, $\mathrm{pa}_{\mathcal{G}}(j)\subseteq[j-1]$. Suppose that
$\mathrm{pa}_{\hat{\mathcal{G}}}(j)\nsubseteq\left\\{i:i<j\right\\}$, let
$\ell\in\mathrm{pa}_{\hat{\mathcal{G}}}(j)\setminus\left\\{i:i<j\right\\}$,
then by induction hypothesis,
$\hat{{\bm{v}}}_{t}=\bm{\tau}_{t}(\hat{{\bm{z}}}),\hat{{\bm{z}}}\in{\bm{O}}_{{\bm{z}}}$,
$t=1,2,\cdots,j,\ell$ are all functions of
$\hat{{\bm{z}}}_{1},\cdots,\hat{{\bm{z}}}_{j}$. Since $\bm{\tau}$ is a
diffeomorphism and ${\bm{O}}_{{\bm{z}}}$ is the support of the distributions
$p_{E},E\in\mathfrak{E}$, we can deduce that the support of the latent
variables $\left({\bm{v}}_{t}:t=1,2,\cdots,j,\ell\right)$ lie on a submanifold
with dimension $\leqslant j$, which is impossible since ${\bm{v}}$ is
supported on the open set ${\bm{O}}_{{\bm{v}}}\subseteq\mathbb{R}^{d}$ by
assumption (i).

Hence, we must have
$\mathrm{pa}_{\hat{\mathcal{G}}}(j)\subseteq\left\\{i:i<j\right\\}$.
Furthermore, if there exists $i\in\mathrm{pa}_{\hat{\mathcal{G}}}(j)$ such
that $i\notin\mathrm{pa}_{\mathcal{G}}(j)$ , then the induction hypothesis
implies that $\frac{\partial{\bm{v}}_{i}}{\partial{\bm{z}}_{i}}\not\equiv 0$,
but ${\bm{v}}_{i}$ is a function of
${\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(j)}$ as previously derived,
which is also a contradiction. Thus we actually have
$\mathrm{pa}_{\hat{\mathcal{G}}}(j)\subseteq\mathrm{pa}_{\mathcal{G}}(j)$.

In a completely symmetric manner, we can take the derivatives of 26 w.r.t.
${\bm{v}}_{i},\forall i\in\overline{\mathrm{pa}}_{\hat{\mathcal{G}}}(j)$ and
obtain that
$\mathrm{pa}_{\mathcal{G}}(j)\subseteq\mathrm{pa}_{\hat{\mathcal{G}}}(j)$.
Hence, $\mathrm{pa}_{\hat{\mathcal{G}}}(j)=\mathrm{pa}_{\mathcal{G}}(j)$,
completing the proof of (1) and (3) for the $j$ case.

Finally, if $\frac{\partial{\bm{v}}_{j}}{\partial{\bm{z}}_{j}}\equiv 0$, then
by (3) and the induction hypothesis, ${\bm{v}}_{1},\cdots,{\bm{v}}_{j}$ are
all functions of ${\bm{z}}_{[j-1]}$, which implies that
$\left({\bm{v}}_{1},\cdots,{\bm{v}}_{j}\right)$ lies on a submanifold with
dimension $\leqslant j-1$, again contradicting assumption (i). Thus
$\frac{\partial{\bm{v}}_{j}}{\partial{\bm{z}}_{j}}\not\equiv 0$. This
completes the proof of our inductive step.

To recap, we now know that

  * •

$\mathcal{G}=\hat{\mathcal{G}}$, and

  * •

For $\forall i\in[d]$, there exists a function $\Upsilon_{i}$ such that
${\bm{v}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}=\Upsilon_{i}\left({\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}\right)$.

It remains to show that for $\forall
k\in\mathrm{pa}_{\mathcal{G}}(i)\setminus\mathrm{dom}_{\mathcal{G}}(i)$,
$\Upsilon_{i}$ doesn’t depend on ${\bm{z}}_{k}$.

By definition, if
$k\in\mathrm{pa}_{\mathcal{G}}(i)\setminus\mathrm{dom}_{\mathcal{G}}(i)$, we
know that there exists $j\in\mathrm{ch}_{\mathcal{G}}(i)$ such that
$j\notin\mathrm{ch}_{\mathcal{G}}(k)$. We have shown that ${\bm{v}}_{i}$, as a
component of ${\bm{v}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(j)}$, is a
function of ${\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(j)}$. By the
choice of $k$, we have $k\notin\overline{\mathrm{pa}}_{\mathcal{G}}(j)$, so
that ${\bm{v}}_{i}$ does not depend on ${\bm{z}}_{k}$. The conclusion follows.

##  Appendix G Omitted Proofs from Section 8

In this section we provide detailed proofs of main results in Section 8. We
first recall Definition 7 below:

######  Definition 14.

We say that a matrix ${\bm{M}}\in\mathbb{R}^{d\times d}$ is effect-respecting
for a causal graph $\mathcal{G}$, or
${\bm{M}}\in\mathcal{M}_{\mathrm{dom}}(\mathcal{G})$, if ${\bm{M}}_{ij}\neq
0\Leftrightarrow j\in\overline{\mathrm{dom}}_{\mathcal{G}}(i)$. We also write
${\bm{M}}\in\mathcal{M}_{\mathrm{dom}}^{0}(\mathcal{G})$ if ${\bm{M}}$ is
invertible and ${\bm{M}}_{ij}\neq 0\Rightarrow
j\in\overline{\mathrm{dom}}_{\mathcal{G}}(i)$. Finally, we write
${\bm{M}}\in\overline{\mathcal{M}}_{\mathrm{dom}}(\mathcal{G})$ if
${\bm{M}}_{ij}\neq 0\Rightarrow j\in\overline{\mathrm{dom}}_{\mathcal{G}}(i)$.

######  Remark 3.

By definition $\mathcal{M}_{\mathrm{dom}}^{0}(\mathcal{G})$ is the set of all
matrices ${\bm{M}}$ where ${\bm{M}}_{ij}\neq 0,\forall
j\notin\overline{\mathrm{dom}}_{\mathcal{G}}(i)$, so it can be identified as
$\mathbb{R}^{d+d_{\mathcal{G}}}$ where
$d_{\mathcal{G}}=\sum_{i=1}^{d}\left|\mathrm{dom}_{\mathcal{G}}(i)\right|$.
Equipped with the Lebesgue measure, we have
$\mathcal{M}_{\mathrm{dom}}(\mathcal{G})\subset\mathcal{M}_{\mathrm{dom}}^{0}(\mathcal{G})\subset\overline{\mathcal{M}}_{\mathrm{dom}}(\mathcal{G})$
and
$\overline{\mathcal{M}}_{\mathrm{dom}}(\mathcal{G})\setminus\mathcal{M}_{\mathrm{dom}}(\mathcal{G})$
is a null set. In the remaining part of this section, we will use measure-
theoretic statement for ${\bm{M}}\in\mathcal{M}_{\mathrm{dom}}(\mathcal{G})$
in the above sense.

###  G.1 Proof of Proposition 3

We first prove the following lemma:

######  Lemma 20.

Let ${\bm{M}}\in\mathcal{M}_{\mathrm{dom}}^{0}(\mathcal{G})$ and latent
variables ${\bm{v}}={\bm{M}}{\bm{z}}$, then for $\forall i\in[d]$, there
exists invertible matrices ${\bm{M}}_{i}$ and ${\bm{M}}_{i}^{-}$ such that
${\bm{v}}_{\mathrm{pa}_{\mathcal{G}}(i)}={\bm{M}}_{i}^{-}{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)}$
and
${\bm{v}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}={\bm{M}}_{i}{\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}$.

###### Proof.

$\forall j\in\overline{\mathrm{pa}}_{\mathcal{G}}(i)$, we know that
${\bm{v}}_{j}$ is a linear function of
${\bm{z}}_{\ell},\ell\in\overline{\mathrm{dom}}_{\mathcal{G}}(j)$. By Lemma 8,
we know that
$\overline{\mathrm{dom}}_{\mathcal{G}}(j)\subseteq\overline{\mathrm{pa}}_{\mathcal{G}}(i)$,
so each ${\bm{v}}_{j},j\in\overline{\mathrm{pa}}_{\mathcal{G}}(i)$ is a linear
function of ${\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}$. Thus we can
write
${\bm{v}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}={\bm{M}}_{i}{\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}$.
In the following we argue that ${\bm{M}}_{i}$ is invertible. Let $\pi$ be a
permutation on $\overline{\mathrm{pa}}_{\mathcal{G}}(i)$ such that
$k\in\mathrm{pa}_{\mathcal{G}}(\ell)\Rightarrow\pi(k)<\pi(\ell)$ (such $\pi$
can always be chosen since $\mathcal{G}$ is acyclic), then we can write

$\left(\hat{{\bm{v}}}_{\pi(j)}:j\in\overline{\mathrm{pa}}_{\mathcal{G}}(i)\right)^{\top}=\tilde{{\bm{M}}}_{i}\left(\hat{{\bm{z}}}_{\pi(j)}:j\in\overline{\mathrm{pa}}_{\mathcal{G}}(i)\right)^{\top}$
(27)

where $\tilde{{\bm{M}}}_{i}$ is an upper triangular matrix with non-zero
diagonal entries by our choice of ${\bm{M}}$. Since ${\bm{M}}_{i}$ can be
obtained from $\tilde{{\bm{M}}}_{i}$ be exchanging a few rows and columns,
${\bm{M}}_{i}$ is invertible as well.

Similarly, using the fact that $\forall j\in\mathrm{pa}_{\mathcal{G}}(i)$,
$\overline{\mathrm{dom}}_{\mathcal{G}}(j)\subseteq\mathrm{pa}_{\mathcal{G}}(i)$,
we can prove the existence of an invertible matrix ${\bm{M}}_{i}^{-}$ such
that
${\bm{v}}_{\mathrm{pa}_{\mathcal{G}}(i)}={\bm{M}}_{i}^{-}{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)}$.
∎

Returning to the proof of Proposition 3. Assume WLOG that the nodes of
$\mathcal{G}$ are ordered in a way such that
$i\in\mathrm{pa}_{\mathcal{G}}(j)\Rightarrow i<j$, so that ${\bm{M}}$ is a
lower-triangular matrix. The joint density of ${\bm{v}}$ can be written as

$q({\bm{v}})=\prod_{i=1}^{d}q\left({\bm{v}}_{i}\mid{\bm{v}}_{1},\cdots,{\bm{v}}_{i-1}\right).$

Since ${\bm{v}}={\bm{M}}z$ and ${\bm{M}}$ is lower triangular and invertible
(hence, with non-zero diagonals), we know that
$({\bm{v}}_{1},{\bm{v}}_{2},\cdots,{\bm{v}}_{i-1})$ is an invertible linear
function of $({\bm{z}}_{1},{\bm{z}}_{2},\cdots,{\bm{z}}_{i-1})$ and
$({\bm{v}}_{1},{\bm{v}}_{2},\cdots,{\bm{v}}_{i})$ is an invertible linear
function of $({\bm{z}}_{1},{\bm{z}}_{2},\cdots,{\bm{z}}_{i})$. Let
$\hat{{\bm{v}}}={\bm{M}}\hat{{\bm{z}}}\in\mathbb{R}^{d}$, then we have

$\displaystyle
q\left(\hat{{\bm{v}}}_{i}\mid\hat{{\bm{v}}}_{1},\cdots,\hat{{\bm{v}}}_{i-1}\right)$
$\displaystyle=\frac{q(\hat{{\bm{v}}}_{1},\hat{{\bm{v}}}_{2},\cdots,\hat{{\bm{v}}}_{i})}{q(\hat{{\bm{v}}}_{1},\hat{{\bm{v}}}_{2},\cdots,\hat{{\bm{v}}}_{i-1})}=\frac{p(\hat{{\bm{z}}}_{1},\hat{{\bm{z}}}_{2},\cdots,\hat{{\bm{z}}}_{i})\det\hat{{\bm{M}}}_{1:i,1:i}}{p(\hat{{\bm{z}}}_{1},\hat{{\bm{z}}}_{2},\cdots,\hat{{\bm{z}}}_{i-1})\det\hat{{\bm{M}}}_{1:i-1,1:i-1}}$
$\displaystyle\propto\frac{p(\hat{{\bm{z}}}_{1},\hat{{\bm{z}}}_{2},\cdots,\hat{{\bm{z}}}_{i})}{p(\hat{{\bm{z}}}_{1},\hat{{\bm{z}}}_{2},\cdots,\hat{{\bm{z}}}_{i-1})}=p\left(\hat{{\bm{z}}}_{i}\mid\hat{{\bm{z}}}_{1},\cdots,\hat{{\bm{z}}}_{i-1}\right)=p_{i}\left(\hat{{\bm{z}}}_{i}\mid\hat{{\bm{z}}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right),$

where $\hat{{\bm{M}}}_{1:i,i:i}$ denotes that top-left submatrix of
$\hat{{\bm{M}}}$ of size $i\times i$, and the last step follows from the
causal Markov condition (Definition 1). On the other hand, let
$q_{i}\left(\hat{{\bm{v}}}_{i}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)$
be the conditional density of ${\bm{v}}_{i}$ on its parents at
$\hat{{\bm{v}}}\in\mathbb{R}^{d}$. For $\forall
j\in\mathrm{pa}_{\mathcal{G}}(i)$, from ${\bm{v}}={\bm{M}}{\bm{z}}$ we know
that ${\bm{v}}_{j}$ is a linear function of
${\bm{z}}_{\overline{\mathrm{dom}}_{\mathcal{G}}(j)}$. By Lemma 20 we know
that $\hat{{\bm{v}}}_{\mathrm{pa}_{\mathcal{G}}(i)}$ is a linear function of
$\hat{{\bm{z}}}_{\mathrm{pa}_{\mathcal{G}}(i)}$ and
$\hat{{\bm{v}}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}$ is a linear
function of $\hat{{\bm{z}}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}$, so
that

$q\left(\hat{{\bm{v}}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)\propto
p\left(\hat{{\bm{z}}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)\quad\text{and}\quad
q\left(\hat{{\bm{v}}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}\right)\propto
p\left(\hat{{\bm{z}}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}\right)$

and

$q_{i}\left(\hat{{\bm{v}}}_{i}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)\propto\frac{p\left(\hat{{\bm{z}}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}\right)}{p\left(\hat{{\bm{z}}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)}=p_{i}\left(\hat{{\bm{z}}}_{i}\mid\hat{{\bm{z}}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right).$

Hence, we have
$q_{i}\left(\hat{{\bm{v}}}_{i}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)\propto
q\left(\hat{{\bm{v}}}_{i}\mid\hat{{\bm{v}}}_{1},\cdots,\hat{{\bm{v}}}_{i-1}\right)$,
so that

$q(\hat{{\bm{v}}})=\prod_{i=1}^{d}q_{i}\left(\hat{{\bm{v}}}_{i}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)\propto\prod_{i=1}^{d}q_{i}\left(\hat{{\bm{v}}}_{i}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right).$

Since both sides integrate to $1$, it turns out that they are equal, as
desired.

###  G.2 Proof of Theorem 5

We define

${\bm{v}}={\bm{M}}{\bm{z}}$ (28)

where ${\bm{M}}$ is an effect-respecting matrix. At this point we do not make
any other restrictions on ${\bm{M}}$, but we will specify the appropriate
choise of ${\bm{M}}$ later.

By assumption, the latent variables in the $k$-th environment are generated by

${\bm{z}}={\bm{A}}_{k}{\bm{z}}+\bm{\Omega}_{k}^{\frac{1}{2}}\epsilon,$

then
${\bm{v}}={\bm{M}}({\bm{I}}-{\bm{A}}_{k})^{-1}\bm{\Omega}_{k}^{\frac{1}{2}}\epsilon$.
Let $\hat{\bm{\Omega}}_{k}$ be the diagonal matrix with entries
${\bm{M}}_{ii}^{2}\cdot(\bm{\Omega}_{k})_{ii},i\in[d]$ and
$\hat{{\bm{A}}}_{k}={\bm{I}}-\hat{\bm{\Omega}}_{k}^{\frac{1}{2}}\bm{\Omega}_{k}^{-\frac{1}{2}}({\bm{I}}-{\bm{A}}_{k}){\bm{M}}^{-1}$,
then
${\bm{v}}=\hat{{\bm{A}}}_{k}{\bm{v}}+\hat{\bm{\Omega}}_{k}^{\frac{1}{2}}\epsilon$.
Note that the choice of $\hat{\bm{\Omega}}_{k}$ here is to that the diagonal
entries of $\hat{{\bm{A}}}_{k}$ are zero, as we show below. It remains to show
that: for almost all ${\bm{M}}\in\mathcal{M}_{\mathrm{dom}}^{0}(\mathcal{G})$,
it holds for $\forall k\in[K]$ that
$(\hat{{\bm{A}}}_{k})_{ij}=0\Leftrightarrow
j\notin\mathrm{pa}_{\mathcal{G}}(i)$.

For the $\Leftarrow$ direction, since
${\bm{M}}\in\mathcal{M}_{\mathrm{dom}}^{0}(\mathcal{G})$,
${\bm{M}}^{-1}\in\mathcal{M}_{\mathrm{dom}}^{0}(\mathcal{G})$ as well. Thus,
$\forall j\notin\mathrm{pa}_{\mathcal{G}}(i)$ we have

$\displaystyle\left[({\bm{I}}-{\bm{A}}_{k}){\bm{M}}^{-1}\right]_{ij}$
$\displaystyle=\sum_{\ell=1}^{d}({\bm{I}}-{\bm{A}}_{k})_{i\ell}\cdot({\bm{M}}^{-1})_{\ell
j}=\sum_{\ell\in\overline{\mathrm{pa}}_{\mathcal{G}}(i)\cap\\{\ell^{\prime}:j\in\overline{\mathrm{dom}}_{\mathcal{G}}(\ell^{\prime})\\}}({\bm{I}}-{\bm{A}}_{k})_{i\ell}\cdot({\bm{M}}^{-1})_{\ell
j}$ $\displaystyle=\left\\{\begin{aligned} 0&\quad\text{if
}j\notin\overline{\mathrm{pa}}_{\mathcal{G}}(i)\\\
({\bm{M}}^{-1})_{ii}&\quad\text{if }j=i\end{aligned}\right.$

where the last step holds because $\forall\ell\in[d]$,
$\ell\in\overline{\mathrm{pa}}_{\mathcal{G}}(i),j\in\overline{\mathrm{dom}}_{\mathcal{G}}(\ell)\Rightarrow
j\in\overline{\mathrm{pa}}_{i}$, and when $j=i$, the only such $\ell$ is
$\ell=i$. Hence, we can see that our choice of $\hat{{\bm{A}}}_{k}$ satisfies

$\left(\hat{{\bm{A}}}_{k}\right)_{ij}=\left\\{\begin{aligned}
0-0=0&\quad\text{if }j\notin\overline{\mathrm{pa}}_{\mathcal{G}}(i)\\\
1-\hat{\omega}_{k,i,i}^{\frac{1}{2}}\omega_{k,i,i}^{-\frac{1}{2}}({\bm{M}}^{-1})_{ii}=0&\quad\text{if
}j=i,\end{aligned}\right.$

so $\left(\hat{{\bm{A}}}_{k}\right)_{ij}\neq 0\Rightarrow
j\in\mathrm{pa}_{\mathcal{G}}(i)$.

Conversely, for $\forall j\in\mathrm{pa}_{\mathcal{G}}(i)$,

$(\hat{{\bm{A}}}_{k})_{ij}=0\Leftrightarrow\sum_{s\in\overline{\mathrm{pa}}_{\mathcal{G}}(i)}({\bm{I}}-{\bm{A}}_{k})_{is}({\bm{M}}^{-1})_{sj}=0\Leftrightarrow\sum_{s\in\overline{\mathrm{pa}}_{\mathcal{G}}(i)}(-1)^{s}({\bm{I}}-{\bm{A}}_{k})_{is}\det{\bm{M}}_{sj}^{-}=0$
(29)

where ${\bm{M}}_{sj}^{-}$ is the $(d-1)\times(d-1)$ matrix obtained by
removing the $s$-th row and $j$-th column of ${\bm{M}}$, and the second step
in the equation above follows from the fact that
${\bm{M}}^{-1}=\det({\bm{M}})^{-1}\mathrm{adj}({\bm{M}})$, where
$\mathrm{adj}({\bm{M}})$ denotes the adjugate matrix of ${\bm{M}}$ whose
$(i,j)$-th entry is $(-1)^{i+j}\det{\bm{M}}_{ij}^{-}$.

29 holds if only if ${\bm{M}}$ takes values on a lower-dimensional algebraic
manifold of its embedded space $\mathbb{R}^{d+d_{\mathcal{G}}}$ (see Remark
3). As a result, for almost every
${\bm{M}}\in\mathcal{M}_{\mathrm{dom}}^{0}(\mathcal{G})$, ${\bm{v}}$ is
generated from a linear causal model with graph $\mathcal{G}$ as defined in 4.
Moreover, let $\hat{{\bm{B}}}_{k}={\bm{B}}_{k}{\bm{M}}^{-1},k\in[K]$ , so that
$\epsilon=\hat{{\bm{B}}}_{k}{\bm{v}}$ in the $k$-th environment. Then for all
nodes $i\in[d]$ and $S\subseteq\mathrm{pa}(i)\cup\\{i\\}$, we have

$\displaystyle\dim\mathrm{span}\left\langle\left(\hat{{\bm{B}}_{k}}^{\top}{\bm{e}}_{i}\right)_{S}:k\in[K]\right\rangle=~{}$
$\displaystyle\dim\mathrm{span}\left\langle{\bm{M}}^{-\top}\left(\left({\bm{B}}_{k}^{\top}{\bm{e}}_{i}\right)_{S}:k\in[K]\right)\right\rangle$
$\displaystyle=~{}$
$\displaystyle\dim\mathrm{span}\left\langle\left({\bm{B}}_{k}^{\top}{\bm{e}}_{i}\right)_{S}:k\in[K]\right\rangle=\left|\mathrm{pa}_{\mathcal{G}}(i)\right|+1,$

implying that $\hat{{\bm{B}}}_{k},k\in[K]$ satisfy Assumption 5.

Now we have shown that for almost every
${\bm{M}}\in\mathcal{M}_{\mathrm{dom}}^{0}(\mathcal{G})$, we can construct a
hypothetical data generating process with latent variables
${\bm{v}}={\bm{M}}{\bm{z}}$ that satisfies all requirements in Theorem 5.
Choose an arbitrary ${\bm{M}}$ that is in
$\mathcal{M}_{\mathrm{dom}}(\mathcal{G})$, then we have that

$\frac{\partial{\bm{v}}_{i}}{\partial{\bm{z}}_{j}}\neq 0,\quad
j\notin\overline{\mathrm{dom}}_{\mathcal{G}}(i).$

Finally, if we additionally assume single-node interventions, $\forall
k,\ell\in\mathfrak{E}_{i}$, we have that
$({\bm{B}}_{k})_{j}\neq({\bm{B}}_{\ell})_{j}\Leftrightarrow j=i$. For any
${\bm{M}}\in\mathcal{M}_{\mathrm{dom}}^{0}(\mathcal{G})$ (and specifically the
${\bm{M}}$ that we have already chosen above), we have
$(\hat{{\bm{B}}}_{k})_{j}=({\bm{B}}_{k})_{j}{\bm{M}}^{-1}$ and
$(\hat{{\bm{B}}}_{\ell})_{j}=({\bm{B}}_{\ell})_{j}{\bm{M}}^{-1},\forall
j\in[d]$. Thus,
$(\hat{{\bm{B}}}_{k})_{j}\neq(\hat{{\bm{B}}}_{\ell})_{j}\Leftrightarrow j=i$
as well, implying that $\mathfrak{E}_{i}$ is also a group of single-node
interventions on ${\bm{v}}$, concluding the proof.

###  G.3 Proof of Theorem 6

We state and prove a stronger version of Theorem 6:

######  Theorem 8.

For any causal model $({\bm{h}},\mathcal{G})$ and any set of environments
$\mathfrak{E}$, suppose that we have observations
$\left\\{P_{{\bm{X}}}^{E}\right\\}_{E\in\mathfrak{E}}$ satisfying Assumption
1:

$\forall E\in\mathfrak{E},\quad{\bm{z}}\sim
p_{E}(z)=\prod_{i=1}^{d}p_{i}^{E}\left(z_{i}\mid
z_{\mathrm{pa}_{\mathcal{G}}(i)}\right),\quad{\bm{x}}={\bm{h}}^{-1}({\bm{z}})$

such that

  1. (i)

all densities $p_{i}^{E}$ are continuously differentiable and the joint
density $p_{E}$ is positive everywhere;

  2. (ii)

the environments are groups of single-node interventions: there exists a
partition $\mathfrak{E}=\cup_{i=1}^{d}\mathfrak{E}_{i}$ such that
$\mathcal{I}_{{\bm{z}}}^{\mathfrak{E}_{i}}=\\{i\\}$;

  3. (iii)

the intervention distributions on each node are non-degenerate: $\forall
i\in[d]$, the set of distributions
$\left\\{p_{i}^{E}:E\in\mathfrak{E}_{i}\right\\}$ satisfy Definition 6,

then there must exist a candidate solution $(\hat{{\bm{h}}},\mathcal{G})$ and
a hypothetical data generating process

$\forall E\in\mathfrak{E},\quad{\bm{v}}\sim
q_{E}(v)=\prod_{i=1}^{d}q_{i}^{E}\left(v_{i}\mid
v_{\mathrm{pa}_{\mathcal{G}}(i)}\right),\quad{\bm{x}}=\hat{{\bm{h}}}^{-1}({\bm{v}})$

such that

  1. (i′)

all densities $q_{i}^{E}$ are continuously differentiable and the joint
density $q_{E}$ is positive everywhere;

  2. (ii′)

for the same partition $\mathfrak{E}=\cup_{i=1}^{d}\mathfrak{E}_{i}$, we have
$\mathcal{I}_{{\bm{v}}}^{\mathfrak{E}_{i}}=\\{i\\}$;

  3. (iii′)

$\forall i\in[d]$, the set of distributions
$\left\\{q_{i}^{E}:E\in\mathfrak{E}_{i}\right\\}$ satisfy Definition 6,

but

$\frac{\partial{\bm{v}}_{i}}{\partial{\bm{z}}_{j}}\neq 0,\quad\forall
j\in\overline{\mathrm{dom}}_{\mathcal{G}}(i).$

Finally, if we additionally assume minimality (Assumption 7) and/or
faithfulness (Assumption 8) of all $p_{E}$’s, we can guarantee the existence
of $(\hat{{\bm{h}}},\mathcal{G})$ and $q_{E}$’s satisfying minimality and/or
faithfulness in addition to the properties listed above. In other words,
assuming minimality and/or faithfulness does not resolve the ambiguity.

###### Proof.

We define

${\bm{v}}={\bm{M}}{\bm{z}}$ (30)

where ${\bm{M}}$ is an effect-respecting matrix. At this point we do not make
any other restrictions on ${\bm{M}}$, and we will choose appropriate
${\bm{M}}$ later. By Lemma 20, there exists invertible matrices ${\bm{M}}_{i}$
and ${\bm{M}}_{i}^{-}$ such that
${\bm{v}}_{\mathrm{pa}_{\mathcal{G}}(i)}={\bm{M}}_{i}^{-}{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)}$
and
${\bm{v}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}={\bm{M}}_{i}{\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}$,
so for all environment $E\in\mathfrak{E}$ we have

$q_{i}^{E}({\bm{v}}_{\mathrm{pa}_{\mathcal{G}}(i)})=p_{i}^{E}({\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)})\cdot\left|\det({\bm{M}}_{i}^{-})^{-1}\right|,\quad
q_{i}^{E}({\bm{v}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)})=p_{i}^{E}({\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)})\cdot\left|\det({\bm{M}}_{i})^{-1}\right|$

so that

$q_{i}^{E}\left({\bm{v}}_{i}\mid{\bm{v}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)=p_{i}^{E}\left({\bm{z}}_{i}\mid{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)\frac{\left|\det{\bm{M}}_{i}^{-1}\right|}{\left|\det({\bm{M}}_{i}^{-})^{-1}\right|},\quad\forall
i\in[d].$ (31)

In the following, assuming that $\left(p_{i}^{E}:E\in\mathfrak{E}\right)$
satisfies any of the listed assumptions, we show that
$\left(q_{i}^{E}:E\in\mathfrak{E}\right)$ satisfies the same assumption as
well.

Firstly, 31 immediately implies that the density of ${\bm{v}}$ is continuous
differentiable and positive everywhere. Secondly, $\forall
k,\ell\in\mathfrak{E}_{i}$, we have that

$p_{j}^{E_{k}}\left({\bm{z}}_{j}\mid{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(j)}\right)=p_{j}^{E_{\ell}}\left({\bm{z}}_{j}\mid{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(j)}\right)\Leftrightarrow
j=i.$

By 31 it is easy to see that

$q_{j}^{E_{k}}\left({\bm{v}}_{j}\mid{\bm{v}}_{\mathrm{pa}_{\mathcal{G}}(j)}\right)=q_{j}^{E_{\ell}}\left({\bm{v}}_{j}\mid{\bm{v}}_{\mathrm{pa}_{\mathcal{G}}(j)}\right)\Leftrightarrow
j=i$

as well, _i.e.,_ $q^{k},k\in\mathfrak{E}_{i}$ are single-node interventions on
${\bm{v}}_{i}$ according to Definition 3.

Thirdly, we verify the non-degeneracy condition for $q_{i}^{E}$’s. Indeed we
have for $\forall k\geqslant 2$ that

$\displaystyle\nabla_{{\bm{v}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}}\frac{q_{i}^{E_{1}}}{q_{i}^{E_{k}}}\left({\bm{v}}_{i}\mid{\bm{v}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)$
$\displaystyle=\frac{\partial{\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}}{\partial{\bm{v}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}}\nabla_{{\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}}\frac{q_{i}^{E_{1}}}{q_{i}^{E_{k}}}\left({\bm{z}}_{i}\mid{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right)={\bm{M}}_{i}^{-1}\nabla_{{\bm{z}}_{\overline{\mathrm{pa}}_{\mathcal{G}}(i)}}\frac{q_{i}^{E_{1}}}{q_{i}^{E_{k}}}\left({\bm{z}}_{i}\mid{\bm{z}}_{\mathrm{pa}_{\mathcal{G}}(i)}\right).$

Since ${\bm{M}}_{i}$ is invertible, the above equation and the non-degeneracy
of $p^{E_{k}},k\in[K]$ immediately implies that non-degeneracy of
$q^{E_{k}},k\in[K]$.

Thus, for arbitrary ${\bm{M}}\in\mathcal{M}_{\mathrm{dom}}(\mathcal{G})$, we
have constructed a hypothetical data generating process with latent variable
${\bm{v}}={\bm{M}}{\bm{z}}$ that satisfies all given conditions. It remains to
show that such construction is still possible under additional minimality and
faithfulness conditions.

Claim 1. There exists a neighbourhood $O$ of the identity matrix ${\bm{I}}$ in
$\overline{\mathcal{M}}_{\mathrm{dom}}(\mathcal{G})$ (in the sense of Remark
3) such that for $\forall{\bm{M}}\in
O\cap\mathcal{M}_{\mathrm{dom}}^{0}(\mathcal{G})$, $p^{E_{k}},k\in[K]$ satisfy
Assumption 8 $\Rightarrow$ $q^{E_{k}},k\in[K]$ satisfy Assumption 8.

For $\forall i,j$ not $d$-separated by $S\subseteq[d]$, for all $k\in[K]$
there exists $\hat{{\bm{z}}}\in\mathbb{R}^{d}$ such that
$\Delta_{k}^{(i,j,S)}=p^{E_{k}}\left(\hat{{\bm{z}}}_{i},\hat{{\bm{z}}}_{j}\mid\hat{{\bm{z}}}_{S}\right)-p^{E_{k}}\left(\hat{{\bm{z}}}_{i}\mid\hat{{\bm{z}}}_{S}\right)p^{E_{k}}\left(\hat{{\bm{z}}}_{j}\mid\hat{{\bm{z}}}_{S}\right)\neq
0$. By continuous differentiability of $p^{E_{k}}$, we know that there exists
$\delta_{k}^{(i,j,S)}>0$ such that for all
${\bm{M}}\in\overline{\mathcal{M}}_{\mathrm{dom}}(\mathcal{G})$ such that
$\left\|{\bm{M}}-{\bm{I}}\right\|_{F}\leqslant\delta_{k}^{(i,j,S)}$, the
density of the variable ${\bm{v}}={\bm{M}}{\bm{z}}$ satisfies
$q^{E_{k}}\left(\hat{{\bm{v}}}_{i},\hat{{\bm{v}}}_{j}\mid\hat{{\bm{v}}}_{S}\right)\neq
q^{E_{k}}\left(\hat{{\bm{v}}}_{i}\mid\hat{{\bm{v}}}_{S}\right)q^{k}\left(\hat{{\bm{v}}}_{j}\mid\hat{{\bm{v}}}_{S}\right)$
for $\hat{{\bm{v}}}={\bm{M}}\hat{{\bm{z}}}$, which implies that ${\bm{v}}_{i}$
and ${\bm{v}}_{j}$ are dependent given ${\bm{v}}_{S}$. Now choose
$\delta=\min_{k,i,j,S}\delta_{k}^{(i,j,S)}>0$, then for all
${\bm{M}}\in\overline{\mathcal{M}}_{\mathrm{dom}}(\mathcal{G})$ such that
$\left\|{\bm{M}}-{\bm{I}}\right\|_{F}\leqslant\delta$, the resulting
distributions $q^{E_{k}},k\in[K]$ satisfy assumption Assumption 7.

Claim 2. There exists a neighbourhood $O$ of ${\bm{I}}$ in
$\overline{\mathcal{M}}_{\mathrm{dom}}(\mathcal{G})$ (in the sense of Remark
3) such that for almost all ${\bm{M}}\in
O\cap\mathcal{M}_{\mathrm{dom}}^{0}(\mathcal{G})$, $p^{E_{k}},k\in[K]$
satisfies Assumption 7 $\Rightarrow$ $p^{E_{k}},k\in[K]$ satisfies Assumption
7.

The proof is similar to the previous statement. Since Assumption 7 causal
minimality is satisfied for ${\bm{z}}$, for $\forall k\in[K],i\in[d]$, let
$\mathcal{G}_{ij}$ be the resulting graph obtained by removing the edge $j\to
i$ from $\mathcal{G}$, then there must exists some $\alpha_{ijk}\in[d]$ such
that ${\bm{z}}_{\alpha_{ijk}}\not\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}{\bm{z}}_{\mathrm{nd}_{\mathcal{G}_{ij}}(\alpha_{ijk})}\mid{\bm{z}}_{\mathrm{pa}_{\mathcal{G}_{ij}}(\alpha_{ijk})}$.
Hence, there exists $\hat{{\bm{z}}}^{ijk}\in\mathbb{R}^{d}$ such that

$p^{E_{k}}\left(\hat{{\bm{z}}}_{\alpha_{ijk}}^{ijk}\mid\hat{{\bm{z}}}_{\mathrm{pa}_{\mathcal{G}_{ij}}(\alpha_{ijk})}^{ijk}\right)p^{E_{k}}\left(\hat{{\bm{z}}}_{\mathrm{nd}_{\mathcal{G}_{ij}}(\alpha_{ijk})}^{ijk}\mid\hat{{\bm{z}}}_{\mathrm{pa}_{\mathcal{G}_{ij}}(\alpha_{ijk})}^{ijk}\right)\neq
p^{E_{k}}\left(\hat{{\bm{z}}}_{\overline{\mathrm{nd}}_{\mathcal{G}_{ij}}(\alpha_{ijk})}^{ijk}\mid\hat{{\bm{z}}}_{\mathrm{pa}_{\mathcal{G}_{ij}}(\alpha_{ijk})}^{ijk}\right).$

By continuous differentiability of $p^{E_{k}}$, there exists
$\delta_{k}^{(i,j)}>0$ such that for all
${\bm{M}}\in\bar{\mathcal{M}}_{\mathrm{dom}}(\mathcal{G})$ such that
$\left\|{\bm{M}}-{\bm{I}}\right\|_{F}\leqslant\delta_{k}^{(i,j)}$, the density
$q_{ij}^{E_{k}}$ of the variable
$\hat{{\bm{v}}}^{ijk}={\bm{M}}\hat{{\bm{z}}}^{ijk}$ satisfies

$q^{E_{k}}\left(\hat{{\bm{v}}}_{\alpha_{ijk}}^{ijk}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\mathcal{G}_{ij}}(\alpha_{ijk})}^{ijk}\right)q^{E_{k}}\left(\hat{{\bm{v}}}_{\mathrm{nd}_{\mathcal{G}_{ij}}(\alpha_{ijk})}^{ijk}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\mathcal{G}_{ij}}(\alpha_{ijk})}^{ijk}\right)\neq
q^{E_{k}}\left(\hat{{\bm{v}}}_{\overline{\mathrm{nd}}_{\mathcal{G}_{ij}}(\alpha_{ijk})}^{ijk}\mid\hat{{\bm{v}}}_{\mathrm{pa}_{\mathcal{G}_{ij}}(\alpha_{ijk})}^{ijk}\right).$

for $\hat{{\bm{v}}}^{ijk}={\bm{M}}\hat{{\bm{z}}}^{ijk}$. This implies that
removing the edge $j\to i$ in $\mathcal{G}$ would break the causal Markov
condition for $q^{E_{k}}$. Now let $\delta=\min_{k,i,j}\delta_{k}^{(i,j)}>0$,
then for all ${\bm{M}}\in\bar{\mathcal{M}}_{\mathrm{dom}}(\mathcal{G})$ such
that $\left\|{\bm{M}}-{\bm{I}}\right\|_{F}\leqslant\delta$, the resulting
distributions $q^{E_{k}},k\in[K]$ satisfy assumption Assumption 1.

Combining the above two statements and what we have proven before, it is
straightfoward to see that one can choose some
${\bm{M}}\in\mathcal{M}_{\mathrm{dom}}(\mathcal{G})$ in a small neighbourhood
of ${\bm{I}}$ that satisfies all the requirements, completing the proof. ∎