${\bm{a}}\in{\mathcal{A}}:=\\{\bm{0},{\bm{e}}_{1},{\bm{e}}_{2},{\bm{e}}_{3}\\}$
where ${\bm{e}}_{\ell}$ is the $\ell$th one-hot and we interpret $\bm{0}$ to
correspond to the observational setting and ${\bm{e}}_{\ell}$ to correspond to
the $\ell$th intervention. Recall that in this interpretation, ${\bm{G}}^{a}$
describes which latent variable is targeted by each intervention. Let
$p({\bm{z}}^{t}\mid{\bm{z}}^{t-1},{\bm{a}})={\mathcal{N}}({\bm{z}}^{t};{\bm{\mu}}({\bm{z}}^{t-1},{\bm{a}}),\sigma^{2}{\bm{I}})$
where

$\displaystyle{\bm{\mu}}({\bm{z}}^{t-1},{\bm{a}}):={\bm{z}}^{t-1}+(\mathbbm{1}-{\bm{G}}^{a}{\bm{a}})\odot{\bm{g}}({\bm{z}}^{t-1})\,,$

where ${\bm{g}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{z}}$ is some
function respecting the graph ${\bm{G}}^{z}$ (e.g.
${\bm{g}}({\bm{z}})={\bm{W}}{\bm{z}}$ where
${\bm{W}}\in{\mathbb{R}}^{d_{z}\times d_{z}}_{{\bm{G}}^{z}}$). The
observational dynamics is then
${\bm{\mu}}({\bm{z}}^{t},{\bm{a}}=\bm{0})={\bm{z}}^{t-1}+{\bm{g}}({\bm{z}}^{t-1})$
and the interventional settings correspond to zeroing out the elements of
${\bm{g}}({\bm{z}}^{t-1})$ targeted by the intervention. Using Lemma 3, we can
compute

$\displaystyle\
\Delta^{\epsilon=1}_{{\bm{a}},\ell}D_{z}q({\bm{z}}^{t}\mid{\bm{z}}^{t-1},{\bm{a}}=\bm{0})$
$\displaystyle=$ $\displaystyle\
D_{z}q({\bm{z}}^{t}\mid{\bm{z}}^{t-1},{\bm{a}}={\bm{e}}_{\ell})-D_{z}q({\bm{z}}^{t}\mid{\bm{z}}^{t-1},{\bm{a}}=\bm{0})=-\frac{1}{\sigma^{2}}{\bm{G}}^{a}_{\cdot,\ell}\odot{\bm{g}}({\bm{z}}^{t-1})\,.$

One can see that, as soon as the image of ${\bm{g}}$ spans
${\mathbb{R}}^{d_{z}}$, Assumption 7 is satisfied since we can choose values
${\bm{z}}_{(1)},\dots,{\bm{z}}_{(d_{z})}\in{\mathbb{R}}^{d_{z}}$ such that
$\mathrm{span}\\{{\bm{g}}({\bm{z}}_{(1)}),\dots,{\bm{g}}({\bm{z}}_{(d_{z})})\\}={\mathbb{R}}^{d_{z}}$,
which implies
$\mathrm{span}\\{{\bm{G}}^{a}_{\cdot,\ell}\odot{\bm{g}}({\bm{z}}_{(1)}),\dots,{\bm{G}}^{a}_{\cdot,\ell}\odot{\bm{g}}({\bm{z}}_{(d_{z})})\\}={\mathbb{R}}^{d_{z}}_{{\bf
Ch}^{a}_{\ell}}$. An example of transition function ${\bm{g}}$ satisfying this
property is ${\bm{g}}({\bm{z}}):={\bm{W}}{\bm{z}}$ where
${\bm{W}}\in{\mathbb{R}}^{d_{z}\times d_{z}}_{{\bm{G}}^{z}}$ is invertible.

Note that even if the temporal dependencies are not sparse, they are still
helpful for identifiability as they make it more likely to satisfy the
sufficient influence assumption (Assumption 7).

######  Example 12 (Grouped multi-target interventions for disentanglement
without time)

In this example, we assume there are no temporal dependencies ($T=1$) and that
the learner has access to $d_{a}$ groups of interventions where the
interventions belonging to the $\ell$th group are known to target the same
latent variables given by ${\bm{G}}^{a}_{\cdot,\ell}$ (these targets are
unknown). Here is how this setting can be accommodated by our framework: given
we have $d_{a}$ groups of interventions where the $\ell$th group contains
$k_{\ell}$ interventions, we set
${\mathcal{A}}:=\\{\bm{0},1{\bm{e}}_{1},...,k_{1}{\bm{e}}_{1},1{\bm{e}}_{2},...,k_{2}{\bm{e}}_{2},...,k_{d_{a}}{\bm{e}}_{d_{a}}\\}$.
In this setting, ${\bm{a}}=j{\bm{e}}_{\ell}$ corresponds to the $j$th
intervention of the $\ell$th group. Moreover, the sufficient influence
assumption requires that the interventions within a group $\ell$ span
${\mathbb{R}}^{d_{z}}_{{\bf Ch}^{a}_{\ell}}$. More precisely, we need
$\mathrm{span}\\{\Delta^{\epsilon}_{a,\ell}D_{z}\log
p({\bm{z}}\mid{\bm{a}}=0)\\}_{\epsilon=1}^{k_{\ell}}={\mathbb{R}}^{d_{z}}_{{\bf
Ch}^{a}_{\ell}}$.

####  3.8.3 Temporal dependencies (Theorem 3)

Finally, we provide an example (Example 13) where temporal dependencies alone
(no auxiliary variable ${\bm{a}}$) is enough to disentangle. We start with an
important remark about the sufficient influence assumption of Theorem 3.

######  Remark 7 (Auxiliary variables or non-Markovianity are required)

An important observation is that, if the transition model does not have an
auxiliary variable ${\bm{a}}$ and is Markovian, i.e.
$p({\bm{z}}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t})=p({\bm{z}}^{t}\mid{\bm{z}}^{t-1})$,
then Assumption 8 cannot be satisfied (except in trivial circumstances). To
see this, simply note that, in that case,
$H^{t,t-1}_{z,z}q({\bm{z}}^{t}\mid{\bm{z}}^{t-1})$ depends only on
${\bm{z}}^{t-1}$, which is forced to be equal to ${\bm{z}}^{t}$. This means
the span of the Hessian must be at most one-dimensional, which means that the
assumption cannot hold as soon as $||{\bm{G}}^{z}||_{0}>1$. Therefore, when no
auxiliary variable ${\bm{a}}$ is observed, Assumption 8 requires the
transition model to be non-Markovian. In Example 13, we provide a concrete
example of transition model without auxiliary variable ${\bm{a}}$ that
satisfies this assumption. We will also see in Section 4 that if the
transition model $p({\bm{z}}^{t}\mid{\bm{z}}^{t-1})$ is in the exponential
family, this assumption can be relaxed so that non-Markovianity is not
required anymore.

######  Example 13 (Sparse temporal dependencies for disentanglement without
auxiliary variables)

We continue with Examples 5 & 6 which were based on the graphs ${\bm{G}}^{z}$
depicted in Figures 3(d) & 3(e), respectively. Assume that no action is
observed, i.e. we can only leverage the sparsity of ${\bm{G}}^{z}$ to
disentangle. Examples 5 & 6 already showed that these graph structures allow
for complete disentanglement, as long as the sufficient influence of
${\bm{z}}$ assumption (Assumption 8) is satisfied. We now provide concrete
transition models $p({\bm{z}}^{t}\mid{\bm{z}}^{<t})$ that satisfies this
requirement. Similarly to previous examples, assume
$p({\bm{z}}^{t}\mid{\bm{z}}^{<t})={\mathcal{N}}({\bm{z}}^{t}\mid{\bm{\mu}}({\bm{z}}^{t-1},{\bm{z}}^{t-2}),\sigma^{2}{\bm{I}})$
where

$\displaystyle{\bm{\mu}}({\bm{z}}^{t-1},{\bm{z}}^{t-2}):={\bm{z}}^{t-1}+{\bm{W}}({\bm{z}}^{t-2}){\bm{z}}^{t-1}\,,$
(56)

where
${\bm{W}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}_{{\bm{G}}^{z}}^{d_{z}\times
d_{z}}$ is some function of ${\bm{z}}^{t-2}$. Using Lemma 3, we can derive

$\displaystyle
H^{t,t-1}_{z,z}q({\bm{z}}^{t}\mid{\bm{z}}^{<t})=\frac{1}{\sigma^{2}}[{\bm{I}}+{\bm{W}}({\bm{z}}^{t-2})]\,.$
(57)

Thus Assumption 8 holds when there exists
$\\{{\bm{z}}_{(r)}^{t-2}\\}_{r=1}^{||{\bm{G}}^{z}||_{0}}$ such that

$\displaystyle\mathrm{span}\\{{\bm{I}}+{\bm{W}}({\bm{z}}_{(r)}^{t-2})\\}_{r=1}^{||{\bm{G}}^{z}||_{0}}={\mathbb{R}}_{{\bm{G}}^{z}}^{d_{z}\times
d_{z}}\,.$ (58)

One can directly see that, if ${\bm{W}}({\bm{z}}^{t-2})$ was actually constant
in ${\bm{z}}^{t-2}$, the assumption could not hold (unless
$||{\bm{G}}^{z}||_{0}\leq 1$). This case would correspond to a simple linear
model of the form
${\bm{\mu}}({\bm{z}}^{t-1}):={\bm{z}}^{t-1}+{\bm{W}}{\bm{z}}^{t-1}$. Our
theory suggests this transition function is “too simple” to allow
disentanglement.

Nevertheless, we can find examples satisfying (58). For example, if
${\bm{G}}^{z}={\bm{I}}$, we can take

$\displaystyle{\bm{W}}({\bm{z}})=\begin{bmatrix}{\bm{z}}_{1}&0&0\\\
0&{\bm{z}}_{2}&0\\\ 0&0&{\bm{z}}_{3}\end{bmatrix}\,$ (59)

and see that the family of functions
$(1+{\bm{z}}_{1},1+{\bm{z}}_{2},1+{\bm{z}}_{3})$ is linearly independent (when
seen as functions from ${\mathbb{R}}^{3}$ to ${\mathbb{R}}$). By Lemma 5 in
the appendix, this is equivalent to the existence of
${\bm{z}}_{(1)},{\bm{z}}_{(2)},{\bm{z}}_{(3)}\in{\mathbb{R}}^{d_{z}}$ such
that (58) holds (see also Remark 5). In other words, the sufficient influence
assumption holds. In the case where ${\bm{G}}^{z}$ is lower triangular like in
Figure 3(e), one can take

$\displaystyle{\bm{W}}({\bm{z}})=\begin{bmatrix}{\bm{z}}_{1}&0&0\\\
{\bm{z}}_{2}^{2}&{\bm{z}}_{2}&0\\\
{\bm{z}}_{3}^{3}&{\bm{z}}_{3}^{2}&{\bm{z}}_{3}\end{bmatrix}\,$ (60)

and see that the family of functions
$(1+{\bm{z}}_{1},1+{\bm{z}}_{2},1+{\bm{z}}_{3},{\bm{z}}_{2}^{2},{\bm{z}}_{3}^{2},{\bm{z}}_{3}^{3})$
are linearly independent, which similarly implies the existence of
${\bm{z}}_{(1)},\dots,{\bm{z}}_{(6)}\in{\mathbb{R}}^{d_{z}}$ such that (58)
holds.

Example 15 will show how one can leverage the exponential family assumption to
allow for Markovianity even without auxiliary variables.

##  4 Partial disentanglement via mechanism sparsity in exponential families

The goal of this section is to understand how restricting the transition model
to be in the exponential family allows us to weaken the sufficient influence
assumption of Theorem 3. Section 4.1 introduces the exponential family
assumption. Section 4.2 follows Khemakhem et al. (2020a) and shows that this
additional assumption guarantees that the entanglement map ${\bm{v}}$ is
“quasi-linear”, which means
${\bm{v}}({\bm{z}}):={\bm{s}}^{-1}({\bm{L}}{\bm{s}}({\bm{z}})+{\bm{b}})$,
where ${\bm{L}}$ is a matrix and ${\bm{s}}$ is an element-wise invertible
function. Section 4.3 will introduce an identifiability result analogous to
Theorem 3 for sparse $\hat{\bm{G}}^{z}$ that leverages the quasi-linearity of
${\bm{v}}$ to weaken Assumption 8 (sufficient influence of ${\bm{z}}$). We
also briefly discuss an additional result from Appendix B.4 that shows
connections between the nonparametric sufficient influence assumptions of this
work (Assumptions 7 & 8) and their counterparts in Lachapelle et al. (2022)
(Assumptions 11 & 12).

###  4.1 Exponential family latent transition models

We will assume that the conditional densities
$p({\bm{z}}_{i}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t})$ are from an exponential
family (Wainwright and Jordan, 2008):

######  Assumption 9 (Exponential family transition model)

For all $i\in[d_{z}]$, we have

$\displaystyle
p({\bm{z}}_{i}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t})=h_{i}({\bm{z}}^{t}_{i})\exp\\{{\bm{s}}_{i}({\bm{z}}^{t}_{i})^{\top}{\bm{\lambda}}_{i}({\bm{z}}^{<t},{\bm{a}}^{<t})-\psi_{i}({\bm{z}}^{<t},{\bm{a}}^{<t})\\}\,.$
(61)

Well-known distributions which belong to this family include the Gaussian and
beta distribution. In the Gaussian case, the sufficient statistic is
${\bm{s}}_{i}(z):=(z,z^{2})$ and the base measure is
$h_{i}(z):=\frac{1}{\sqrt{2\pi}}$. The function
${\bm{\lambda}}_{i}({\bm{z}}^{<t},{\bm{a}}^{<t})$ outputs the natural
parameter vector for the conditional distribution and can be itself
parametrized, for instance, by a multi-layer perceptron (MLP) or a recurrent
neural network (RNN). We will refer to the functions ${\bm{\lambda}}_{i}$ as
the mechanisms or the transition functions. In the Gaussian case, the natural
parameter is two-dimensional and is related to the usual parameters $\mu$ and
$\sigma^{2}$ via the equation
$(\lambda_{1},\lambda_{2})=(\frac{\mu}{\sigma^{2}},-\frac{1}{2\sigma^{2}})$.
We will denote by $k$ the dimensionality of the natural parameter and that of
the sufficient statistic (which are equal). Thus, $k=2$ in the Gaussian case.
The remaining term $\psi_{i}({\bm{z}}^{<t},{\bm{a}}^{<t})$ acts as a
normalization constant.

We define
${\bm{\lambda}}({\bm{z}}^{<t},{\bm{a}}^{<t})\in{\mathbb{R}}^{kd_{z}}$ to be
the concatenation of all ${\bm{\lambda}}_{i}({\bm{z}}^{<t},{\bm{a}}^{<t})$ and
similarly for ${\bm{s}}({\bm{z}}^{t})\in{\mathbb{R}}^{kd_{z}}$. Similarly to
the nonparameteric case, the learnable parameters are
${\bm{\theta}}:=({\bm{f}},{\bm{\lambda}},{\bm{G}})$. Note that throughout, we
assume that the sufficient statistic ${\bm{s}}$ is not learned and known in
advance. With this notation, we can write the full transition model as

$\displaystyle
p({\bm{z}}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t})=h({\bm{z}}^{t})\exp\\{{\bm{s}}({\bm{z}}^{t})^{\top}{\bm{\lambda}}({\bm{z}}^{<t},{\bm{a}}^{<t})-\psi({\bm{z}}^{<t},{\bm{a}}^{<t})\\}\,,$
(62)

where $h:=\prod_{i=1}^{d_{z}}h_{i}$ and $\psi=\sum_{i=1}^{d_{z}}\psi_{i}$.

######  Remark 8 (Applying nonparametric identifiability results to
exponential families)

One can apply the nonparametric results (Theorems 1, 2 & 3) to models
satisfying the exponential family assumption. In fact, all examples of Section
3.8 were Gaussians and thus are in the exponential family.

###  4.2 Conditions for quasi-linear identifiability

In this section, we follow Khemakhem et al. (2020a) and show that the
exponential family assumption combined with an additional sufficient
variability assumption allows to go from identifiability up to diffeomorphism
(Definition 5) to identifiability up to quasi-linearity, which we define next:

######  Definition 17 (Quasi-linear equivalence)

We say two models ${\bm{\theta}}:=({\bm{f}},{\bm{\lambda}},{\bm{G}})$ and
$\tilde{{\bm{\theta}}}:=(\tilde{\bm{f}},{\bm{\lambda}},\tilde{\bm{G}})$
satisfying Assumptions 1, 2 & 9 are equivalent up to quasi-linearity, denoted
${\bm{\theta}}\sim_{\textnormal{lin}}\tilde{\bm{\theta}}$, if and only if
${\bm{\theta}}\sim_{\textnormal{diff}}\tilde{\bm{\theta}}$ and there exist an
invertible matrix ${\bm{L}}\in{\mathbb{R}}^{kd_{z}\times kd_{z}}$ and a vector
${\bm{b}}\in{\mathbb{R}}^{kd_{z}}$ such that the map
${\bm{v}}:={\bm{f}}^{-1}\circ\tilde{\bm{f}}$ satisfies

$\displaystyle{\bm{s}}({\bm{v}}({\bm{z}}))={\bm{L}}{\bm{s}}({\bm{z}})+{\bm{b}},\
\forall{\bm{z}}\in{\mathbb{R}}^{d_{z}}\,.$ (63)

If the sufficient statistic ${\bm{s}}$ is invertible, one obtains

$\displaystyle{\bm{v}}({\bm{z}})={\bm{s}}^{-1}({\bm{L}}{\bm{s}}({\bm{z}})+{\bm{b}}),\
\forall{\bm{z}}\in{\mathbb{R}}^{d_{z}}\,.$ (64)

Equation (64) is particularly interesting, as it says that the mapping
relating both representations is “almost” linear in the following sense:
although the map is not necessarily linear because the sufficient statistic
${\bm{s}}$ might not be, the “mixing” between components is linear. Indeed,
notice that the sufficient statistic ${\bm{s}}$ and its inverse operates
“element-wise”. The mixing between components is only due to the matrix
${\bm{L}}$. This specific form simplifies a few steps in the identifiability
proof, which might explain the popularity of this assumption in the literature
on nonlinear ICA (Hyvarinen and Morioka, 2016; Khemakhem et al., 2020a, b;
Hälvä and Hyvärinen, 2020; Morioka et al., 2021; Yang et al., 2021; Lachapelle
et al., 2022; Liu et al., 2023; Xi and Bloem-Reddy, 2023).

The following theorem provides conditions to guarantee identifiability up to
quasi-linearity. This is an adaptation and minor extension of Theorem 1 from
Khemakhem et al. (2020a). For completeness, we provide a proof in Appendix
B.2.

######  Theorem 4 (Conditions for linear identifiability - Adapted from
Khemakhem et al. (2020a))

Let ${\bm{\theta}}:=({\bm{f}},{\bm{\lambda}},{\bm{G}})$ and
$\hat{{\bm{\theta}}}:=(\hat{\bm{f}},\hat{\bm{\lambda}},\hat{\bm{G}})$ be two
models satisfying Assumptions 1, 2 & 9. Further assume that

  1. 1.

[Observational equivalence]
${\bm{\theta}}\sim_{\textnormal{obs}}\hat{\bm{\theta}}$ (Definition 4);

  2. 2.

[Minimal sufficient statistics] For all $i$, the sufficient statistic
${\bm{s}}_{i}$ is minimal (see below).

  3. 3.

[Sufficient variability] The natural parameter ${\bm{\lambda}}$ varies
“sufficiently” as formalized by Assumption 10 (see below).

Then, ${\bm{\theta}}\sim_{\textnormal{lin}}\hat{\bm{\theta}}$ (Def. 17).

The “minimal sufficient statistics” assumption is a standard one saying that
${\bm{s}}_{i}$ is defined appropriately to ensure that the parameters of the
exponential family are identifiable (see e.g. Wainwright and Jordan (2008, p.
40)). See Definition 20 for a formal definition of minimality. The last
assumption is sometimes called the assumption of variability (Hyvärinen et
al., 2019), and requires that the conditional distribution of ${\bm{z}}^{t}$
depends “sufficiently strongly” on ${\bm{z}}^{<t}$ and/or ${\bm{a}}^{<t}$. We
stress the fact that this assumption concerns the ground-truth data generating
model ${\bm{\theta}}$.

######  Assumption 10 (Sufficient variability in exponential families)

There exist $({\bm{z}}_{(r)},{\bm{a}}_{(r)})_{p=0}^{kd_{z}}$ in their
respective supports such that the $kd_{z}$-dimensional vectors
${({\bm{\lambda}}({\bm{z}}_{(r)},{\bm{a}}_{(r)})-{\bm{\lambda}}({\bm{z}}_{(0)},{\bm{a}}_{(0)})})_{r=1}^{kd_{z}}$
are linearly independent.

Notice that the ${\bm{z}}_{(r)}$ represent values of ${\bm{z}}^{<t}$ for
potentially different values of $t$ and can thus have different dimensions.

