\section{Introduction}

Equipped with an intuitive causal interpretation, structural equation models are very popular tools in a broad range of applied sciences   \citep{spirtes2000causation,pearl2009causality,peters2017}.  Often, structural equation models involve latent variables, and it becomes a key problem to clarify whether parameters of interest are identifiable from the joint distribution of the observable variables.  Many different criteria have been developed to decide such identifiability.  The dominant approach in  state-of-the-art methods is to project away latent variables, i.e., their effects are absorbed into correlations among error terms in the structural equations.  In contrast, we here consider models with explicit latent variables and show how the latent dependence structure may be used to certify identifiability even in cases with dense latent confounding, where projection approaches remain inconclusive.

Concretely, we study linear structural equation models with explicit latent variables.  The precise setting of interest may be described as follows. Let $X=(X_v)_{v\in V}$ be a collection of $d=|V|$ observed variables, and let $L=(L_h)_{h\in\mathcal{L}}$ be $\ell=|\mathcal{L}|$ latent (unobserved) variables. Suppose all variables are related by linear equations as
$$
    X_v = \sum_{w \neq v} \lambda_{wv} X_w + \sum_{h\in\mathcal{L}} \gamma_{hv} L_h + \varepsilon_v, \qquad v\in V,
$$
where $\lambda_{wv}$ and $\gamma_{hv}$ are real-valued parameters that are also known as \emph{direct causal effects} of $X_w$ on $X_v$ and $L_h$ on $X_v$, respectively.  The $\varepsilon_v$ are independent mean zero random variables that model noise.  We assume that each $\varepsilon_v$ has finite variance $\omega_v > 0$.  The latent variables $(L_h)_{h\in\mathcal{L}}$ are assumed to be independent, and also independent of the noise terms $\varepsilon = (\varepsilon_v)_{v\in V}$.  Without loss of generality, the latent scale is fixed such that each $L_h$ has mean zero and variance 1.  Viewing $X$, $L$, and $\varepsilon$ as vectors,
the above equation system can be presented in the form
\begin{equation}\label{eq:def-model}
    X = \Lambda^{\top} X + \Gamma^{\top} L + \varepsilon
\end{equation}
with $d \times d$ parameter matrix $\Lambda=(\lambda_{wv})$ and $\ell \times d$ parameter matrix $\Gamma=(\gamma_{hv})$. The matrix $\Lambda$ has zeros along the diagonal.  
Specific models are now derived from \eqref{eq:def-model} by assuming specific sparsity patterns in $\Lambda$ and $\Gamma$.  The resulting models 
are discussed, for example, in \citet{bollen1989structural}, and they assume that all unobserved confounding is caused only by the explicitly modeled, independent latent variables.  Thus the latent structure corresponds to factor analysis models,  and we will refer to the latent variables also as \emph{latent factors}. 

The focus of this paper will be on the covariance structure posited by models derived from  \eqref{eq:def-model}.  In particular, we will be interested in determining when sparsity in the matrices $\Lambda$ and $\Gamma$ allows one to \emph{identify} (i.e., uniquely recover) the direct effects $\lambda_{wv}$ from the covariance matrix of the observable random vector $X$.  
Solving \eqref{eq:def-model}, we find
\[
X = (I_d - \Lambda)^{-\top}(\Gamma^{\top} L + \varepsilon).
\]
The vector $\Gamma^{\top} L + \varepsilon$ follows a latent factor model and has  covariance matrix
\begin{equation} \label{eq:omega}
\Omega = \text{Var}[ \varepsilon]+\Gamma^{\top}\text{Var}[ L]\Gamma = \O_{\mathsf{diag}} + \Gamma^{\top} \Gamma = \O_{\mathsf{diag}} + \sum_{h \in \cL} \Gamma^{\top}_h \Gamma_h,
\end{equation}
where $\O_{\mathsf{diag}}$ is diagonal with entries $\O_{\mathsf{diag},vv} = \omega_v$ and $\Gamma_h$ is the $h$-th row of $\Gamma$ such that the entries of $\Gamma_h$ correspond to the causal effects associated to the latent factor $L_h$.  We term the matrix $\Omega$ the \emph{latent covariance matrix}.  
 It follows that  $X$ has 
  covariance matrix 
$$ \label{eq:sigma}
\Sigma = (I_d - \Lambda)^{-\top}\Omega(I_d-\Lambda)^{-1}.
$$

In order to study structural equation models it is useful to adopt a graphical perspective.  To this end, the zero patterns in $\Lambda$ and $\Gamma$ are associated to a directed graph $G = (V\cup\cL, D)$, where  $D \subset (V\cup\cL)\times (V\cup \cL)$ is a collection of directed edges $w \rightarrow v$. For two observed nodes $v,w \in V$, the effect $\lambda_{wv}$ may be nonzero only if the edge $w \rightarrow v$ is contained in the set $D$. Similarly, for a latent node $h \in \cL$ and an observed node $v \in V$, the effect $\gamma_{hv}$ is possibly nonzero if $h \rightarrow v \in D$. In figures we draw latent nodes $h$ in gray, and we draw edges $h \rightarrow v$ dashed for better distinction. This is illustrated in the next example.

\begin{figure}[t]
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.6cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[fill=lightgray] (l) at (1.875,1.1) {$L$};
      \node[] (t1) at (0,0) {$T_1$};
      \node[] (o1) at (1.25,0) {$O_1$};
      \node[] (o2) at (2.5,0) {$O_2$};
      \node[] (t2) at (3.75,0) {$T_2$};
      \node[] (o3) at (5,0) {$O_3$};
      \node[] (z) at (-1.25,0) {$Z$};
      
      \draw[red, dashed] [-latex] (l) edge (z);
      \draw[red, dashed] [-latex] (l) edge (o1);
      \draw[red, dashed] [-latex] (l) edge (o2);
      \draw[red, dashed] [-latex] (l) edge (o3);
      
      \draw[blue] [-latex] (t1) edge (o1);
      \draw[blue] [-latex] (o1) edge (o2);
      \draw[blue] [-latex] (o2) edge (t2);
      \draw[blue] [-latex] (t2) edge (o3);
      
      \draw[blue] [-latex, bend right] (t1) edge (o2);
      \draw[blue] [-latex, out=-45, in=-135] (t1) edge (t2);
      \draw[blue] [-latex, out=-45, in=-135] (t1) edge (o3);
      \draw[blue] [-latex, bend right] (o1) edge (t2);
    \end{tikzpicture}
    
    \caption{Graph corresponding to a randomized clinical trial for sequential administered treatments with a latent factor $L$.}
    \label{fig:intro-example}
\end{figure}

\begin{exmp}
    We consider an augmented version of an example from \citet[Section 7]{stanghellini2005on}, which pertains to the effects of sequential treatments in randomized clinical trials. Suppose that the patients receive two treatment doses in sequence, $T_1$ and $T_2$, and at both times the treatment dose is assigned at random.  The randomization distribution of the second treatment dose $T_2$ depend on the previous treatment dose $T_1$ and on two intermediate outcome measures $O_1$ and $O_2$. The intermediate outcome measures are deemed potentially related, i.e.,  $O_2$ may causally depend on $O_1$. After the second treatment a final outcome measure $O_3$ is recorded.
    Assume now that there is a latent factor $L$, such as a specific characteristic of a patient, that has effects on all outcomes  $O_1, O_2, O_3$.  Finally, as in \citet{stanghellini2005on}, we assume that there exists an auxiliary observed variable $Z$ that provides a noisy measurement of $L$.  The direct effects in this setup are depicted in the  graph shown in Figure~\ref{fig:intro-example}.  
   
\end{exmp}


We aim to characterize those models of the form \eqref{eq:def-model} that are rationally identifiable, i.e., all possibly nonzero direct causal effects $\lambda_{wv}$ can be uniquely recovered as rational functions of the entries of the observable covariance matrix $\Sigma$. This kind of identifiability has been examined in previous research in the context of latent projections where latent variables are not explicitly modeled. Instead, models correspond to \emph{mixed graphs} that contain only the observed nodes $V$, but bidirectional edges in addition to the directed edges. Each bidirected edge represents a possibly nonzero entry in the latent covariance matrix $\Omega$, i.e., it implicitly indicates the presence of a confounding latent factor. The starting point for deriving sufficient criteria for rational identifiability are then the equations
\begin{equation} \label{eq:old-approach}
    [(I_d - \Lambda)^{\top}\Sigma(I_d-\Lambda)]_{vw} = \Omega_{vw}  = 0,
\end{equation}
which hold whenever no confounding latent factor affects both, $X_v$ and $X_w$ with $v\neq w$.  The equations \eqref{eq:old-approach} are then solved to obtain the nonzero effects in $\Lambda$. This strategy has been leveraged to formulate graphical criteria applicable to mixed graph representations of latent variable models. 

An example of a graphical criterion leveraging the latent projection approach is the half-trek criterion of \cite{foygel2012halftrek}, which can be considered as a predecessor and special case of the new results in this paper. But there are also various other graphical criteria on mixed graphs such as instrumental variables \citep{bowden1984instrumental}, the $G$-criterion \citep{brito2006graphical}, conditional instruments \citep{vanderzander2015efficiently}, auxiliary variables (\citeauthor{chen2016incorporating}, \citeyear{chen2016incorporating} and \citeauthor{chen2017identification}, \citeyear{chen2017identification}), decomposition techniques \citep{tian2005identifying} and several generalizations and further developments, cf. \citet{tian2009parameter}, \citet{drton2016generic}, \citet{leung2016identifiability}, \citet{weihs2017determinantal}, \citet{kumor2019efficient} and \citet{kumor2020efficient}.



In contrast, in this work we consider the original, unprojected latent variable model as defined in \eqref{eq:def-model}, and we allow the latent covariance matrix $\Omega$ to be dense with only few or no zero entries. Then the usual approach exploiting the zero structure in $\Omega$ that was highlighted in \eqref{eq:old-approach} is no longer effective.  However, dense confounding of the observed variables may be caused by only a small number of latent factors, in which case the latent covariance matrix $\Omega$ exhibits exploitable structure. Our key observation is that $\Omega$ may contain rank-deficient submatrices.  For example, let $Y, Z \subseteq V$ be two disjoint sets  of observed nodes. Then by \eqref{eq:omega} the submatrix $\Omega_{Y,Z}$ equals
$$
\Omega_{Y,Z} =  (\O_{\mathsf{diag}})_{Y,Z} + \sum_{h \in \cL} (\Gamma^{\top}_h \Gamma_h)_{Y,Z} = \sum_{h \in H} (\Gamma^{\top}_h \Gamma_h)_{Y,Z},
$$
where the subset $H \subseteq \cL$ over which we sum on the right-hand side contains exactly those latent factors that have an effect on a node in $Y$ and at the same time also an effect on a node in $Z$.
Since the matrix $\Gamma^{\top}_h \Gamma_h$ has rank one for each latent node $h$, the submatrix $\Omega_{Y,Z}$ is not of full column rank if $|H| < |Z|$. Exploiting this low rank structure of the latent covariance matrix $\Omega$ yields our main result, which is a sufficient criterion  for rational identifiability of the direct causal effects $\lambda_{wv}$.  We show how to convert the criterion into a graphical condition that can be checked using efficient algorithms under a bound on the considered rank.  Crucially, the graphical criterion is directly applicable to directed graphs $G = (V\cup\cL, D)$ that explicitly contain the latent nodes $\cL$, i.e., the criterion operates on the unprojected latent variable model.  We refer to it as the \emph{latent-factor half-trek criterion} (LF-HTC).


\begin{exmp}
   We take up the earlier example of a randomized clinical trial with sequential treatments, which we summarized in the graph in Figure~\ref{fig:intro-example}. 
   It is natural to investigate the direct causal effects between the observed variables $T_1, O_1, O_2, T_2$ and $O_3$. These direct causal effects correspond to the blue (non-dashed) edges in the figure.  Our new latent-factor half-trek criterion will be able to certify that the whole parameter matrix $\Lambda$ is rationally identifiable and all nonzero effects $\lambda_{vw}$ can be written as rational formulas in the entries of the observable covariance matrix $\Sigma$. For example, the direct effect from the first treatment dose $T_1$ on the intermediate outcome $O_1$ is given by $\Sigma_{T_1, O_1} / \Sigma_{T_1, T_1}$; a standard regression coefficient. But remarkably, we can even identify effects corresponding to the edges $T_1 \rightarrow O_2$ and $O_1 \rightarrow O_2$ by the latent-factor half-trek criterion. We verified that it is impossible to identify the latter two effects with the help of the original half-trek criterion \citep{foygel2012halftrek}, by ancestor decomposition \citep{drton2016generic}, or by edgewise and trek separation identification \citep{weihs2017determinantal} applied in the latent projection framework (cf. Section \ref{sec:latent-proj}).  The mentioned algorithms are implemented in the \texttt{R} package \texttt{SEMID} \citep{R, semid}.
