# Stability for UMAP

J.F. Jardine Supported by NSERC. Department of Mathematics
University of Western Ontario
London, Ontario, Canada

###### Abstract

This paper displays the Healy-McInnes UMAP construction V(X,N) as an iterated
ushout of Vietoirs-Rips objects $V(X,D_{x})$, which are associated to extended
pseudo metric spaces (ep-metric spaces) defined by a system $N$ of
neighbourhoods of the elements of a finite set $X$. An inclusion of finite
sets $X\subset Y$ defines a map of UMAP systems $V(X,N)\to V(Y,N^{\prime})$ in
the presence of a compatible system of neighbourhoods $N^{\prime}$ for $Y$.
There is also an induced map of ep-metric spaces $(X,D)\to(Y,D^{\prime})$,
where $D$ and $D^{\prime}$ are colimits (global averages) of the metrics
defined by the respective neighbourhood systems. We prove a stablity result
for the restriction of this ep-metric space map to global components. This
stability result translates, via excision for path components, to a stability
result for global components of the UMAP systems.

The main result of [1] says that if $X$ is a finite extended pseudo-metric
space (ep-metric space), then the canonical map

$\eta:V(X)_{s}\to S(X)_{s}$

is a weak equivalence for all distance parameters $s$. Here, $V(X)$ is the
Vietoris-Rips system and $X\mapsto S(X)$ is the singular functor.

In this paper, we use this result to model the UMAP construction, and we prove
a stability result for the resulting hierarchies of clusters.

For the general program, we start with sets $N_{x}$ (disjoint from $x$) for
each $x\in X$, and distances (or weights) $d_{x}(x,y)\geq 0$ for all $y\in
N_{x}$. These distances canonically extend to an ep-metric space structure
$(U_{x},D_{x})$ on the set

$U_{x}=\\{x\\}\sqcup N_{x},$

and then to an ep-metric space structure $(X,D_{x})$ on all of $X$, for which
$D_{x}(y,z)=\infty$ unless both $y$ and $z$ are in $U_{x}$. The metric space
structures $(X,D_{x})$ can be glued together along ep-metric space morphisms
$(X,\infty)\to(X,D_{x})$ to produce an ep-metric space

$(X,D)=\vee_{x\in X}\ (X,D_{x}).$

Similarly, the Vietoris-Rips systems $V(X,D_{x})$ can be glued together along
the maps $X\to V(X,D_{x})$ to produce a system

$V(X,N)=\vee_{x\in X}\ V(X,D_{x}).$

The notation $V(X,N)$ reflects the fact that this system of spaces depends on
the family $N=\\{N_{x},\ x\in X\\}$ of neighbourhoods, which includes choices
of weights $d_{x}$ within each neighbourhood $N_{x}$.

The object $V(X,N)$, for suitable choices of neighbourhoods and weights, gives
the various models for the UMAP system.

The original UMAP system $S(X,N)$ of Healy and McInnes [2], is constructed
from Spivak’s singular functor [3], [1], with

$S(X,N):=\vee_{x\in X}\ S(X,D_{x}).$

There is a sectionwise weak equivalence $V(X,N)\to S(X,N)$ by the main result
of [1], and we use the Vietoris-Rips construction $V(X,N)$ since it is more
familiar and easier to manipulate.

The choice of neighbourhood sets $N_{x}$ can be arbitrary, but in [2] it is
the set of $k$-nearest neighbours. The collections of distances $d_{x}(x,y)$
are also arbitrary, but are defined in [2], variously, as the original
distance $d_{x}(x,y)=d(x,y)$ or the probability
$d_{x}(x,y)=\frac{1}{r_{x}}d(x,y)$, or
$d_{x}(x,y)=\frac{1}{r_{x}}(d(x,y)-s_{x})$. Here, $r_{x}=\max_{y\in
N_{x}}d(x,y)$ and $s_{x}=\min_{y\in N_{x}}d(x,y)$.

All corresponding constructions $V(X,N)$ are variants of the UMAP
construction, and they are easily compared. The shrpest results on the general
structure of $V(X,N)$ require the weights $d_{x}(x,y)>0$ for $y\in N_{x}$, and
this is assumed for most of the paper.