The following example builds on Example 10 and shows that the sufficient
variability of the above theorem might hold or not. The first case is
interesting since it guarantees that ${\bm{v}}$ is linear while the second is
interesting because it showcases a situation where the theory of Khemakhem et
al. (2020a) and Lachapelle et al. (2022) do not apply (since they both rely on
the above theorem) thus highlighting the importance of our nonparametric
extension.

######  Example 14 (Satisfying or not the sufficient variability assumption of
Theorem 4)

We recallExample 10 in which $d_{a}=d_{z}$,
${\bm{a}}\in{\mathcal{A}}:=\\{\bm{0},{\bm{e}}_{1},\dots,{\bm{e}}_{d_{a}}\\}$
and ${\bm{G}}^{a}={\bm{I}}$ without temporal dependencies: For all
$i\in[d_{z}]$,
$p({\bm{z}}_{i}\mid{\bm{a}})={\mathcal{N}}({\bm{z}};{\bm{\mu}}_{i}{\bm{a}}_{i},1+{\bm{\delta}}_{i}{\bm{a}}_{i})$
where ${\bm{\mu}}_{i}\in{\mathbb{R}}$ and ${\bm{\delta}}_{i}>-1$. We consider
the cases where $\forall i,\ {\bm{\delta}}_{i}=0$ (unchanged variances) and
$\forall i,\ {\bm{\delta}}_{i}\not=0$ (variances change).

If $\forall i,\ {\bm{\delta}}_{i}=0$, we can represent
$p({\bm{z}}_{i}\mid{\bm{a}})$ in its exponential form with a one-dimensional
sufficient statistic given by ${\bm{s}}_{i}({\bm{z}}_{i})={\bm{z}}_{i}$ and
natural parameter given by
${\bm{\lambda}}_{i}({\bm{a}})={\bm{\mu}}_{i}{\bm{a}}_{i}$. It can be easily
seen that if $\forall i,\ {\bm{\mu}}_{i}\not=0$ (i.e. the mean changes after
the intervention), then the sufficient variability assumption of Theorem 4
holds since the vectors
${\bm{\lambda}}({\bm{e}}_{i})-{\bm{\lambda}}(\bm{0})={\bm{\mu}}_{i}{\bm{e}}_{i}$
do span ${\mathbb{R}}^{d_{z}}$.

If $\forall i,\ {\bm{\delta}}_{i}\not=0$, we can represent
$p({\bm{z}}_{i}\mid{\bm{a}})$ in its exponential form with a two-dimensional
sufficient statistics given by
${\bm{s}}_{i}({\bm{z}}_{i})=({\bm{z}}_{i},{\bm{z}}_{i}^{2})$ and natural
parameter given by
${\bm{\lambda}}_{i}({\bm{a}})=\left(\frac{{\bm{\mu}}_{i}{\bm{a}}_{i}}{1+{\bm{\delta}}_{i}{\bm{a}}_{i}},\frac{-1}{2(1+{\bm{\delta}}_{i}{\bm{a}}_{i})}\right)$.
Note that, because we only have $d_{z}$ interventions, for any choice of
${\bm{a}}_{(0)}\in{\mathcal{A}}$, the vectors
$\\{{\bm{\lambda}}({\bm{a}})-{\bm{\lambda}}({\bm{a}}_{(0)})\\}_{{\bm{a}}\in{\mathcal{A}}}$
can span at most a $d_{z}$-dimensional subspace, which is insufficient
variability according to Theorem 4 since it requires spanning
${\mathbb{R}}^{2d_{z}}$.

###  4.3 Partial disentanglement via sparse time dependencies in exponential
families

We now provide a (partial) disentanglement guarantee which leverages sparsity
regularization of $\hat{\bm{G}}^{z}$ and is specialized for exponential
families with a one-dimensional sufficient statistic ($k=1$). We will see that
this extra parametric assumption on the transition model allows us to weaken
the sufficient influence assumption of Theorem 3 (Assumption 8). In
particular, this is going to allow for Markovian transitions without auxiliary
variables, which was not allowed by the nonparametric result (Remark 7).

The sufficient influence of ${\bm{z}}$ assumption specialized to exponential
families with $k=1$ is directly taken from Lachapelle et al. (2022):

######  Assumption 11 (Sufficient influence of ${\bm{z}}$ (Lachapelle et al.,
2022))

Assume $k=1$ and $D{\bm{s}}({\bm{z}})$ is invertible everywhere. There exist
$\\{({\bm{z}}_{(r)},{\bm{a}}_{(r)},\tau_{(r)})\\}_{r=1}^{||{\bm{G}}^{z}||_{0}}$
belonging to their respective support such that

$\displaystyle\mathrm{span}\left\\{D^{\tau_{(r)}}_{z}{\bm{\lambda}}({\bm{z}}_{(r)},{\bm{a}}_{(r)})D{\bm{s}}({\bm{z}}^{\tau_{(r)}}_{(r)})^{-1}\right\\}_{r=1}^{||{\bm{G}}^{z}||_{0}}={\mathbb{R}}^{d_{z}\times
d_{z}}_{{\bm{G}}^{z}}\,,$

where $D^{\tau_{(r)}}_{z}{\bm{\lambda}}$ and $D{\bm{s}}$ are Jacobians with
respect to ${\bm{z}}^{\tau_{(r)}}$ and ${\bm{z}}$, respectively.

In Appendix B.4, we show that the above assumption is implied by its
nonparametric version (Assumption 8) when the transition model is in an
exponential family with $k=1$. However, Assumption 11 is strictly weaker than
its nonparametric counterpart, Assumption 8. The reason is that, in the
former, ${\bm{z}}^{\tau_{(r)}}$ can vary for different $p$ whereas this is not
allowed in the latter since we require ${\bm{z}}={\bm{z}}^{\tau_{(r)}}$ for
all $r$.

The following theorem, extended from Lachapelle et al. (2022), shows that
making stronger parametric assumptions on the transition model allows to
weaken the sufficient influence assumption. Note that its structure is nearly
identical to Theorem 3. Its proof can be found in Appendix B.3.

######  Theorem 5 (Disentanglement via sparse temporal dependencies in
exponential families)

Let
${\bm{\theta}}:=({\bm{f}},{\bm{\lambda}},{\bm{G}})$ and
$\hat{{\bm{\theta}}}:=(\hat{\bm{f}},\hat{\bm{\lambda}},\hat{\bm{G}})$ be two
models satisfying Assumptions 1, 2, 3, 4, 9 as well as all assumptions of
Theorem 4. Further suppose that

  1. 1.

The sufficient statistic ${\bm{s}}$ is $d_{z}$-dimensional ($k=1$) and is a
diffeomorphism from ${\mathbb{R}}^{d_{z}}$ to
${\bm{s}}({\mathbb{R}}^{d_{z}})$;

  2. 2.

[Sufficient influence of ${\bm{z}}$] The Jacobian of the ground-truth
transition function ${\bm{\lambda}}$ with respect to ${\bm{z}}$ varies
“sufficiently”, as formalized in Assumption 11;

Then, there exists a permutation matrix ${\bm{P}}$ such that
${\bm{P}}{\bm{G}}^{z}{\bm{P}}^{\top}\subseteq\hat{\bm{G}}^{z}$. Further assume
that

  1. 3.

[Sparsity regularization] $||\hat{\bm{G}}^{z}||_{0}\leq||{\bm{G}}^{z}||_{0}$;

Then, ${\bm{\theta}}\sim_{\textnormal{con}}^{\bm{z}}\hat{\bm{\theta}}$ (Def.
14) & ${\bm{\theta}}\sim_{\textnormal{lin}}\hat{\bm{\theta}}$ (Def. 17), which
together implies that

${\bm{v}}({\bm{z}})={\bm{s}}^{-1}({\bm{C}}{\bm{P}}^{\top}{\bm{s}}({\bm{z}})+{\bm{b}})\,,$

where ${\bm{b}}\in{\mathbb{R}}^{d_{z}}$ and
${\bm{C}}\in{\mathbb{R}}^{d_{z}\times d_{z}}$ is invertible,
${\bm{G}}^{\bm{z}}$\- and $({\bm{G}}^{\bm{z}})^{\top}$-preserving (Definition
11).

The reason we can simplify the sufficient influence assumption in the
exponential family case has to do with the quasi-linear form of ${\bm{v}}$.
Indeed, in that case, one can compute that the Jacobian of ${\bm{v}}$ takes a
special form:
$D{\bm{v}}({\bm{z}})=D{\bm{s}}({\bm{v}}({\bm{z}}))^{-1}{\bm{L}}D{\bm{s}}({\bm{z}})$.
Since $D{\bm{s}}$ is diagonal everywhere, one can see that the “non-diagonal
part” of $D{\bm{v}}({\bm{z}})$, i.e. ${\bm{L}}$, does not depend on
${\bm{z}}$, which simplifies the proof. See Appendix B.3 for details.

In Appendix D.2, we discuss how Khemakhem et al. (2020a) & Yao et al. (2022b)
obtain disentanglement guarantee and how their assumptions differ from ours.

######  Example 15 (Markovian sparse temporal dependencies without auxiliary
variables)

Recall Remark 7 which pointed out that, without auxiliary variables, non-
Markovianity was necessary to satisfy the nonparametric Assumption 8. We now
illustrate that the analogous assumption specialized for exponential families
with $k=1$ (Assumption 11) is not as restrictive, i.e. it allows for
Markovianity even when there are no auxiliary variables.

We start from Example 6 which was based on the situation depicted in Figures 1
& 3(e) where the temporal graph ${\bm{G}}^{z}$ is lower triangular. Assume
that no action is observed, i.e. we can only leverage the sparsity of
${\bm{G}}^{z}$ to disentangle. We now provide a concrete Markovian transition
model $p({\bm{z}}^{t}\mid{\bm{z}}^{t-1})$ that satisfies Assumption 11.
Similarly to previous examples, assume
$p({\bm{z}}^{t}\mid{\bm{z}}^{t-1})={\mathcal{N}}({\bm{z}}^{t};{\bm{\mu}}({\bm{z}}^{t-1}),\sigma^{2}{\bm{I}})$
where

$\displaystyle{\bm{\mu}}({\bm{z}}):={\bm{z}}+\begin{bmatrix}{\bm{z}}_{1}^{2}/2\\\
{\bm{z}}_{1}^{3}/3\\\ {\bm{z}}_{1}^{4}/4\end{bmatrix}+\begin{bmatrix}0\\\
{\bm{z}}_{2}^{2}/2\\\ {\bm{z}}_{2}^{3}/3\end{bmatrix}+\begin{bmatrix}0\\\ 0\\\
{\bm{z}}_{3}^{2}/2\end{bmatrix}\,.$ (65)

Because the variance $\sigma^{2}$ is not influenced by ${\bm{z}}^{t-1}$, we
can represent this transition model in an exponential family with $k=1$ where
the natural parameter is given by

$\displaystyle{\bm{\lambda}}({\bm{z}}^{t-1})=\mu({\bm{z}}^{t-1})/\sigma$ (66)

and the sufficient statistic is given by ${\bm{s}}({\bm{z}})={\bm{z}}/\sigma$.
We can thus compute

$\displaystyle
D{\bm{\lambda}}({\bm{z}})D{\bm{s}}({\bm{z}})^{-1}={\bm{I}}+\begin{bmatrix}{\bm{z}}_{1}&0&0\\\
{\bm{z}}_{1}^{2}&{\bm{z}}_{2}&0\\\
{\bm{z}}_{1}^{3}&{\bm{z}}_{2}^{2}&{\bm{z}}_{3}\end{bmatrix}$ (67)

which spans the 6-dimensional space ${\mathbb{R}}^{3\times 3}_{{\bm{G}}^{z}}$,
as showed in Example 13.

##### Connecting with the sufficient influence assumption of ${\bm{a}}$ in
Lachapelle et al. (2022)

The previous work of Lachapelle et al. (2022) could also leverage sparse
influence of ${\bm{a}}$ to disentangle and was based on exponential family and
sufficient influence assumptions. In Appendix B.4, Proposition 12 shows that
their sufficient influence of ${\bm{a}}$ assumption is actually equivalent to
our nonparametric version (Assumption 7) in the exponential family case with
$k=1$. An important conclusion of this observation is that the identifiability
result via sparse ${\bm{G}}^{\bm{a}}$ from Lachapelle et al. (2022), which was
limited to the exponential family case with $k=1$, can be derived from the
more general nonparametric result of Theorem 2 we introduced earlier.

##  5 Model estimation with sparsity constraint

The identifiability results presented in this work are based on two crucial
postulates: (i) the distribution over observations of both the learned and
ground-truth models must match, i.e.
$\hat{\bm{\theta}}\sim_{\textnormal{obs}}{\bm{\theta}}$ (Definition 4), and
(ii) the learned graphs $\hat{\bm{G}}^{a}$ and $\hat{\bm{G}}^{z}$ must be as
sparse as their ground-truth counterparts, respectively ${\bm{G}}^{a}$ and
${\bm{G}}^{z}$. The theory suggests that, in order to learn a (partially)
disentangled representation, one should learn a model that satisfies these two
requirements. In this section, we present one particular practical approach to
achieve this approximately. Appendix C.2 provides further details.

##### Data fitting.

The first condition can be achieved by fitting a model to data. Since the
models discuss in this work present latent variable models, a natural idea is
to use a maximum likelihood approach based on the well-known framework of
variational autoencoders (VAEs) (Kingma and Welling, 2014) in which the
decoder neural network corresponds to the mixing function $\hat{\bm{f}}$. We
consider an approximate posterior of the form

$\displaystyle q({\bm{z}}^{\leq T}\mid{\bm{x}}^{\leq
T},{\bm{a}}^{<T}):=\prod_{t=1}^{T}q({\bm{z}}^{t}\mid{\bm{x}}^{t})\,,$ (68)

where $q({\bm{z}}^{t}\mid{\bm{x}}^{t})$ is a Gaussian distribution with mean
and diagonal covariance outputted by a neural network
$\texttt{encoder}({\bm{x}}^{t})$. In our experiments, the latent model
$\hat{p}({\bm{z}}_{i}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t})$ is a Gaussian
distribution with mean $\hat{\bm{\mu}}_{i}({\bm{z}}^{<t},{\bm{a}}^{<t})$
parameterized as a fully connected neural network that “looks” only at a fixed
window of $s$ lagged latent variables.555The theory we developed would allow
for a ${\bm{\mu}}$ function that depends on all previous time steps, not only
the $s$ previous ones. This could be achieved with a recurrent neural network
or transformer, but we leave this to future work. Furthermore, the variances
are learned but does not depend on $({\bm{z}}^{<t},{\bm{a}}^{<t})$ (see
Appendix C.2 for details). This variational inference model induces the
following evidence lower bound (ELBO) on $\log\hat{p}({\bm{x}}^{\leq
T}|{\bm{a}}^{<T})$:

$\displaystyle\log\hat{p}({\bm{x}}^{\leq
T}|{\bm{a}}^{<T})\geq\text{ELBO}(\hat{\bm{f}},\hat{\bm{\mu}},\hat{\bm{G}},q;{\bm{x}}^{\leq
T},{\bm{a}}^{<T}):=$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\sum_{t=1}^{T}\mathop{{\mathbb{E}}}_{q({\bm{z}}^{t}|{\bm{x}}^{t})}[\log\hat{p}({\bm{x}}^{t}\mid{\bm{z}}^{t})]-\mathop{{\mathbb{E}}}_{q({\bm{z}}^{<t}\mid{\bm{x}}^{<t})}KL(q({\bm{z}}^{t}\mid{\bm{x}}^{t})||\hat{p}({\bm{z}}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t}))\,.$
(69)

We derive this fact in Appendix D.3. This lower bound can then be maximized
using some variant of stochastic gradient ascent such as Adam (Kingma and Ba,
2015). We note that many works have proposed learning dynamical models with
latent variables using VAEs (Girin et al., 2020), with various choice of
architectures and approximate posteriors. Our specific choices were made out
of a desire for simplicity, but the reader should be aware of other
possibilities.

The learned distribution will exactly match the ground truth distribution if
(i) the model has enough capacity to express the ground-truth generative
process, (ii) the approximate posterior has enough capacity to express the
ground-truth posterior $p({\bm{z}}^{t}|{\bm{x}}^{\leq T},{\bm{a}}^{<T})$,
(iii) the dataset is sufficiently large and (iv) the optimization finds the
global optimum. If, in addition, the ground truth generative process satisfies
the assumptions of Proposition 2, we can guarantee that the learned model
$\hat{{\bm{\theta}}}$ will be equivalent to the ground truth model
${\bm{\theta}}$ up to diffeomorphism (Definition 5).

##### Learning $\hat{\bm{G}}$ with sparsity constraints.

To go from equivalence up to diffeomorphism to actual disentanglement (partial
or not), Theorems 1, 2, 3 & 5 suggest we should not only fit the data, but
also choose the learned graph $\hat{\bm{G}}$ such that
$||\hat{{\bm{G}}}^{a}||_{0}\leq||{{\bm{G}}}^{a}||_{0}$ and/or
$||\hat{{\bm{G}}}^{z}||_{0}\leq||{{\bm{G}}}^{z}||_{0}$. In order to allow for
gradient-based optimization, our strategy consists in treating each edge
$\hat{\bm{G}}_{i,j}$ as independent Bernoulli random variable with probability
of success $\sigma({\bm{\gamma}}_{i,j})$, where $\sigma$ is the sigmoid
function and ${\bm{\gamma}}_{i,j}$ is a parameter learned using the Gumbel-
Softmax trick (Jang et al., 2017; Maddison et al., 2017). Let
$\text{ELBO}(\hat{\bm{f}},\hat{\bm{\mu}},\hat{\bm{G}},q)$ be the ELBO
objective of (69) averaged over the whole dataset. We tackle the following
constrained optimization problem:

$\displaystyle\max_{\hat{\bm{f}},\hat{\bm{\mu}},{\bm{\gamma}},q}{\mathbb{E}}_{\hat{\bm{G}}\sim\sigma({\bm{\gamma}})}\text{ELBO}(\hat{\bm{f}},\hat{\bm{\mu}},\hat{\bm{G}},q)\
\ \text{subject to}\ \
{\mathbb{E}}_{\hat{\bm{G}}\sim\sigma({\bm{\gamma}})}||\hat{\bm{G}}||_{0}\leq\beta\,.$
(70)

where $\beta$ is an hyperparameter (which should be set ideally to
$\beta^{*}:=||{\bm{G}}||_{0}$, i.e. the number of edges in the ground-truth
graph) and $\hat{\bm{G}}\sim\sigma({\bm{\gamma}})$ means that
$\hat{\bm{G}}_{i,j}$ are independent and distributed according to
$\sigma({\bm{\gamma}}_{i,j})$. Because
${\mathbb{E}}_{\hat{\bm{G}}\sim\sigma({\bm{\gamma}})}||\hat{\bm{G}}||_{0}=||\sigma({\bm{\gamma}})||_{1}$
where $\sigma({\bm{\gamma}})$ is matrix, the constraint becomes
$||\sigma({\bm{\gamma}})||_{1}\leq\beta$. To solve this problem, we perform
gradient descent-ascent on the Lagrangian function given by

$\displaystyle{\mathbb{E}}_{\hat{\bm{G}}\sim\sigma({\bm{\gamma}})}\text{ELBO}(\hat{\bm{f}},\hat{\bm{\mu}},\hat{\bm{G}},q)-\alpha(||\sigma({\bm{\gamma}})||_{1}-\beta)$
(71)

where the ascent step is performed w.r.t.
$\hat{\bm{f}},\hat{\bm{\mu}},\hat{\bm{G}}$ and $q$; and the descent step is
performed w.r.t. Lagrangian multiplier $\alpha$, which is forced to remain
greater or equal to zero via a simple projection step. As suggested by
Gallego-Posada et al. (2021), we perform dual restarts which simply means
that, as soon as the constraint is satisfied, the Lagrangian multiplier is
reset to $0$. We used the library Cooper (Gallego-Posada and Ramirez, 2022),
which implements many constrained optimization procedure in Python, including
the one described above. Note that we use Adam (Kingma and Ba, 2015) for the
ascent steps and standard gradient descent for the descent step on the
Lagrangian multiplier $\alpha$.

We also found empircally that the following schedule for $\beta$ is helpful:
We start training with $\beta=\max_{\hat{\bm{G}}}||\hat{\bm{G}}||_{0}$ and
linearly decreasing its value until the desired number of edges is reached.
This avoid getting a sparse graph too quickly while training, thus letting
enough time to the model parameters to learn. In each experiment, we trained
for 300K iterations, and the $\beta$ takes 150K to go from its initial value
to its desired value. We discuss how to select the hyperparameter $\beta$ in
Section 8.

##  6 Evaluation with $R_{\textnormal{con}}$ and SHD