\end{exmp}


It should be noted that, in principle, rational identifiability is always decidable by computational algebraic geometry \citep{garcia2010identifying} involving Gr\"obner basis computations \citep{cox2007ideals}. However, in the worst case, the complexity of these methods can be double exponential in the size of the graph. Thus, they may be infeasible even for relatively small graphs, and more efficient graphical criteria are of great value.  To check the latent-factor half-trek criterion we propose an algorithm based on max-flow computations \citep{cormen2009introduction} that runs in polynomial time in the size of the graph if we confine ourselves to search only over subsets of latent factors of bounded size. We show that the restriction of the search space is necessary since the task of checking the latent-factor half-trek criterion without restrictions is in general NP-complete.  


The organization of the paper is as follows. In Section \ref{sec:graph-rep-and-ident} we provide a precise definition of linear structural equation models given by directed graphs and rigorously introduce the concept of rational identifiability. Moreover, we derive basic necessary conditions for rational identifiability based on dimension arguments. In Section \ref{sec:main-result} we present our main result, the LF-HTC. In Section \ref{sec:latent-proj} we discuss the latent projection framework considered in previous research and compare the new LF-HTC to existing criteria. In particular, we compare the LF-HTC to the original half-trek criterion. In Section \ref{sec:computation} we present an algorithm to check the LF-HTC efficiently. Using this algorithm we systematically check identifiability of certain classes of small latent-factor graphs in Section \ref{sec:experiments}.  The restriction to small graphs allows for these checks to be validated using suitably designed Gr\"obner basis computations.   Finally, the proof of the main result is given in Section \ref{sec:proof-lfhtc}.  The Appendix contains additional material such as further elements of proofs (Appendix \ref{sec:proofs}), a hardness result for checking the LF-HTC without a bound on the cardinality of searched sets of latent variables  (Appendix \ref{sec:NP-completeness}), and an explanation on how to effectively deploy techniques from computational algebraic geometry  (Appendix \ref{sec:algebraic-techniques}).





\section{Graphical Representation and Identifiability} \label{sec:graph-rep-and-ident}
Let $G = (V\cup\cL, D)$ be a directed graph where  $V$ and $\cL$ are finite disjoint sets of observed and latent nodes, respectively.  We emphasize that $G$ is allowed to contain directed cycles.  Let $d=|V|$ and $\ell=|\cL|$.  The edge set $D \subset (V\cup\cL)\times (V\cup \cL)$ 
is assumed to be free of self-loops, so $v \rightarrow v \notin D$ for all $v \in V\cup\cL$. For each vertex $v \in V\cup\cL$, define its set of parents as $\mathrm{pa}(v) = \{w \in V\cup\cL: w \rightarrow v \in D\}$. Throughout the paper we require $\mathrm{pa}(h)=\emptyset$ for all $h\in \cL$, so that all latent nodes are source nodes and the outgoing edges of latent nodes only point to observed nodes. If this condition is satisfied, we call $G$ a \emph{latent-factor graph} and, to emphasize the set of latent variables, write $G^\cL$ instead of $G$.


The edge set of a latent-factor graph may be partitioned as $D = D_V \cup D_{\cL V}$, where $D_V = D \cap (V \times V)$ is the set of directed edges between observed nodes and $D_{\cL V} = D \cap (\cL \times V)$ is the set of directed edges that point from latent to observed nodes. Let $\mathbb{R}^{D_V}$ be the set of real $d \times d$ matrices $\Lambda = (\lambda_{wv})$ with support $D_V$, that is, $\lambda_{wv} = 0$ if $w \rightarrow v \notin D_V$. Write $\mathbb{R}^{D_V}_{\mathrm{reg}}$ for the subset of matrices $\Lambda \in \mathbb{R}^{D_V}$ with $I_d - \Lambda$  invertible;  recall that we allow $G^\cL$ to contain directed cycles. Similarly, let $\mathbb{R}^{D_{\cL V}}$ be the set of real $\ell \times d$ matrices $\Gamma = (\gamma_{hv})$ with support $D_{\cL V}$, that is, $\gamma_{hv} = 0$ if $h \rightarrow v \notin D_{\cL V}$. Additionally, we write $\mathrm{diag}^{+}_d$ for the set of all $d \times d$ diagonal matrices with a positive diagonal indexed by the elements of $V$.

Each latent-factor graph postulates a covariance model that corresponds to a linear structural equation model specified via \eqref{eq:def-model}.


\begin{defn} \label{def:model-def}
 The covariance model given by a latent-factor graph $G^\cL = (V\cup\cL, D)$ with $|V|=d$ and $|\cL|= \ell$ is the family of covariance matrices
  \begin{equation} \label{eq:param-sigma}
      \Sigma = (I_d - \Lambda)^{-\top}\Omega(I_d-\Lambda)^{-1}
  \end{equation}
  obtained from choices of $\Lambda \in \mathbb{R}^{D_V}_{\mathrm{reg}}$ and $\Omega$ in the image of the map
  \begin{align*}
    \tau : \mathbb{R}^{D_{\cL V}} \times  \mathrm{diag}^{+}_d&\longrightarrow \textit{PD}(d) \\
    (\Gamma, \O_{\mathsf{diag}}) &\longmapsto \O_{\mathsf{diag}} + \Gamma^{\top} \Gamma,
\end{align*}
where $\textit{PD}(d)$ is the cone of positive definite symmetric $d \times d$ matrices.  We term the image $\text{Im}(\tau) \subseteq \textit{PD}(d)$ the \emph{cone of latent covariance matrices}.
\end{defn}







 We are interested in the question of identifiability, i.e., whether the matrix $\Lambda$ can be uniquely recovered from a given covariance matrix $\Sigma$ of the form \eqref{eq:param-sigma}. If it is possible to recover the whole matrix $\Lambda$ uniquely, we can determine $\Omega$ uniquely by the equation
\begin{equation}
\label{eq:Omega-start}
    (I_d - \Lambda)^{\top}\Sigma(I_d-\Lambda) = \Omega,
\end{equation}
since the matrix $I_d - \Lambda$ is assumed to be invertible. Thus, for $\Theta = \mathbb{R}^{D_V}_{\mathrm{reg}} \times \text{Im}(\tau)$, identifiability holds if the parametrization map
\begin{align} \label{eq:param-map}
\begin{split}
    \phi_{G^\cL} : \Theta &\longrightarrow \textit{PD}(d) \\
    (\Lambda, \Omega) &\longmapsto (I_d - \Lambda)^{-\top}\Omega(I_d-\Lambda)^{-1} 
\end{split}
\end{align}
is injective on $\Theta$, or a suitably large subset. Since identifiability will usually not hold on the whole set $\Theta$, we need to clarify what we mean by a ``suitably large'' subset. We use terminology from algebraic geometry, background can be found in \citet{cox2007ideals}, \citet{shafarevich2013basic} or \citet{hartshorne1977algebraic}.

A property on an irreducible algebraic set $W$ is said to be generically true if the property holds on the complement $W \setminus A$ of a proper algebraic subset $A \subseteq W$.  Due to irreducibility, the complement $W \setminus A$ is dense in $W$ with respect to the Zariski topology and therefore considered as a ``suitably large'' subset.  In our case, where $W$ is equal to a Euclidean space, a proper algebraic subset has Lebesgue measure zero, see e.g.~the Lemma in \citet{okamoto1973distinctness}. 

To connect this terminology to our setup, we observe that the Zariski closure $\overline{\Theta}$, i.e., the smallest algebraic subset that contains the domain $\Theta$, is irreducible. This is true because $\Theta$ is the polynomial image of an open set.  Hence we say that a property on $\Theta$ is generically true if there exists a proper algebraic subset $A \subset \overline{\Theta}$ such that the property holds on the complement $\Theta \setminus A$.
Our interest is now in generically identifying the direct causal effects $\lambda_{wv}$ by rational formulas. This motivates the following definition.




\begin{defn}[Rational identifiability] \label{def:rat-ident}
\mbox{ }
\begin{itemize}
    \item[(a)] The latent-factor graph $G^\cL$ is said to be rationally identifiable if there exists a proper algebraic subset $A \subset \overline{\Theta}$ and a rational map $\psi : \textit{PD}(d) \longrightarrow \mathbb{R}^{D_V}_{\mathrm{reg}} \times \textit{PD}(d)$ such that $\psi \circ \phi_{G^\cL}(\Lambda, \Omega) = (\Lambda, \Omega)$ for all $(\Lambda, \Omega) \in \Theta \setminus A$.
    \item[(b)] 
   
    The direct causal effect $\lambda_{vw}$, or also simply the edge $v \rightarrow w \in D_V$, is rationally identifiable if there exists a proper algebraic subset $A \subset \overline{\Theta}$ and a rational map $\psi : \textit{PD}(d) \longrightarrow \mathbb{R}$ such that $\psi \circ \phi_{G^\cL}(\Lambda, \Omega) = \lambda_{vw}$ for all $(\Lambda, \Omega) \in \Theta \setminus A$.
\end{itemize}
\end{defn}

Rational identifiability of $G^\cL$ is equivalent to rational identifiability of all edges in $D_V$; recall~\eqref{eq:Omega-start}.
If $G^\cL$ is rationally identifiable, then a (absolutely continuous) random choice of the effects in $(\Lambda,\Gamma)$ and the error variances in $\O_{\mathsf{diag}}$ will almost surely yield a covariance matrix for the observable vector $X$ from which $\Lambda$ can be recovered uniquely by rational formulas.
If $G^\cL$ is not rationally identifiable, its parametrization $\phi_{G^\cL}$ may be either generically finite-to-one or generically infinite-to-one:

\begin{defn}
    Let $f: S \rightarrow \mathbb{R}^n$ be a map defined on a subset $S \subseteq \mathbb{R}^m$ such that the Zariski closure $\overline{S}$ is irreducible. Then $f$ is generically finite-to-one if there exists a proper algebraic subset $A \subseteq \overline{S}$ such that the fiber $\mathcal{F}_{f}(s) = f^{-1}(f(s))$ is finite for all $s \in S \setminus A$. Otherwise, $f$ is said to be generically infinite-to-one.
\end{defn}


\begin{defn} \label{def:finite-to-one}
  A latent-factor graph $G^\cL$ is generically finite-to-one if its parametrization $\phi_{G^\cL}$ is generically finite-to-one. In this case we will also say that $G^\cL$ is finitely identifiable. Otherwise,  $G^\cL$ is said to be generically infinite-to-one.
\end{defn}

Note that if a latent-factor graph $G^\cL$ is rationally identifiable, then the fiber $\mathcal{F}_{\phi_{G^\cL}}(\Lambda, \Omega) = \{(\Lambda, \Omega)\}$ for all parameter choices outside of a proper algebraic subset. In particular, a graph that is rationally identifiable is generically finite-to-one. The following Lemma is an important tool to check if a rational map is generically finite-to-one. For completeness, we provide a proof in Appendix \ref{sec:proofs}.  Here, we rely on the notion of semialgebraic sets, which are finite unions of sets defined by
finitely many  polynomial equations and inequalities. For background on semialgebraic sets we refer to \citet{bochnak1998real}, \citet{basu2006algorithms} and \citet{benedetti1990real}.

\begin{lem} \label{lem:finite-to-one}
    Let $S \subseteq \mathbb{R}^m$ be a semialgebraic set such that the Zariski closure $\overline{S}$ is irreducible. Then a rational mapping $f:S \rightarrow \mathbb{R}^n$ is generically finite-to-one if and only if $\dim(f(S)) = \dim(S)$.  In particular, if $\dim(S)>n$ then $f$ must be generically infinite-to-one.
