Functorial Manifold Learning

Suppose we have a finite pseudometric space $(X,d_{X})$ that we assume has been sampled from some larger space $\mathbf{X}$ according to some probability measure $\mu_{\mathbf{X}}$ over $\mathbf{X}$. Manifold Learning algorithms like Isomap [23], Metric Multidimensional Scaling [2], and UMAP [19] construct $\mathbb{R}^{m}$-embeddings for the points in $X$, which we interpret as coordinates for the support of $\mu_{\mathbf{X}}$. These techniques are based on the assumption that this support can be well-approximated with a manifold. In this paper we use functoriality, a basic concept from Category Theory, to explore two aspects of manifold learning algorithms:

• •

  Equivariance: A manifold learning algorithm is equivariant to a transformation if applying that transformation to its inputs results in a corresponding transformation of its outputs. Understanding the equivariance of a transform lets us understand how it will behave on new types of data.

• •

  Stability: The stability of a manifold learning algorithm captures how well the embeddings it generates on noisy data approximate the embeddings it would generate on noiseless data. Understanding the stability of a transform helps us predict its performance on real-world applications.

Given a choice of $m\in\mathbb{N}$, a manifold learning algorithm constructs an $n\times m$ real valued matrix of embeddings in $\mathbf{Mat}_{n,m}=\mathbb{R}^{n\times m}$ from a finite pseudometric space with $n$ points. In this work we focus on algorithms that operate by solving embedding optimization problems, or tuples $(n,m,l)$ where $l:\mathbf{Mat}_{n,m}\rightarrow\mathbb{R}$ is a loss function, or a penalty term. We call the set of all $A\in\mathbf{Mat}_{n,m}$ that minimize $l(A)$ the solution set of the embedding optimization problem. In particular, we focus on pairwise embedding optimization problems, or embedding optimization problems where $l$ can be expressed as a sum of pairwise terms $l_{{}_{ij}}:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}$ such that $l(A)=\sum_{\begin{subarray}{c}i\in 1...n\\ j\in 1...n\end{subarray}}l_{{}_{ij}}(\|A_{i}-A_{j}\|)$. Intuitively the terms $l_{{}_{ij}}$ act as a penalty on bad embeddings. We express such a pairwise embedding optimization problem with the tuple $(n,m,\{l_{{}_{ij}}\})$.

Formally we define a manifold learning problem to be a function that maps the pseudometric space $(X,d_{X})$ to a pairwise embedding optimization problem of the form $(|X|,m,\{l_{{}_{ij}}\})$. Note that this definition does not include any specification of how the optimization problem is solved (such as gradient descent or reduction to an eigenproblem). For example, the Metric Multidimensional Scaling manifold learning problem maps the pseudometric space $(X,d_{X})$ to $(|X|,m,\{l_{{}_{ij}}\})$ where $l_{{}_{ij}}(\delta)=(d_{X}(x_{i},x_{j})-\delta)^{2}$. Optimizing this objective involves finding a matrix $A$ that minimizes $\sum_{\begin{subarray}{c}i,j\in 1...|X|\end{subarray}}(d_{X}(x_{i},x_{j})-\|A_{i}-A_{j}\|)^{2}$. That is, the Euclidean distance matrix of the rows of the optimal $A$ is as close as possible to the $d_{X}$ distance matrix.

If a manifold learning problem maps isometric pseudometric spaces to embedding optimization problems with the same solution set, we call it isometry-invariant. Intuitively, isometry-invariant manifold learning algorithms do not change their output based the ordering of $X$. A particularly useful property of isometry-invariant manifold learning problems is that they factor through hierarchical clustering algorithms.

Intuitively, Proposition 1 holds because manifold learning problems generate loss functions by grouping points in the finite pseudometric space together. In order to use this property to adapt clustering theorems into manifold learning theorems we will introduce a target category of pairwise embedding optimization problems and replace functions with functors from $\mathcal{\mathbf{PMet}}$ into this category. To start, consider the category $\mathbf{L}$:

Given a choice of $m$ we can view the object $(n,\{l_{{}_{ij}}\})$ in $\mathbf{L}$ as a pairwise embedding optimization problem. However, $\mathbf{L}$ is not quite expressive enough to serve as our target category. Recall the Metric Multidimensional Scaling manifold learning problem, which maps the pseudometric space $(X,d_{X})$ to the pairwise embedding optimization problem $(|X|,m,\{l_{{}_{ij}}\})$ where $l_{{}_{ij}}(\delta)=(d_{X}(x_{i},x_{j})-\delta)^{2}$. Since $l_{{}_{ij}}$ does not vary monotonically with $d_{X}$, it is clear that this manifold learning problem is not a functor from $\mathcal{\mathbf{PMet}}$ to $\mathbf{L}$. However, note that we can express $l_{{}_{ij}}(A)$ as the sum of a term that increases monotonically in $d_{X}(x_{i},x_{j})$ and a term that decreases monotonically in $d_{X}(x_{i},x_{j})$:

We will see in Section 2.3 that the embedding optimization problems associated with many common manifold learning algorithms decompose similarly. We can build on this insight to create a new category $\mathbf{Loss}$ with the following pullback:

where $U$ is the forgetful functor that maps $(n,\{l_{{}_{ij}}\})$ to $n$. Intuitively $\mathbf{Loss}$ is a subcategory of $\mathbf{L}^{op}\times\mathbf{L}$ and we can write the objects in $\mathbf{Loss}$ as tuples $(n,\{c_{{}_{ij}},e_{{}_{ij}}\})$ where $(n,\{c_{{}_{ij}},e_{{}_{ij}}\})\leq(n^{\prime},\{c_{{}_{ij}}^{\prime},e_{{}_{ij}}^{\prime}\})$ iff for any $x\in\mathbb{R}_{\geq 0},i,j\in\mathbb{N}$ we have $c_{{}_{ij}}^{\prime}(x)\leq c_{{}_{ij}}(x)$ and $e_{{}_{ij}}(x)\leq e_{{}_{ij}}^{\prime}(x)$. Given a choice of $m$, each object $(n,\{c_{{}_{ij}},e_{{}_{ij}})$ in $\mathbf{Loss}$ corresponds to the pairwise embedding optimization problem $(n,m,\{l_{{}_{ij}}\})$ where $l_{{}_{ij}}(\delta)=c_{{}_{ij}}(\delta)+e_{{}_{ij}}(\delta)$.

Similarly to the representation of hierarchical clustering algorithms as maps into a category $\mathbf{F}\mathbf{Cov}$ of functors $(0,1]^{\text{op}}\rightarrow\mathbf{Cov}$, we will represent manifold learning algorithms as mapping into a category $\mathbf{F}\mathbf{Loss}$ of functors $(0,1]^{\text{op}}\rightarrow\mathbf{Loss}$. The objects in $\mathbf{F}\mathbf{Loss}$ are functors $F:(0,1]^{\text{op}}\rightarrow\mathbf{Loss}$ that commute with the forgetful functor that maps $(n,\{c_{{}_{ij}},e_{{}_{ij}}\})$ to $n$, and the morphisms are natural transformations. We call $n$ the cardinality of $F$. We can define a functor $Flatten:\mathbf{F}\mathbf{Loss}\rightarrow\mathbf{Loss}$ which maps the functor $F$ where $F(a)=(n,\{c_{{F(a)}_{ij}},e_{{F(a)}_{ij}}\})$ to the tuple $(n,\{c_{{}_{ij}},e_{{}_{ij}}\})$ where:

Therefore, each functor $F\in\mathbf{F}\mathbf{Loss}$ with cardinality $n$ corresponds to the pairwise embedding optimization problem $(n,m,\{l_{{F}_{ij}}\})$ where $l_{{F}_{ij}}(\delta)=\int_{a\in(0,1]}c_{{F(a)}_{ij}}(\delta)+e_{{F(a)}_{ij}}(\delta)\ da$. We will call the sum of these terms, $\mathbf{l}_{F}(A)$, the $F$-loss:

We can now give our definition of a manifold learning functor:

Intuitively a manifold learning functor $\mathbf{D}\xrightarrow{H}\mathbf{D}^{\prime}\xrightarrow{L}\mathbf{F}\mathbf{Loss}$ factors through a hierarchical clustering functor and sends $(X,d_{X})$ to $F$ where $F(a)=(|X|,\{c_{{F(a)}_{ij}},e_{{F(a)}_{ij}}\})$. We will say that $M=L\circ H$ is in standard form if $M$ maps the one-point metric space $(\{*\},0)$ to some $F$ where $c_{{F(a)}_{ij}}(x)=e_{{F(a)}_{ij}}(x)=0$ and $\forall\epsilon,\delta\in\mathbb{R}_{\geq 0},H(X,d_{X}+\epsilon)(-\log(\delta))\simeq H(X,d_{X})(-\log(\delta+\epsilon))$. Each manifold learning functor corresponds to a manifold learning problem that maps $(X,d_{X})$ to $(|X|,m,\mathbf{l}_{M(X,d_{X})})$.

We can use this functorial perspective on manifold learning to reason about the stability of manifold learning algorithms under dataset noise. An $\epsilon$-interleaving between the functors $F,G:\mathbb{R}_{\geq 0}\rightarrow\mathbf{C}$ is a collection of commuting natural transformations between $F(\delta)\rightarrow G(\delta+\epsilon)$ and $G(\delta)\rightarrow F(\delta+\epsilon)$ [10, 11]. The interleaving distance $d_{I}$ between such functors is the smallest $\epsilon$ such that an $\epsilon$-interleaving exists. In order to study interleavings between functors in $\mathbf{F}\mathbf{Cov}$ or $\mathbf{F}\mathbf{Loss}$ whose domain is $(0,1]^{\text{op}}$ rather than $\mathbb{R}_{\geq 0}$, we will say that the functors $F,G$ are $\epsilon_{*}$-interleaved when there is an $\epsilon$-interleaving between the functors $F\circ r$ and $G\circ r$ where $r(x)=e^{-x}$. We will also write $d_{I_{*}}(F,G)=d_{I}(F\circ r,G\circ r)$.

Proposition 8 is similar in spirit to previous results that use the Gromov-Hausdorff distance between metric spaces to bound the bottleneck or homotopy interleaving distances between their corresponding Vietoris-Rips complexes [11, 8, 20, 6]. As a special case, if $M$ is an $\mathcal{\mathbf{PMet}}_{\mathit{bij}}$-manifold learning functor and there exists an $\epsilon$-isometry between $(X,d_{X}),(Y,d_{Y})$ then $d_{I_{*}}(M(X,d_{X}),M(Y,d_{Y}))\leq\epsilon$. We can use this to prove the following:

For a very simple example, consider Multidimensional Scaling without dimensionality reduction. In this case $M=\mathit{MDS}\circ\mathcal{ML}$ and $(X,d_{X}),(Y,d_{Y})$ are each finite ordered $n$-element subspaces of $\mathbb{R}^{m}$ with Euclidean distance. If we write the vectors in $X$ and $Y$ as matrices $A_{X},A_{Y}\in\mathbf{Mat}_{n,m}$, then these matrices respectively minimize $\mathbf{l}_{M(X,d_{X})}$ and $\mathbf{l}_{M(Y,d_{Y})}$, and $\mathbf{l}_{M(X,d_{X})}(A_{X})=\mathbf{l}_{M(Y,d_{Y})}(A_{Y})=0$. Since the function that sends the $i$th element of $X$ to the $i$th element of $Y$ must be an $\inf\{2\epsilon\ |\ \forall_{i}\|A_{X_{i}}-A_{Y_{i}}\|\leq\epsilon\}$-isometry, Proposition 9 bounds the average of the squared distances between the paired rows of two matrices in terms of the largest such distance.

These bounds apply to a very general class of manifold learning algorithms, including topologically unstable algorithms like IsoMap [5]. As an example, consider using IsoMap to project $n$ evenly spaced points that lie upon the surface of a radius $r$ circle in $\mathbb{R}^{2}$ onto $\mathbb{R}^{1}$. In this case $(X,d_{X})$ is a finite ordered $n$-element subspace of $\mathbb{R}^{2}$ with Euclidean distance, $M=\mathit{MDS}\circ IsoCluster_{\delta}$ and for any matrix $A_{X}\in\mathbf{Mat}_{n,1}$ that consists of $n$ evenly spaced points along the real line such that $A_{X_{i+1}}-A_{X_{i}}=2r\sin(\frac{2\pi}{2n})$ we have $\mathbf{l}_{M(X,d_{X})}(A_{X})=0$. Now suppose that we instead apply IsoMap to a noisy view of $(X,d_{X})$: a finite ordered $n$-element subspace $(Y,d_{Y})$ of $\mathbb{R}^{2}$ where $d_{Y}$ is Euclidean distance and $\forall_{i=1...n}d_{X}(X_{i},Y_{i})=d_{Y}(X_{i},Y_{i})=\|X_{i}-Y_{i}\|\leq\epsilon$. Then for any matrix $A_{Y}\in\mathbf{Mat}_{n,1}$ that minimizes $\mathbf{l}_{M(Y,d_{Y})}$, Proposition 9 bounds the average squared difference between $|A_{Y_{i+1}}-A_{Y_{i}}|$ and $2r\sin(\frac{2\pi}{2n})$.

One benefit of the functorial perspective on manifold learning is that it provides a natural way to produce new manifold learning algorithms by recombining the components of existing algorithms. Suppose we are able to express two existing manifold learning algorithms $M_{1},M_{2}$ in this framework such that $M_{1}=L_{1}\circ H_{1}$ and $M_{2}=L_{2}\ \circ H_{2}$ where $H_{1},H_{2}$ are hierarchical clustering functors. Then we can use the compositionality of functors to define the manifold learning algorithms $L_{2}\circ H_{1}$ or $L_{1}\circ H_{2}$. We can use this procedure to combine the strengths of multiple algorithms in a way that preserves functoriality (and therefore also stability by Proposition 9). For example, if we compose the $\mathit{FuzzySimplex}$ functor from Proposition 6 with $\mathit{MDS}$ we form the $\mathcal{\mathbf{PMet}}_{\mathit{isom}}$-manifold learning functor $\mathit{MDS}\circ\mathit{FuzzySimplex}$ which maps $(X,d_{X})$ to the embedding optimization problem $(|X|,m,l)$ where $l(A)=\sum_{\begin{subarray}{c}i,j\in 1...|X|\end{subarray}}(-\log(\alpha_{ij})-\|A_{i}-A_{j}\|)^{2}$ and $\alpha_{ij}$ is the strength of the fuzzy simplex that UMAP forms between $x_{i}$ and $x_{j}$.

For a more illustrative example, consider a DNA recombination task in which we attempt to match a string of DNA that has been repeatedly mutated back to the original string. One way to solve this task is to generate embeddings for each string of DNA and look at the nearest neighbors of the mutated string. We can simulate this task as follows

1. 1.

   Generate $N$ original random sequences of DNA of length $L$ (strings of “A”, “C”, “G”, “T”).

2. 2.

   For each sequence, mutate the sequence $M$ times to produce a mutation list, or a list of sequences which each start with an original DNA sequence and end with a final DNA sequence.

3. 3.

   Collect each of the $M$ sequences in each of these $N$ mutation lists into an $N*M$ element finite pseudometric space with Hamming distance.

4. 4.

   Build embeddings from this pseudometric space and compute the percentage of mutation lists for which the nearest neighbor of the last DNA sequence in that list among the set of all original sequences is the first sequence in that list (the accuracy).

A manifold learning algorithm that performs well on this task will need to take advantage of the intermediate mutation states to recognize that the first state and final state in a mutation list should be embedded as close together as possible. We can follow the procedure in Section 2.1 to adapt the Metric Multidimensional Scaling algorithm $\mathit{MDS}\circ\mathcal{ML}$ (Section 2.3.1) into such an algorithm by forming the maximally interconnected functor $\mathit{MDS}\circ\mathcal{SL}$. Intuitively, this functor maps $(X,d_{X})$ to a loss function that corresponds to the optimization objective for Metric Multidimensional Scaling where Euclidean distance is replaced with:

We call this the Single Linkage Scaling algorithm (Algorithm 1). Since this algorithm embeds points that are connected by a sequence in the original space as close together as possible, we expect Single Linkage Scaling to outperform Metric Multidimensional Scaling on this task. This is exactly what we see in Table 4. We also show the embeddings for each sequence in each list in Figure 1.