In this section, we tackle the problem of evaluating quantitatively whether a
learned representation $\hat{\bm{z}}$ is completely or partially disentangled
w.r.t. the ground-truth representation ${\bm{z}}$, given a dataset of paired
representations $\\{({\bm{z}}^{i},\hat{\bm{z}}^{i})\\}_{i\in[N]}$. More
precisely, want to evaluate whether two models are ${\bm{a}}$-consistent or
${\bm{z}}$-consistent (Definitions 13 & 14). To achieve this, we have to
evaluate whether there exists a graph preserving map ${\bm{c}}$ (Definition
12) and a permutation matrix ${\bm{P}}$ such that for all $i\in[N]$,
${\bm{z}}^{i}={\bm{c}}({\bm{P}}^{\top}\hat{\bm{z}}^{i})$. For evaluation
purposes, we assume we observe the ground-truth latent representation for each
observation, i.e. we have $\\{({\bm{x}}^{i},{\bm{z}}^{i})\\}_{i\in N}$ sampled
i.i.d. from the ground-truth data generating process. We will take
$\hat{\bm{z}}^{i}:=\texttt{encoder}({\bm{x}}^{i})$ where encoder is from the
learned VAE model introduced in Section 5. For simplicity, we assume that
${\bm{c}}$ is affine.666This is not a simplification when the latent factors
in the model and in the data-generating process are Gaussian with fixed
variance and the assumptions of Theorem 4 hold. That is because the latent
model is in the exponential family with sufficient statistic
${\bm{s}}({\bm{z}})={\bm{z}}$ and, by Theorem 4, we must have that
${\bm{z}}={\bm{s}}^{-1}({\bm{L}}{\bm{s}}(\hat{\bm{z}})+{\bm{b}})={\bm{L}}\hat{\bm{z}}+{\bm{b}}$.

We start with how to evaluate complete disentanglement. A popular choice for
this is the mean correlation coefficient (MCC), which is obtained by first
computing the Pearson correlation matrix ${\bm{K}}\in{\mathbb{R}}^{d_{z}\times
d_{z}}$ between the ground-truth representation and the learned representation
(${\bm{K}}_{i,j}$ is the correlation between ${\bm{z}}_{i}$ and
$\hat{\bm{z}}_{j}$). Then
$\text{MCC}:=\max_{{\bm{P}}\in\text{permutations}}\tfrac{1}{d_{z}}\sum_{i=1}^{d_{z}}|({\bm{K}}{\bm{P}})_{i,i}|$.
We denote by $\hat{{\bm{P}}}$ the optimal permutation found by MCC.

To evaluate whether the learned representation is identified up to linear
transformation (Definition 17), we perform linear regression to predict the
ground-truth latent factors from the learned ones, and report the mean of the
Pearson correlations between the predicted ground-truth latents and the actual
ones. This metric is sometimes called the coefficient of multiple correlation,
and happens to be the square root of the better known coefficient of
determination, usually denoted by $R^{2}$. The advantage of using $R$ instead
of $R^{2}$ is that the former is comparable to MCC, and we always have
$\text{MCC}\leq R$. Let us denote by $\hat{\bm{L}}$ the matrix of estimated
coefficients, which should be thought of as an estimation of ${\bm{L}}$ in
Definition 17 (assuming ${\bm{s}}({\bm{z}})={\bm{z}}$, as is the case with
Gaussian latents with fixed variance). Note that $\hat{\bm{L}}$ was fitted on
standardized ${\bm{z}}$ and $\hat{\bm{z}}$ (shifted and scaled to have mean 0
and 1). This yields coefficients $\hat{\bm{L}}_{i,j}$ that are directly
comparable without changing the value of the $R$ score. We visualize
$\hat{\bm{L}}$ in Figures 6 & 8.

To evaluate whether the learned representation is ${\bm{a}}$-consistent or
${\bm{z}}$-consistent to the ground-truth (Definitions 13 & 14), as predicted
by Theorems 1 & 3, we introduce a novel metric, denoted by $R_{\text{con}}$.
The idea behind $R_{\text{con}}$ is to predict the ground-truth factors
${\bm{z}}$ from only the inferred factors $\hat{\bm{z}}$ that are allowed by
the equivalence relations. For instance, for ${\bm{a}}$-consistency
(Definition 13), the relation between ${\bm{z}}$ and $\hat{\bm{z}}$ is given
by ${\bm{z}}={\bm{c}}({\bm{P}}^{\top}\hat{\bm{z}})$ where ${\bm{c}}$ is a
${\bm{G}}^{a}$-preserving diffeomorphism. Since we assume for simplicity that
${\bm{c}}$ is affine, we have
${\bm{z}}={\bm{C}}{\bm{P}}^{\top}\hat{\bm{z}}+{\bm{b}}$ where ${\bm{C}}$ is a
${\bm{G}}^{a}$-preserving matrix. The idea is then to estimate both ${\bm{P}}$
and ${\bm{C}}$ using samples $({\bm{z}},\hat{\bm{z}})$. The permutation
${\bm{P}}$ is estimated by $\hat{\bm{P}}$, which was found when computing MCC
(Section 8). To estimate ${\bm{C}}$, we compute
$\hat{\bm{z}}_{\text{perm}}:=\hat{\bm{P}}^{\top}\hat{\bm{z}}$ and then compute
the mask ${\bm{M}}\in\\{0,1\\}^{d_{z}\times d_{z}}$ specifying which entries
of ${\bm{C}}$ are allowed to be nonzero, as required by the
${\bm{G}}^{a}$-preservation property (Proposition 3). Then, for every $i$, we
predict the ground-truth ${\bm{z}}_{i}$ by performing linear regression only
on the allowed factors, i.e.
${\bm{M}}_{i,\cdot}\odot\hat{\bm{z}}_{\text{perm}}$, and compute the
associated coefficient of multiple correlations $R_{\text{con},i}$ and report
the mean, i.e.
$R_{\text{con}}:=\frac{1}{d_{z}}\sum_{i=1}^{d_{z}}R_{\text{con},i}$. It is
easy to see that we must have $R_{\text{con}}\leq R$, since $R_{\text{con}}$
was computed with less features than $R$. Moreover, $\text{MCC}\leq
R_{\text{con}}$, because MCC can be thought of as computing exactly the same
thing as for $R_{\text{con}}$, but by predicting ${\bm{z}}_{i}$ only from
$\hat{\bm{z}}_{\text{perm},i}$, i.e. with less features than $R_{\text{con}}$.
This means we always have $0\leq\text{MCC}\leq R_{\text{con}}\leq R\leq 1$.
This is a nice property which allows to compare all three metrics together and
reflects the hierarchy between equivalence relations. Note that
$R_{\text{con}}$ depends implicitly on the ground-truth graph, since the
matrix ${\bm{M}}$ indicating which entries of ${\bm{C}}$ are forced to be zero
by the equivalence relation depends on ${\bm{G}}$.

To compare the learned graph $\hat{\bm{G}}$ to the ground-truth ${\bm{G}}$, we
report the (normalized) structural Hamming distance (SHD) between the ground-
truth graph and the estimated graph permuted by $\hat{\bm{P}}$. More
precisely, we report
$\text{SHD}=(||{\bm{G}}^{a}-\hat{\bm{P}}^{\top}\hat{\bm{G}}^{a}||_{0}+||{\bm{G}}^{z}-\hat{\bm{P}}^{\top}\hat{\bm{G}}^{z}\hat{\bm{P}}||_{0})/(d_{a}d_{z}+d_{z}^{2})$,
where $\hat{\bm{P}}$ is the permutation found by MCC and
$(d_{a}d_{z}+d_{z}^{2})$ is the maximal number of edges ${\bm{G}}$ can have.

##  7 Related work

##### Linear and nonlinear ICA.

The first results showing latent variables can be identified up to permutation
and rescaling at least date back to classical linear ICA which assumes a
linear mixing function ${\bm{f}}$ and mutually independent and non-Gaussian
latent variables (Jutten and Herault, 1991; Tong et al., 1993; Comon, 1994).
Hyvärinen and Pajunen (1999) showed that when allowing ${\bm{f}}$ to be a
general nonlinear transformation, a setting known as nonlinear ICA, mutual
independence and non-Gaussianity alone are insufficient to identify the latent
variables. This inspired multiple variations of nonlinear ICA that enabled
identifiability by leveraging, e.g., nonstationarity (Hyvarinen and Morioka,
2016) and temporal dependencies (Hyvarinen and Morioka, 2017). Hyvärinen et
al. (2019) generalized these works by introducing a general data generating
process in which the latent variables are conditionally mutually independent
given an observed auxiliary variable (corresponding to ${\bm{a}}$ in our
work). These last three works rely on some form of noise contrastive
estimation (NCE) (Gutmann and Hyvärinen, 2012), but similar identifiability
results have also been shown for VAEs (Khemakhem et al., 2020a; Locatello et
al., 2020; Klindt et al., 2021), normalizing flows (Sorrenson et al., 2020)
and energy-based models (Khemakhem et al., 2020b).

##### Causal representation learning (static).

Since the publication of the first iteration of this work at CLeaR 2022, the
field now known as causal representation learning (CRL) (Schölkopf et al.,
2021) gained significant traction. The prototypical problem of CRL is similar
to nonlinear ICA in that the goal is to identify latent factors of variations,
but differs in that the latent variables are assumed to be related via a
causal graphical model (CGM) and interventions on the latents are typically
observed. While a few works assumed the causal graph structure is known
(Kocaoglu et al., 2018; Shen et al., 2022; Nair et al., 2019; Liang et al.,
2023), significant progress has been achieved recently in the setting where
the latent causal graph is unknown and must be inferred from single-node
interventions targeting the latent variables (Ahuja et al., 2023; Squires et
al., 2023; Buchholz et al., 2023; von Kügelgen et al., 2023; Zhang et al.,
2023; Jiang and Aragam, 2023; Varici et al., 2023b, a). In a similar spirit,
Liu et al. (2023); Yang et al. (2021) leverage a form of nonstationarity that
does not necessarily correspond to interventions and Bengio et al. (2020)
suggests using adaptation speed as a heuristic objective to disentangle latent
factors in the bivariate case, although without identifiability guarantees.
The above works do not support temporal dependencies, unlike the framework
presented in this work. While we do focus on temporal dependencies, the
special case where $T=1$ fleshed out in Examples 9, 10 & 12 can be categorized
as static CRL with independent latent factors, i.e. empty latent causal graph.
This approach has been applied to single-cell data with gene perturbations
(Lopez et al., 2023; Bereket and Karaletsos, 2023). Importantly, Example 12
illustrates how multi-node interventions on the latent factors can yield
(partial) disentanglement in the independent factors regime. To the best of
our knowledge, this constitutes the first identifiability guarantee from
multi-node interventions and should form an important step towards
generalizing to arbitrary latent graphs.

CRL is closely related to methods that assume access to paired observations
$({\bm{x}},{\bm{x}}^{\prime})$ that are generated from a common decoder
${\bm{f}}$. These are in contrast with the works discussed above which assume
the samples from observational and interventional distributions are unpaired.
In the paired data regime, Locatello et al. (2020) and Ahuja et al. (2022b)
assume that only a small set of latent factors $S\subseteq[d_{z}]$ changes
between ${\bm{x}}$ and ${\bm{x}}^{\prime}$. Interestingly, Locatello et al.
(2020) assume that, for all $i$, $P(S\cap S^{\prime}=\\{i\\})>0$ (for i.i.d
$S$ and $S^{\prime}$), which resembles our graphical criterion for complete
disentanglement (Definition 5). Karaletsos et al. (2016) proposed a related
strategy based on triplets of observations and weak labels indicating which
observation is closer to the reference in the (masked) latent space. Von
Kügelgen et al. (2021) modelled the self-supervised setting with data
augmentation using a similar idea and showed block-identifiability of the
latent variables shared among ${\bm{x}}$ and ${\bm{x}}^{\prime}$. Brehmer et
al. (2022) assumes that the latent variables are sampled from a structural
causal model (SCM) (Peters et al., 2017) and that ${\bm{x}}^{\prime}$ is
counterfactual in the sense that it is generated using the same SCM and
exogenous noise values as ${\bm{x}}$ except for some noises which are modified
randomly. Similar approaches can also provide identifiability guarantees in
the multi-view setting where the decoders for the different views ${\bm{x}}$
and ${\bm{x}}^{\prime}$ are allowed to be different (Gresele et al., 2020;
Daunhawer et al., 2023). The paired observations setting bears some similarity
with the temporal setting covered in this work since the pairs
$({\bm{x}}^{t},{\bm{x}}^{t-1})$ are observed jointly. However contrarily to
the above works, Theorems 3 & 5 allow all latent variables to change between
$t-1$ and $t$, only the temporal dependencies between them are assumed sparse.
Morioka and Hyvarinen (2023) can also be seen as paired CRL in which the
latents of different views can interact causally in an restricted manner.
Recently, Yao et al. (2023) generalized previous work by allowing more than
two views.

##### Leveraging temporal dependencies or non-stationarity.

Tong et al. (1990) proved identifiability of linear ICA when the latent factor
${\bm{z}}_{i}^{t}$ are correlated across time steps $t$ but remain independent
across components $i$, an idea that has been extended to nonlinear mixing
(Hyvarinen and Morioka, 2017; Klindt et al., 2021; Schell and Oberhauser,
2023). Using our notation, these works assume a diagonal adjacency matrix
${\bm{G}}^{z}$ which contrasts with Theorems 3 & 5 which allow for general
${\bm{G}}^{z}$ (although some graphs might not yield complete
disentanglement). Yao et al. (2022a, Theorem 1) also allows for general
${\bm{G}}^{z}$, but do not rely on sparsity of ${\bm{G}}^{z}$ nor sparse
interventions on the latent factors for identification. Instead, it relies on
conditional independence of ${\bm{z}}_{i}^{t}$ given ${\bm{z}}^{t-1}$ and on a
“sufficient variability” condition involving the third cross-derivatives
$\frac{\partial^{3}}{(\partial{\bm{z}}^{t}_{i})^{2}\partial{\bm{z}}^{t-1}_{j}}\log
p({\bm{z}}_{i}^{t}\mid{\bm{z}}^{t-1})$ which excludes simple Gaussian models
with homoscedastic variance like the ones we considered in Examples 8, 9, 11
and in our experiments of Section 8. General non-stationarity of the latent
distribution, i.e. that are not sparse like the type of non-stationarity
considered in this work, can also be used to identify the latent factors
(Hyvarinen and Morioka, 2016; Hyvärinen et al., 2019; Khemakhem et al., 2020a;
Hälvä and Hyvärinen, 2020; Morioka et al., 2021; Yao et al., 2022b, a), but
these results require sufficient variability of higher-order
derivatives/differences of the log-densities, which again typically exclude
simple homoscedastic Gaussian models (see Appendix D.2 for more). Ahuja et al.
(2022a) characterized the indeterminacies of the representation in dynamical
latent models to be the set of equivariances of the transition mechanism.
Apart from temporal dependencies, one can also consider latent factors
structured according to a spatial topology (Hälvä et al., 2021).

##### Dynamical causal representation learning:

The previous iteration of this work (Lachapelle et al., 2022) concurrently
with Lippe et al. (2022) introduced latent variables identifiability
guarantees for dynamical latent models based on sparse interventions. Lippe et
al. (2023b) later proposed a generalization in which instantaneous causal
connections are allowed. Key differences with the present work are (i) Lippe
et al. (2023b) considers interventions with known targets while the present
work (as well as Lachapelle et al. (2022)) consider interventions with unknown
targets; (ii) Lachapelle et al. (2022, Theorem 5) and Theorems 3 & 5 do not
need interventions to disentangle since they leverage sparsity of the temporal
dependencies, contrarily to Lippe et al. (2023b); (iii) Lippe et al. (2023b)
allows for instantaneous causal connections, unlike the present work; and (iv)
Lippe et al. (2023b) demonstrates their approach on image data. The concurrent
work of Volodin (2021) independently proposed a very similar approach which
also learns a sparse latent causal graph relating them together and to actions
using binary masks, but focuses on testing various algorithmic variants and
verifies empirically that the approach works on interactive environments
rather than on formal identifiability guarantees. Lopez et al. (2023); Lei et
al. (2023) found that such models adapt to sparse interventions more quickly
than their entangled counterparts. Keurti et al. (2023) discusses
disentanglement in the temporal regimes through the lens of group theory but
does not provide identifiability guarantees. Recently, Lippe et al. (2023a)
proposed a model similar to ours with disentanglement guarantees based on the
constraint that the effect of the variable ${\bm{a}}^{t-1}$ (analogous to $R$
in their work) on each ${\bm{z}}^{t}_{i}$ is mediated by a deterministic
binary variable.

##### Constraining the decoder function ${\bm{f}}$.

It is worth noting that one can also obtain disentanglement guarantees by
constraining the decoder function ${\bm{f}}$ in some way (Taleb and Jutten,
1999; Gresele et al., 2021; Buchholz et al., 2022; Leemann et al., 2023;
Lachapelle et al., 2023b; Horan et al., 2021). In particular, this can be
achieved by enforcing some form of sparsity on ${\bm{f}}$ (Moran et al., 2022;
Zheng et al., 2022; Brady et al., 2023; Xi and Bloem-Reddy, 2023). In
contrast, the present work assumes only that ${\bm{f}}$ is a general
diffeomorphism onto its image. Note that Zheng et al. (2022) reused many proof
strategies of the shorter version of this work (Lachapelle et al., 2022).

##### Disentanglement with explicit supervision.

Some works leverage more explicit supervision to disentangle. For example,
Ahuja et al. (2022c) assumes labels are given by a linear transformation of
mutually independent and non-Gaussian latent factors. Instead of relying on
independence, Lachapelle et al. (2023a); Fumero et al. (2023) leverage the
sparsity of the linear map to disentangle.

##### Other relevant works on sparsity.

The assumption that high-level variables are sparsely related to one another
and/or to actions was discussed by Bengio (2019); Goyal and Bengio (2021); Ke
et al. (2021). These ideas have been leveraged also by Goyal et al. (2021b,
a); Madan et al. (2021) via attention mechanisms. Although these works are, in
part, motivated by the same core assumption as ours, their focus is more on
empirically verifying out-of-distribution generalization than it is on
disentanglement (Definition 7) and formal identifiability results. The
assumption that individual actions often affect only one factor of variation
has been leveraged for disentanglement by Thomas et al. (2018). Loosely
speaking, the theory we developed in the present work can be seen as a formal
justification for such approaches.

##  8 Experiments

To illustrate our identifiability results and the benefit of mechanism
sparsity regularization for disentanglement, we apply the sparsity regularized
VAE method of Section 5 on various synthetic datasets. Section 8.1 focuses on
graphs satisfying the criterion of Assumption 5 which, as we saw, guarantees
complete disentanglement. We also verify experimentally that the sufficient
influence assumptions are indeed important for disentanglement and explore
latent model with both homoscedastic and heteroscedastic variance. Section 8.2
explores graphs that do not satisfy the criterion. Details about our
implementation are provided in Appendix C.2 and the code used to run these
experiments can be found here:
https://github.com/slachapelle/disentanglement_via_mechanism_sparsity.

##### Synthetic datasets.

The datasets we considered are separated in two groups: Action & Time
datasets. The former group has only auxiliary variables, which we interpret as
actions, without temporal dependence, we thus fix $\hat{{\bm{G}}}^{z}=\bm{0}$.
The latter group has only temporal dependence without actions, we thus fix
$\hat{{\bm{G}}}^{a}=\bm{0}$. In each dataset, the ground-truth mixing function
${\bm{f}}$ is a randomly initialized neural network. The dimensionality of
${\bm{z}}$ and ${\bm{x}}$ are $d_{z}=10$ and $d_{x}=20$, respectively. In the
action datasets, the dimensionality of ${\bm{a}}$ is $d_{a}=10$, unless
specified otherwise. The ground-truth transition model
$p({\bm{z}}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t})$ is always a Gaussian with a
mean outputted by some function ${\bm{\mu}}_{\bm{G}}({\bm{z}}^{t-1},a^{t-1})$
(the data is Markovian). For all datasets considered the covariance matrix is
given by $\sigma_{z}^{2}{\bm{I}}$, i.e. the variance if homoscedastic, except
for the datasets $\textnormal{ActionNonDiag}_{k=2}$ and
$\textnormal{TimeNonDiag}_{k=2}$ which have heteroscedastic variance. Appendix
C.1 provides a more detailed descriptions of the datasets including the
explicit form of ${\bm{\mu}}$ and ${\bm{G}}$ in each case. Note that the
learned transition model
$\hat{p}({\bm{z}}^{t}\mid{\bm{z}}^{t-1},{\bm{a}}^{t-1})$ is also an
homoscedastic Gaussian where the mean function $\hat{\bm{\mu}}$ is an MLP.

##### Baselines.

On the action datasets, we compare with TCVAE (Chen et al., 2018), iVAE
(Khemakhem et al., 2020a). Only iVAE leverages the action. On the temporal
datasets, we compare our approach with TCVAE, PCL (Hyvarinen and Morioka,
2017) and SlowVAE (Klindt et al., 2021). Only PCL and SlowVAE leverages the
temporal dependencies. We also report the performance of a randomly
initialized encoder (Random) and one trained via least-square regression
directly on the ground-truth latent factors (Supervised). See Appendix C.3 for
details on the baselines.