\end{lem}

In our context, the rational mapping of interest is the parametrization map $\phi_{G^\cL}$, which maps into the positive definite cone $\textit{PD}(d)$.
We observe that a latent-factor graph $G^\cL$ cannot be finite-to-one if the dimension of the domain $\Theta = \mathbb{R}^{D_V}_{\mathrm{reg}} \times \text{Im}(\tau)$ is larger than the dimension of $\textit{PD}(d)$. This gives a basic necessary condition.

\begin{cor} \label{cor:infinite-to-one}
    A latent-factor graph $G^\cL$ is generically infinite-to-one if $|D_V|+\dim(\mathrm{Im}(\tau)) > \binom{d+1}{2}$.
\end{cor}

\begin{figure}[t]
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.45cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[fill=lightgray] (h1) at (0,1) {$h_{1}$};
      \node[] (1) at (-2,0) {1};
      \node[] (2) at (-1,0) {2};
      \node[] (3) at (-0,0) {3};
      \node[] (4) at (1,0) {4};
      \node[] (5) at (2,0) {5};
      
      \draw[red, dashed] [-latex] (h1) edge (1);
      \draw[red, dashed] [-latex] (h1) edge (2);
      \draw[red, dashed] [-latex] (h1) edge (3);
      \draw[red, dashed] [-latex] (h1) edge (4);
      \draw[red, dashed] [-latex] (h1) edge (5);
      
      \draw[blue] [-latex] (1) edge (2);
      \draw[blue] [-latex] (2) edge (3);
      \draw[blue] [-latex] (3) edge (4);
      \draw[blue] [-latex] (4) edge (5);
      \draw[blue] [-latex, bend right] (1) edge (3);
      \draw[blue] [-latex, bend right] (3) edge (5);
      
    \end{tikzpicture}
    \caption{Latent-factor graph that is (trivially) generically infinite-to-one.}
    \label{fig:inf-to-one}
\end{figure}

\begin{proof}
    To apply Lemma \ref{lem:finite-to-one} we have to show that $\Theta = \mathbb{R}^{D_V}_{\mathrm{reg}} \times \text{Im}(\tau)$ is semialgebraic, its closure is irreducible and that the parametrization map $\phi_{G^\cL}$ is rational. The first two claims are true since $\Theta$ is the polynomial image of an open semialgebraic set. Moreover, the map $\phi_{G^\cL}$ is rational due to Cramer's rule. 
    
    Now, we study the dimensions of $\Theta$ and the image $\phi_{G^\cL}(\Theta)$. The dimension of $\Theta$ is equal to $|D_V| + \dim(\text{Im}(\tau))$ since the dimension of the product of two semialgebraic sets is the sum of their individual dimensions \citep[Prop. 2.8.5]{bochnak1998real}. Since the image of $\phi_{G^\cL}$ lies in the positive definite cone $\textit{PD}(d)$, we have 
    $$
        \dim(\phi_{G^\cL}(\Theta)) \leq \dim(\textit{PD}(d)) = \binom{d+1}{2}.
    $$
    Thus, if $|D_V|+\dim(\mathrm{Im}(\tau)) > \binom{d+1}{2}$, then $\dim(\Theta) > \dim(\phi_{G^\cL}(\Theta))$ and by Lemma \ref{lem:finite-to-one} we conclude that $\phi_{G^\cL}$ is generically infinite-to-one.
\end{proof}

\begin{exmp}
Consider the graph in Figure \ref{fig:inf-to-one} where the latent structure is that of a one-factor model. By Theorem 2 in \citet{drton2007algebraic} we have $\dim(\text{Im}(\tau)) = 10$; with only one factor the dimension is equal to the number of edges from the latent node to the observed nodes, $|D_{LV}|=5$, plus the $5$ parameters appearing on the diagonal of the matrix $\O_{\mathsf{diag}}$. But since the number of observed edges $|D_V|=6$ we have that $16 = |D_V|+\dim(\text{Im}(\tau)) > \binom{6}{2}=15$ and therefore the graph is generically infinite-to-one by Corollary \ref{cor:infinite-to-one}.
\end{exmp}


If a latent-factor graph is not trivially infinite-to-one by dimension comparison, then it becomes more difficult to decide whether it is generically infinite-to-one, generically finite-to-one or rationally identifiable. Figure \ref{fig:examples} shows latent-factor graphs that only have subtle differences in their structures but each of them has a different status of identifiability.


\begin{figure}[ht]
    (a)
    \begin{subfigure}{.45\linewidth}
   
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.45cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[fill=lightgray] (h1) at (0,1) {$h_{1}$};
      \node[] (1) at (-2,0) {1};
      \node[] (2) at (-1,0) {2};
      \node[] (3) at (-0,0) {3};
      \node[] (4) at (1,0) {4};
      \node[] (5) at (2,0) {5};
      
      \draw[red, dashed] [-latex] (h1) edge (1);
      \draw[red, dashed] [-latex] (h1) edge (2);
      \draw[red, dashed] [-latex] (h1) edge (3);
      \draw[red, dashed] [-latex] (h1) edge (4);
      \draw[red, dashed] [-latex] (h1) edge (5);
      
      \draw[blue] [-latex] (2) edge (3);
      \draw[blue] [-latex] (3) edge (4);
      \draw[blue] [-latex] (4) edge (5);
      \draw[blue] [-latex, bend right] (3) edge (5);
    \end{tikzpicture}
    \end{subfigure}
    (b)
    
    \begin{subfigure}{.45\linewidth}
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.45cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[fill=lightgray] (h1) at (0,1) {$h_{1}$};
      \node[] (1) at (-2,0) {1};
      \node[] (2) at (-1,0) {2};
      \node[] (3) at (-0,0) {3};
      \node[] (4) at (1,0) {4};
      \node[] (5) at (2,0) {5};
      
      \draw[red, dashed] [-latex] (h1) edge (1);
      \draw[red, dashed] [-latex] (h1) edge (2);
      \draw[red, dashed] [-latex] (h1) edge (3);
      \draw[red, dashed] [-latex] (h1) edge (4);
      \draw[red, dashed] [-latex] (h1) edge (5);
      
      \draw[blue] [-latex, bend right] (1) edge (3);
      \draw[blue] [-latex] (2) edge (3);
      \draw[blue] [-latex] (3) edge (4);
      \draw[blue] [-latex] (4) edge (5);
      
    \end{tikzpicture}
    \end{subfigure}

    (c)
    \begin{subfigure}{.45\linewidth}
   
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.45cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[fill=lightgray] (h1) at (0,1) {$h_{1}$};
      \node[] (1) at (-2,0) {1};
      \node[] (2) at (-1,0) {2};
      \node[] (3) at (-0,0) {3};
      \node[] (4) at (1,0) {4};
      \node[] (5) at (2,0) {5};
      
      \draw[red, dashed] [-latex] (h1) edge (1);
      \draw[red, dashed] [-latex] (h1) edge (2);
      \draw[red, dashed] [-latex] (h1) edge (3);
      \draw[red, dashed] [-latex] (h1) edge (4);
      \draw[red, dashed] [-latex] (h1) edge (5);
      
      \draw[blue] [-latex] (1) edge (2);
      \draw[blue] [-latex] (3) edge (4);
      \draw[blue] [-latex] (4) edge (5);
      \draw[blue] [-latex, bend right] (3) edge (5);
      
    \end{tikzpicture}
    \end{subfigure}
    
    \caption{Latent-factor graphs with one latent-factor. (a) Rationally identifiable.  (b) Generically finite-to-one but not rationally identifiable. (c) Generically infinite-to-one.}
    \label{fig:examples}
\end{figure}














\section{Main Identifiability Result} \label{sec:main-result}
The main idea underlying our sufficient condition for rational identifiability is to exploit the low rank structure of the latent covariance matrix
$$
    \Omega = \O_{\mathsf{diag}} + \sum_{h \in \cL} \Gamma_h^{\top} \Gamma_h.
$$
Recall that $\O_{\mathsf{diag}} \in \mathrm{diag}^{+}_d$ is diagonal and  $\Gamma_h$ is the $h$-th row of $\Gamma \in \mathbb{R}^{D_{\cL V}}$. For a node $v \in V$, denote by $\mathrm{pa}_V(v) = \{w \in V : w \rightarrow v \in D_V\}$ the set of \emph{observed parents} and by $\mathrm{pa}_{\cL}(v) = \{w \in \cL : w \rightarrow v \in D_{\cL V}\}$ the set of \emph{latent parents}.  So, $\mathrm{pa}(v) = \mathrm{pa}_V(v) \cup \mathrm{pa}_{\cL}(v)$. Focusing on a fixed node $v \in V$, it is our goal to find linear equations that determine the direct causal effects corresponding to the observed parents, that is, we aim to determine the vector  $\Lambda_{\mathrm{pa}_V(v), v}$. Our approach is to find suitable sets of observed nodes $Y,Z \subseteq V\setminus\{v\}$ and a set of latent nodes $H \subseteq \cL$  with $|H|=|Z|$ such that the latent covariance matrix contains a submatrix that satisfies
\begin{equation} \label{eq:low-rank matrix}
   
    \Omega_{Y, Z \cup \{v\}} = \sum_{h \in H} (\Gamma_h^{\top} \Gamma_h)_{Y, Z \cup \{v\}}
\end{equation}
and fails to have full column rank.  The drop in rank means that the entries of the submatrix exhibit algebraic relations, which we may then use to identify the targeted direct causal effects.

The equality in \eqref{eq:low-rank matrix} holds if (i) $Y \cap (Z \cup \{v\})=\emptyset$ and (ii) $\mathrm{pa}_{\cL}(Y) \cap \mathrm{pa}_{\cL}(Z \cup \{v\}) \subseteq H$.  Indeed, (i) ensures that $(\O_{\mathsf{diag}})_{Y, Z \cup \{v\}} = 0$ because the considered submatrix does not involve any diagonal elements.  And by (ii), the set $H$ contains all latent factors that have an effect on a node in $Y$ and at the same time an effect on a node in $Z \cup \{v\}$.  Assume there exists a triple of sets $(Y,Z,H)$ with $|H|=|Z|$ and satisfying (i) and (ii) above. Then
$$
    \text{rank}\left(\Omega_{Y, Z \cup \{v\}}\right) = \text{rank}\left(\sum_{h \in H} (\Gamma_h^{\top} \Gamma_h)_{Y, Z \cup \{v\}}\right) \leq |H| = |Z|,
$$
since the matrix $\Gamma_h^{\top} \Gamma_h$ has rank one for each $h \in \cL$. Hence the matrix $\Omega_{Y, Z \cup \{v\}}$ does not have full column rank. 
Moreover, suppose that we are able to ensure that the smaller submatrix $\Omega_{Y,Z}$ is of full column rank $|Z|$. Then, since the column ranks of $\Omega_{Y, Z \cup \{v\}}$ and $\Omega_{Y,Z}$ are equal, the vector $\Omega_{Y,v}$ must be a linear combination of the columns of $\Omega_{Y,Z}$, i.e., there exists $\psi  \in \mathbb{R}^{|Z|}$ such that $\Omega_{Y,Z} \cdot \psi = \Omega_{Y,v}$. 
Using the identity $(I_d - \Lambda)^{\top}\Sigma(I_d-\Lambda) = \Omega$ from \eqref{eq:Omega-start}, this is equivalent to
$$
    [(I_d-\Lambda)^{\top} \Sigma (I_d - \Lambda)]_{Y,v} - \Omega_{Y,Z} \cdot \psi = 0.
$$
Rewriting the matrix on the left we get the system of equations
\begin{equation} \label{eq:matrix-equation}
    \begin{pmatrix} [(I_d-\Lambda)^{\top} \Sigma]_{Y, \mathrm{pa}_V(v)} & \Omega_{Y,Z} \end{pmatrix}\cdot \begin{pmatrix} \Lambda_{\mathrm{pa}_V(v),v} \\ \psi\end{pmatrix} = [(I_d - \Lambda)^{\top} \Sigma]_{Y,v}.