Suppose given an ep-metric space map $i:(X,d_{X})\to(Y,d_{Y})$, where the
underlying function is an injection, and $X$ and $Y$ are finite. The
assumption that $i$ is an ep-metric space morphism means that $i$ compresses
distance in the sense that $d_{Y}(i(x),i(y))\leq d_{X}(x,y)$ for all $x,y\in
X$.

We can assume for now that $X$ and $Y$ are metric spaces, and are therefore
globally connected in the sense that $d(x,y)<\infty$ for all $x,y$. In that
case, since $X$ is finite, we define the compression factor $m(i)$ by

$m(i)=\max_{x\neq y}\ \frac{d_{X}(x,y)}{d_{Y}(i(x),i(y))}$

This makes sense because none of the distances in the ratio are either $0$ or
$\infty$.

If we further assume that for every $y\in Y$ there is an $x\in X$ such that
$d_{Y}(y,x)\leq r$, then the same argument as for the ordinary Rips stability
theorem produces a homotopy interleaving

$\textstyle{V(X)_{s}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\scriptstyle{i}$$\textstyle{V(X)_{m(i)(s+2r)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{i}$$\textstyle{V(Y)_{s}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\scriptstyle{\theta}$$\textstyle{V(Y)_{m(i)(s+2r)}}$

This statement appears as Proposition 8 in this paper.

Suppose now that $i:X\subset Y$ is an inclusion of finite sets, and we have
made choice of neighbourhoods $N_{x},\ x\in X$ and $N_{y},\ y\in Y$. Suppose
that

  * 1)

the inclusion $i$ induces inclusions $i:N_{x}\subset N_{i(x)}$, and

  * 2)

the weights are chosen such that $d_{x}(x,x^{\prime})>0$ for $x^{\prime}\neq
x\in N_{x}$, $d_{y}(y,y^{\prime})>0$ for $y^{\prime}\neq y\in N_{y}$, and
$d_{i(x)}(i(x),i(y))\leq d_{x}(x,y)$ for all $y\in N_{x}$.

The assumptions imply that the inclusion $i$ induces an ep-metric space map
$i:(X,D)\to(X,D^{\prime})$, and the global connected components of both ep-
metric spaces are metric spaces. If $E$ is a global connected component of
$(X,D)$, then there is a global connected component $F$ of $(Y,D^{\prime})$
such that $i$ restricts of a ep-metric space morphism
$i:(E,D)\to(F,D^{\prime})$ of metric spaces.

Subject to the assumptions of the last paragraph, it follows from Proposition
8 that, if for every $y\in F$ there is an $x\in E$ such that
$d_{Y}(y,i(x))\leq r$, then there is a homotopy interleaving

$\textstyle{V(E,D)_{s}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\scriptstyle{i}$$\textstyle{V(E,D)_{m(i)(s+2r)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{i}$$\textstyle{V(F,D^{\prime})_{s}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\scriptstyle{\theta}$$\textstyle{V(F,D^{\prime})_{m(i)(s+2r)}}$
(1)

This is a componentwise stability result for the ep-metric space morphism
$i:(X,D)\to(Y,D^{\prime})$, which appears as Theorem 9 in this paper. The
input for this result involves compatible choices of neighbourhoods and
weights within those neighbourhoods, rather than distance.

The canonical ep-metric space maps $(X,D_{x})\to(X,D)$ induce a map of systems

$\phi:V(X,N)=\vee_{x\in X}\ V(X,D_{x})\to V(X,D)$

which is natural with respect to inclusions $i:X\subset Y$ satisfying the
conditions above.

The ep-metric space $(X,D)$ is a disjoint union of its global connected
components $E$, and the system $V(X,D)$ is a disjoint union of the systems
$V(E,D)$. This splitting defines a disjoint union structure

$V(X,N)=\bigsqcup_{E}\ V(X,N)(E),$

where $V(X,N)_{E}$ is the pullback of the system $V(E)$ under the map $\phi$.
The induced map

$\phi_{\ast}:\pi_{0}V(X,N)(E)\to\pi_{0}V(E)$

is an isomorphism of systems of sets, by path component excision (Lemma 2).

The componentwise stability result displayed in the interleaving (1) therefore
specializes to interleavings in clusters

$\textstyle{\pi_{0}V(X,N)(E)_{s}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\scriptstyle{i}$$\textstyle{\pi_{0}V(X,N)(E)_{m(i)(s+2r)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{i}$$\textstyle{\pi_{0}V(Y,N^{\prime})(F)_{s}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\scriptstyle{\theta}$$\textstyle{\pi_{0}V(Y,N^{\prime})(F)_{m(i)(s+2r)}}$
(2)

This is a stability result for UMAP, which appears as Theorem 10 below.
Theorem 10 is the main result of this paper.

###### Contents

  1. 1 General constructions
  2. 2 UMAP
  3. 3 Stability

##  1 General constructions

Suppose that we have a set $X$ with a finite list of ep-metric space
structures $(X,d_{i})$, $i=1,\dots,k$. We can also endow $X$ with a discrete
ep-metric space structure, so that $d_{\infty}(x,y)=\infty$ for all $x,y\in
X$. Suppose that $X$ has a total ordering.

There are canonical ep-metric space morphisms $(X,d_{\infty})\to(X,d_{i})$,
all of which are the identity on $X$. Write $(X,D)$ for the colimit in
$ep-\mathbf{Met}$, giving a diagram

$\textstyle{(X,d_{\infty})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{(X,d_{i})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau_{i}}$$\textstyle{(X,d_{j})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tau_{j}}$$\textstyle{(X,D)}$

The maps $\tau_{i}:(X,d_{i})\to(X,D)$ are the canonical maps into the colimit.
Recall [1] that the colimit $(X,D)$ is formed by taking the colimit of the
underlying functions, and endowing it with a metric, in this case $D$. The
colimit of functions, which are identity functions on $X$, is $X$ again, so
that the notation $(X,D)$ makes sense.

We also write

$(X,D)=\vee_{i}\ (X,d_{i})$

to reflect the fact that we are gluing together the ep-metric spaces
$(X,d_{i})$ along the underlying set $X$.

Formally,

$D(x,y)=\inf_{P}\ (\sum\ d_{i_{j}}(x_{j},x_{j+1})),$

indexed over all polygonal paths

$x=x_{0},x_{1},\dots,x_{n}=y$

and choices of metrics $d_{i_{j}}$ in the list $d_{i},\ 1\leq i\leq k$. The
pair $x,y$ forms a polygonal path, so that

$D(x,y)\leq d_{i}(x,y)$

for all $i$. In this sense, the ep-metric $D$ optimizes the metrics $d_{i}$.

There may not be a polygonal path $P$ and metrics $d_{i_{j}}$ such that all
$d_{i_{j}}(x_{i},x_{i+1})$ are finite. In that case, we have $D(x,y)=\infty$.

If $X$ is a finite set, then the collection of polygonal paths from $x$ to $y$
in $X$ is finite, and so

$D(x,y)=\sum\ d_{i_{j}}(x_{j},x_{j+1})$

for some choice of polygonal path $P$ and metrics $d_{i_{j}}$. In that case,
$d_{i_{j}}(x_{j},x_{j+1})$ must be minimal among all $d_{k}(x_{j},x_{j+1})$.

The maps $(X,d_{\infty})\to(X,d_{i})$ induce maps $X\to V(X,d_{i})$ into
Vietoris-Rips systems, and we form the iterated pushout

$V(X,D):=\vee_{i}\ V(X,d_{i})$ (3)

in the category of systems. This means that the object (3) is the colimit of
all maps

$X\to V(X,d_{i}),$ (4)

over the discrete system $X$. The maps (4) are sectionwise monomorphisms, so
the object $V(X,D)$ is a type of homotopy colimit.

######  Remark 1.

In practice and in general, although one tends to be notationally lazy, it is
better to replace the Vietoris-Rips system $s\mapsto V_{s}(X)$ with the
homotopy equivalent system $s\mapsto BP_{s}(X)$, where $P_{s}(X)$ is the poset
of non-degenerate simplices of $V_{s}(X)$, and $BP_{s}(X)$ is the nerve of
$P_{s}(X)$. The poset $P_{s}(X)$ can be described explicitly as the collection
of subsets $\sigma$ of $X$ such that $d(x,y)\leq s$ for all $x,y\in\sigma$.
The structure of the poset $P_{s}(X)$ does not depend on an ordering of the
set $X$.

The ep-metric space maps $(X,d_{i})\to(X,D)$ induce commutative diagrams

$\textstyle{BP(X,d_{i})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\gamma}$$\scriptstyle{\simeq}$$\textstyle{BP(X,D)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\gamma_{\ast}}$$\textstyle{V(X,d_{i})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{V(X,D)}$

of maps of systems, where the map $\gamma$ is a sectionwise weak equivalence
defined by subdivision, and the induced map $\gamma_{\ast}$ is a sectionwise
weak equivalence arising from the displayed comparison of homotopy colimits.

From this perspective, we can write

$V(X,D)=BP(X,D)=\vee_{i}\ BP(X,d_{i})=\vee_{i}\ V(X,d_{i})$

as sectionwise homotopy types.

######  Lemma 2 (Excision).

Suppose that $X$ is a finite set, with a finite collection of ep-metric
structures $d_{i}$.

Then the canononical map

$\phi:\vee_{i}\ V(X,d_{i})\to V(X,D)$

induces bijections

$\phi_{\ast}:\pi_{0}(\vee_{i}\
V(X,d_{i}))_{s}\xrightarrow{\cong}\pi_{0}V(X,D)_{s}$

for all $s$.

###### Proof.

The map $\phi$ is the identity on vertices, so that $\phi_{\ast}$ is
surjective.

Suppose that $D(x,y)\leq s$ in $(X,D)$. There is a polygonal path

$P:x=x_{0},x_{1},\dots,x_{n}=y$

and metrics $d_{i_{j}}$ such that

$D(x,y)=\sum_{j}\ d_{i_{j}}(x_{j},x_{j+1})\leq s,$

since $X$ is finite. This means that $d_{i_{j}}(x_{j},x_{j+1})\leq s$ for all
$j$, and so there are $1$-simplices $(x_{j},x_{j+1})$ in $V(X,d_{i_{j}})_{s}$
which together describe a path from $x$ to $y$ in $\vee_{X}\ V_{s}(X,d_{i})$.

It follows that, if $x,y$ are in the same path component of $V(X,D)_{s}$, then
$x,y$ are in the same path component of $\vee_{i}V(X,d_{i})_{s}$. ∎

##  2 UMAP

The UMAP algorithm of [2] starts with a finite metric space $X$. We assume
that $X$ has a total ordering.

For each point $x\in X$ one finds the list

$N_{x}:=\\{x_{1},\dots,x_{k}\\}$

of distinct $k$-nearest neighbours with $x_{i}\neq x$, with maximum distance
$r_{x}=\max_{i}\ d(x,x_{i})$.

The set $N_{x}$ is the set of neighbours of $x$.

In much of what follows, the choices of the sets $N_{x}$ can be quite
arbitrary. In all applications, one assigns distances $d_{x}(x,y)$ for all
neighbours $y\in N_{x}$, and then one extends functorially to an ep-metric
$D_{x}$ on $X$. This is done for all $x\in X$.

Examples: Possibilities for $d_{x}(x,y)$ include $\frac{1}{r_{x}}d(x,y)$,
$\frac{1}{r_{x}}(d(x,)-\eta_{x})$ where $\eta_{x}$ is the distance from $x$ to
a nearest neighbour. We can also use the ambient metric $d_{x}(x,y)=d(x,y)$
from $X$.

######  Remark 3.

Explicitly, given $x\in X$ we find a set (and a listing)
$N_{x}=\\{x_{1},\dots,x_{k}\\}$ of $k$-nearest neighbours, by finding an
element $x_{1}$ (in the total order) such that $d(x,x_{1})$ is minimal
($x_{1}$ is a nearest neighbour). Then $x_{2}\in X-\\{x,x_{1}\\}$ is chosen
such that $d(x,x_{2})$ is minimal and $x_{2}$ is the first element in the
total order that has this property, and so on.

The algorithm is set up such that the sublist
$\\{x_{i},x_{i+1},\dots,x_{k}\\}$ of elements having $d(x,x_{j})=r$ has
$x_{i}<x_{i+1}<\dots<x_{k}$ in the total order.

Assumptions: Suppose that $X$ is a finite set. Suppose given a system of
neighbourhoods $N_{x}$ for $x\in X$, and define distances $d_{x}(x,y)>0$ for
each $y\in N_{x}$.

One defines an ep-metric $D_{x}$ first on the set

$U_{x}=\\{x\\}\sqcup N_{x}$

and then one extends to all of $X$ with the decomposition

$X=U_{x}\sqcup(\bigsqcup_{y\in X-U_{x}}\ \\{y\\}).$ (5)

The ep-metric space structure on the set $U_{x}$ is given by the wedge

$(U_{x},D_{x})=\vee_{y\in N_{x}}\ (\\{x,y\\},d_{x})$

over $x$ of the $2$-element metric spaces $(\\{x,y\\},d_{x})$, in the category
of ep-metric spaces. The metric $D_{x}$ on $U_{x}$ has the property that
$D_{x}(x,y)=d_{x}(x,y)$ for $y\in N_{x}$. The triangle inequality forces

$D_{x}(y,z)\leq d_{x}(y,x)+d_{x}(x,z)$

for $y\neq z$ in $N_{x}$. At the same time, the sum $d_{x}(y,x)+d_{x}(x,z)$ is
the length of the shortest polygonal path $(y,x,z)$ between $y$ and $z$ in
$U_{x}$, and so it follows that

$D_{x}(y,z)=d_{x}(y,x)+d_{x}(x,z)$

for $y\neq z$ in $N_{x}$.

Use the decomposition (5) to extend $D_{x}$ to an ep-metric on all of $X$.
This forces $D_{x}(y,z)=\infty$ unless $y$ and $z$ are both in $U_{x}$.

Define systems of simplicial sets $V(X,N)$ and $S(X,N)$ by setting

$V(X,N)=\vee_{x\in X}V(X,D_{x})$

and

$S(X,N)=\vee_{x\in X}S(X,D_{x}),$

respectively. Here, $V(X,N)$ is the iterated pushout of the cofibrations $X\to
V(X,D_{x})$, where the set $X$ is identified with a constant, discrete system.
Similarly, $S(X,N)$ is the iterated pushout of the cofibrations $X\to
S(X,D_{x})$.

The maps $\eta:V(X,D_{x})\to S(X,D_{x})$ are sectionwise weak equivalences by
[1], and therefore induce a sectionwise weak equivalence

$\eta:V(X,N)\to S(X,N)$ (6)

by comparison of iterated pushouts (or homotopy colimits).

Spivak’s realization construction $\operatorname{Re}$ preserves colimits, and
there is a natural isomorphism $\operatorname{Re}(V(X,D_{x}))\cong(X,D_{x})$
(see [1]), so that the realization

$\operatorname{Re}(V(X,D))\cong\vee_{X}\ (X,D_{x})=(X,D)$

is the iterated pushout of the maps $X\to(X,D_{x})$ in the ep-metric space
category, as in the first section.

######  Remark 4.

The set $X$ is finite. The distances $d_{x}$ have the property that
$d_{x}(x,y)>0$ for all $y\in N_{x}$, $x\in X$, and one can show that
$D(u,v)=0$ in $(X,D)$ forces $u=v$.

In effect, $D(u,v)$ is a sum

$D(u,v)=\sum D_{z_{i}}(x_{i},x_{i+1})$

which is defined by a particular polygonal path $P:u=x_{0},\dots,x_{n}=v$
(since there are only finitely many such paths). Then $D(u,v)=0$ forces all

$D_{z_{i}}(x_{i},x_{i+1})=d_{z_{i}}(x_{i},z_{i})+d_{z_{i}}(z_{i},x_{i+1})$

to be $0$, so that $x_{i}=z_{i}=x_{i+1}$ for all $i$, and $u=v$.

######  Remark 5.

It is time for a homotopy theory interlude.

Suppose that each map

$V=\\{0,1,\dots,n\\}\subset\Delta^{n}=X_{i},\ i\geq 0,$

is the inclusion of the set of vertices $V$ of the standard $n$-simplex
$\Delta^{n}$, and let $Y_{k}=X_{0}\cup\dots\cup X_{k}$ be an iterated pushout
of $n$-simplices over the common vertex set $V$.

There is a pushout diagram

$\textstyle{V\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X_{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{X_{0}\cup_{V}X_{1}}$

in which both $X_{0}$ and $X_{1}$ are contractible. It follows that
$X_{0}\cup_{V}X_{1}$ has the homotopy type of the suspension
$X_{1}/V\simeq\Sigma V$ for a suitable choice of base point of the discrete
set $V$ — choose $0$. Then $V=\\{0,1\\}\vee\\{0,2\\}\vee\dots\vee\\{0,n\\}$ is
a wedge of $n$ copies of $S^{0}$, and $\Sigma V$ is a wedge of $n$ copies of
$\Sigma S^{0}=S^{1}$. Thus,

$Y_{1}=X_{0}\cup_{V}X_{1}\simeq S^{1}\vee\dots\vee S^{1}\enskip\text{($n$
summands)}.$

More generally, consider the space
$Y_{k}=X_{0}\cup_{V}X_{1}\cup_{V}\dots\cup_{V}X_{k}$. Collapsing the
contractible space $X_{0}$ to a point gives

$Y_{k}\simeq(X_{1}/V)\vee(X_{2}/V)\vee\dots\vee(X_{k}/V).$

Each $X_{i}/V$ is an $n$-fold wedge of circles, by the above, so that $Y_{k}$
is a $k\cdot n$-fold wedge of circles.

Suppose that the finite set $X$ has $M+1$ elements. Then $V(X,D)_{\infty}$ is
an iterated pushout of the maps $X\subset V(X,D_{x})_{\infty}$. Each
$V(X,D_{x})_{\infty}$ is a copy of the $M$-simplex $\Delta^{M}$, and each map
$X\subset V(X,D_{x})_{\infty}$ is a copy of the inclusion of vertices
$\mathbf{M}\subset\Delta^{M}$.

It follows that $V(X,D)_{\infty}$ is a large wedge of circles. Explicitly,
there is a weak equivalence

$V(X,D)_{\infty}\simeq\vee_{M^{2}}\ S^{1}.$

This space is path connected.

The system of path component sets

$s\mapsto\pi_{0}V(X,d)_{s}$

therefore describes a hierarchy, as in the standard algorithms of topological
data analyis.

##  3 Stability

Suppose that $(X,d)$ is an ep-metric space, and that $x\in X$. The global
connected component of $x$ is the collection of $y\in X$ such that
$d(x,y)<\infty$. Say that $X$ is globally connected if $d(x,y)<\infty$ for all
$x,y\in X$.

Global connectedness has the following general properties:

  * 1)

Every ep-metric space $(X,d)$ is a disjoint union of its set
$\pi_{\infty}(X,d)$ of global components.

  * 2)

An ep-metric space morphism $f:(X,d_{X})\to(Y,d_{Y})$ preserves global
connected components: if $d_{X}(x,y)<\infty$ then

$d_{Y}(f(x),f(y))\leq d_{X}(x,y)<\infty,$

so that $f(y)$ is in the connected component of $f(x)$. We therefore have an
induced function $f_{\ast}:\pi_{\infty}(X,d_{X})\to\pi_{\infty}(Y,d_{Y})$.

  * 3)

Every metric space is globally connected.

######  Example 6.

Suppose that $X$ is a finite set with a system of neighbourhoods $N_{x}$ and
associated distances $d_{x}$ for all $x\in X$ as in the list of Assumptions
above, with the resulting ep-metric space $(X,D)$.

The ep-metric space $(X,D)$ has the property that $D(x,y)=0$ forces $x=y$, by
Remark 4. It follows that the global connected components of the ep-metric
space $(X,D)$ are metric spaces.

Say that a pair of elements $(x,y)$ of $X$ is a neighbourhood pair if $x\in
N_{y}$ or $y\in N_{x}$. The argument of Remark 4 shows that elements $u$ and
$v$ of $(X,D)$ are in the same global connected component if and only if there
is a polygonal path

$P:u=x_{0},x_{1},\dots,x_{n}=v$

such that each pair $(x_{i},x_{i+1})$ is a neighbourhood pair.

Suppose that $(X,d_{X})$ and $(Y,d_{Y})$ are finite metric spaces, and that
there is a monomorphism $i:X\subset Y$ that defines a map of ep-metric spaces,
so that $d_{Y}(x,y)\leq d_{X}(x,y)$ for all $x,y\in X$. Set

$m(i)=\max_{x\neq y\in X}\ \\{\frac{d_{X}(x,y)}{d_{Y}(i(x),i(y))}\\}.$

Then $1\leq m(i)<\infty$ since $X$ is finite.

The number $m(i)$ is the compression factor for the monomorphism $i$.

######  Example 7.

Suppose that $i:X\subset Y$ is an inclusion of finite sets, and choose systems
of neighbourhoods $N_{x}$, $x\in X$ and $N^{\prime}_{y}$, $y\in Y$, with
distances $d_{x}$ and $d^{\prime}_{y}$. Suppose that $N_{x}\subset
N^{\prime}_{i(x)}$ for all $x\in X$, and that

$d_{i(x)}^{\prime}(i(x),i(z))\leq d_{x}(x,z)$ (7)

for all $z\in N_{x}$, and for all $x\in X$.

Then the inclusions $i:N_{x}\subset N^{\prime}_{i(x)}$ and the relations (7)
define system morphisms $V(X,D_{x})\to V(Y,D^{\prime}_{i(x)})$ and $V(X,D)\to
V(Y,D^{\prime})$, as well as ep-metric space morphisms
$(X,D)\to(Y,D^{\prime})$.

The ep-metric space map $(X,D)\to(Y,D^{\prime})$ is the realization of the
system morphism $V(X,D)\to V(Y,D^{\prime})$.

The ep-metric space morphism $(X,D)\to(Y,D^{\prime})$ preserves global
connected components, and the global connected components of $(X,D)$ and
$(Y,D^{\prime})$ are finite metric spaces.

For the following, recall that if $(X,d)$ is an ep-metric space, then
$P_{s}(X,d)$ is the poset of subsets $\sigma$ of $X$ such that $d(x,y)\leq s$
for all $x,y\in\sigma$. Recall further that the nerve $BP_{s}(X,d)$ is the
barycentric subdivision of the Vietoris-Rips complex $V(X,d)_{s}$, so that the
systems $BP(X,d)$ and $V(X,d)$ are naturally sectionwise homotopy equivalent.

######  Proposition 8.

Suppose that $i:X\subset Y$ is an inclusion of finite sets. Suppose that $X$
and $Y$ have metric space structures such that $i$ defines a morphism
$i:(X,d_{X})\to(Y,d_{Y})$ of ep-metric spaces. Suppose that for esvery $y\in
Y$ there is an $x\in X$ such that $d_{Y}(y,i(x))<r$ in $Y$.

Then there are diagrams of poset morphisms

$\textstyle{P_{s}(X,d_{X})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\scriptstyle{i}$$\textstyle{P_{m(i)\cdot(s+2r)}(X,d_{X})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{i}$$\textstyle{P_{s}(Y,d_{Y})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\scriptstyle{\theta}$$\textstyle{P_{m(i)\cdot(s+2r)}(Y,d_{Y})}$

for all $0\leq s<\infty$, in which the upper triangle commutes and the lower
triangle homotopy commutes rel $P_{s}(X,d_{X})$.

###### Proof.

Define a function $\theta:Y\to X$ by setting $\theta(x)=x$ for $x\in X$, and
by choosing $\theta(y)$ such that $d_{Y}(y,i(\theta(y)))<r$ for $y$ outside of
$X$.

Then

$\displaystyle d_{Y}(i(\theta(y_{1})),i(\theta(y_{2})))$ $\displaystyle\leq
d_{Y}(i(\theta(y_{1})),y_{1})+d_{Y}(y_{1},y_{2})+d_{Y}(y_{2},i(\theta(y_{2})))$
$\displaystyle<d_{Y}(y_{1},y_{2})+2r,$

and it follows that

$d_{X}(\theta(y_{1}),\theta(y_{2}))\leq m(i)\cdot(d_{Y}(y_{1},y_{2})+2r).$

If $\sigma=\\{y_{1},\dots,y_{n}\\}$ is a subset of $Y$ such that
$d(y_{j},y_{k})\leq s$ for all $j,k$, then
$\theta(\sigma)=\\{\theta(y_{1}),\dots,\theta(y_{n})\\}$ has
$d(\theta(y_{j}),\theta(y_{k}))\leq m(i)\cdot(s+2r)$ for all $j,k$.

The subset $\sigma\cup i(\theta(\sigma))$ of $Y$ has distance between any two
elements bounded above by $m(i)\cdot(s+2r)$. The natural inclusions

$\sigma\subset\sigma\cup i(\theta(\sigma))\supset i(\theta(\sigma))$

define the required homotopies. ∎

As in Example 7, suppose that $i:X\subset Y$ is an inclusion of finite sets,
and choose systems of neighbourhoods $N_{x}$, $x\in X$ and $N^{\prime}_{y}$,
$y\in Y$, with distances $d_{x}$ and $d^{\prime}_{y}$. Suppose that
$N_{x}\subset N^{\prime}_{i(x)}$ for all $x\in X$, and that

$0\neq d_{i(x)}^{\prime}(i(x),i(z))\leq d_{x}(x,z)$

for all $z\in N_{x}$, for all $x\in X$. Form the corresponding ep-metric space
morphism $i:(X,D)\to(Y,D^{\prime})$.

Suppose that $E$ is a global connected component of $(X,D)$ and that $F$ is a
global connected component of $(Y,D^{\prime})$ such that $i(E)\subset F$.
Consider the restriction of the ep-metric space morphism
$i:(X,D)\subset(Y,D^{\prime})$ to the ep-metric space morphism
$i:(E,D)\to(F,D^{\prime})$. Suppose that $m(i)$ is the compression factor for
the map $i$ of global components.

The objects $(E,D)$ and $(F,D^{\prime})$ are metric spaces, by the choices of
all weights $d_{x}$ and $d^{\prime}_{y}$ — see Example 6.

The following result is a corollary of Proposition 8.

######  Theorem 9.

Suppose that the map $i:(E,D)\to(F,D^{\prime})$ is the ep-metric space
morphism between metric spaces that is described above. Suppose that for every
$y\in F$ there is an $x\in E$ such that $D^{\prime}(y,i(x))<r$. Then there are
diagrams

$\textstyle{P_{s}(E,D)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\scriptstyle{i}$$\textstyle{P_{m(i)\cdot(s+2r)}(E,D)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{i}$$\textstyle{P_{s}(F,D^{\prime})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\scriptstyle{\theta}$$\textstyle{P_{m(i)\cdot(s+2r)}(F,D^{\prime})}$

for all $0\leq s<\infty$, in which the upper triangle commutes and the lower
triangle homotopy commutes rel $P_{s}(E)$.

The canonical map

$\phi:V(X,N)=\vee_{x}\ V(X,D_{x})\to V(X,D),$

is induced by the ep-metric space maps $(X,D_{x})\to(X,D)$.

The ep-metric space $(X,D)$ is a disjoint union of its global connected
components $E$, and the system $V(X,D)$ is a disjoint union of the systems
$V(E,D)$. Form the pullback diagram

$\textstyle{V(X,N)(E)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\phi}$$\textstyle{V(X,N)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\phi}$$\textstyle{V(E,D)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{V(X,D)}$

The disjoint union

$V(X,D)=\bigsqcup_{E\in\pi_{\infty}(X,D)}\ V(E,D)$

pulls back to a disjoint union structure

$V(X,N)=\bigsqcup_{E\in\pi_{\infty}(X,D)}\ V(X,N)(E)$

on $V(X,N)$.

The excision isomorphisms

$\phi_{\ast}:\pi_{0}V(X,N)_{s}\xrightarrow{\cong}\pi_{0}V(X,D)_{s}$

of Lemma 2 restrict to isomorphisms

$\phi_{\ast}:\pi_{0}V(X,N)(E)_{s}\xrightarrow{\cong}\pi_{0}V(E,D)_{s}.$ (8)

We finish with a corollary of Theorem 9:

######  Theorem 10.

Suppose that the map $i:(E,D)\to(F,D^{\prime})$ is the ep-metric space
morphism between metric spaces that is described above. Suppose that for every
$y\in F$ there is an $x\in E$ such that $D^{\prime}(y,i(x))<r$. Then there are
commutative diagrams

$\textstyle{\pi_{0}V(X,N)(E)_{s}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\scriptstyle{i}$$\textstyle{\pi_{0}V(X,N)(E)_{m(i)\cdot(s+2r)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{i}$$\textstyle{\pi_{0}V(Y,N^{\prime})(F)_{s}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\scriptstyle{\theta}$$\textstyle{\pi_{0}V(Y,N^{\prime})(F)_{m(i)\cdot(s+2r)}}$

for all $0\leq s<\infty$, where $m(i)$ is the compression factor for the map
$i$.

Theorem 10 is a stability result for clustering in UMAP.

## References

  * [1] J.F. Jardine.  Metric spaces and homotopy types.  Preprint, http://uwo.ca/math/faculty/jardine/, 2020.
  * [2] Leland McInnes and John Healy.  UMAP: uniform manifold approximation and projection for dimension reduction.  CoRR, abs/1802.03426, 2018.
  * [3] D.I. Spivak.  Metric realization of fuzzy simplicial sets.  Preprint, 2009.