##### Unsupervised hyperparameter selection.

In practice, the hyperparameters cannot be selected so as to optimize MCC,
since this metric requires access to the ground-truth latent factors. Duan et
al. (2020) introduced unsupervised disentanglement ranking (UDR) as a solution
to unsupervised hyperparameter selection for disentanglement. Figures 5 & 7
shows the performance of all approaches using UDR to select the hyperparameter
(when it has one). For our approach, we show a range of sparsity bounds
$\beta$ and indicate the hyperparameter selected by UDR with a black star.
Note that, for our approach, we excluded from the UDR selection
hyperparameters that yielded graphs with fewer edges than latent factors, as a
heuristic to prevent UDR from selecting overly sparse graphs. Figures 5 & 7
show this unsupervised procedure selects a reasonable regularization level (as
indicated by the black star), although not always the optimal one. See
Appendix C.4 for details.

###  8.1 Graphs allowing complete disentanglement (satisfying Assumption 5)

Figure 5: Graphical criterion holds: Datasets ActionDiag and TimeDiag have
diagonal graphs while ActionNonDiag and TimeNonDiag have non-diagonal graphs.
Sufficient influence is always satisfied. For our regularized VAE approach, we
report performance for multiple sparsity levels $\beta$. In the left column,
only $\hat{{\bm{G}}}^{a}$ is learned while in the right column, only
$\hat{{\bm{G}}}^{z}$ is learned. For more details on the synthetic datasets,
see Appendix C.1. The black star indicates which regularization parameter is
selected by the filtered UDR procedure (see Appendix C.4). For $R$ and MCC,
higher is better. For SHD, lower is better. Performance is reported on 5
random seeds.

(a) ActionNonDiag dataset, $\beta=20$

(b) TimeNonDiag dataset, $\beta=50$

Figure 6: For each dataset, we visualize the median SHD run among the five
randomly initialized runs of Figure 5 with the sparsity level $\beta$ that is
the closest to the ground-truth sparsity level $||{\bm{G}}||_{0}$. For each
dataset, we visualize (i) the ground-truth graph, (ii) the permuted estimated
graph, (iii) the entanglement graph predicted by our theory, and (iv) the
permuted matrix of regression coefficients in absolute value normalized by the
maximum coefficient i.e.
${|\hat{\bm{L}}\hat{\bm{P}}|}/{\max_{i,j}|\hat{\bm{L}}_{i,j}|}$. In Figure
6(a), the estimated graph is exactly the ground-truth and
$|\hat{\bm{L}}\hat{\bm{P}}|$ is perfectly diagonal, indicating complete
disentanglement. In Figure 6(b), the learned graph is close but not equal to
the ground-truth. We can see that the off-diagonal nonzero values in
$|\hat{\bm{L}}\hat{\bm{P}}|$ align with the poorly estimated parts of the
graph.

##### Satisfying sufficient influence assumptions.

Figure 5 reports the MCC and $R$ scores of all methods on four datasets that
satisfy both the graphical criterion and the sufficient influence assumption:
the datasets ActionDiag and TimeDiag have “diagonal” graphs, i.e.
${\bm{G}}^{a}={\bm{I}}$ and ${\bm{G}}^{a}={\bm{I}}$, while ActionNonDiag and
TimeNonDiag present more involved graphs (depicted in Figure 6). Observations:
We see that the sparsity constraint improves MCC and SHD on all datasets.
Although most baselines obtain good $R$ scores, which indicates their
representation encodes all the information about the factors of variations,
they obtain poor MCC in comparison to our approach with a properly selected
sparsity level, which indicates they fail to disentangle. Moreover, the
sparsity level selected by UDR (indicated by a black star) corresponds to the
lowest SHD value for three out of four datasets and when it does not, it is
still better than no sparsity at all. Figure 6 shows examples of estimated
graphs. More details can be found in the caption.

##### Violating sufficient influence assumptions.

The left column of Table 3 reports performance of all methods on the
$\text{ActionNonDiag}_{\text{NoSuffInf}}$ and
$\text{TimeNonDiag}_{\text{NoSuffInf}}$ datasets, which are essentially the
same as ActionNonDiag and TimeNonDiag but do not satisfy the sufficient
influence assumptions (see Appendix C.1 for details). Observations: For the
$\text{ActionNonDiag}_{\text{NoSuffInf}}$ dataset, we still see an improvement
in MCC and SHD when regularizing for sparsity, but not as important as for
ActionNonDiag, which got $\text{MCC}\approx 1$ and $\text{SHD}\approx 0$.
Still, our approach outperforms the baselines. For the
$\text{TimeNonDiag}_{\text{NoSuffInf}}$ dataset, there is simply no
improvement in MCC from sparsity regularization. In that case, SlowVAE (with
hyperparameter selected to maximize MCC) and PCL have higher MCC. These
observations confirm the importance of the sufficient influence assumptions.

##### Heteroscedastic variance ($k=2$).

The right column of Table 3 reports performance of all methods on the
$\textnormal{ActionNonDiag}_{k=2}$ and $\textnormal{TimeNonDiag}_{k=2}$
datasets, which are essentially the same as ActionNonDiag and TimeNonDiag but
presents heteroscedastic variance, i.e.
$\text{var}({\bm{z}}^{t}\mid{\bm{z}}^{t-1},{\bm{a}}^{t-1})$ is not a constant
function of $({\bm{z}}^{t-1},{\bm{a}}^{t-1})$. This setting is interesting
since it is not covered by the exponential family theory of Lachapelle et al.
(2022) which assumed a one-dimensional sufficient statistic ${\bm{s}}$ ($k=1$)
whereas here we have $k=2$. Both datasets fall under the umbrella of our
nonparametric theory. However, $\textnormal{TimeNonDiag}_{k=2}$ cannot satisfy
the sufficient influence assumption because the data is Markovian and does not
present an auxiliary variable (see Remark 7). Observations: Both datasets
benefit from sparsity and outperform the baselines. On
$\textnormal{ActionNonDiag}_{k=2}$ we obtain near perfect MCC and SHD while on
$\textnormal{TimeNonDiag}_{k=2}$ we obtain performance similar to TimeNonDiag.
We hypothesize that the performance bottleneck in both TimeNonDiag and
$\textnormal{TimeNonDiag}_{k=2}$ is graph estimation, as in both cases SHD is
always greater than $\approx 20\%$.

Datasets | $\text{ActionNonDiag}_{\text{NoSuffInf}}$ | $\textnormal{ActionNonDiag}_{k=2}$
---|---|---
Metrics | SHD | MCC | $R$ | SHD | MCC | $R$
iVAE | – | .61$\pm$.02 | .97$\pm$.00 | – | .59$\pm$.03 | .94$\pm$.00
TCVAE (UDR) | – | .58$\pm$.03 | .88$\pm$.01 | – | .55$\pm$.02 | .96$\pm$.00
TCVAE (MCC) | – | .61$\pm$.02 | .96$\pm$.00 | – | .55$\pm$.02 | .96$\pm$.00
Ours (no sparsity) | .80$\pm$.00 | .62$\pm$.02 | .93$\pm$.00 | .80$\pm$.00 | .70$\pm$.03 | .97$\pm$.00
Ours (sparsity) | .13$\pm$.03 | .86$\pm$.04 | 1.0$\pm$.00 | .03$\pm$.01 | .98$\pm$.02 | 1.0$\pm$.00
Random | – | .37$\pm$.02 | .63$\pm$.02 | – | .37$\pm$.02 | .60$\pm$.02
Supervised | – | 1.0$\pm$.00 | 1.0$\pm$.00 | – | 1.0$\pm$.00 | 1.0$\pm$.00
Datasets | $\text{TimeNonDiag}_{\text{NoSuffInf}}$ | $\textnormal{TimeNonDiag}_{k=2}$
Metrics | SHD | MCC | $R$ | SHD | MCC | $R$
PCL | – | .66$\pm$.04 | .96$\pm$.00 | – | .58$\pm$.04 | .83$\pm$.01
SlowVAE (UDR) | – | .59$\pm$.02 | .98$\pm$.00 | – | .57$\pm$.01 | .93$\pm$.00
SlowVAE (MCC) | – | .71$\pm$.02 | .98$\pm$.00 | – | .58$\pm$.02 | .95$\pm$.00
TCVAE (UDR) | – | .58$\pm$.03 | .98$\pm$.00 | – | .57$\pm$.01 | .96$\pm$.00
TCVAE (MCC) | – | .58$\pm$.03 | .98$\pm$.00 | – | .57$\pm$.01 | .96$\pm$.00
Ours (no sparsity) | .45$\pm$.00 | .62$\pm$.04 | .98$\pm$.00 | .45$\pm$.00 | .62$\pm$.01 | .98$\pm$.00
Ours (sparsity) | .32$\pm$.05 | .63$\pm$.03 | .99$\pm$.00 | .20$\pm$.07 | .74$\pm$.04 | .98$\pm$.00
Random | – | .40$\pm$.04 | .67$\pm$.02 | – | .36$\pm$.01 | .59$\pm$.02
Supervised | – | 1.0$\pm$.00 | 1.0$\pm$.00 | – | 1.0$\pm$.00 | 1.0$\pm$.00

Table 3: Datasets $\text{ActionNonDiag}_{\text{NoSuffInf}}$ and
$\text{TimeNonDiag}_{\text{NoSuffInf}}$ do not satisfy their respective
sufficient influence assumptions (Assumptions 6 & 11). Datasets
$\textnormal{ActionNonDiag}_{k=2}$ and $\textnormal{TimeNonDiag}_{k=2}$ are
such that $\text{var}({\bm{z}}^{t}\mid{\bm{z}}^{t-1},{\bm{a}}^{t-1})$ depends
on ${\bm{z}}^{t-1}$ or ${\bm{a}}^{t-1}$ (which means the sufficient statistic
has dimension $k=2$, contrarily to all other datasets). For our method, we
show performance both with and without the sparsity constraint. In the former
case, the constraint is set to the number of edges in the ground-truth graph.
For baselines that have hyperparameters, we report their performance with the
hyperparameter configurations that maximize UDR and MCC.

###  8.2 Graphs allowing only partial disentanglement (not satisfying
Assumption 5)

In this section, we explore datasets with graphs that do not satisfy the
criterion of Assumption 5. This means our theory can only guarantee a form a
partial disentanglement. For this reason, we will report the $R_{\text{con}}$
metric introduced in Section 6 which measures whether two representations are
${\bm{a}}$-consistent (Definition 13) or ${\bm{z}}$-consistent (Definition
14).

##### Satisfying sufficient influence assumptions.

Figure 7 reports the MCC, $R_{\text{con}}$ and $R$ scores of all methods on
four datasets that satisfy the sufficient influence assumption but not the
graphical criterion: the datasets ActionBlockDiag and TimeBlockDiag have
“block diagonal” graphs, while ActionBlockNonDiag and TimeBlockNonDiag have
more intricate graphs (depicted in Figure 8). See Appendix C.1 for details
about the datasets. Observations: In all four datasets, some sparsity level
yields near perfect $R_{\text{con}}$, indicating the learned models are
approximately ${\bm{a}}$-consistent or ${\bm{z}}$-consistent to the ground-
truth. Morevover, SHD is correlated with $R_{\text{con}}$. Without surprise,
MCC never comes close to one since complete disentanglement is not guaranteed
by our theory. Analogously to Figure 5, the baselines have decent $R$ values
but very low MCC and $R_{\text{con}}$, indicating they cannot achieve partial
disentanglement. Figure 8 shows examples of estimated graph. When it comes to
hyperparameter selection, UDR selects the hyperparameter with the lowest SHD
on three out of four datasets, which indicates that UDR does reasonably well.

Figure 7: Graphical criterion does not hold: Datasets ActionBlockDiag and
TimeBlockDiag have block-diagonal graphs while ActionBlockNonDiag and
TimeBlockNonDiag have non-diagonal graphs. Sufficient influence is always
satisfied. In the left column, only $\hat{{\bm{G}}}^{a}$ is learned and we
vary $\beta_{a}$, and in the right column, only $\hat{{\bm{G}}}^{z}$ is
learned and we vary $\beta_{z}$. For more details on the synthetic datasets,
see Appendix C.1. The black star indicates which regularization parameter is
selected by the filtered UDR procedure (see Appendix C.4). For $R$ and MCC,
higher is better. For SHD, lower is better. Performance is reported on 5
random seeds.

(a) ActionBlockNonDiag dataset, $\beta=10$

(b) TimeBlockNonDiag dataset, $\beta=30$

Figure 8: For each dataset, we visualize the median SHD run among the five
randomly initialized runs of Figure 7 with the sparsity level $\beta$ that is
the closest to the ground-truth sparsity level $||{\bm{G}}||_{0}$. For each
dataset, we visualize (i) the ground-truth graph, (ii) the permuted estimated
graph, (iii) the entanglement graph predicted by our theory, and (iv) the
permuted matrix of regression coefficients in absolute value normalized by the
maximum coefficient i.e.
${|\hat{\bm{L}}\hat{\bm{P}}|}/{\max_{i,j}|\hat{\bm{L}}_{i,j}|}$. For both
datasets, the learn graph is very close to the ground-truth. Furthermore, the
match between the zero entries of $\hat{\bm{L}}\hat{\bm{P}}$ and those of the
theoretical entanglement graph ${\bm{C}}$ is very good, although not perfect.
Notice how certain blocks of latent factors remain entangled, as predicted by
the theory.

ActionRandomGraphs
---
| Without sparsity | With sparsity |
$p(\text{edge})$ | MCC | $R_{\text{con}}$ | $R$ | MCC | $R_{\text{con}}$ | $R$ | SHD | ${\mathbb{E}}||{\bm{V}}||_{0}$
$10\%$ | .58$\pm$.13 | .61$\pm$.11 | .68$\pm$.13 | .69$\pm$.14 | .70$\pm$.12 | .70$\pm$.12 | .00$\pm$.00 | 45.0
$20\%$ | .67$\pm$.06 | .69$\pm$.05 | .83$\pm$.08 | .85$\pm$.08 | .86$\pm$.08 | .86$\pm$.09 | .01$\pm$.01 | 25.8
$40\%$ | .67$\pm$.03 | .70$\pm$.03 | .93$\pm$.04 | .94$\pm$.05 | .95$\pm$.05 | .98$\pm$.04 | .06$\pm$.05 | 15.8
$60\%$ | .69$\pm$.06 | .73$\pm$.05 | .96$\pm$.00 | .88$\pm$.07 | .91$\pm$.05 | .99$\pm$.01 | .14$\pm$.08 | 15.8
$90\%$ | .63$\pm$.04 | .81$\pm$.08 | .97$\pm$.00 | .60$\pm$.01 | .78$\pm$.07 | .97$\pm$.00 | .21$\pm$.07 | 45.0
TimeRandomGraphs
| Without sparsity | With sparsity |
$p(\text{edge})$ | MCC | $R_{\text{con}}$ | $R$ | MCC | $R_{\text{con}}$ | $R$ | SHD | ${\mathbb{E}}||{\bm{V}}||_{0}$
$10\%$ | .66$\pm$.03 | .66$\pm$.03 | .98$\pm$.00 | 1.0$\pm$.00 | 1.0$\pm$.00 | 1.0$\pm$.00 | .01$\pm$.02 | 10.2
$20\%$ | .63$\pm$.05 | .63$\pm$.05 | .98$\pm$.00 | .99$\pm$.01 | .99$\pm$.01 | .99$\pm$.00 | .08$\pm$.09 | 10.2
$40\%$ | .61$\pm$.02 | .61$\pm$.02 | .98$\pm$.00 | .82$\pm$.16 | .82$\pm$.16 | .98$\pm$.01 | .27$\pm$.13 | 10.2
$60\%$ | .58$\pm$.02 | .58$\pm$.02 | .98$\pm$.00 | .71$\pm$.12 | .71$\pm$.12 | .98$\pm$.00 | .33$\pm$.06 | 10.4
$90\%$ | .58$\pm$.03 | .63$\pm$.08 | .98$\pm$.00 | .58$\pm$.02 | .63$\pm$.08 | .98$\pm$.00 | .20$\pm$.07 | 26.1

Table 4: Experiments with randomly generated graphs. The probability of
sampling an edge is $p(\text{edge})$. We report an estimation of
${\mathbb{E}}||{\bm{V}}||_{0}$ which is the average number of edges in the
entanglement graph ${\bm{V}}$ entailed by the random ground-truth graph
${\bm{G}}$.

##### Random graphs of varying sparsity levels.

In Table 4, we consider the same ${\bm{\mu}}$ functions as in datasets
ActionNonDiag and TimeNonDiag, but explore more diverse randomly generated
ground-truth graphs with various degrees of sparsity. Edges are sampled i.i.d.
with some probability $p(\text{edge})$. However note that, for
TimeRandomGraphs dataset, the self-loops are presents with probability one. We
report the performance of our approach both with and without sparsity
regularization. When using sparsity, we set the $\beta$ equal to the ground-
truth number of edges $||{\bm{G}}||_{0}$. Observations: First, all datasets
obtain an improvement in MCC and $R_{\text{con}}$ from sparsity
regularization, except for the very dense graphs with $p(\text{edge})=90\%$,
in which case regularization does nothing or slightly degrades performance.
Secondly, we can see that the SHD tends to be higher for larger graphs,
suggesting these are harder to learn. Thirdly, in the ActionRandomGraphs
datasets, we can see a negative correlation between MCC and
${\mathbb{E}}||{\bm{V}}||_{0}$, which is expected since $||{\bm{V}}||_{0}$
close to 10 means complete disentanglement is possible (assuming the graph is
learned properly). This pattern also appears to some extent in the
TimeRandomGraphs datasets. Notice how, among the TimeRandomGraphs datasets,
all datasets sparser than $p(\text{edge})=90\%$ always have
${\mathbb{E}}||{\bm{V}}||_{0}\approx 10$, indicating complete disentanglement
should be possible.777We suspect this occurs because the self-loops which are
present with probability one, unlike the Action dataset. This is confirmed by
very high MCC, at least for sparser graphs which are learned properly.
Finally, we note that the $R$ score is low for the very sparse action
datasets. We suspect this is because very sparse graphs are less likely to
satisfy the assumption of sufficient variability (Theorem 4) which guarantees
quasi-linear equivalence (here it is actually linear equivalence, because of
Gaussianity). Indeed, for very sparse graphs, some latent factors might end up
without parents. This is not the case in the time datasets because of the
self-loops which are always presents.

##  9 Conclusion

This work proposed a novel principle for disentanglement based on mechanism
sparsity regularization. The idea is based on the assumption that the
mechanisms that govern the dynamics of high-level concepts are often sparse:
actions usually affect only a few entities and objects usually interact
sparsely with each other. We provided novel nonparametric identifiability
guarantees for this setting which gives sufficient conditions for
disentanglement, whether complete or partial. Given the dependency structure
between latent factors and auxiliary variables, our theory predicts the
entanglement graph describing which estimated latent factors are expected to
remain entangled. This constitutes a significant extension of the shorter
version of this work (Lachapelle et al., 2022). We further provide various
examples to illustrates the consequences of our guarantees as well as the
assumptions it relies on. For instance, we show that multi-node interventions
with unknown targets fall under the umbrella of our framework. Finally, we
demonstrate the theory experimentally by training a sparsity-constrained
variational autoencoder on synthetic data, which allows us to explore various
settings. Our work establishes a solid theoretical grounding for further
empirical investigations in more realistic scenarios, such as single-cell data
with gene perturbations (Lopez et al., 2023) and video (Lei et al., 2023).
Future works include relaxing assumptions such as conditional independence or
considering more permissive settings such as “contextual sparsity”, i.e., the
assumption that objects only interact with each other in particular
situations. We believe the latter could be formalized and leveraged for
disentanglement using the tools developed in this work.

Acknowledgments and Disclosure of Funding

The authors would like to thank Aristide Baratin for important feedback on the
manuscript. This research was partially supported by the Canada CIFAR AI Chair
Program, by an IVADO excellence PhD scholarship, by a Google Focused Research
award, the German Federal Ministry of Education and Research (BMBF): Tübingen
AI Center, FKZ: 01IS18039A, and by Mitacs through the Mitacs Accelerate
program. The experiments were in part enabled by computational resources
provided by Calcul Quebec and the Digital Research Alliance of Canada. The
authors would like to thank Yoshua Bengio for inspiring mechanism sparsity
regularization through various talks and discussions. The authors would also
like to thank the International Max Planck Research School for Intelligent
Systems (IMPRS-IS) for supporting Yash Sharma. Simon Lacoste-Julien is a CIFAR
Associate Fellow in the Learning in Machines & Brains program.