\end{equation}
Now, if we make sure the matrix on the left-hand side in \eqref{eq:matrix-equation} is square and invertible, we can solve the system for the unknown parameters $\Lambda_{\mathrm{pa}_V(v), v}$.  However, for this to be useful for parameter identification, suitable entries of $\Lambda$ and $\Omega$ must already be known from earlier similar calculations in order to determine the coefficient matrix and the vector on the right-hand side of \eqref{eq:matrix-equation}.

Our main result shows that the above story can be made practical and yields a criterion to recursively identify columns in $\Lambda$.  Importantly, the imposed conditions can all be translated into combinatorial conditions on the considered latent-factor graph.  The resulting method is proven correct in Theorem~\ref{thm:lfhtc} below.  Before stating the theorem we define the necessary graphical concepts, which involve special types of paths that we term latent-factor half-treks. Recall that a path from node $v$  to $w$ in a latent-factor graph $G^\cL = (V \cup \cL, D)$ is a sequence of edges that connects the consecutive nodes in a sequence of nodes beginning in $v$ and ending in $w$. 


\begin{defn}[Latent-factor half-trek]\label{def:latent_halftrek}
  A path $\pi$ in the latent-factor graph $G^\cL$ is a
  \emph{latent-factor half-trek from source $v$ to target $w$} if it is a path
  from $v \in V$ to $w \in V$ in $G^\cL$ and is of the form
  \[
    v \rightarrow x_1 \rightarrow \dots \rightarrow x_n \rightarrow w
  \]
  or of the form
  \[
    v \leftarrow h \rightarrow x_1 \rightarrow \dots \rightarrow x_n \rightarrow w
  \]
  for $x_1,\dots,x_n\in V$ and for some $h\in \cL$.
\end{defn}

The name latent-factor half-trek is inspired by the customary notion of a trek, which is a pair of directed paths $(\pi_1, \pi_2)$ that share the same source node.
If a latent-factor half-trek is of the first form in Definition \ref{def:latent_halftrek}, we say that the left-hand side of $\pi$, written $\text{Left}(\pi)$, is the node $v$ and the right-hand side, written $\text{Right}(\pi)$, is the set of nodes $\{v, x_1, \ldots, x_n, w\}$. In the second case $\text{Left}(\pi) = \{v, h\}$ and $\text{Right}(\pi) = \{h, x_1, \ldots, x_n, w\}$. A latent-factor half-trek from $v$ to $v$ may have no edges, in this case $\text{Left}(\pi) = \text{Right}(\pi)=\{v\}$ and the half-trek is called trivial, denoted by $v \equiv v$ . For a set of $n$ latent-factor half-treks, $\Pi = \{\pi_1, \ldots, \pi_n\}$, let $v_i$ and $w_i$ be the source and the target of $\pi_i$. If the sources are all distinct and the targets are all distinct, then we say that $\Pi$ is a system of latent-factor half-treks from $A=\{v_1, \ldots, v_n\}$ to $B=\{w_1, \ldots, w_n\}$. A set of latent-factor half-treks $\Pi = \{\pi_1, \ldots, \pi_n\}$ has no sided intersection if
$$
\text{Left}(\pi_i) \cap \text{Left}(\pi_j) = \emptyset = \text{Right}(\pi_i) \cap \text{Right}(\pi_j) \ \mathrm{for} \ \mathrm{all} \ i \neq j.
$$


      
      

 \begin{exmp}
     Consider the graph in Figure \ref{fig:examples} (a). Then the system of latent-factor half-treks
     $$
        \{\pi_1: 2 \leftarrow h_1 \rightarrow 3, \quad \pi_2: 4 \rightarrow 5\}
     $$
     has no sided intersection. On the other hand, the system 
     $$
        \{\widetilde{\pi}_1: 2 \leftarrow h_1 \rightarrow 3, \quad \widetilde{\pi}_2: 3 \rightarrow 4 \rightarrow 5\}
     $$
     has sided intersection since $\text{Right}(\widetilde{\pi}_1) \cap \text{Right}(\widetilde{\pi}_2) = \{3\}$.
 \end{exmp}


\begin{defn}[Latent-factor half-trek reachability]\label{def:latent_htr}
  Let $v,w\in V$ be two distinct observed nodes in a latent-factor graph $G^\cL$.  Let $H\subseteq \cL$ be a set of latent factors.  If there exists a latent-factor half-trek from $v$ to
  $w$ through the latent-factor graph $G^\cL$, which does not pass through any node in $H$, then we say that \emph{$w$ is half-trek
  reachable from $v$ while avoiding $H$}, and write
  $w\in\mathrm{htr}_H(v)$. For a set $U\subseteq V$, we write $w\in\mathrm{htr}_H(U)$ if
  $w\in\mathrm{htr}_H(u)$ for some $u\in U$.
\end{defn}

 \begin{exmp}
     Consider the graph in Figure \ref{fig:examples} (a), and let $H=\emptyset$. Then $2 \in \mathrm{htr}_H(1)$ since there is the latent-factor half-trek $1 \leftarrow h_1 \rightarrow 2$ and $h_1 \not\in H$. But if $H=\{h_1\}$, then $\mathrm{htr}_H(1) = \emptyset$ since there is no latent-factor half-trek from node $1$ to  any other node in the graph while avoiding the node $h_1$.
 \end{exmp}



\begin{defn}[Latent-factor half-trek criterion]\label{def:latent_htc}
  Given a node $v\in V$, the triple
  $(Y,Z,H)\in 2^{V\setminus \{v\}}\times 2^{V\setminus \{v\}} \times 2^{\cL}$ satisfies the
  \emph{latent-factor half-trek criterion} (LF-HTC) with respect to
  $v$ if
  \begin{enumerate}[(i)]
  \item $|Y| = |\mathrm{pa}_V(v)| + |H|$ and $|Z|=|H|$ with $Z \cap \mathrm{pa}_V(v) = \emptyset$,
  \item $Y\cap (Z\cup \{v\})=\emptyset$ and $\mathrm{pa}_{\cL}(Y) \cap \mathrm{pa}_{\cL}(Z \cup \{v\}) \subseteq H$, and
 
  \item there exists a system of latent-factor half-treks with no sided intersection from $Y$ to $Z\cup \mathrm{pa}_V(v)$ in $G^\cL$, such that for each $z\in Z$, the half-trek terminating at $z$ takes the form $y\leftarrow h \rightarrow z$ for some $y\in Y$ and some $h\in H$.
  \end{enumerate}
\end{defn}

If a triple $(Y,Z,H)$ satisfies the LF-HTC with respect to a node $v$, then
condition (ii) ensures that the submatrix $\Omega_{Y, Z \cup \{v\}}$ of the latent covariance matrix can be written as in \eqref{eq:low-rank matrix} and, since $|Z|=|H|$, the submatrix does not have full column rank. Moreover, condition (iii) ensures that the matrix on the left-hand side of \eqref{eq:matrix-equation} is invertible. The latter claim will be established by means of an application of the Gessel-Viennot-Lindstr\"om Lemma \citep{gessel1985binomial, lindstrom1973on}. We now state our main result; its proof is deferred to Section \ref{sec:proof-lfhtc}. For a directed edge $u \rightarrow y \in D$ we say that $y$ is the \textit{head} of the edge.

\begin{thm}[LF-HTC-identifiability] \label{thm:lfhtc}
  Suppose that the triple
  $(Y,Z,H)\in 2^{V\setminus \{v\}}\times 2^{V\setminus \{v\}}\times
  2^\cL$ satisfies the LF-HTC with respect to $v\in V$. If all
  directed edges $u\to y\in D_V$ with head
  $y\in Z\cup(Y\cap \mathrm{htr}_H(Z\cup\{v\}))$ are rationally
  identifiable, then all directed edges in $D_V$ with $v$ as a head are
  rationally identifiable.
\end{thm}

This theorem yields the basis for an efficient algorithm that recursively solves for all direct causal effects corresponding to the edges $D_V$ in a latent-factor graph. That is, we recover the matrix $\Lambda$ column-by-column. The corresponding algorithm is detailed in Section \ref{sec:computation}. We refer to a latent-factor graph $G^\cL$ as \emph{LF-HTC-identifiable} if all columns of  $\Lambda$ may be recovered recursively by Theorem \ref{thm:lfhtc}.



\begin{exmp} \label{ex:first-example}
    The latent-factor graph in Figure \ref{fig:examples} (a) is LF-HTC-identifiable. To see this, we recursively check all nodes $v \in V=\{1,2,3,4,5\}$. That is, for each $v \in V$ we find a triple $(Y,Z,H)$ that satisfies the LF-HTC such that all nodes in $Z\cup(Y\cap \mathrm{htr}_H(Z\cup\{v\}))$ were already checked successfully to satisfy the LF-HTC in the steps before.\\
    $\underline{v=1,2}$: The triple $(Y,Z,H) = (\emptyset, \emptyset, \emptyset)$ trivially satisfies the LF-HTC since $\mathrm{pa}_V(v) = \emptyset$. \\
    $\underline{v=4}$: Let $(Y,Z,H) = (\{2,3\}, \{1\}, \{h_1\})$. Conditions (i) and (ii) are easily checked and for condition (iii) consider the system of latent-factor half-treks $\{3 \equiv 3, 2 \leftarrow h_1 \rightarrow 1\}$. Finally, note that $Y \cap \mathrm{htr}_H(Z\cup\{v\}) = \{2,3\} \cap \{4,5\} = \emptyset$ and that the node $1 \in Z$ was already checked successfully in the last step. \\
    $\underline{v=3}$: Let $(Y,Z,H) = (\{2,4\}, \{1\}, \{h_1\})$. Then the system of latent-factor half-treks $\{2 \equiv 2, 4 \leftarrow h_1 \rightarrow 1\}$ satisfies (iii) and $Z \cup (Y \cap \mathrm{htr}_H(Z\cup\{v\})) = \{1,4\}$. \\
    $\underline{v=5}$: Let $(Y,Z,H) = (\{2,3,4\}, \{1\}, \{h_1\})$. Then the system of latent-factor half-treks $\{3 \equiv 3, 4 \equiv 4, 2 \leftarrow h_1 \rightarrow 1\}$ satisfies (iii) and $Z \cup (Y \cap \mathrm{htr}_H(Z\cup\{v\})) = \{1\}$. 
\end{exmp}











\section{Latent Projections} \label{sec:latent-proj}

As mentioned in the introduction, previous criteria for rational identifiability of direct causal effects operate on mixed graphs obtained by a projection.


\begin{defn}[\citeauthor{maathuis2019handbook}, \citeyear{maathuis2019handbook}, Chap.~2]
  Let $G^\cL = (V\cup\cL, D)$ be a latent-factor graph. Define a new graph starting with the induced subgraph $G^{\prime} = (V, D_V)$ and add edges as follows:
  $$
    \mathrm{Whenever} \ v \leftarrow h \rightarrow w \ \mathrm{in} \ G^\cL \ \mathrm{for} \ h \in \cL \ \mathrm{and} \  v,w \in V, \ \mathrm{add} \ v \leftrightarrow w \ \mathrm{to} \  G^{\prime}.
  $$
  The mixed graph $G^{\prime} = (V, D_V, B)$ is the \emph{latent projection} of $G^\cL$, where $B$ is the collection of bidirected edges $v \leftrightarrow w$. They have no orientation, i.e., $v \leftrightarrow w \in B$ if and only if $w \leftrightarrow v \in B$.
\end{defn}


Every mixed graph defines a covariance model. Denote $\textit{PD}(B) \subseteq \textit{PD}(d)$ the subcone of matrices with support $B$, that is, for $\Omega = (\omega_{vw}) \in \textit{PD}(B)$ we have $\omega_{vw} = 0$ if $v \neq w$ and $v \leftrightarrow w \notin B$.

\begin{defn
  The covariance model given by a mixed graph $G^{\prime} = (V, D_V, B)$  with $V=|d|$ is the family of covariance matrices
  $$
    \Sigma = (I_d - \Lambda)^{-\top}\Omega(I_d-\Lambda)^{-1}
  $$
  obtained from choices of $\Lambda \in \mathbb{R}^{D_V}_{\mathrm{reg}}$ and $\Omega \in \textit{PD}(B)$.
\end{defn}

For any latent-factor graph, the cone of latent covariance matrices $\text{Im}(\tau)$ is clearly a subset of  $\textit{PD}(B)$, the cone of latent covariance matrices of the latent projection. Thus, a covariance model given by a latent-factor graph is a submodel of the covariance model given by its latent projection.  More details on the at times subtle differences between  $\text{Im}(\tau)$ and $\textit{PD}(B)$ can be found in \cite{drtonyu2010}.

In the remainder of this section, we focus on the predecessor of the LF-HTC that operates on mixed graphs, namely the original half-trek criterion (HTC) of \citet{foygel2012halftrek}. We say that a mixed graph is HTC-identifiable if it is rationally identifiable by this criterion.  

At first sight, it appears as if the HTC coincides with the version of the LF-HTC obtained by only allowing $H=Z=\emptyset$; compare Def.~4 in \citet{foygel2012halftrek} with Definition~\ref{def:latent_htc} here.  However, as will show below there is a subtle difference in the way systems of half-treks with no sided intersection are defined.  Indeed, in the setting of the LF-HTC two half-treks may also intersect at latent nodes, whereas in the HTC intersections are only possible at observed nodes.  Intuitively, each bidirected edge in a latent projection amounts to confounding induced by a separate latent variable.  Before highlighting this subtlety, we first exemplify an application of HTC.

\begin{exmp} \label{ex:latent-projection}
    Figure \ref{fig:example-projection} shows two latent-factor graphs and their latent projection. Both latent-factor graphs are LF-HTC-identifiable, cf.~Example \ref{ex:first-example}. But only the latent projection in the upper panel (a) is HTC-identifiable while the latent projection in panel (b) is generically infinite-to-one. The latter is easily seen since the number of model parameters corresponding to the mixed graph is larger than the dimension $\binom{d+1}{2}$ of the space $\textit{PD}(d)$, see e.g.~Proposition 2 in \citet{foygel2012halftrek}. 
\end{exmp}

\begin{figure}[ht]
    (a)
    \begin{subfigure}{.45\linewidth}
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.45cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[fill=lightgray] (h1) at (-0.5,1) {$h_{1}$};
      \node[] (1) at (-2,0) {1};
      \node[] (2) at (-1,0) {2};
      \node[] (3) at (-0,0) {3};
      \node[] (4) at (1,0) {4};
      \node[] (5) at (2,0) {5};
      
      \draw[red, dashed] [-latex] (h1) edge (1);
      \draw[red, dashed] [-latex] (h1) edge (3);
      \draw[red, dashed] [-latex] (h1) edge (4);
      
      \draw[blue] [-latex] (2) edge (3);
      \draw[blue] [-latex] (3) edge (4);
      \draw[blue] [-latex] (4) edge (5);
      \draw[blue] [-latex, bend right] (3) edge (5);
    \end{tikzpicture}
    \end{subfigure}
    \begin{subfigure}{.45\linewidth}
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.45cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[] (1) at (-2,0) {1};
      \node[] (2) at (-1,0) {2};
      \node[] (3) at (-0,0) {3};
      \node[] (4) at (1,0) {4};
      \node[] (5) at (2,0) {5};
      
      \draw[red, dashed] [latex-latex, bend left] (1) edge (3);
      \draw[red, dashed] [latex-latex, bend left] (3) edge (4);
      \draw[red, dashed] [latex-latex, bend left, out=50, in=130] (1) edge (4);
      
      \draw[blue] [-latex] (2) edge (3);
      \draw[blue] [-latex] (3) edge (4);
      \draw[blue] [-latex] (4) edge (5);
      \draw[blue] [-latex, bend right] (3) edge (5);
    \end{tikzpicture}
    \end{subfigure}
    \\
    
    
    (b)
    \begin{subfigure}{.45\linewidth}
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.45cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[fill=lightgray] (h1) at (0,1) {$h_{1}$};
      \node[] (1) at (-2,0) {1};
      \node[] (2) at (-1,0) {2};
      \node[] (3) at (-0,0) {3};
      \node[] (4) at (1,0) {4};
      \node[] (5) at (2,0) {5};
      
      \draw[red, dashed] [-latex] (h1) edge (1);
      \draw[red, dashed] [-latex] (h1) edge (2);
      \draw[red, dashed] [-latex] (h1) edge (3);
      \draw[red, dashed] [-latex] (h1) edge (4);
      \draw[red, dashed] [-latex] (h1) edge (5);
      
      \draw[blue] [-latex] (2) edge (3);
      \draw[blue] [-latex] (3) edge (4);
      \draw[blue] [-latex] (4) edge (5);
      \draw[blue] [-latex, bend right] (3) edge (5);
    \end{tikzpicture}
    \end{subfigure}
    \begin{subfigure}{.45\linewidth}
   
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.45cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[] (1) at (-2,0) {1};
      \node[] (2) at (-1,0) {2};
      \node[] (3) at (-0,0) {3};
      \node[] (4) at (1,0) {4};
      \node[] (5) at (2,0) {5};
      
      \draw[red, dashed] [latex-latex, bend left] (1) edge (2);
      \draw[red, dashed] [latex-latex, bend left] (2) edge (3);
      \draw[red, dashed] [latex-latex, bend left] (3) edge (4);
      \draw[red, dashed] [latex-latex, bend left] (4) edge (5);
      \draw[red, dashed] [latex-latex, bend left, out=40, in=140] (1) edge (3);
      \draw[red, dashed] [latex-latex, bend left, out=40, in=140] (2) edge (4);
      \draw[red, dashed] [latex-latex, bend left, out=40, in=140] (3) edge (5);
      \draw[red, dashed] [latex-latex, bend left, out=60, in=120] (1) edge (4);
      \draw[red, dashed] [latex-latex, bend left, out=60, in=120] (2) edge (5);
      \draw[red, dashed] [latex-latex, bend left, out=80, in=100] (1) edge (5);
      
      \draw[blue] [-latex] (2) edge (3);
      \draw[blue] [-latex] (3) edge (4);
      \draw[blue] [-latex] (4) edge (5);
      \draw[blue] [-latex, bend right] (3) edge (5);
    \end{tikzpicture}
    \end{subfigure}
    \caption{Latent-factor graphs and their latent projection.}
    \label{fig:example-projection}
    
\end{figure}




Comparing the graphs in Figure \ref{fig:example-projection}, the latent-factor graphs on the left-hand side  assume that all unobserved confounding is caused by a single latent factor. In contrast, for the latent projections on the right-hand side, there may be multiple latent factors that are the sources of confounding represented by bidirected edges. This leads to rational identifiability of the latent-factor graphs while the projection on the mixed graphs may be generically infinite-to-one. 
\medskip

Surprisingly, a mixed graph $G^{\prime}$ being rationally identifiable does \textit{not} imply that all latent-factor graphs $G^{\cL}$ having $G^{\prime}$ as their latent projection are rationally identifiable.
Recall that in the case of rational identifiability of the latent projection there may be a proper algebraic subset $A$ of the Zariski closure of $\mathbb{R}^{D_V}_{\mathrm{reg}} \times  \textit{PD}(B)$ such that identification is not possible on $A$. If the dimensionality of the cone of latent covariance matrices $\text{Im}(\tau)$ is strictly smaller than the dimension of $\textit{PD}(B)$, it can therefore happen that $\Theta = \mathbb{R}^{D_V}_{\mathrm{reg}}  \times \text{Im}(\tau) \subseteq A$ and the latent-factor graph is generically infinite-to-one. As an example, the latent projection in Figure \ref{fig:counterexmp} is HTC-identifiable while the latent-factor graph itself is generically infinite-to-one. In this example,  $\dim(\text{Im}(\tau)) = 11$ while $\dim(\textit{PD}(B))=13$.  Hence, although the model given by the graph to the left is still a submodel of the one given by the graph to the right, the relevant notion of genericity is different, referring to proper subsets of $\textit{PD}(B)$ and of $\text{Im}(\tau)$, respectively.



\begin{figure}[ht]
    \begin{subfigure}{.49\linewidth}
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.45cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[fill=lightgray] (h1) at (-0.5,1) {$h_{1}$};
      \node[fill=lightgray] (h2) at (1.5,1) {$h_{2}$};
      \node[fill=lightgray] (h3) at (1,-1) {$h_{3}$};
      \node[] (1) at (-2,0) {1};
      \node[] (2) at (-1,0) {2};
      \node[] (3) at (-0,0) {3};
      \node[] (4) at (1,0) {4};
      \node[] (5) at (2,0) {5};
      
      \draw[red, dashed] [-latex] (h1) edge (1);
      \draw[red, dashed] [-latex] (h1) edge (2);
      \draw[red, dashed] [-latex] (h1) edge (3);
      \draw[red, dashed] [-latex] (h1) edge (4);
      \draw[red, dashed] [-latex] (h2) edge (4);
      \draw[red, dashed] [-latex] (h2) edge (5);
      \draw[red, dashed] [-latex] (h3) edge (3);
      \draw[red, dashed] [-latex] (h3) edge (5);
      
      \draw[blue] [-latex] (4) edge (5);
      \draw[blue] [-latex, bend right] (3) edge (5);
    \end{tikzpicture}
    \end{subfigure}
    \begin{subfigure}{.49\linewidth}
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.45cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[] (1) at (-2,0) {1};
      \node[] (2) at (-1,0) {2};
      \node[] (3) at (-0,0) {3};
      \node[] (4) at (1,0) {4};
      \node[] (5) at (2,0) {5};
      
      \draw[red, dashed] [latex-latex] (1) edge (2);
      \draw[red, dashed] [latex-latex] (2) edge (3);
      \draw[red, dashed] [latex-latex] (3) edge (4);
      \draw[red, dashed] [latex-latex, bend left] (1) edge (3);
      \draw[red, dashed] [latex-latex, bend left] (2) edge (4);
      \draw[red, dashed] [latex-latex, bend left, out=50, in=130] (1) edge (4);
      \draw[red, dashed] [latex-latex, bend left] (4) edge (5);
      \draw[red, dashed] [latex-latex, bend right, out=-50, in=-130] (3) edge (5);
      
      \draw[blue] [-latex] (4) edge (5);
      \draw[blue] [-latex, bend right] (3) edge (5);
    \end{tikzpicture}
    \end{subfigure}
    \caption{Latent-factor graph that is generically infinite-to-one but its latent projection is HTC-identifiable.}
    \label{fig:counterexmp}
\end{figure}



In the experiments in Section \ref{sec:experiments}, we systematically compare LF-HTC-identifiability of latent-factor graphs with HTC-identifiability applied to the corresponding latent projection.














\section{Computation} \label{sec:computation}

In this section we propose an efficient algorithm for deciding whether a latent-factor graph is LF-HTC-identifiable. It is similar to the algorithm of the original half-trek criterion in \citet{foygel2012halftrek} and makes use of maximum flows in a special flow graph $G_{\textrm{flow}}=(V_f, D_f)$ from a designated source node $s \subseteq V_f$ to a target node $t \subseteq V_f$. The standard maximum-flow framework is introduced in \citet{cormen2009introduction}. We highlight that the maximum flow can be computed in polynomial time and the complexity is $\mathcal{O}((|V_f|+r)^3)$ where $r \leq |D_f|/2$ is the number of reciprocal edge pairs in $D_f$. A reciprocal edge pair is a pair $v \rightarrow w$ and $w \rightarrow v$ for distinct nodes $v \neq w \in V_f$. 

Let $G^\cL$ be a latent-factor graph, and fix a node $v \in V$. Then we denote by  \texttt{LF-HTC}$(G^\cL,v)$ the problem of finding a triple $(Y,Z,H) \in 2^{V\setminus\{v\}}\times 2^{V\setminus \{v\}}\times 2^\cL$ satisfying the LF-HTC for $v \in V$ in $G^\cL$.  To solve this problem, we first address a subproblem by assuming that we are given a fixed set $H \subseteq \cL$ and a fixed set $Z \subseteq \text{ch}(H) \setminus (\{v\} \cup \mathrm{pa}_V(v))$ such that $|Z|=|H|$. 
Since the second part of condition (ii) of the LF-HTC is equivalent to $Y \cap \text{ch}(\mathrm{pa}_{\cL}(Z \cup \{v\}) \setminus H) = \emptyset$, the set $A = V\setminus (Z \cup \{v\} \cup \text{ch}(\mathrm{pa}_{\cL}(Z \cup \{v\}) \setminus H))$ is the set of ``allowed'' nodes that may contain a set $Y \subseteq A$ such that $(Y,Z,H)$ satisfies the LF-HTC with respect to $v$. We are able to find such a set $Y$ or prove its inexistence efficiently by one maximum flow computation on a suitable flow graph $G_{\textrm{flow}}(v, A, Z)=(V_f, D_f)$. 

The flow graph is defined as follows: Let $V^{\prime}$ and $\cL^{\prime}$ be copies of the sets $V$ and $\cL$. Then the graph contains the nodes $V_f = (A \cup \cL) \cup (V^{\prime} \cup \cL^{\prime}) \cup \{s,t\}$, where $s$ is a source node and $t$ is a sink node. The set of edges $D_f$ contains
\begin{itemize}
    \item[(a)] $s \rightarrow a$ for all $a \in A$,
    \item[(b)] $a \rightarrow w$ if $a \in A$ and $w \rightarrow a \in D_{\cL V}$,
    \item[(c)] $w \rightarrow w^{\prime}$ for all $w \in A \cup \cL$,
    \item[(d)] $u^{\prime} \rightarrow w^{\prime}$ for all $u \rightarrow w \in D_{\cL V}$ and for all $u \rightarrow w \in D_V $ such that $w \notin Z$,
    \item[(e)] $w^{\prime} \rightarrow t$ for all $w \in \mathrm{pa}_V(v) \cup Z$.
\end{itemize}
We assign to all edges capacity $\infty$. The source node $s$ and the target node $t$ have capacity $\infty$ while all other nodes have capacity 1. Note that, by construction, no flow in $G_{\textrm{flow}}(v, A, Z)$ can exceed $|\mathrm{pa}_V(v)| + |Z|$ in size, therefore one may replace the infinite capacities with  $|\mathrm{pa}_V(v)| + |Z|$ in practice. An example of a flow graph is shown in Figure \ref{fig:example-flow-graph}(b).




\begin{figure}[ht]

    \begin{subfigure}{.45\linewidth}
    (a)
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.45cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[fill=lightgray] (h1) at (0,1) {$h_{1}$};
      \node[] (1) at (-2,0) {1};
      \node[] (2) at (-1,0) {2};
      \node[] (3) at (-0,0) {3};
      \node[] (4) at (1,0) {4};
      \node[] (5) at (2,0) {5};
      
      \draw[red, dashed] [-latex] (h1) edge (1);
      \draw[red, dashed] [-latex] (h1) edge (2);
      \draw[red, dashed] [-latex] (h1) edge (3);
      \draw[red, dashed] [-latex] (h1) edge (4);
      \draw[red, dashed] [-latex] (h1) edge (5);
      
      \draw[blue] [-latex] (2) edge (3);
      \draw[blue] [-latex] (3) edge (4);
      \draw[blue] [-latex] (4) edge (5);
      \draw[blue] [-latex, bend right] (3) edge (5);
    \end{tikzpicture}
    \end{subfigure}
    \begin{subfigure}{.45\linewidth}
    (b)
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.45cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[fill=lightgray] (h1) at (-3,0) {$h_{1}$};
      \node[] (2) at (-1,0) {2};
      \node[] (3) at (-0,0) {3};
      \node[] (5) at (2,0) {5};
      
      \node[fill=lightgray] (h1p) at (-3,-1) {$h_{1}^{\prime}$};
      \node[] (1p) at (-2,-1) {$1^{\prime}$};
      \node[] (2p) at (-1,-1) {$2^{\prime}$};
      \node[] (3p) at (-0,-1) {$3^{\prime}$};
      \node[] (4p) at (1,-1) {$4^{\prime}$};
      \node[] (5p) at (2,-1) {$5^{\prime}$};
      
      \node[] (s) at (1,1) {$s$};
      \node[] (t) at (-1,-2.1) {$t$};
      
      \draw[] [-latex] (s) edge (2);
      \draw[] [-latex] (s) edge (3);
      \draw[] [-latex] (s) edge (5);
       
      \draw[red, dashed] [-latex, bend right] (2) edge (h1);
      \draw[red, dashed] [-latex, bend right] (3) edge (h1);
      \draw[red, dashed] [-latex, bend right] (5) edge (h1);
      
      \draw[] [-latex] (h1) edge (h1p);
      \draw[] [-latex] (2) edge (2p);
      \draw[] [-latex] (3) edge (3p);
      \draw[] [-latex] (5) edge (5p);
      
      \draw[red, dashed] [-latex] (h1p) edge (1p);
      \draw[red, dashed] [-latex, bend right] (h1p) edge (2p);
      \draw[red, dashed] [-latex, bend right] (h1p) edge (3p);
      \draw[red, dashed] [-latex, bend right] (h1p) edge (4p);
      \draw[red, dashed] [-latex, bend right] (h1p) edge (5p);
      
      \draw[blue] [-latex] (2p) edge (3p);
      \draw[blue] [-latex] (3p) edge (4p);
      \draw[blue] [-latex] (4p) edge (5p);
      \draw[blue] [-latex, bend left] (3p) edge (5p);
      
      \draw[] [-latex] (1p) edge (t);
      \draw[] [-latex] (3p) edge (t);
    \end{tikzpicture}
    \end{subfigure}
    \caption{Using maximum-flow to find a set $Y \subseteq A$ such that the triple $(Y,Z,H)$ with fixed sets $H=\{h_1\}$ and $Z=\{1\}$ satisfies the LF-HTC with respect to $v=4$. The set of allowed nodes is $A=\{2,3,5\}$. (a) The concerned latent-factor graph. (b) The corresponding flow graph $G_{\textrm{flow}}(v, A, Z)$. }
    \label{fig:example-flow-graph}
\end{figure}


Let $\texttt{MaxFlow}(G_{\textrm{flow}}(v, A, Z))$ be the maximum flow from $s$ to $t$ in the graph $G_{\textrm{flow}}(v, A, Z)$. The following theorem is proven in Appendix \ref{sec:proofs}.

\begin{thm} \label{thm:check-solution}
  Let $G^\cL=(V \cup \cL, D)$ be a latent-factor graph, and fix a node $v \in V$, a set $H \subseteq \cL$ and a set $Z \subseteq \textrm{ch}(H) \setminus (\{v\} \cup \mathrm{pa}_V(v))$ such that $|Z|=|H|$. For the set of allowed nodes $A = V\setminus (Z \cup \{v\} \cup \mathrm{ch}(\mathrm{pa}_{\cL}(Z \cup \{v\}) \setminus H))$ we have that $\texttt{MaxFlow}(G_{\textrm{flow}}(v, A, Z)) = |\mathrm{pa}_V(v)| + |Z|$ if and only if there exists $Y \subseteq A$ such that the triple $(Y,Z,H)$ solves \texttt{LF-HTC}$(G^\cL,v)$.
\end{thm}

For solving \texttt{LF-HTC}$(G^\cL,v)$ we iterate over all suitable sets $H \subseteq \cL$ and $Z \subseteq \text{ch}(H) \setminus (\{v\} \cup \mathrm{pa}_V(v))$ such that $|Z|=|H|$ and check for each pair $(Z,H)$ if there is a corresponding set $Y \subseteq A$. In each iteration, we have to compute one maximum flow by Theorem \ref{thm:check-solution}. It is enough to iterate over subsets $H \subseteq \cL_{\geq 4}$ where  $\cL_{\geq 4} = \{h \in \cL : |\text{ch}(h)| \geq 4\}$ contains only those latent nodes with more than four children. Recall that the children of a node $v \in V \cup \cL$ are formally defined as $\text{ch}(v) = \{w \in V \cup \cL : v \rightarrow w \in D\}.$   We prove the following fact in Appendix \ref{sec:proofs}.

\begin{prop} \label{prop:four-children}
  Let $G^\cL=(V \cup \cL, D)$ be a latent-factor graph, and fix a node $v \in V$. If the triple  $(Y,Z,H)$ solves \texttt{LF-HTC}$(G^\cL,v)$ and there is a node $h \in H$ such that $|\textrm{ch}(h)| \leq 3$, then there are subsets $\widetilde{Y} \subseteq Y$ and $\widetilde{Z} \subseteq Z$ such that the triple $(\widetilde{Y}, \widetilde{Z} , \widetilde{H})$ with $\widetilde{H} = H \setminus \{h\}$  solves \texttt{LF-HTC}$(G^\cL,v)$ as well.
\end{prop}


Next, we give an algorithm to determine whether a graph $G^\cL$ is LF-HTC-identifiable by iterating over all nodes $v \in V$ and solving \texttt{LF-HTC}$(G^\cL,v)$ in each step. Moreover, when solving \texttt{LF-HTC}$(G^\cL,v)$ for a specific node $v \in V$, we have to make sure that, for a possible solution $(Y,Z,H)$, each node $w \in Z \cup (Y \cap \mathrm{htr}_H(Z \cup \{v\}))$ was solved before. This intuition is formalized in Algorithm \ref{alg:check-lfhtc}. In Theorem \ref{thm:algo-correct} we prove that the algorithm correctly determines LF-HTC-identifiability.




\begin{algorithm}[ht]
\caption{Testing LF-HTC-identifiability of a latent-factor graph}\label{graph-algo}
\begin{algorithmic}[1]
\REQUIRE Latent-factor graph $G^\cL = (V \cup \cL, D)$.\\
\ENSURE Solved nodes $S \leftarrow \{v \in V: \mathrm{pa}_V(v) = \emptyset\}$.
\REPEAT 
    \FOR {$v \in V \setminus S$}
        \FOR {$H \in \cL_{\geq 4}$}
            \STATE{$Z_a \leftarrow (S \cap \text{ch}(H)) \setminus (\{v\} \cup \mathrm{pa}_V(v))$.}
            \FOR {$Z \subseteq Z_a$ such that $|Z| = |H|$} 
                \STATE{$A \leftarrow V \setminus (Z \cup \{v\} \cup \text{ch}(\mathrm{pa}_{\cL}(Z \cup \{v\}) \setminus H) \cup (\mathrm{htr}_H(Z \cup \{v\}) \setminus S))$.}
                \IF {$\texttt{MaxFlow}(G_{\textrm{flow}}(v,A,Z))  = |\mathrm{pa}_V(v)| + |Z|$}
                     \STATE {$S \leftarrow S \cup \{v\}$}
                     \STATE \algorithmicbreak
                \ENDIF
            \ENDFOR
            \IF {$v \in S$}
                \STATE \algorithmicbreak
            \ENDIF
        \ENDFOR
    \ENDFOR
\UNTIL{$S = V$ or no change has occurred in the last iteration.}
\RETURN ``yes'' if $S=V$, ``no'' otherwise.
\end{algorithmic}
\label{alg:check-lfhtc}
\end{algorithm}


\begin{thm} \label{thm:algo-correct}
  A latent-factor graph $G^\cL = (V \cup \cL, D)$ is LF-HTC-identifiable if and only if Algorithm \ref{alg:check-lfhtc} returns ``yes''. If we only allow sets $H$ with $|H| \leq k$ in line $3$, then the algorithm has complexity at most $\mathcal{O}(|V|^{2+k} |\cL|^k (|V|+|\cL|+r)^3)$ where $r \leq |D_V|/2$ is the number of reciprocal edge pairs in $D_V$.
\end{thm}

In Algorithm \ref{alg:check-lfhtc} we iterate over subsets of the power sets of $\cL$ and $V$, and we put effort into iterating over a small subset. Nevertheless, if we allow the cardinality of $|H|$ to be unbounded in line three, then we search over an exponentially large space and, thus, our algorithm will in general take exponential time $\mathcal{O}(2^{|\cL|+|V|})$.  In fact, there is a fundamental barrier in finding a polynomial time algorithm as we are able to show that \texttt{LF-HTC}$(G^\cL,v)$  is an NP-complete problem. 

To see that \texttt{LF-HTC}$(G^\cL,v)$ is NP-complete, first note that \texttt{LF-HTC}$(G^\cL,v)$ is in the NP-complexity class due to Theorem \ref{thm:check-solution}. Every candidate triple $(Y,Z,H)$ to solve \texttt{LF-HTC}$(G^\cL,v)$ can be checked to be a solution in polynomial time by first checking if $(Y,Z,H)$ satisfies conditions (i) and (ii) of the LF-HTC and then checking if $\texttt{MaxFlow}(G_{\textrm{flow}}(v, Y, Z)) = |\mathrm{pa}_V(v)| + |Z|$.   Moreover, we are able to show NP-hardness of \texttt{LF-HTC}$(G^\cL,v)$ by a reduction from  the Boolean satisfiability problem in conjunctive normal form; this result is developed in Appendix \ref{sec:NP-completeness}.
























\section{Numerical Experiments} \label{sec:experiments}


This section reports on the results of experiments with small latent-factor graphs, for which the identification problem can be fully solved by techniques from computational algebraic geometry, as we discuss in Appendix \ref{sec:algebraic-techniques}. We study graphs whose observed part $(V, D_V)$ is a directed acyclic graph (DAG) with $|V|=6$ nodes. 

In the first experimental setup we consider one global latent factor that has an effect on all observed variables, as illustrated in Figure \ref{fig:exp-one-latent}.  All possible DAGs on 6 nodes are considered for the observed part $(V, D_V)$.  Table \ref{table:exp-one-latent} lists the counts when there are $|D_V|\le 9$ edges in the observed part of the graph.  Graphs with $|D_V| > 9$ are trivially generically infinite-to-one by Corollary \ref{cor:infinite-to-one}. In the counts in Table \ref{table:exp-one-latent} we treat graphs as unlabeled, that is, we count isomorphism classes of graphs. Formally, two latent-factor graphs $G=(V \cup \cL, D)$ and $G^{\prime}=(V \cup \cL, D^{\prime})$ with the same set of nodes  are isomorphic if there is a permutation $\pi$ of the observed nodes $V$ such that for two nodes $h \in \cL$ and $ v \in V$ the edge $h \rightarrow v \in D$ if and only if $h \rightarrow \pi(v) \in D^{\prime}$ and for two nodes $v,w \in V$ the edge $v \rightarrow w \in D$ if and only if $\pi(v) \rightarrow \pi(w) \in D^{\prime}$.

 


\begin{figure}[ht]
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.45cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[fill=lightgray] (h1) at (0,1.3) {$h_{1}$};
      \node[] (1) at (-2.5,0) {};
      \node[] (2) at (-1.5,0) {};
      \node[] (3) at (-0.5,0) {};
      \node[] (4) at (0.5,0) {};
      \node[] (5) at (1.5,0) {};
      \node[] (6) at (2.5,0) {};
      
      \draw[red, dashed] [-latex] (h1) edge (1);
      \draw[red, dashed] [-latex] (h1) edge (2);
      \draw[red, dashed] [-latex] (h1) edge (3);
      \draw[red, dashed] [-latex] (h1) edge (4);
      \draw[red, dashed] [-latex] (h1) edge (5);
      \draw[red, dashed] [-latex] (h1) edge (6);
      
    \end{tikzpicture}
    \caption{Latent structure of unlabeled latent-factor graph with one global latent factor.}
    \label{fig:exp-one-latent}
\end{figure}

\begin{table*}[ht]\centering 
\begin{tabular}{@{}c|rrrr@{}}\toprule
\shortstack{nr of obs. \\ edges $|D_V|$} & total & \shortstack{generically \\ finite-to-one} & \shortstack{rationally \\ identifiable} & \shortstack{LF-HTC- \\ identifiable} \\ 
\midrule
0 & 1 & 1 & 1 & 1  \\
1 & 1 & 1 & 1 & 1  \\
2 & 4 & 4 & 4 & 4  \\
3 & 13 & 13 & 13 & 13  \\
4 & 51 & 51 & 51 & 50  \\
5 & 163 & 160 & 159 & 134  \\
6 & 407 & 401 & 398 & 250  \\
7 & 796 & 770 & 747 & 234  \\
8 & 1169 & 1047 & 963 & 64  \\
9 & 1291 & 896 & 661 & 4  \\
\midrule
Total & 3896 & 3344 & 2998 & 755 \\
\bottomrule
\end{tabular}
\caption{Counts of unlabeled DAGs with $|V|=6$ observed nodes and one latent node as in Figure \ref{fig:exp-one-latent}.}
\label{table:exp-one-latent}
\end{table*}



In the second setup we consider two latent factors, each of them only having influence on some of the observed variables. The precise latent structure is illustrated in Figure \ref{fig:exp-two-latent}.  Since the number of isomorphism classes is much larger in this case, for computational reasons we only consider graphs with at most $|D_V|=6$ edges between observed nodes.  Up to this constraint, the observed part may be any DAG.  Table \ref{table:exp-two-latent} lists the counts for these graphs, again up to isomorphism. In this setup it is possible that the latent projection is rationally identifiable. Thus, we compare the LF-HTC with the original HTC applied to the projection and the results are counted in an additional column.

\begin{figure}[ht]
    \centering
    \tikzset{
      every node/.style={circle, inner sep=0.3mm, minimum size=0.45cm, draw, thick, black, fill=white, text=black},
      every path/.style={thick}
    }
    \begin{tikzpicture}[align=center]
      \node[fill=lightgray] (h1) at (-1,1.3) {$h_{1}$};
      \node[fill=lightgray] (h2) at (1.5,1.3) {$h_{2}$};
      \node[] (1) at (-2.5,0) {};
      \node[] (2) at (-1.5,0) {};
      \node[] (3) at (-0.5,0) {};
      \node[] (4) at (0.5,0) {};
      \node[] (5) at (1.5,0) {};
      \node[] (6) at (2.5,0) {};
      
      \draw[red, dashed] [-latex] (h1) edge (1);
      \draw[red, dashed] [-latex] (h1) edge (2);
      \draw[red, dashed] [-latex] (h1) edge (3);
      \draw[red, dashed] [-latex] (h1) edge (4);
      \draw[red, dashed] [-latex] (h2) edge (4);
      \draw[red, dashed] [-latex] (h2) edge (5);
      \draw[red, dashed] [-latex] (h2) edge (6);
      
    \end{tikzpicture}
    \caption{Latent structure of unlabeled latent-factor graphs with two latent factors.}
    \label{fig:exp-two-latent}
\end{figure}




\begin{table*}[ht]\centering 
\begin{tabular}{@{}c|rrrrr@{}}\toprule
\shortstack{nr of obs. \\ edges $|D_V|$} & total & \shortstack{generically \\ finite-to-one} & \shortstack{rationally \\ identifiable} & \shortstack{LF-HTC- \\ identifiable} & \shortstack{HTC- \\ identifiable}\\ 
\midrule
0 & 1 & 1 & 1 & 1 & 1\\
1 & 8 & 6 & 6 & 6 & 4 \\
2 & 63 & 45 & 45 & 43 & 24  \\
3 & 391 & 255 & 255 & 236 & 104 \\
4 & 1983 & 1171 & 1171 & 1018 & 384  \\
5 & 7570 & 3907 & 3898 & 3028 & 900  \\
6 & 21029 & 9080 & 8980 & 5861 & 1157 \\
\midrule
Total & 31045 & 14465 & 14356 & 10193 & 2574 \\
\bottomrule
\end{tabular}
\caption{Counts of unlabeled DAGs with $|V|=6$ observed nodes and two latent nodes as in Figure \ref{fig:exp-two-latent}.}
\label{table:exp-two-latent}
\end{table*}

In the considered setups, we see that the latent factor-criterion is very successful in certifying the graphs to be rationally identifiable as long as the number of observed edges $|D_V|$ is not too large. It misses more graphs the larger the number of observed edges is. Moreover, in the second setup, the latent-factor half-trek criterion  declares about four times more graphs to be rationally identifiable than the original half-trek criterion applied to the latent projection. 



\section{Proof of main result}
\label{sec:proof-lfhtc}
In this section we prove the main theorem.

\begin{proof}[Proof of Theorem \ref{thm:lfhtc}]
  Let $\mathrm{pa}_V(v) = \{p_1,\dots,p_n\}$, $H\subseteq \cL$ with $|H|=r$, $Y = \{y_1,\dots,y_{n+r}\}$, and $Z = \{z_1,\dots,z_r\}$ be as in the statement of the theorem. Define matrices $A\in\bR^{(n+r)\times n},B\in\bR^{(n+r)\times r}$ and a vector $c\in\bR^{n+r}$ as follows:
\[A_{ij} = \begin{cases}
\left[(I - \L)^\top\Sigma\right]_{y_ip_j},&\text{ if }y_i\in\mathrm{htr}_{H}(Z\cup \{v\}),\\
\Sigma_{y_ip_j},&\text{ if }y_i\not\in\mathrm{htr}_{H}(Z\cup\{v\}),
\end{cases}\]
and
\[B_{ij} = \begin{cases}
\left[(I - \L)^\top\Sigma(I -\L)\right]_{y_iz_j},&\text{ if }y_i\in\mathrm{htr}_{H}(Z\cup \{v\}),\\
\left[\Sigma(I -\L)\right]_{y_iz_j},&\text{ if }y_i\not\in\mathrm{htr}_{H}(Z\cup\{v\}),
\end{cases}\]
and
\[c_i = \begin{cases}
\left[(I-\L)^\top\Sigma\right]_{y_iv},&\text{ if }y_i\in\mathrm{htr}_{H}(Z\cup\{v\}),\\
\Sigma_{y_iv},&\text{ if }y_i\not\in\mathrm{htr}_{H}(Z\cup\{v\}).
\end{cases}\]

\textbf{Claim $1$.} The matrices $A$ and $B$ and the vector $c$ are
all rationally identifiable.  \\[0.1cm]
By assumption, all columns of $\L$ indexed by a vertex in $Z\cup (Y\cap \mathrm{htr}_{H}(Z\cup\{v\}))$ are rationally identifiable (i.e., rational functions of $\Sigma$).  Inspecting the above expressions, we observe that only entries from these columns of $\L$ appear in the definition of $A$, $B$, and $c$.  Hence, $A$, $B$, and $c$ are rationally identifiable, as claimed.


\smallskip

Next, note that there is a set $Y_Z \subseteq Y$ such that there is a system of latent-factor half-treks with no sided intersection from $Y_Z$ to $Z$. In this system each half-trek takes the form $y \leftarrow h \rightarrow z$ for $y \in Y$, $z \in Z$ and $h \in H$. Since the system has no sided intersection, it follows from Proposition 3.4 in \citet{sullivant2010trek} that $\det(\Omega_{Y_Z, Z}) \neq 0$ generically. Thus the matrix $\Omega_{Y, Z}$ has full column rank $r$ because $\Omega_{Y_Z, Z}$ is a submatrix. Using this fact we prove our next claim. 
\smallskip

\textbf{Claim $2$.} There exists some $\psi\in\bR^r$ such that
\begin{align*}
  \begin{pmatrix} A & B \end{pmatrix}\cdot \begin{pmatrix} \L_{\mathrm{pa}_V(v),v} \\ \psi\end{pmatrix} = c\,.
\end{align*}

\noindent
To see this, we will implicitly construct $\psi$.  Let $\O_h = \Gamma_h^{\top} \Gamma_h$ for each $h \in \cL$, and observe that
\begin{align*}
  \O_{Y,Z\cup\{v\}} = (\O_{\mathsf{diag}})_{Y,Z\cup\{v\}} + \sum_{h\in H}(\O_{h})_{Y,Z\cup\{v\}} + \sum_{h\in\cL\backslash H}(\O_{h})_{Y,Z\cup\{v\}}\;.
\end{align*}
Since $Y\cap (Z\cup\{v\})=\emptyset$ by definition of the
latent-factor half-trek criterion, we have that
$ (\O_{\mathsf{diag}})_{Y,Z\cup\{v\}} =0$.  The definition of the
latent-factor half-trek criterion yields furthermore that for any $h\in\cL\setminus H$, either $Y\cap \text{ch}(h)=\emptyset$ or
$(Z\cup\{v\})\cap \text{ch}(h) =\emptyset$.  Hence,
$(\O_{h})_{Y,Z\cup\{v\}}=0$.  We obtain that
\begin{align*}
  \O_{Y,Z\cup\{v\}} =  \sum_{h\in H}(\O_{h})_{Y,Z\cup\{v\}} = (\O_{H})_{Y,Z\cup\{v\}}\;,
\end{align*}
where $\O_{H} := \sum_{h\in H}\O_h$. Note that
$\text{rank}(\O_H)\leq |H| = r$.  Moreover, $(\O_H)_{V,Z}$ has full column
rank $r$ by assumption (since $\O_{Y,Z}$ is a submatrix of this
matrix), which proves that
\begin{equation}\label{eq:def-psi}
    (\O_H)_{V,Z} \cdot \psi = (\O_H)_{V,v}
\end{equation}
for some $\psi\in\bR^r$.


Next, consider any index $i$ such that $y_i\in\mathrm{htr}_{H}(Z\cup\{v\})$. Then
\begin{align}
\nonumber
&\left[\begin{pmatrix} A & B \end{pmatrix}\cdot \begin{pmatrix} \L_{\mathrm{pa}_V(v),v} \\ \psi\end{pmatrix} \right]_i\\
\nonumber
&=\left[(I - \L)^\top\Sigma\right]_{y_i,\mathrm{pa}_V(v)}\cdot \L_{\mathrm{pa}_V(v),v} + \left[(I - \L)^\top\Sigma(I -\L)\right]_{y_i,Z}\cdot \psi\\
\label{eq:id-equation}
&=\left[(I - \L)^\top\Sigma\cdot \L\right]_{y_iv} + \left[\O_{Y,Z}\cdot \psi\right]_i
\end{align}
because $\L_{wv}=0$ unless $w\in\mathrm{pa}_V(v)$ and $ (I-\L)^\top\Sigma(I-\L)=\O $.  Since $\O_{Y,Z\cup\{v\}} = (\O_{H})_{Y,Z\cup \{v\}}$, it follows from \eqref{eq:def-psi} that
\[
\left[\O_{Y,Z}\cdot \psi\right]_i = \left[\O_{Y,v}\right]_i = \O_{y_iv}.
\]
Hence, we may rewrite \eqref{eq:id-equation} as
\begin{align*}
\left[\begin{pmatrix} A & B \end{pmatrix}\cdot \begin{pmatrix} \L_{\mathrm{pa}_V(v),v} \\ \psi\end{pmatrix} \right]_i
&=\left[(I - \L)^\top\Sigma\right]_{y_iv} - \left[(I - \L)^\top\Sigma (I-\L)\right]_{y_iv} + \O_{y_iv}\\
&=\left[(I - \L)^\top\Sigma\right]_{y_iv} - \O_{y_iv} + \O_{y_iv}\\
&=c_i, 
\end{align*}
by the definition of $c$.

To conclude the proof of Claim 2, consider any index $i$ such that $y_i\not\in\mathrm{htr}_{H}(Z\cup\{v\})$.  For any such $i$, any latent-factor half-trek from a node $w\in Z\cup\{v\}$ to $y_i$ must be of the form
\[w \leftarrow h \rightarrow x_1 \rightarrow \dots \rightarrow x_m \rightarrow y_i\]
for some $h\in H$. This implies that
\begin{equation}\label{eqn:not_htr}\left[\O (I - \L)^{-1}\right]_{wy_i} = \left[\O_{H} (I - \L)^{-1}\right]_{wy_i}\end{equation}
for all $w\in Z\cup\{v\}$.  Consequently,
\begin{align}
\nonumber
\left[\begin{pmatrix} A & B \end{pmatrix}\cdot \begin{pmatrix} \L_{\mathrm{pa}_V(v),v} \\ \psi\end{pmatrix} \right]_i
&=\Sigma_{y_i,\mathrm{pa}(v)}\cdot \L_{\mathrm{pa}_V(v),v} + \left[\Sigma(I -\L)\right]_{y_i,Z}\cdot \psi\\
\nonumber
&=\left[\Sigma \L\right]_{y_i v} + \left[\Sigma(I -\L)\right]_{y_i,Z}\cdot \psi\\
\nonumber
&=\Sigma_{y_i v} - \left[\Sigma (I - \L)\right]_{y_i v} + \left[\Sigma(I -\L)\right]_{y_i,Z}\cdot \psi\\
\label{eq:claim2_3}
&=\Sigma_{y_i v} - \left[(I - \L)^{-\top}\O\right]_{y_i v} + \left[(I -\L)^{-\top}\O\right]_{y_i,Z}\cdot \psi,
\end{align}
because $\O = (I-\L)^\top\Sigma(I-\L)$.  Applying first~\eqref{eqn:not_htr} and then~\eqref{eq:def-psi}, we find that
\begin{align*}
- \left[(I - \L)^{-\top}\O\right]_{y_i v} &+ \left[(I -\L)^{-\top}\O\right]_{y_i,Z}\cdot \psi \\
&=- \left[(I - \L)^{-\top}\O_{H}\right]_{y_i v} + \left[(I -\L)^{-\top}\O_{H}\right]_{y_i,Z}\cdot \psi\\
&=- \left[(I - \L)^{-\top}\O_{H}\right]_{y_i v} + \left[(I -\L)^{-\top}\O_{H}\right]_{y_iv} \qquad=\; 0.
\end{align*}
Taking up \eqref{eq:claim2_3} and recalling the definition of $c$, we conclude that
\begin{align*}
\left[\begin{pmatrix} A & B \end{pmatrix}\cdot \begin{pmatrix} \L_{\mathrm{pa}_V(v),v} \\ \psi\end{pmatrix} \right]_i
&=\Sigma_{y_i v} = c_i.
\end{align*}

The theorem is now proven if the equation system exhibited in Claim 2 has a unique solution generically.  This is addressed by our last claim:
\smallskip

\textbf{Claim $3$.} The matrix
$\begin{pmatrix} A & B \end{pmatrix}$
is generically invertible.
\smallskip

\noindent
To prove Claim $3$, we will show that if we set some parameters equal to zero, then the considered matrix is invertible for generic choices of the remaining free parameters, which is sufficient to show that the matrix will be generically invertible with respect to choices of all parameters.


By assumption, the latent-factor graph $G^\cL$ contains a system of latent-factor half-treks from $Y$ to $Z\cup\mathrm{pa}_V(v)$, where half-treks terminating at any $z\in Z$ are of the form $y_i \leftarrow h \rightarrow z$ for some $h\in H$. 
 For every $z\in Z$, set $\L_{\mathrm{pa}_V(z),z}=0$. Furthermore, every node $h\in H$ appears in at most one of the latent-factor half-treks in the system. Suppose it appears as
$y_i \leftarrow h \rightarrow w$. Then we will define $\Omega_h$ to have value $\omega_{y_iw}$ at entries $\{y_i,w\}\times \{y_i,w\}$, and zeros elsewhere. 

Consider now a mixed graph $\widehat{G}$ constructed as follows. Starting with the induced subgraph $\widehat{G}=(V,D_V)$, first remove all edges with head in $Z$. Next, looking at the selected system of latent-factor half-treks from $Y$ to $Z\cup \mathrm{pa}_V(v)$ in the latent-factor graph $G^\cL$, any time we see a half-trek beginning with $y_i \leftarrow h\rightarrow w$, add a bidirected edge $y_i\leftrightarrow w$ to $\widehat{G}$.

By definition of the new graph $\widehat{G}$, the selected system of latent-factor half-treks from $Y$ to $Z\cup \mathrm{pa}_V(v)$ in $G^\cL$ has a corresponding system of half-treks in $\widehat{G}$.  Here, any latent-factor half-trek that begins with edges $y_i \leftarrow h \rightarrow w$ has these two initial two edges replaced by the bidirected edge $y_i\leftrightarrow w$.  The resulting system of half-treks in $\widehat{G}$ has no sided intersection. Let $\widehat{\L}$ and $\widehat{\O}$ be the parameter matrices for this graph. Note that $(I - \widehat{\L})_{*,Z} = I_{*,Z}$ because $\widehat{\L}_{*,Z}=0$ by construction. Therefore, we can write
\[B_{ij} = \begin{cases}
\left[(I - \L)^\top\Sigma\right]_{y_iz_j},&\text{ if }y_i\in\mathrm{htr}_{H}(Z\cup\{v\}),\\
\Sigma_{y_iz_j},&\text{ if }y_i\not\in\mathrm{htr}_{H}(Z\cup\{v\}).
\end{cases}\]
We now apply Lemma 2 in the original half-trek paper \citep{foygel2012halftrek} to conclude that $\begin{pmatrix} A & B \end{pmatrix}$
is generically invertible.
\end{proof}

\section{Discussion}
In this work we have proposed a graphical criterion that provides an effective sufficient condition for rational identifiability in linear structural equation models where latent variables are not projected to correlation among noise terms. To the best of our knowledge, it is the first general graphical criterion to decide identifiability on graphs explicitly including latent nodes. The new criterion can be checked in time that is polynomial in the size of the graph if we search only over subsets of latent nodes of bounded size. 
The restriction of the search space is necessary since checking the criterion without any restriction is in general NP-hard. 


The criterion applies to a wide range of models and allows for presence of multiple latent factors that may even have an effect on many or all of the observed variables. The corresponding directed graph is allowed to be cyclic, the only restriction is that all latent factors are source nodes in the graph. It is noteworthy that even if a model is not LF-HTC-identifiable, the latent-factor half-trek method can still prove certain columns of $\Lambda$ to be identifiable. This is the case if the recursive procedure of Algorithm \ref{alg:check-lfhtc} stops early declaring some but not all nodes to satisfy the LF-HTC.  In this case, the status of identifiability of the whole graph remains inconclusive but for the nodes $v$ that the method successfully visits, the parameters $\Lambda_{\mathrm{pa}_V(v), v}$ are proven to be rationally identifiable.

An interesting research program emerges from the work presented here.  Indeed, one may strive to improve and extend the efficiency of the LF-HTC along similar lines as those that have been applied in previous work in order to improve the original half-trek criterion for mixed graphs. 
In particular, it would be useful to find a latent-factor modification of the criterion for edgewise identifiability that allows for identification of a subset or even single direct causal effects $\lambda_{wv}$ instead of only targeting whole columns $\Lambda_{\mathrm{pa}_V(v), v}$; compare to \citet{weihs2017determinantal} and references therein.  This extension is of interest when effects between particular variables are the primary targets of investigation, but it may also make the criterion more powerful as a whole. Another way to extend the scope of the LF-HTC would be to apply graph decomposition techniques as proposed by \citet{tian2005identifying}; see also \citet{foygel2012halftrek} and \citet[Section 6]{drton:2018}. 

Furthermore, it would be interesting to generalize the LF-HTC to a version in which we relax the condition that all latent factors are source nodes in the graph. For example, one may consider models where latent nodes are only required to be \emph{upstream}, i.e., there may be direct causal effects between latent variables but no effects from observed variables to latent variables. Put differently, in addition to the equation system \eqref{eq:def-model} that defines the model, the vector of latent variables  $(L_h)_{h\in\mathcal{L}}$ is required to satisfy the equation
$$
    L = B^{T}L + \delta
$$
where $B$ is an $\ell \times \ell$ matrix with zeros along the diagonal and the noise terms $\delta = (\delta_h)_{h\in\mathcal{L}}$ are independent with mean zero and variance $1$. The latent covariance matrix is now of the form
$$
    \Omega = \O_{\mathsf{diag}} + \Gamma^{\top} (I_{\ell} - B)^{-\top} (I_{\ell} - B)^{-1} \Gamma.
$$
Thus the parametrization $\tau$ of the cone of latent covariance matrices is rational and depends on the three parameter matrices $(B, \Gamma, \O_{\mathsf{diag}})$. The question is how to identify effects between observed variables in this case, or, even more, what can be said in terms of identifying causal effects between latent variables. 


A different task for future work is to derive a non-trivial necessary condition for rational identifiability in the form of an efficient graphical criterion.  A starting point would be to study the Jacobian matrix of the parametrization $\phi_{G^\cL}$ in order to better understand the dimension of the model. If the dimension of the image is smaller than the dimension of the domain, the parametrization map has to be generically infinite-to-one by Lemma \ref{lem:finite-to-one}.  



\section*{Acknowledgments}
This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 883818). Nils Sturma acknowledges support by the Munich Data Science Institute (MDSI) at Technical University of Munich (TUM) via the Linde/MDSI PhD Fellowship program.  Rina Foygel Barber was supported by the U.S.~National Science Foundation via grants
DMS-1654076 and DMS-2023109, and by the Office of Naval Research via grant N00014-20-1-2337.