Table 5: Table of Notation. Calligraphic & indexing conventions
---
$[n]$ | $:=$ |  $\\{1,2,\dots,n\\}$
$x$ |  |  Scalar (random or not, depending on context)
${\bm{x}}$ |  |  Vector (random or not, depending on context)
${\bm{X}}$ |  |  Matrix
${\mathcal{X}}$ |  |  Set/Support
$f$ |  |  Scalar-valued function
${\bm{f}}$ |  |  Vector-valued function
$Df$, $D{\bm{f}}$ |  |  Jacobian of $f$ and ${\bm{f}}$
$D^{2}f$ |  |  Hessian of $f$
$B\subseteq[n]$ |  |  Subset of indices
${\bm{x}}_{B}$ |  |  Vector formed with the $i$th coordinates of ${\bm{x}}$, for all $i\in B$
${\bm{X}}_{B,B^{\prime}}$ |  |  Matrix formed with the entries $(i,j)\in B\times B^{\prime}$ of ${\bm{X}}$.
Recurrent notation
${\bm{x}}^{t}\in{\mathbb{R}}^{d_{x}}$ |  |  Observation at time $t$
${\bm{x}}^{\leq t}\in{\mathbb{R}}^{d_{x}\times t}$ |  |  Matrix of observations at times $1,\dots,t$
${\bm{z}}^{t}\in{\mathbb{R}}^{d_{z}}$ |  |  Vector of latent factors of variations at time $t$
${\bm{z}}^{\leq t}\in{\mathbb{R}}^{d_{z}\times t}$ |  |  Matrix of latent vectors at times $1,\dots,t$
${\bm{a}}^{t}\in{\mathbb{R}}^{d_{a}}$ |  |  Vector of auxiliary variables at time $t$
${\bm{a}}^{<t}\in{\mathbb{R}}^{d_{a}\times t}$ |  |  Matrix of auxiliary vectors at times $0,1\dots,t-1$
${\mathcal{A}}\subseteq{\mathbb{R}}^{d_{a}}$ |  |  Support of ${\bm{a}}^{t}$
${\bm{f}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{x}}$ |  |  Ground-truth decoder function
$\hat{\bm{f}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{d_{x}}$ |  |  Learned decoder function
$p({\bm{z}}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t})$ |  |  Ground-truth latent transition model
$\hat{p}({\bm{z}}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t})$ |  |  Learned latent transition model
${\bm{G}}^{a}\in\\{0,1\\}^{d_{z}\times d_{a}}$ |  |  Ground-truth adjacency matrix of graph connecting ${\bm{a}}^{<t}$ to ${\bm{z}}^{t}$
${\bm{G}}^{z}\in\\{0,1\\}^{d_{z}\times d_{z}}$ |  |  Ground-truth adjacency matrix of graph connecting ${\bm{z}}^{<t}$ to ${\bm{z}}^{t}$
$\hat{\bm{G}}^{a},\hat{\bm{G}}^{z}$ |  |  Learned adjacency matrices
${\bf Pa}_{i}^{a}\subseteq[d_{a}]$ |  |  Parents of ${\bm{z}}^{t}_{i}$ in ${\bm{G}}^{a}$
${\bf Ch}_{\ell}^{a}\subseteq[d_{z}]$ |  |  Children of ${\bm{a}}^{t}_{\ell}$ in ${\bm{G}}^{z}$
${\bf Pa}_{i}^{z}\subseteq[d_{z}]$ |  |  Parents of ${\bm{z}}^{t}_{i}$ in ${\bm{G}}^{z}$
${\bf Ch}_{i}^{z}\subseteq[d_{z}]$ |  |  Children of ${\bm{z}}^{t-1}_{i}$ in ${\bm{G}}^{z}$
$D^{t}_{z}\log p\in{\mathbb{R}}^{1\times d_{z}}$ |  |  Jacobian vector of $\log p({\bm{z}}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t})$ w.r.t. ${\bm{z}}^{t}$
$H^{t,\tau}_{z,a}\log p\in{\mathbb{R}}^{d_{z}\times d_{a}}$ |  |  Hessian matrix of $\log p({\bm{z}}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t})$ w.r.t. ${\bm{z}}^{t}$ and ${\bm{a}}^{\tau}$
$H^{t,\tau}_{z,z}\log p\in{\mathbb{R}}^{d_{z}\times d_{z}}$ |  |  Hessian matrix of $\log p({\bm{z}}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t})$ w.r.t. ${\bm{z}}^{t}$ and ${\bm{z}}^{\tau}$
$\sigma:[d_{z}]\rightarrow[d_{z}]$ |  |  A permutation
Topology
$\overline{{\mathcal{X}}}$ |  |  Closure of the set ${\mathcal{X}}\subseteq{\mathbb{R}}^{n}$
${\mathcal{X}}^{\circ}$ |  |  Interior of the set ${\mathcal{X}}\subseteq{\mathbb{R}}^{n}$

##  Appendix A Identifiability theory - Nonparametric case

###  A.1 Useful Lemmas

######  Definition 18 (Regular closed set)

A set $A\subseteq{\mathbb{R}}^{n}$ is regular closed when it is equal to the
closure of its interior, i.e. $\overline{A^{\circ}}=A$.

###### Lemma 4

Let $A\subseteq{\mathbb{R}}^{n}$ and ${\bm{f}}:A\rightarrow{\mathbb{R}}^{m}$
be a $C^{k}$ function. Then, its $k$ first derivatives is uniquely defined on
$\overline{A^{\circ}}$ in the sense that they do not depend on the specific
choice of $C^{k}$ extension.

Proof Let ${\bm{g}}:U\rightarrow{\mathbb{R}}^{n}$ and
${\bm{h}}:V\rightarrow{\mathbb{R}}^{n}$ be two $C^{k}$ extensions of
${\bm{f}}$ to $U\subseteq{\mathbb{R}}^{n}$ and $V\subseteq{\mathbb{R}}^{n}$
both open in ${\mathbb{R}}^{n}$. By definition,

$\displaystyle{\bm{g}}({\bm{x}})={\bm{f}}({\bm{x}})={\bm{h}}({\bm{x}}),\
\forall{\bm{x}}\in A\,.$ (72)

The usual derivative is uniquely defined on the interior of the domain, so
that

$\displaystyle D{\bm{g}}({\bm{x}})=D{\bm{f}}({\bm{x}})=D{\bm{h}}({\bm{x}}),\
\forall{\bm{x}}\in A^{\circ}\,.$ (73)

Consider a point ${\bm{x}}_{0}\in\overline{A^{\circ}}$. By definition of
closure, there exists a sequence $\\{{\bm{x}}_{k}\\}_{k=1}^{\infty}\subseteq
A^{\circ}$ s.t. $\lim_{k\rightarrow\infty}{\bm{x}}_{k}={\bm{x}}_{0}$. We thus
have that

$\displaystyle\lim_{k\to\infty}D{\bm{g}}({\bm{x}}_{k})$
$\displaystyle=\lim_{k\to\infty}D{\bm{h}}({\bm{x}}_{k})$ (74) $\displaystyle
D{\bm{g}}({\bm{x}}_{0})$ $\displaystyle=D{\bm{h}}({\bm{x}}_{0})\,,$ (75)

where we used the fact that the derivatives of ${\bm{g}}$ and ${\bm{h}}$ are
continuous to go to the second line. Thus, all the $C^{k}$ extensions of
${\bm{f}}$ must have equal derivatives on $\overline{A^{\circ}}$. This means
we can unambiguously define the derivative of ${\bm{f}}$ everywhere on
$\overline{A^{\circ}}$ to be equal to the derivative of one of its $C^{k}$
extensions.

Since ${\bm{f}}$ is $C^{k}$, its derivative $D{\bm{f}}$ is $C^{k-1}$, we can
thus apply the same argument to get that the second derivative of ${\bm{f}}$
is uniquely defined on $\overline{\overline{A^{\circ}}^{\circ}}$. It can be
shown that $\overline{\overline{A^{\circ}}^{\circ}}=\overline{A^{\circ}}$. One
can thus apply the same argument recursively to show that the first $k$
derivatives of ${\bm{f}}$ are uniquely defined on $\overline{A^{\circ}}$.

###### Lemma 5

Let $X$ be some set. A family of functions
$(f_{i}:X\rightarrow{\mathbb{R}})_{i=1}^{n}$ is linearly independent if and
only if there exists $x_{1},...,x_{n}\in X$ such that the family of vectors
$((f_{1}(x_{i}),...,f_{n}(x_{i})))_{i=1}^{n}$ is linearly independent.

Proof We start by proving the “if” part. Assume the functions are linearly
dependent. Then there exists $\bm{\alpha}\not=0$ such that, for all $x\in X$,
$\sum_{i=1}^{n}\bm{\alpha}_{i}f_{i}(x)=0$. Choose distinct $x_{1},...,x_{n}\in
X$. We have thus have that for all $j\in[n]$,
$\sum_{i=1}^{n}\bm{\alpha}_{i}f_{i}(x_{j})=0$. This can be written in matrix
form:

$\displaystyle\begin{bmatrix}f_{1}(x_{1})&\cdots&f_{1}(x_{n})\\\
\vdots&\ddots&\vdots\\\
f_{n}(x_{1})&\cdots&f_{n}(x_{n})\end{bmatrix}\bm{\alpha}=\bm{0}\,,$ (76)

which implies that the columns are linearly dependent.

We now show the “only if” part. Suppose that for all
$\\{x_{1},\dots,x_{n}\\}\subseteq X$, the family of vectors
$((f_{1}(x_{i}),...,f_{n}(x_{i})))_{i=1}^{n}$ is linearly dependent. This
means that the set $U=\mathrm{span}\\{(f_{1}(x),...,f_{n}(x))\mid x\in X\\}$
is a proper linear subspace of ${\mathbb{R}}^{n}$. This means that there is a
nonzero $u\in U^{\perp}$, the orthogonal complement of $U$. By definition, $u$
is orthogonal to all elements in $\\{(f_{1}(x),...,f_{n}(x))\mid x\in X\\}$.
In other words, for all $x\in X$, $\sum_{i=1}^{n}u_{i}f_{i}(x)=0$. Hence the
${\bm{f}}_{i}$ are linearly dependent.

###  A.2 Proof of Proposition 1

See 1

Proof The “$\implies$” direction holds because since we can simply
differentiate ${\bm{h}}_{i}({\bm{a}})=\bar{\bm{h}}_{i}({\bm{a}}_{-j})$ w.r.t.
${\bm{a}}_{j}$ to get zero.

We now show the “$\impliedby$” direction. Suppose that for all
${\bm{a}}\in{\mathbb{R}}^{n}$, $D{\bm{h}}({\bm{a}})_{i,j}=0$. We must now show
that ${\bm{h}}_{i}({\bm{a}})$ is constant in ${\bm{a}}_{j}$ for all
${\bm{a}}_{-j}$. Choose any ${\bm{a}}^{0},{\bm{a}}^{1}\in{\mathbb{R}}^{n}$
such that ${\bm{a}}^{0}_{-j}={\bm{a}}^{1}_{-j}$. Thanks to the fundamental
theorem of calculus, we can write

$\displaystyle{\bm{h}}_{i}({\bm{a}}^{1})-{\bm{h}}_{i}({\bm{a}}^{0})$
$\displaystyle=\int_{[0,1]}\frac{d}{d\alpha}{\bm{h}}_{i}((1-\alpha){\bm{a}}^{0}+\alpha{\bm{a}}^{1}))d\alpha$
(77)
$\displaystyle=\int_{[0,1]}\underbrace{D{\bm{h}}((1-\alpha){\bm{a}}^{0}+\alpha{\bm{a}}^{1})_{i,\cdot}}_{\text{zero
at $j$}}\cdot\underbrace{({\bm{a}}^{1}-{\bm{a}}^{0})}_{\text{zero except at
$j$}}d\alpha$ (78) $\displaystyle=0\,.$ (79)

Since ${\bm{a}}^{0}$ and ${\bm{a}}^{1}$ were arbitrary points such that
${\bm{a}}^{0}_{-j}={\bm{a}}^{1}_{-j}$, this means the function
${\bm{h}}_{i}({\bm{a}})$ is constant in ${\bm{a}}_{j}$ for all values of
${\bm{a}}_{-j}$.

###  A.3 Proof of Proposition 2

In this section, we prove Proposition 2. Before doing so, we first recall the
definition of the support of a random variable (Definition 19) and prove a
useful lemma (Lemma 6).

###### Definition 19

(Support of a random variable) Let ${\bm{x}}$ be a random variable with values
in $\mathbb{R}^{n}$ with distribution ${\mathbb{P}}_{\bm{x}}$. Let
$\mathcal{O}_{n}$ be the standard topology of $\mathbb{R}^{n}$ (i.e. the set
of open sets of $\mathbb{R}^{n}$). The support of ${\bm{x}}$ is defined as

$\displaystyle\textnormal{supp(${\bm{x}}$)}:=\\{{\bm{x}}\in\mathbb{R}^{n}\mid{\bm{x}}\in
O\in\mathcal{O}_{n}\implies{\mathbb{P}}_{\bm{x}}(O)>0\\}\,.$ (80)

###### Lemma 6

Let ${\bm{z}}$ be a random variable with values in ${\mathbb{R}}^{m}$ with
distribution ${\mathbb{P}}_{\bm{z}}$ and ${\bm{y}}:={\bm{f}}({\bm{z}})$ where
${{\bm{f}}:\textnormal{supp}({\bm{z}})\rightarrow{\mathbb{R}}^{n}}$ is a
homeomorphism onto its image. Then

$\displaystyle{\bm{f}}(\textnormal{supp}({\bm{z}}))\subseteq\textnormal{supp}({\bm{y}})\subseteq\overline{{\bm{f}}(\textnormal{supp}({\bm{z}}))}\,.$
(81)

where the closure is taken w.r.t. to the topology of ${\mathbb{R}}^{n}$.

Proof We first prove that
$f(\text{supp}({\bm{z}}))\subseteq\text{supp}({\bm{y}})$. Let
${\bm{y}}^{0}\in{\bm{f}}(\text{supp}({\bm{z}}))$ and $N$ be an open
neighborhood of ${\bm{y}}^{0}$, i.e. ${\bm{y}}^{0}\in N\in{\mathcal{O}}_{n}$.
Note that there exists ${\bm{z}}^{0}\in\text{supp}({\bm{z}})$ such that
${\bm{f}}({\bm{z}}^{0})={\bm{y}}^{0}$. Note that
${{\bm{z}}^{0}\in{\bm{f}}^{-1}(\\{{\bm{y}}^{0}\\})\subseteq{\bm{f}}^{-1}(N)}$
and that, by continuity of ${\bm{f}}$, ${\bm{f}}^{-1}(N)$ is an open
neighborhood of ${\bm{z}}^{0}$. Since ${\bm{z}}^{0}\in\text{supp}({\bm{z}})$,
we have

$\displaystyle 0$ $\displaystyle<{\mathbb{P}}_{\bm{z}}(f^{-1}(N))$ (82)
$\displaystyle={\mathbb{P}}_{\bm{z}}\circ f^{-1}(N)$ (83)
$\displaystyle={\mathbb{P}}_{\bm{y}}(N)\,.$ (84)

Hence ${\bm{y}}^{0}\in\text{supp}({\bm{y}})$, which concludes the
“$\subseteq$” part.

We now prove the other inclusion. Let
${\bm{y}}^{0}\in\textnormal{supp}({\bm{y}})$ and suppose, by contradiction,
that ${\bm{y}}^{0}\not\in\overline{{\bm{f}}(\textnormal{supp}({\bm{z}}))}$.
Since $\overline{{\bm{f}}(\textnormal{supp}({\bm{z}}))}$ is closed in
${\mathbb{R}}^{n}$, there exists $N$ s.t. ${\bm{y}}^{0}\in
N\in{\mathcal{O}}_{n}$ with
$N\cap\overline{{\bm{f}}(\textnormal{supp}({\bm{z}}))}=\emptyset$. Since
${\bm{y}}^{0}\in\textnormal{supp}({\bm{y}})$,

$\displaystyle 0$ $\displaystyle<{\mathbb{P}}_{\bm{y}}(N)$ (85)
$\displaystyle={\mathbb{P}}_{\bm{z}}({\bm{f}}^{-1}(N))$ (86)
$\displaystyle={\mathbb{P}}_{\bm{z}}(\emptyset)=0\,.$ (87)

The above contradiction implies that
${\bm{y}}^{0}\in\overline{{\bm{f}}(\textnormal{supp}({\bm{z}}))}$.

See 2

Proof

Equality of Denoised Distributions. Given an arbitrary
${\bm{a}}^{<T}\in{\mathcal{A}}^{T}$ and a parameter
${\bm{\theta}}=({\bm{f}},p,{\bm{G}})$, let ${\mathbb{P}}_{{\bm{x}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}}$ be the conditional probability
distribution of ${\bm{x}}^{\leq T}$, let ${\mathbb{P}}_{{\bm{z}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}}$ be the conditional probability
distribution of ${\bm{z}}^{\leq T}$ and let ${\mathbb{P}}_{{\bm{n}}^{\leq T}}$
be the probability distribution of ${\bm{n}}^{\leq T}$ (the Gaussian noises
added on ${\bm{f}}({\bm{z}}^{\leq T})$, defined in Sec. 2.1). Let
${{\bm{y}}^{t}:={\bm{f}}({\bm{z}}^{t})}$ and ${\mathbb{P}}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}}$ be its conditional probability
distribution. First, notice that

$\displaystyle\mathbb{P}_{{\bm{x}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}}=\mathbb{P}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}}*{\mathbb{P}}_{{\bm{n}}^{\leq T}}\,,$ (88)

where $*$ is the convolution operator between two measures. We now show that
if two models agree on the observations, i.e. $\mathbb{P}_{{\bm{x}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}}=\mathbb{P}_{{\bm{x}}^{\leq
T}\mid{\bm{a}}^{<T};\hat{{\bm{\theta}}}}$, then $\mathbb{P}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}}=\mathbb{P}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};\hat{{\bm{\theta}}}}$. The following argument makes use of
the Fourier transform $\mathcal{F}$ generalized to arbitrary probability
measures. This tool is necessary to deal with measures which do not have a
density w.r.t either the Lebesgue or the counting measure, as is the case of
$\mathbb{P}_{{\bm{y}}^{\leq T}\mid{\bm{a}}^{<T};{\bm{\theta}}}$ (all its mass
is concentrated on the set ${\bm{f}}({\mathbb{R}}^{d_{z}})$). See Pollard
(2001, Chapter 8) for an introduction and useful properties.

$\displaystyle\mathbb{P}_{{\bm{x}}^{\leq T}\mid{\bm{a}}^{<T};{\bm{\theta}}}$
$\displaystyle=\mathbb{P}_{{\bm{x}}^{\leq
T}\mid{\bm{a}}^{<T};\hat{{\bm{\theta}}}}$ (89)
$\displaystyle\mathbb{P}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}}*{\mathbb{P}}_{{\bm{n}}^{\leq T}}$
$\displaystyle=\mathbb{P}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};\hat{{\bm{\theta}}}}*{\mathbb{P}}_{{\bm{n}}^{\leq T}}$
(90) $\displaystyle\mathcal{F}(\mathbb{P}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}}*{\mathbb{P}}_{{\bm{n}}^{\leq T}})$
$\displaystyle=\mathcal{F}(\mathbb{P}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};\hat{{\bm{\theta}}}}*{\mathbb{P}}_{{\bm{n}}^{\leq T}})$
(91) $\displaystyle\mathcal{F}(\mathbb{P}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}})\mathcal{F}({\mathbb{P}}_{{\bm{n}}^{\leq
T}})$ $\displaystyle=\mathcal{F}(\mathbb{P}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};\hat{{\bm{\theta}}}})\mathcal{F}({\mathbb{P}}_{{\bm{n}}^{\leq
T}})$ (92) $\displaystyle\mathcal{F}(\mathbb{P}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}})$
$\displaystyle=\mathcal{F}(\mathbb{P}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};\hat{{\bm{\theta}}}})$ (93)
$\displaystyle\mathbb{P}_{{\bm{y}}^{\leq T}\mid{\bm{a}}^{<T};{\bm{\theta}}}$
$\displaystyle=\mathbb{P}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};\hat{{\bm{\theta}}}}\,,$ (94)

where (91) & (94) use the fact that the Fourier transform is invertible, (92)
is an application of the fact that the Fourier transform of a convolution is
the product of their Fourier transforms and (93) holds because the Fourier
transform of a Normal distribution is nonzero everywhere. Note that the latter
argument holds because we assume $\sigma^{2}$, the variance of the Gaussian
noise added to ${\bm{y}}^{t}$, is the same for both models. Notice that, since
${\bm{f}}({\mathbb{R}}^{d_{z}})$ and $\hat{\bm{f}}({\mathbb{R}}^{d_{z}})$ are
closed in ${\mathbb{R}}^{d_{x}}$ and the support of ${\bm{z}}^{\leq T}$ is
${\mathbb{R}}^{d_{z}\times T}$, Lemma 6 implies that

$\displaystyle{\bm{f}}({\mathbb{R}}^{d_{z}\times
T})=\text{supp}(\mathbb{P}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}})\quad\quad\&\quad\quad\text{supp}(\mathbb{P}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};\hat{{\bm{\theta}}}})=\hat{{\bm{f}}}({\mathbb{R}}^{d_{z}\times
T})$ (95)

where we overloaded the notation by defining ${\bm{f}}({\bm{z}}^{\leq
T}):=({\bm{f}}({\bm{z}}^{1}),...,{\bm{f}}({\bm{z}}^{T}))$ and analogously for
$\hat{{\bm{f}}}({\bm{z}}^{\leq T})$. Since both measure in (94) are equal,
their supports must also be. This implies that
${\bm{f}}({\mathbb{R}}^{d_{z}})=\hat{\bm{f}}({\mathbb{R}}^{d_{z}})$, which is
part of the definition of equivalence up to diffeomorphism (Definition 5).

Equality of densities. Continuing with (94),

$\displaystyle{\mathbb{P}}_{{\bm{y}}^{\leq T}\mid{\bm{a}}^{<T};{\bm{\theta}}}$
$\displaystyle={\mathbb{P}}_{{\bm{y}}^{\leq
T}\mid{\bm{a}}^{<T};\hat{{\bm{\theta}}}}$ (96)
$\displaystyle{\mathbb{P}}_{{\bm{z}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}}\circ{\bm{f}}^{-1}$
$\displaystyle={\mathbb{P}}_{{\bm{z}}^{\leq
T}\mid{\bm{a}}^{<T};\hat{{\bm{\theta}}}}\circ\hat{{\bm{f}}}^{-1}$ (97)
$\displaystyle{\mathbb{P}}_{{\bm{z}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}}\circ{{\bm{f}}}^{-1}\circ\hat{\bm{f}}$
$\displaystyle={\mathbb{P}}_{{\bm{z}}^{\leq
T}\mid{\bm{a}}^{<T};\hat{{\bm{\theta}}}}$ (98)
$\displaystyle{\mathbb{P}}_{{\bm{z}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}}\circ{\bm{v}}$
$\displaystyle={\mathbb{P}}_{{\bm{z}}^{\leq
T}\mid{\bm{a}}^{<T};\hat{{\bm{\theta}}}}\,,$ (99)

where ${\bm{v}}:={{\bm{f}}}^{-1}\circ\hat{\bm{f}}$ is a composition of
diffeomorphisms and thus a diffeomorphism from ${\mathbb{R}}^{d_{z}}$ to
itself. Note that this composition is well defined because
${\bm{f}}{({\mathbb{R}}^{d_{z}})}=\hat{{\bm{f}}}({\mathbb{R}}^{d_{z}})$. We
chose to work directly with measures (functions on sets), as opposed to
manifold integrals in Khemakhem et al. (2020a), because it simplifies the
derivation of (99) and avoids having to define densities w.r.t. measures
concentrated on a manifold.

The density of ${\mathbb{P}}_{{\bm{z}}^{\leq
T}\mid{\bm{a}}^{<T};{{\bm{\theta}}}}\circ{\bm{v}}$ w.r.t. to the Lebesgue
measure is given by the change-of-variable rule for random vectors (which can
be applied because ${\bm{v}}$ is a diffeomorphism) and is given by
$\prod_{t=1}^{T}{p}({\bm{v}}({\bm{z}}^{t})\mid{\bm{v}}({\bm{z}}^{<t}),{\bm{a}}^{<t})|\det
D{\bm{v}}({\bm{z}}^{t})|$, where $p$ refers to the density model with
parameter ${\bm{\theta}}$ and $D{\bm{v}}({\bm{z}}^{t})$ is the Jacobian matrix
of ${\bm{v}}$. Since ${\mathbb{P}}_{{\bm{z}}^{\leq
T}\mid{\bm{a}}^{<T};{\bm{\theta}}}\circ{\bm{v}}={\mathbb{P}}_{{\bm{z}}^{\leq
T}\mid{\bm{a}}^{<T};\hat{{\bm{\theta}}}}$, their respective densities w.r.t.
Lebesgue must also agree:

$\displaystyle\prod_{t=1}^{T}\hat{p}({\bm{z}}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t})=\prod_{t=1}^{T}{p}({\bm{v}}({\bm{z}}^{t})\mid{\bm{v}}({\bm{z}}^{<t}),{\bm{a}}^{<t})|\det
D{\bm{v}}({\bm{z}}^{t})|\,,$ (100)

where $\hat{p}$ refers to the conditional density of the model with parameter
$\hat{\bm{\theta}}$.

For a given $t_{0}$, we have

$\displaystyle\prod_{t=1}^{t_{0}}\hat{p}({\bm{z}}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t})=\prod_{t=1}^{t_{0}}{p}({\bm{v}}({\bm{z}}^{t})\mid{\bm{v}}({\bm{z}}^{<t}),{\bm{a}}^{<t})|\det
D{\bm{v}}({\bm{z}}^{t})|\,,$ (101)

by integrating first ${\bm{z}}^{T}$, then ${\bm{z}}^{t\shortminus 1}$, then …,
up to ${\bm{z}}^{t_{0}+1}$. Note that we can integrate ${\bm{z}}^{t_{0}}$ and
get

$\displaystyle\prod_{t=1}^{t_{0}-1}\hat{p}({\bm{z}}^{t}\mid{\bm{z}}^{<t},{\bm{a}}^{<t})=\prod_{t=1}^{t_{0}-1}{p}({\bm{v}}({\bm{z}}^{t})\mid{\bm{v}}({\bm{z}}^{<t}),{\bm{a}}^{<t})|\det
D{\bm{v}}({\bm{z}}^{t})|\,.$ (102)

By dividing (101) by (102), we get

$\displaystyle\hat{p}({\bm{z}}^{t_{0}}\mid$
$\displaystyle{\bm{z}}^{<{t_{0}}},{\bm{a}}^{<{t_{0}}})={p}({\bm{v}}({\bm{z}}^{t_{0}})\mid{\bm{v}}({\bm{z}}^{<{t_{0}}}),{\bm{a}}^{<{t_{0}}})|\det
D{\bm{v}}({\bm{z}}^{{t_{0}}})|\,,$ (103)

which completes the proof.

###  A.4 The consistency relations (Definitions 13 & 14) are equivalence
relations

In this section, we demonstrate that the relations
$\sim_{\textnormal{con}}^{\bm{a}}$ and $\sim_{\textnormal{con}}^{\bm{z}}$ are
equivalence relations by leveraging the the fact that the set of
${\bm{G}}$-preserving diffeomorphisms form a group under composition
(Proposition 5). We start by showing a fact that will be useful below.

###### Lemma 7

Let ${\bm{G}}\in\\{0,1\\}^{m\times n}$.

  1. 1.

A map ${\bm{c}}:{\mathbb{R}}^{m}\rightarrow{\mathbb{R}}^{m}$ is
${\bm{G}}$-preserving if and only if ${\bm{c}}$ is
${\bm{G}}{\bm{P}}$-preserving, where ${\bm{P}}$ is an $n\times n$ permutation
matrix.

  2. 2.

A map ${\bm{c}}:{\mathbb{R}}^{m}\rightarrow{\mathbb{R}}^{m}$ is
${\bm{G}}$-preserving if and only if
${\bm{P}}\circ{\bm{c}}\circ{\bm{P}}^{\top}$ is ${\bm{P}}{\bm{G}}$-preserving,
where ${\bm{P}}$ is a $m\times m$ permutation matrix.

  3. 3.

When m = n, a map ${\bm{c}}:{\mathbb{R}}^{m}\rightarrow{\mathbb{R}}^{m}$ is
${\bm{G}}$-preserving if and only if
${\bm{P}}\circ{\bm{c}}\circ{\bm{P}}^{\top}$ is
${\bm{P}}{\bm{G}}{\bm{P}}^{\top}$-preserving, where ${\bm{P}}$ is a $m\times
m$ permutation matrix.

Proof Let ${\bm{C}}$ be the dependency graph of ${\bm{c}}$.

  1. 1.

${\bm{C}}^{\top}{\mathbb{R}}^{m\times
n}_{\bm{G}}\subseteq{\mathbb{R}}^{m\times
n}_{\bm{G}}\iff{\bm{C}}^{\top}{\mathbb{R}}^{m\times
n}_{\bm{G}}{\bm{P}}\subseteq{\mathbb{R}}^{m\times
n}_{\bm{G}}{\bm{P}}\iff{\bm{C}}^{\top}{\mathbb{R}}^{m\times
n}_{{\bm{G}}{\bm{P}}}\subseteq{\mathbb{R}}^{m\times n}_{{\bm{G}}{\bm{P}}}$

  2. 2.

First, notice that the dependency graph of
${\bm{P}}\circ{\bm{c}}\circ{\bm{P}}^{\top}$ is
${\bm{P}}{\bm{C}}{\bm{P}}^{\top}$.

$({\bm{P}}{\bm{C}}{\bm{P}}^{\top})^{\top}{\mathbb{R}}^{m\times
n}_{{\bm{P}}{\bm{G}}}\subseteq{\mathbb{R}}^{m\times
n}_{{\bm{P}}{\bm{G}}}\iff{\bm{P}}{\bm{C}}^{\top}{\bm{P}}^{\top}{\bm{P}}{\mathbb{R}}^{m\times
n}_{{\bm{G}}}\subseteq{\bm{P}}{\mathbb{R}}^{m\times
n}_{{\bm{G}}}\iff{\bm{C}}^{\top}{\mathbb{R}}^{m\times
n}_{\bm{G}}\subseteq{\mathbb{R}}^{m\times n}_{\bm{G}}$

  3. 3.

This is a consequence of the first two statements.

We are now ready to show that the relation $\sim_{\textnormal{con}}^{\bm{a}}$
(Definition 13) is an equivalence relation.

###### Proposition 9

The consistency relation, $\sim_{\textnormal{con}}^{\bm{a}}$ (Def. 13), is an
equivalence relation.

Proof

Reflexivity. It is easy to see that
${\bm{\theta}}\sim_{\textnormal{con}}^{\bm{a}}{\bm{\theta}}$, by simply
setting ${\bm{v}}({\bm{z}}):={\bm{z}}$ with ${\bm{P}}:={\bm{I}}$.

Symmetry. Assume
${\bm{\theta}}\sim_{\textnormal{con}}^{\bm{a}}\tilde{\bm{\theta}}$. Hence, we
have ${\bm{P}}{\bm{G}}^{a}=\tilde{\bm{G}}^{a}$ as well as

$\displaystyle{\bm{f}}({\mathbb{R}}^{d_{z}})$
$\displaystyle=\tilde{\bm{f}}({\mathbb{R}}^{d_{z}}),\text{and}$ (104)
$\displaystyle\tilde{p}({\bm{z}}^{t}\mid{\bm{z}}^{<{t}},{\bm{a}}^{<{t}})$
$\displaystyle=p({\bm{v}}({\bm{z}}^{t})\mid{\bm{v}}({\bm{z}}^{<{t}}),{\bm{a}}^{<{t}})|\det
D{\bm{v}}({\bm{z}}^{{t}})|\,,$ (105)

where ${\bm{v}}:={\bm{f}}^{-1}\circ\tilde{\bm{f}}$ can be written as
${\bm{v}}:={\bm{c}}\circ{\bm{P}}^{\top}$, where ${\bm{c}}$ is a
${\bm{G}}^{a}$-preserving diffeomorphism and ${\bm{P}}$ is a permutation. We
can massage (105) to get

$\displaystyle
p({\bm{z}}^{t}\mid{\bm{z}}^{<{t}},{\bm{a}}^{<{t}})=\tilde{p}({\bm{v}}^{-1}({\bm{z}}^{t})\mid{\bm{v}}^{-1}({\bm{z}}^{<t}),{\bm{a}}^{<t})|\det
D{\bm{v}}^{-1}({\bm{z}}^{t})|\,.$ (106)

Of course, we also have that $\tilde{\bm{P}}\tilde{\bm{G}}^{a}={\bm{G}}^{a}$,
where $\tilde{\bm{P}}:={\bm{P}}^{\top}$. Now the only thing left to prove is
that ${\bm{v}}^{-1}$ can be written as
$\tilde{\bm{c}}\circ\tilde{\bm{P}}^{\top}$ where $\tilde{\bm{c}}$ is
$\tilde{\bm{G}}^{a}$-preserving. We know that

$\displaystyle{\bm{v}}^{-1}={\bm{P}}\circ{\bm{c}}^{-1}=\underbrace{{\bm{P}}\circ{\bm{c}}^{-1}\circ{\bm{P}}^{\top}}_{\tilde{{\bm{c}}}:=}\circ{\bm{P}}=\tilde{\bm{c}}\circ\tilde{\bm{P}}^{\top}\,.$
(107)

Note that ${\bm{c}}^{-1}$ is ${\bm{G}}^{a}$-preserving and thus, by Lemma 7,
$\tilde{\bm{c}}$ is ${\bm{P}}{\bm{G}}^{a}$-preserving, i.e.
$\tilde{\bm{G}}^{a}$-preserving. Hence, $\sim_{\textnormal{con}}^{\bm{a}}$ is
symmetric.

Transitivity. Suppose
${\bm{\theta}}\sim_{\textnormal{con}}^{\bm{a}}\tilde{\bm{\theta}}$ and
$\tilde{\bm{\theta}}\sim_{\textnormal{con}}^{\bm{a}}\hat{\bm{\theta}}$. This
means

$\displaystyle{\bm{P}}_{1}{\bm{G}}^{a}$ $\displaystyle=\tilde{\bm{G}}^{a}\,,$
(108) $\displaystyle{\bm{f}}({\mathbb{R}}^{d_{z}})$
$\displaystyle=\tilde{\bm{f}}({\mathbb{R}}^{d_{z}}),\text{and}$ (109)
$\displaystyle\tilde{p}({\bm{z}}^{t}\mid{\bm{z}}^{<{t}},{\bm{a}}^{<{t}})$
$\displaystyle=p({\bm{v}}_{1}({\bm{z}}^{t})\mid{\bm{v}}_{1}({\bm{z}}^{<{t}}),{\bm{a}}^{<{t}})|\det
D{\bm{v}}_{1}({\bm{z}}^{{t}})|\,,$ (110)

where ${\bm{v}}_{1}:={\bm{c}}_{1}\circ{\bm{P}}^{\top}_{1}$ with ${\bm{c}}_{1}$
being ${\bm{G}}^{a}$-preserving; and

$\displaystyle{\bm{P}}_{2}\tilde{\bm{G}}^{a}$
$\displaystyle=\hat{\bm{G}}^{a}\,,$ (111)
$\displaystyle\tilde{\bm{f}}({\mathbb{R}}^{d_{z}})$
$\displaystyle=\hat{\bm{f}}({\mathbb{R}}^{d_{z}}),\text{and}$ (112)
$\displaystyle\hat{p}({\bm{z}}^{t}\mid{\bm{z}}^{<{t}},{\bm{a}}^{<{t}})$
$\displaystyle=\tilde{p}({\bm{v}}_{2}({\bm{z}}^{t})\mid{\bm{v}}_{2}({\bm{z}}^{<{t}}),{\bm{a}}^{<{t}})|\det
D{\bm{v}}_{2}({\bm{z}}^{{t}})|\,,$ (113)

where ${\bm{v}}_{2}:={\bm{c}}_{2}\circ{\bm{P}}^{\top}_{2}$ with ${\bm{c}}_{2}$
being $\tilde{\bm{G}}^{a}$-preserving.

To show that ${\bm{\theta}}\sim_{\textnormal{con}}^{\bm{a}}\hat{\bm{\theta}}$,
we first combine (108) with (111) to get

$\displaystyle\underbrace{{\bm{P}}_{2}{\bm{P}}_{1}}_{{\bm{P}}:=}{\bm{G}}^{a}=\hat{\bm{G}}^{a}\,.$
(114)

Of course we also have that
${\bm{f}}({\mathbb{R}}^{d_{z}})=\tilde{\bm{f}}({\mathbb{R}}^{d_{z}})=\hat{\bm{f}}({\mathbb{R}}^{d_{z}})$.
By massaging both (110) and (113), we get:

$\displaystyle\hat{p}({\bm{z}}^{t}\mid{\bm{z}}^{<{t}},{\bm{a}}^{<{t}})$
$\displaystyle=p({\bm{v}}_{1}\circ{\bm{v}}_{2}({\bm{z}}^{t})\mid{\bm{v}}_{1}\circ{\bm{v}}_{2}({\bm{z}}^{<{t}}),{\bm{a}}^{<{t}})|\det
D({\bm{v}}_{1}\circ{\bm{v}}_{2})({\bm{z}}^{{t}})|\,.$ (115)

Define ${\bm{v}}:={\bm{v}}_{1}\circ{\bm{v}}_{2}$. We now want to show that
${\bm{v}}$ can be written has ${\bm{v}}={\bm{c}}\circ{\bm{P}}^{\top}$ where
${\bm{c}}$ is ${\bm{G}}^{a}$-preserving. We have that

$\displaystyle{\bm{v}}_{1}\circ{\bm{v}}_{2}$
$\displaystyle={\bm{c}}_{1}\circ{\bm{P}}_{1}^{\top}\circ{\bm{c}}_{2}\circ{\bm{P}}_{2}^{\top}$
(116)
$\displaystyle={\bm{c}}_{1}\circ\underbrace{{\bm{P}}_{1}^{\top}\circ{\bm{P}}_{2}^{\top}}_{{\bm{P}}^{\top}=}\circ\underbrace{{\bm{P}}_{2}\circ{\bm{c}}_{2}\circ{\bm{P}}_{2}^{\top}}_{\hat{\bm{c}}:=}$
(117) $\displaystyle={\bm{c}}_{1}\circ{\bm{P}}^{\top}\circ\hat{\bm{c}}$ (118)

where, by Lemma 7, $\hat{\bm{c}}$ is
${\bm{P}}_{2}\tilde{\bm{G}}^{a}$-preserving, i.e.
$\hat{\bm{G}}^{a}$-preserving. We continue and get that

$\displaystyle{\bm{v}}_{1}\circ{\bm{v}}_{2}$
$\displaystyle={\bm{c}}_{1}\circ{\bm{P}}^{\top}\circ\hat{\bm{c}}$ (119)
$\displaystyle={\bm{c}}_{1}\circ\underbrace{{\bm{P}}^{\top}\circ\hat{\bm{c}}\circ{\bm{P}}}_{{\bm{c}}^{\prime}:=}\circ{\bm{P}}^{\top}$
(120)
$\displaystyle={\bm{c}}_{1}\circ{\bm{c}}^{\prime}\circ{\bm{P}}^{\top}\,,$
(121)

where, by Lemma 7, ${\bm{c}}^{\prime}$ is
${\bm{P}}^{\top}\hat{\bm{G}}^{a}$-preserving, i.e. ${\bm{G}}^{a}$-preserving
(by (114)). Since both ${\bm{c}}_{1}$ and ${\bm{c}}^{\prime}$ are
${\bm{G}}^{a}$-preserving, ${\bm{c}}:={\bm{c}}_{1}\circ{\bm{c}}^{\prime}$ is
${\bm{G}}^{a}$-preserving, which concludes the proof.

The same can be shown for $\sim_{\textnormal{con}}^{\bm{z}}$ (Definition 14).

###### Proposition 10

The consistency relation, $\sim_{\textnormal{con}}^{\bm{z}}$ (Def. 14), is an
equivalence relation.

Proof The proof is exactly analogous to the proof that
$\sim_{\textnormal{con}}^{\bm{a}}$ is an equivalence relation. Essentially,
every statement of the form “${\bm{P}}{\bm{G}}^{a}=\tilde{\bm{G}}^{a}$”
becomes “${\bm{P}}{\bm{G}}^{z}{\bm{P}}^{\top}=\tilde{\bm{G}}^{z}$” and
statements of the form “${\bm{c}}$ is ${\bm{G}}^{a}$-preserving” becomes
“${\bm{c}}$ is ${\bm{G}}^{z}$-preserving and
$({\bm{G}}^{z})^{\top}$-preserving”. The full proof is left as an exercise to
the reader.

####  A.4.1 Combining equivalence relations

See 6

Proof The “only if” part of the statement is trivial. We now show the “if”
part.

Let ${\bm{v}}:={\bm{f}}^{-1}\circ\tilde{\bm{f}}$. Since
${\bm{\theta}}\sim_{\textnormal{con}}^{\bm{a}}\tilde{\bm{\theta}}$, we have
that $\tilde{\bm{G}}^{a}={\bm{P}}{\bm{G}}^{a}$ and
${\bm{v}}={\bm{c}}\circ{\bm{P}}^{\top}$ where ${\bm{P}}$ a permutation matrix
and ${\bm{c}}$ is ${\bm{G}}^{a}$-preserving. Since
${\bm{\theta}}\sim_{\textnormal{con}}^{\bm{z}}\tilde{\bm{\theta}}$, we have
that $\tilde{\bm{G}}^{z}=\bar{\bm{P}}{\bm{G}}^{z}\bar{\bm{P}}^{\top}$ and
${\bm{v}}=\bar{\bm{c}}\circ\bar{\bm{P}}^{\top}$ where $\bar{\bm{P}}$ is a
permutation matrix and $\bar{\bm{c}}$ is ${\bm{G}}^{z}$-preserving and
$({\bm{G}}^{z})^{\top}$-preserving. Let ${\bm{C}}$ and $\bar{\bm{C}}$ be the
dependency graphs ${\bm{c}}$ and $\bar{\bm{c}}$, respectively.

Choose an arbitrary ${\bm{z}}$. Since $D{\bm{c}}({\bm{z}})$ is invertible,
Lemma 2 implies that there exists a permutation ${\bm{P}}_{0}$ such that
${\bm{P}}_{0}^{\top}\subseteq D{\bm{v}}({\bm{z}})$, which in turns implies
that ${\bm{P}}_{0}^{\top}\subseteq\bar{\bm{C}}$. Because
${\bm{P}}_{0}^{\top}\subseteq\bar{\bm{C}}$, we have that ${\bm{P}}^{\top}_{0}$
is ${\bm{G}}^{z}$-preserving and $({\bm{G}}^{z})^{\top}$-preserving
(Proposition 3). By closure under composition and inversion,
$\bar{\bm{c}}\circ{\bm{P}}_{0}$ is ${\bm{G}}^{z}$\- and
$({\bm{G}}^{z})^{\top}$-preserving.

Note that

$\displaystyle{\bm{c}}\circ{\bm{P}}^{\top}$
$\displaystyle=\bar{\bm{c}}\circ\bar{\bm{P}}^{\top}$ (122)
$\displaystyle\implies{\bm{C}}{\bm{P}}^{\top}$
$\displaystyle=\bar{\bm{C}}\bar{\bm{P}}^{\top}$ (123)
$\displaystyle{\bm{C}}{\bm{P}}^{\top}\bar{\bm{P}}$
$\displaystyle=\bar{\bm{C}}\supseteq{\bm{P}}_{0}^{\top}$ (124)
$\displaystyle\implies{\bm{C}}$
$\displaystyle\supseteq{\bm{P}}_{0}^{\top}\bar{\bm{P}}^{\top}{\bm{P}}\,.$
(125)

This means the permutation ${\bm{P}}_{0}^{\top}\bar{\bm{P}}^{\top}{\bm{P}}$
must be ${\bm{G}}^{a}$-preserving since ${\bm{C}}$ is (Proposition 3).

This further implies that
${\bm{C}}{\bm{P}}^{\top}\bar{\bm{P}}{\bm{P}}_{0}=\bar{\bm{C}}{\bm{P}}_{0}$ is
${\bm{G}}^{a}$-preserving by closure under multiplication (recall ${\bm{C}}$
is ${\bm{G}}^{a}$-preserving too). Hence $\bar{\bm{c}}\circ{\bm{P}}_{0}$ is
${\bm{G}}^{a}$-preserving.

We thus have that
${\bm{v}}=(\bar{\bm{c}}\circ{\bm{P}}_{0})(\bar{\bm{P}}{\bm{P}}_{0})^{\top}$
where $(\bar{\bm{c}}\circ{\bm{P}}_{0})$ is ${\bm{G}}^{a}$-, ${\bm{G}}^{z}$\-
and $({\bm{G}}^{z})^{\top}$-preserving. The only thing left to show is that
$(\bar{\bm{P}}{\bm{P}}_{0}){\bm{G}}^{a}=\tilde{\bm{G}}^{a}$ and that
$(\bar{\bm{P}}{\bm{P}}_{0}){\bm{G}}^{z}(\bar{\bm{P}}{\bm{P}}_{0})^{\top}=\tilde{\bm{G}}^{z}$.
The former holds since

$(\bar{\bm{P}}{\bm{P}}_{0}){\bm{G}}^{a}={\bm{P}}({\bm{P}}^{\top}\bar{\bm{P}}{\bm{P}}_{0}){\bm{G}}^{a}={\bm{P}}{\bm{G}}^{a}=\tilde{\bm{G}}^{a}\,,$

where the second equality leverages the fact that
${\bm{P}}^{\top}\bar{\bm{P}}{\bm{P}}_{0}$ is ${\bm{G}}^{a}$-preserving.
Furthermore,

$(\bar{\bm{P}}{\bm{P}}_{0}){\bm{G}}^{z}(\bar{\bm{P}}{\bm{P}}_{0})^{\top}=\bar{\bm{P}}{\bm{G}}^{z}(\bar{\bm{P}}{\bm{P}}_{0})^{\top}=\bar{\bm{P}}{\bm{G}}^{z}{\bm{P}}_{0}^{\top}\bar{\bm{P}}^{\top}=\bar{\bm{P}}({\bm{P}}_{0}({\bm{G}}^{z})^{\top})^{\top}\bar{\bm{P}}^{\top}=\bar{\bm{P}}{\bm{G}}^{z}\bar{\bm{P}}^{\top}=\tilde{\bm{G}}^{z}\,,$

where the first and fourth equalities leveraged the fact that ${\bm{P}}_{0}$
is ${\bm{G}}^{z}$\- and $({\bm{G}}^{z})^{\top}$-preserving.

###  A.5 Technical lemmas in the proof of Theorems 1, 2 & 3

The goal of this section is to introduce and prove Lemma 12 which was crucial
in proofs of Theorems 1, 2 & 3. To prove it, we need a few more results, which
we present next.

The following two lemmas are standard, but we provide them with proofs for
completeness.

###### Lemma 8

Let $f:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}$ be continuous and
$A\subseteq{\mathbb{R}}^{n}$. If, for all ${\bm{x}}\in A$,
${\bm{f}}({\bm{x}})=0$, then the equality holds on $\overline{A}$.

Proof We have that $A\subseteq{\bm{f}}^{-1}(\\{0\\})$. Since $\\{0\\}$ is
closed, ${\bm{f}}^{-1}(\\{0\\})$ is also closed by continuity of $f$. This
means $\overline{A}\subseteq{\bm{f}}^{-1}(\\{0\\})$ (since the closure of
${\bm{A}}$ is the smallest closed set containing ${\bm{A}}$).

###### Lemma 9

Let $\mu$ be the Lebesgue measure on ${\mathbb{R}}^{d_{z}}$ and let
$E_{0}\subseteq{\mathbb{R}}^{d_{z}}$ be a zero measure set, i.e.
$\mu(E_{0})=0$. Then, $\overline{{\mathbb{R}}^{d_{z}}\setminus
E_{0}}={{\mathbb{R}}^{d_{z}}}$.

Proof Clearly, $\overline{{\mathbb{R}}^{d_{z}}\setminus
E_{0}}\subseteq{\mathbb{R}}^{d_{z}}$.

We now show that
${\mathbb{R}}^{d_{z}}\subseteq\overline{{\mathbb{R}}^{d_{z}}\setminus E_{0}}$.
Take ${\bm{z}}_{0}\in{\mathbb{R}}^{d_{z}}$ and let $U$ be an open set of
${\mathbb{R}}^{d_{z}}$ containing ${\bm{z}}_{0}$. Every open sets have nonzero
Lebesgue measure, so

$\displaystyle
0\not=\mu(U)=\mu(U\cap{\mathbb{R}}^{d_{z}})=\mu(U\cap({\mathbb{R}}^{d_{z}}\setminus
E_{0}))\implies U\cap({\mathbb{R}}^{d_{z}}\setminus E_{0})\not=\emptyset\,.$
(126)

Since $U$ was arbitrary, this means
${\bm{z}}_{0}\in\overline{{\mathbb{R}}^{d_{z}}\setminus E_{0}}$.

This simple lemma will come in handy when proving Lemma 11.

###### Lemma 10

If a permutation ${\bm{P}}$ is not ${\bm{G}}$-preserving and ${\bm{C}}$ is a
${\bm{G}}$-preserving matrix, we have that ${\bm{C}}{\bm{P}}^{\top}$ and
${\bm{P}}^{\top}{\bm{C}}$ have a zero on their diagonal.

Proof Assume ${\bm{P}}$ is not ${\bm{G}}$-preserving, hence there exists $i$,
$j$ such that ${\bm{G}}_{i,\cdot}\not\subseteq{\bm{G}}_{j,\cdot}$, but
${\bm{P}}_{i,j}=1$. Now note that

$\displaystyle({\bm{C}}{\bm{P}}^{\top})_{i,i}={\bm{C}}_{i,\cdot}({\bm{P}}_{i\cdot})^{\top}={\bm{C}}_{i,\cdot}{\bm{e}}_{j}={\bm{C}}_{i,j}\,,$
(127)

which is equal to zero because ${\bm{C}}$ is ${\bm{G}}$-preserving and
${\bm{G}}_{i,\cdot}\not\subseteq{\bm{G}}_{j,\cdot}$. Similarly,

$\displaystyle({\bm{P}}^{\top}{\bm{C}})_{j,j}=({\bm{P}}_{\cdot,j})^{\top}{\bm{C}}_{\cdot,j}={\bm{e}}_{i}^{\top}{\bm{C}}_{\cdot,j}={\bm{C}}_{i,j}=0\,.$
(128)

which concludes the proof.

The following lemma is the same as Lemma 12 which is used to proved Theorems
1, 2 & 3, except it does not take into account the “almost everywhere”
subtlety. Lemma 12 will extend it to deal with this difficulty.

###### Lemma 11

Let ${\bm{G}}\in\\{0,1\\}^{m\times n}$, let ${\mathcal{Z}}$ be a connected
subset of some topological space and let
${\bm{L}}:{\mathcal{Z}}\rightarrow{\mathbb{R}}^{m\times m}$ be a continuous
function such that ${\bm{L}}({\bm{z}})$ is invertible for all
${\bm{z}}\in{\mathcal{Z}}$. Suppose that, for all ${\bm{z}}\in{\mathcal{Z}}$,
there exists a permutation matrix ${\bm{P}}({\bm{z}})$ such that
${\bm{L}}({\bm{z}}){\bm{P}}({\bm{z}})$ is ${\bm{G}}$-preserving. Then, there
exists a permutation matrix ${\bm{P}}$ such that, for all
${\bm{z}}\in{\mathcal{Z}}$, ${\bm{L}}({\bm{z}}){\bm{P}}$ is
${\bm{G}}$-preserving.

Proof The goal of this lemma is to show that in the statement above, one can
change the order of the “for all ${\bm{z}}\in{\mathcal{Z}}$” and “there exists
a permutation”. To do that, we show that if ${\mathcal{Z}}$ is connected and
the map ${\bm{L}}(\cdot)$ is continuous, then one can find a single
permutation that works for all ${\bm{z}}\in{\mathcal{Z}}$.

Let ${\mathcal{G}}$ be the set of ${\bm{G}}^{a}$-preserving matrices. Recall
that, by Proposition 3, ${\mathcal{G}}$ corresponds to all matrices that have
some set of entries equal to zero.

First, since ${\mathcal{Z}}$ is connected and ${\bm{L}}$ is continuous, its
image, ${\bm{L}}({\mathcal{Z}})$, must be connected (by (Munkres, 2000,
Theorem 23.5)).

Second, from the hypothesis of the lemma, we know that

$\displaystyle{\bm{L}}({\mathcal{Z}})\subseteq{\mathcal{L}}:=\left(\bigcup_{\pi\in\mathfrak{S}_{m}}{\mathcal{G}}{\bm{P}}_{\pi}\right)\setminus\\{\text{singular
matrices}\\}\,,$ (129)

where $\mathfrak{S}_{m}$ is the set of permutations and
${\mathcal{G}}{\bm{P}}_{\pi}=\\{{\bm{L}}{\bm{P}}_{\pi}\mid{\bm{L}}\in{\mathcal{G}}\\}$.
We can rewrite the set ${\mathcal{L}}$ above as

$\displaystyle{\mathcal{L}}=\left(\bigcup_{\pi\in\mathfrak{S}_{m}}{\mathcal{G}}{\bm{P}}_{\pi}\setminus\\{\text{singular
matrices}\\}\right)\,.$ (130)

We now define an equivalence relation $\sim$ over permutations:
$\pi\sim\pi^{\prime}$ iff ${\bm{P}}_{\pi}{\bm{P}}_{\pi^{\prime}}^{\top}$ is
${\bm{G}}$-preserving. One can verify that the relation $\sim$ is indeed an
equivalence relation by using the fact that invertible ${\bm{G}}$-preserving
matrices form a group (Proposition 4). We notice that

$\displaystyle\pi\sim\pi^{\prime}\implies{\mathcal{G}}={\mathcal{G}}{\bm{P}}_{\pi}{\bm{P}}_{\pi^{\prime}}^{\top}\implies{\mathcal{G}}{\bm{P}}_{\pi^{\prime}}={\mathcal{G}}{\bm{P}}_{\pi}\,,$
(131)

where the first implication holds because ${\bm{G}}$-preserving matrices are
closed under matrix multiplication (Proposition 4). Let
$\mathfrak{S}_{m}/\sim$ be the set of equivalence classes induce by $\sim$ and
let $\Pi$ stand for one such equivalence class. Thanks to (131), we can
define, for all $\Pi\in\mathfrak{S}_{m}/\sim$, the following set:

$\displaystyle V_{\Pi}:={\mathcal{G}}{\bm{P}}_{\pi}\setminus\\{\text{singular
matrices}\\},\ \text{for some $\pi\in\Pi$}\,,$ (132)

where the specific choice of $\pi\in\Pi$ is arbitrary (any
$\pi^{\prime}\in\Pi$ would yield the same definition, by (131)). This
construction allows us to write

$\displaystyle{\mathcal{L}}=\bigcup_{\Pi\in\mathfrak{S}_{m}/\sim}V_{\Pi}\,.$
(133)

We now show that $\\{V_{\Pi}\\}_{\Pi\in\mathfrak{S}_{m}/\sim}$ forms a
partition of ${\mathcal{L}}$. Choose two distinct equivalence classes of
permutations $\Pi$ and $\Pi^{\prime}$ and let $\pi\in\Pi$ and
$\pi^{\prime}\in\Pi^{\prime}$ be representatives. We will now prove that

$\displaystyle{\mathcal{G}}{\bm{P}}_{\pi}\cap{\mathcal{G}}{\bm{P}}_{\pi^{\prime}}\subseteq\\{\text{singular
matrices}\\}\,.$ (134)

To achieve this, we proceed by contradiction: Suppose there exists an
invertible matrix
${\bm{A}}\in{\mathcal{G}}{\bm{P}}_{\pi}\cap{\mathcal{G}}{\bm{P}}_{\pi^{\prime}}$.
By Lemma 2, there exists a permutation ${\bm{P}}$ s.t.
${\bm{A}}{\bm{P}}^{\top}$ has no zero on its diagonal. Of course, the
permutation ${\bm{P}}$ belongs to only one equivalence class and thus either
${\bm{P}}\not\in\Pi$ or ${\bm{P}}\not\in\Pi^{\prime}$. Without loss of
generality, assume the former. We thus have that ${\bm{P}}\not\sim\pi$ and
thus ${\bm{P}}_{\pi}{\bm{P}}^{\top}$ is not ${\bm{G}}$-preserving. We can thus
write

$\displaystyle{\bm{A}}\in{\mathcal{G}}{\bm{P}}_{\pi}\cap{\mathcal{G}}{\bm{P}}_{\pi^{\prime}}\implies{\bm{A}}{\bm{P}}^{\top}\in{\mathcal{G}}{\bm{P}}_{\pi}{\bm{P}}^{\top}\cap{\mathcal{G}}{\bm{P}}_{\pi^{\prime}}{\bm{P}}^{\top}\,.$
(135)

By Lemma 10, all matrices in ${\mathcal{G}}{\bm{P}}_{\pi}{\bm{P}}^{\top}$ have
a zero on their diagonal. This is a contradiction with
${\bm{A}}{\bm{P}}^{\top}\in{\mathcal{G}}{\bm{P}}_{\pi}{\bm{P}}^{\top}$, since,
as we said, ${\bm{A}}{\bm{P}}^{\top}$ has no zero on its diagonal. We thus
conclude that no invertible matrix is in the intersection
${\mathcal{G}}{\bm{P}}_{\pi}\cap{\mathcal{G}}{\bm{P}}_{\pi^{\prime}}$ and thus
(134) holds.

We thus have that

$\displaystyle V_{\Pi}\cap V_{\Pi^{\prime}}=\emptyset\,,$ (136)

which shows that $\\{V_{\Pi}\\}_{\Pi\in\mathfrak{S}_{m}/\sim}$ is indeed a
partition of ${\mathcal{L}}$.

Each $V_{\Pi}$ is closed in ${\mathcal{L}}$ (w.r.t. the subset topology
inherited from ${\mathbb{R}}^{m\times m}$) since

$\displaystyle V_{\Pi}={\mathcal{G}}{\bm{P}}_{\pi}\setminus\\{\text{singular
matrices}\\}={\mathcal{L}}\cap\underbrace{{\mathcal{G}}{\bm{P}}_{\pi}}_{\text{closed
in ${\mathbb{R}}^{m\times m}$}}.$ (137)

Moreover, $V_{\Pi}$ is open in ${\mathcal{L}}$, since

$\displaystyle
V_{\Pi}={\mathcal{L}}\setminus\underbrace{\bigcup_{\Pi^{\prime}\not=\Pi}V_{\Pi^{\prime}}}_{\text{closed
in ${\mathcal{L}}$}}\,.$ (138)

Thus, for any $\Pi\in\mathfrak{S}({\mathcal{B}})/\sim$, the sets $V_{\Pi}$ and
$\bigcup_{\Pi^{\prime}\not=\Pi}V_{\Pi^{\prime}}$ forms a separation (see
(Munkres, 2000, Section 23)). Since ${\bm{L}}({\mathcal{Z}})$ is a connected
subset of ${\mathcal{L}}$, it must lie completely in $V_{\Pi}$ or
$\bigcup_{\Pi^{\prime}\not=\Pi}V_{\Pi^{\prime}}$, by (Munkres, 2000, Lemma
23.2). Since this is true for all $\Pi$, it must follow that there exists a
$\Pi^{*}$ such that ${\bm{L}}({\mathcal{Z}})\subseteq V_{\Pi^{*}}$. Choose any
representative ${\bm{P}}_{*}\in\Pi^{*}$. We thus have that, for all
${\bm{z}}\in{\mathcal{Z}}$,
${\bm{L}}({\bm{z}})={\bm{C}}({\bm{z}}){\bm{P}}_{*}^{\top}$, where
${\bm{C}}({\bm{z}})$ is ${\bm{G}}$-preserving, which completes the proof.

The goal of the next result is to relax the conditions of Lemma 11 so that
${\bm{L}}({\bm{z}}){\bm{P}}({\bm{z}})$ is ${\bm{G}}$-preserving for almost all
${\bm{z}}\in{\mathbb{R}}^{d_{z}}$.

###### Lemma 12

Let ${\bm{G}}\in\\{0,1\\}^{m\times n}$ and let
${\bm{L}}:{\mathbb{R}}^{d_{z}}\rightarrow{\mathbb{R}}^{m\times m}$ be a
continuous function such that ${\bm{L}}({\bm{z}})$ is invertible for all
${\bm{z}}\in{\mathbb{R}}^{d_{z}}$. Suppose that, for almost all
${\bm{z}}\in{\mathbb{R}}^{d_{z}}$ (i.e. except on a set $E_{0}$ of Lebesgue
measure zero), there exists a permutation matrix ${\bm{P}}({\bm{z}})$ such
that ${\bm{L}}({\bm{z}}){\bm{P}}({\bm{z}})$ is ${\bm{G}}$-preserving. Then,
there exists a permutation matrix ${\bm{P}}$ such that, for all
${\bm{z}}\in{\mathbb{R}}^{d_{z}}$, ${\bm{L}}({\bm{z}}){\bm{P}}$ is
${\bm{G}}$-preserving.

Proof We know that for all ${\bm{z}}\in{\mathbb{R}}^{d_{z}}\setminus E_{0}$,
where $\mu(E_{0})=0$ (Lebesgue measure zero), there exists a permutation
matrix ${\bm{P}}({\bm{z}})$ such that ${\bm{L}}({\bm{z}}){\bm{P}}({\bm{z}})$
is ${\bm{G}}$-preserving. For all permutations ${\bm{P}}$, define
${\mathcal{Z}}^{({\bm{P}})}:=\\{{\bm{z}}\in{\mathbb{R}}^{d_{z}}\setminus
E_{0}\mid{\bm{P}}({\bm{z}})={\bm{P}}\\}$. The collection of all sets
${\mathcal{Z}}^{({\bm{P}})}$ is finite (since there are finitely many
permutations) and form a partition of ${\mathbb{R}}^{d_{z}}\setminus E_{0}$.
Of course, for all ${\bm{P}}$, ${\bm{L}}({\bm{z}}){\bm{P}}$ is
${\bm{G}}$-preserving for all ${\bm{z}}\in{\mathcal{Z}}^{({\bm{P}})}$. By
Lemma 8, we can extend this statement to the closure, i.e. for all
${\bm{z}}\in\overline{{\mathcal{Z}}^{({\bm{P}})}}$,
${\bm{L}}({\bm{z}}){\bm{P}}$ is ${\bm{G}}$-preserving.

Furthermore, we have that
$\bigcup_{{\bm{P}}}\overline{{\mathcal{Z}}^{({\bm{P}})}}=\overline{\bigcup_{{\bm{P}}}{\mathcal{Z}}^{({\bm{P}})}}=\overline{{\mathbb{R}}^{d_{z}}\setminus
E_{0}}={\mathbb{R}}^{d_{z}}$, where the first equality is a standard property
of closure (which holds only for finite unions), and the last equality holds
by Lemma 9. We thus have that, for all ${\bm{z}}\in{\mathbb{R}}^{d_{z}}$,
there exists a permutation ${\bm{P}}({\bm{z}})$ such that
${\bm{L}}({\bm{z}}){\bm{P}}({\bm{z}})$ is ${\bm{G}}$-preserving. Since
${\mathbb{R}}^{d_{z}}$ is connected we can apply Lemma 11 to get the desired
conclusion.

###  A.6 Connecting to the graphical criterion of Lachapelle et al. (2022)

The goal of this section is to prove Proposition 7 which states if some
graphical criterion holds (Assumption 5), then
${\bm{\theta}}\sim_{\textnormal{con}}^{{\bm{z}},{\bm{a}}}\hat{\bm{\theta}}$
implies ${\bm{\theta}}\sim_{\textnormal{perm}}\hat{\bm{\theta}}$, i.e.
complete disentanglement. We recall Assumption 5.

See 5

We note that the above assumption is slightly different from the original one
from Lachapelle et al. (2022), since the intersections run over ${\bf
Ch}_{i}^{z}$, ${\bf Pa}_{i}^{z}$ and ${\bf Pa}^{\bm{a}}_{i}$ instead of over
some sets of indexes ${\mathcal{I}},{\mathcal{J}}\subseteq\\{1,...,d_{z}\\}$
and ${\mathcal{L}}\subseteq\\{1,...,d_{a}\\}$. This slightly simplified
criterion is equivalent to the original one, which we now demonstrate for the
interested reader.

###### Proposition 11

Let ${\bm{G}}=[{\bm{G}}^{z}\
{\bm{G}}^{a}]\in\\{0,1\\}^{d_{z}\times(d_{z}+d_{a})}$. The criterion of
Assumption 5 holds for ${\bm{G}}$ if and only if the following holds for
${\bm{G}}$: For all $i\in\\{1,...,d_{z}\\}$, there exist sets
${\mathcal{I}},{\mathcal{J}}\subseteq\\{1,...,d_{z}\\}$ and
${\mathcal{L}}\subseteq\\{1,...,d_{a}\\}$ such that

$\displaystyle\left(\bigcap_{j\in{\mathcal{I}}}{\bf
Pa}^{\bm{z}}_{j}\right)\cap\left(\bigcap_{j\in{\mathcal{J}}}{\bf
Ch}^{\bm{z}}_{j}\right)\cap\left(\bigcap_{\ell\in{\mathcal{L}}}{\bf
Ch}^{\bm{a}}_{\ell}\right)=\\{i\\}\,,$

Proof The direction “$\implies$” is trivial, since we can simply choose
${\mathcal{I}}:={\bf Ch}_{i}^{z}$, ${\mathcal{J}}:={\bf Pa}_{i}^{z}$ and
${\mathcal{L}}:={\bf Pa}_{i}^{a}$.

To show the other direction, we notice that we must have
${\mathcal{I}}\subseteq{\bf Ch}^{\bm{z}}_{i}$, ${\mathcal{J}}\subseteq{\bf
Pa}_{i}^{z}$ and ${\mathcal{L}}\subseteq{\bf Pa}_{i}^{a}$, otherwise one of
the sets in the intersection would not contain $i$, contradicting the
criterion. Thus, the criterion of Def. 5 intersects the same sets or more
sets. Moreover these potential additional sets must contain $i$ because of the
obvious facts that $j\in{\bf Ch}_{i}^{z}\iff i\in{\bf Pa}^{\bm{z}}_{j}$ and
$\ell\in{\bf Pa}_{i}^{a}\iff i\in{\bf Ch}^{\bm{a}}_{\ell}$, thus they do not
change the result of the intersection.

To prove Proposition 7, we will need the following lemma.

###### Lemma 13

Let ${\bm{G}}\in\\{0,1\\}^{m\times n}$ and ${\bm{c}}$ be a diffeomorphism with
dependency graph given by ${\bm{C}}\in\\{0,1\\}^{m\times m}$ (Definition 2).
The function ${\bm{c}}$ is ${\bm{G}}$-preserving (Definition 12) if and only
if

$\forall
i,{\bm{C}}_{i,\cdot}\subseteq\bigcap_{k\in{\bm{G}}_{i,\cdot}}{\bm{G}}_{\cdot,k}\,.$

Proof We leverage Proposition 3.

$\displaystyle{\bm{G}}_{i,\cdot}\not\subseteq{\bm{G}}_{j,\cdot}$
$\displaystyle\iff\exists k\text{ s.t. }{\bm{G}}_{i,k}=1\text{ and
}{\bm{G}}_{j,k}=0$ (139) $\displaystyle\iff\exists
k\in{\bm{G}}_{i,\cdot}\text{ s.t. }j\not\in{\bm{G}}_{\cdot,k}$ (140)
$\displaystyle\iff
j\not\in\bigcap_{k\in{\bm{G}}_{i,\cdot}}{\bm{G}}_{\cdot,k}\,.$ (141)

See 7

Proof By definition of $\sim_{\textnormal{con}}^{{\bm{z}},{\bm{a}}}$, we know
that the entanglement graph for $({\bm{f}},\hat{\bm{f}})$ is given by
${\bm{V}}={\bm{C}}{\bm{P}}^{\top}$ where ${\bm{P}}$ is a permutation and
${\bm{C}}$ is a binary matrix that is ${\bm{G}}^{a}$-preserving,
${\bm{G}}^{z}$-preserving and $({\bm{G}}^{z})^{\top}$-preserving. Using Lemma
13, we have that, for all $i$,

$\displaystyle{\bm{C}}_{i,\cdot}$
$\displaystyle\subseteq{\left(\bigcap_{j\in{\bm{G}}^{\bm{z}}_{i,\cdot}}{\bm{G}}^{\bm{z}}_{\cdot,j}\right)\cap\left(\bigcap_{j\in{\bm{G}}^{\bm{z}}_{\cdot,i}}{\bm{G}}^{\bm{z}}_{j,\cdot}\right)\cap\left(\bigcap_{j\in{\bm{G}}^{\bm{a}}_{i,\cdot}}{\bm{G}}^{\bm{a}}_{\cdot,j}\right)}$
(142) $\displaystyle={\left(\bigcap_{j\in{\bf Pa}_{i}^{z}}{\bf
Ch}^{\bm{z}}_{j}\right)\cap\left(\bigcap_{j\in{\bf Ch}_{i}^{z}}{\bf
Pa}^{\bm{z}}_{j}\right)\cap\left(\bigcap_{\ell\in{\bf Pa}^{\bm{a}}_{i}}{\bf
Ch}^{\bm{a}}_{\ell}\right)}$ (143) $\displaystyle={\\{i\\}}\,.$ (144)

Thus ${\bm{C}}$ is in fact the identity matrix, and hence
${\bm{\theta}}\sim_{\textnormal{perm}}\hat{\bm{\theta}}$.

##  Appendix B Identifiability theory - Exponential family case

###  B.1 Technical Lemmas and definitions

We recall the definition of a minimal sufficient statistic in an exponential
family, which can be found in Wainwright and Jordan (2008, p. 40).

######  Definition 20 (Minimal sufficient statistic)

Given a parameterized distribution in the exponential family, as in (61), we
say its sufficient statistic ${\bm{s}}_{i}$ is minimal when there is no
$v\not=0$ such that $v^{\top}{\bm{s}}_{i}(z)$ is constant for all
$z\in\mathcal{Z}$.

The following Lemma gives a characterization of minimality which will be
useful in the proof of Thm. 4.

######  Lemma 14 (Characterization of minimal ${\bm{s}}$)

A sufficient statistic of an exponential family distribution
${\bm{s}}:{\mathcal{Z}}\rightarrow{\mathbb{R}}^{k}$ is minimal if and only if
there exists ${\bm{z}}_{(0)}$, ${\bm{z}}_{(1)}$, …, ${\bm{z}}_{(k)}$ belonging
to the support ${\mathcal{Z}}$ such that the following $k$-dimensional vectors
are linearly independent:

$\displaystyle{\bm{s}}({\bm{z}}_{(1)})-{\bm{s}}({\bm{z}}_{(0)}),...,{\bm{s}}({\bm{z}}_{(k)})-{\bm{s}}({\bm{z}}_{(0)})\,.$
(145)

Proof. We start by showing the “if” part of the statement. Suppose there exist
${\bm{z}}_{(0)},...,{\bm{z}}_{(k)}$ in ${\mathcal{Z}}$ such that the vectors
of (145) are linearly independent. By contradiction, suppose that ${\bm{s}}$
is not minimal, i.e. there exist a nonzero vector $v$ and a scalar $b$ such
that $v^{\top}{\bm{s}}(z)=b$ for all $z\in{\mathcal{Z}}$. Notice that
$b=v^{\top}{\bm{s}}({\bm{z}}_{(0)})$. Hence,
$v^{\top}({\bm{s}}({\bm{z}}_{(i)})-{\bm{s}}({\bm{z}}_{(0)}))=0$ for all
$i=1,...,k$. This can be rewritten in matrix form as

$\displaystyle v^{\top}[{\bm{s}}({\bm{z}}_{(1)})-{\bm{s}}({\bm{z}}_{(0)})\
...\ {\bm{s}}({\bm{z}}_{(k)})-{\bm{s}}({\bm{z}}_{(0)})]=0\,,$ (146)

which implies that the matrix in the above equation is not invertible. This is
a contradiction.

We now show the “only if ” part of the statement. Suppose that there is no
${\bm{z}}_{(0)}$, …, ${\bm{z}}_{(k)}$ such that the vectors of (145) are
linearly independent. Choose an arbitrary ${\bm{z}}_{(0)}\in{\mathcal{Z}}$. We
thus have that $U:=\text{span}\\{{\bm{s}}(z)-{\bm{s}}({\bm{z}}_{(0)})\mid
z\in{\mathcal{Z}}\\}$ is a proper subspace of ${\mathbb{R}}^{k}$. This means
the orthogonal complement of $U$, $U^{\bot}$, has dimension 1 or greater. We
can thus pick a nonzero vector $v\in U^{\bot}$ such that
$v^{\top}({\bm{s}}(z)-{\bm{s}}({\bm{z}}_{0}))=0$ for all $z\in{\mathcal{Z}}$,
which is to say that $v^{\top}{\bm{s}}(z)$ is constant for all
$z\in{\mathcal{Z}}$, and thus, ${\bm{s}}$ is not minimal. $\blacksquare$

###  B.2 Proof of linear identifiability (Theorem 4)

See 4

Proof First, we apply Proposition 2 to get that

$\displaystyle\tilde{p}({\bm{z}}^{t}\mid{\bm{z}}^{<{t}},{\bm{a}}^{<{t}})=p({\bm{v}}({\bm{z}}^{t})\mid{\bm{v}}({\bm{z}}^{<{t}}),{\bm{a}}^{<{t}})|\det
D{\bm{v}}({\bm{z}}^{{t}})|\,,$ (147)

Linear relationship between ${\bm{s}}({\bm{f}}^{-1}(x))$ and
${\bm{s}}(\hat{{\bm{f}}}^{-1}(x))$. By taking the logarithm on each sides of
(147) and expliciting the exponential family form, we get

$\displaystyle\sum_{i=1}^{d_{z}}\log
h_{i}({\bm{z}}_{i}^{t})+{\bm{s}}_{i}({\bm{z}}_{i}^{t})^{\top}{\bm{\lambda}}_{i}({\bm{G}}_{i}^{z}\odot{\bm{z}}^{<t},{\bm{G}}_{i}^{a}\odot{\bm{a}}^{<t})-\psi_{i}({\bm{z}}^{<t},{\bm{a}}^{<t})$
(148) $\displaystyle=$ $\displaystyle\sum_{i=1}^{d_{z}}\log
h_{i}({\bm{v}}_{i}({\bm{z}}^{t}))+{\bm{s}}_{i}({\bm{v}}_{i}({\bm{z}}^{t})))^{\top}\hat{{\bm{\lambda}}}_{i}(\hat{{\bm{G}}}_{i}^{z}\odot{\bm{v}}({\bm{z}}^{<t}),\hat{{\bm{G}}}_{i}^{a}\odot{\bm{a}}^{<t})-\hat{\psi}_{i}({\bm{v}}({\bm{z}}^{<t}),{\bm{a}}^{<t})$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ +\log|\det
D{\bm{v}}({\bm{z}}^{{t}})|$

Note that (148) holds for all ${\bm{z}}^{<t}$ and ${\bm{a}}^{<t}$. In
particular, we evaluate it at the points given in the assumption of sufficient
variability of Thm. 4. We evaluate the equation at
$({\bm{z}}^{t},{\bm{z}}_{(r)},{\bm{a}}_{(r)})$ and
$({\bm{z}}^{t},{\bm{z}}_{(0)},{\bm{a}}_{(0)})$ and take the difference which
yields888Note that ${\bm{z}}_{(0)}$ and ${\bm{z}}_{(r)}$ can have different
dimensionalities if they come from different time steps. It is not an issue to
combine equations from different time steps, since (148) holds for all values
of $t$, ${\bm{z}}^{t}$, ${\bm{z}}^{<t}$ and ${\bm{a}}^{<t}$.

$\displaystyle\sum_{i=1}^{d_{z}}{\bm{s}}_{i}({\bm{z}}_{i}^{t})^{\top}[{\bm{\lambda}}_{i}({{\bm{G}}}_{i}^{z}\odot{\bm{z}}_{(r)},{{\bm{G}}}_{i}^{a}\odot{\bm{a}}_{(r)})-{\bm{\lambda}}_{i}({{\bm{G}}}_{i}^{z}\odot{\bm{z}}_{(0)},{{\bm{G}}}_{i}^{a}\odot{\bm{a}}_{(0)})]-\psi_{i}({\bm{z}}_{(r)},{\bm{a}}_{(r)})+\psi_{i}({\bm{z}}_{(0)},{\bm{a}}_{(0)})$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{d_{z}}{\bm{s}}_{i}({\bm{v}}_{i}({\bm{z}}^{t}))^{\top}[\hat{{\bm{\lambda}}}_{i}(\hat{{\bm{G}}}_{i}^{z}\odot{\bm{v}}({\bm{z}}_{(r)}),\hat{{\bm{G}}}_{i}^{a}\odot{\bm{a}}_{(r)})-\hat{{\bm{\lambda}}}_{i}(\hat{{\bm{G}}}_{i}^{z}\odot{\bm{v}}({\bm{z}}_{(0)}),\hat{{\bm{G}}}_{i}^{a}\odot{\bm{a}}_{(0)})]$
(149) $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \
-\hat{\psi}_{i}({\bm{v}}({\bm{z}}_{(r)}),{\bm{a}}_{(r)})+\hat{\psi}_{i}({\bm{v}}({\bm{z}}_{(0)}),{\bm{a}}_{(0)})$

We regroup all normalization constants $\psi$ into a term
$d({\bm{z}}_{(r)},{\bm{z}}_{(0)},{\bm{a}}_{(r)},{\bm{a}}_{(0)})$ and write

$\displaystyle{\bm{s}}({\bm{z}}^{t})^{\top}[{\bm{\lambda}}({\bm{z}}_{(r)},{\bm{a}}_{(r)})-{\bm{\lambda}}({\bm{z}}_{(0)},{\bm{a}}_{(0)})]$
$\displaystyle=$
$\displaystyle{\bm{s}}({\bm{v}}({\bm{z}}^{t}))^{\top}[\hat{{\bm{\lambda}}}({\bm{v}}({\bm{z}}_{(r)}),{\bm{a}}_{(r)})-\hat{{\bm{\lambda}}}({\bm{v}}({\bm{z}}_{(0)}),{\bm{a}}_{(0)})]+d({\bm{z}}_{(r)},{\bm{z}}_{(0)},{\bm{a}}_{(r)},{\bm{a}}_{(0)})\,.$
(150)

Define

$\displaystyle{\bm{w}}_{(r)}$
$\displaystyle:={\bm{\lambda}}({\bm{z}}_{(r)},{\bm{a}}_{(r)})-{\bm{\lambda}}({\bm{z}}_{(0)},{\bm{a}}_{(0)})$
(151) $\displaystyle\hat{{\bm{w}}}_{(r)}$
$\displaystyle:=\hat{{\bm{\lambda}}}({\bm{v}}({\bm{z}}_{(r)}),{\bm{a}}_{(r)})-\hat{{\bm{\lambda}}}({\bm{v}}({\bm{z}}_{(0)}),{\bm{a}}_{(0)})$
(152) $\displaystyle d_{(r)}$
$\displaystyle:=d({\bm{z}}_{(r)},{\bm{z}}_{(0)},{\bm{a}}_{(r)},{\bm{a}}_{(0)})\,,$
(153)

which yields

$\displaystyle{\bm{s}}({\bm{z}}^{t})^{\top}{\bm{w}}_{(r)}={\bm{s}}({\bm{v}}({\bm{z}}^{t}))^{\top}\hat{{\bm{w}}}_{(r)}+d_{(r)}\,.$
(154)

We can regroup the ${\bm{w}}_{(r)}$ into a matrix and the $d_{(r)}$ into a
vector:

$\displaystyle{\bm{W}}$ $\displaystyle:=[{\bm{w}}_{(1)}...\
{\bm{w}}_{(kd_{z})}]\in{\mathbb{R}}^{kd_{z}\times kd_{z}}$ (155)
$\displaystyle\hat{{\bm{W}}}$ $\displaystyle:=[\hat{{\bm{w}}}_{(1)}...\
\hat{{\bm{w}}}_{(kd_{z})}]\in{\mathbb{R}}^{kd_{z}\times kd_{z}}$ (156)
$\displaystyle{\bm{d}}$ $\displaystyle:=[d_{(1)}...\
d_{(kd_{z})}]\in{\mathbb{R}}^{1\times kd_{z}}\,.$ (157)

Since (154) holds for all $1\leq p\leq kd_{z}$, we can write

$\displaystyle{\bm{s}}({\bm{z}}^{t})^{\top}{\bm{W}}={\bm{s}}({\bm{v}}({\bm{z}}^{t}))^{\top}\hat{{\bm{W}}}+{\bm{d}}\,.$
(158)

Note that ${\bm{W}}$ is invertible by the assumption of variability, hence

$\displaystyle{\bm{s}}({\bm{z}}^{t})^{\top}={\bm{s}}({\bm{v}}({\bm{z}}^{t}))^{\top}\hat{{\bm{W}}}{\bm{W}}^{-1}+{\bm{d}}{\bm{W}}^{-1}\,.$
(159)

Let ${\bm{b}}:=({\bm{d}}{\bm{W}}^{-1})^{\top}$ and
${\bm{L}}:=(\hat{{\bm{W}}}{\bm{W}}^{-1})^{\top}$. We can thus rewrite as

$\displaystyle{\bm{s}}({\bm{z}}^{t})={\bm{L}}{\bm{s}}({\bm{v}}({\bm{z}}^{t}))+{\bm{b}}\,.$
(160)

Invertibility of ${\bm{L}}$. We now show that ${\bm{L}}$ is invertible. By
Lemma 14, the fact that the ${\bm{s}}_{i}$ are minimal is equivalent to, for
all $i\in\\{1,...,d_{z}\\}$, having elements ${\bm{z}}_{i}^{(0)}$, …,
${\bm{z}}_{i}^{(k)}$ in ${\mathcal{Z}}$ such that the family of vectors

$\displaystyle{\bm{s}}_{i}({\bm{z}}_{i}^{(1)})-{\bm{s}}_{i}({\bm{z}}_{i}^{(0)}),\
...\ ,{\bm{s}}_{i}({\bm{z}}_{i}^{(k)})-{\bm{s}}_{i}({\bm{z}}_{i}^{(0)})$ (161)

is linearly independent. Define

$\displaystyle{\bm{z}}^{(0)}:=[{\bm{z}}_{1}^{(0)}\ldots{\bm{z}}_{d_{z}}^{(0)}]^{\top}\in{\mathbb{R}}^{d_{z}}$
(162)

For all $i\in\\{1,...,d_{z}\\}$ and all $p\in\\{1,...,k\\}$, define the
vectors

$\displaystyle{\bm{z}}^{(p,i)}:=[{\bm{z}}_{1}^{(0)}\ldots{\bm{z}}_{i-1}^{(0)}\
{\bm{z}}_{i}^{(p)}\
{\bm{z}}_{i+1}^{(0)}\ldots{\bm{z}}_{d_{z}}^{(0)}]^{\top}\in{\mathbb{R}}^{d_{z}}\,.$
(163)

For a specific $1\leq p\leq k$ and $i\in\\{1,...,d_{z}\\}$, we can take the
following difference based on (160)

$\displaystyle{\bm{s}}({\bm{z}}^{(p,i)})-$
$\displaystyle{\bm{s}}({\bm{z}}^{(0)})={\bm{L}}[{\bm{s}}({\bm{v}}({\bm{z}}^{(p,i)}))-{\bm{s}}({\bm{v}}({\bm{z}}^{(0)}))]\,,$
(164)

where the left hand side is a vector filled with zeros except for the block