Theory

Introduction

Uniform Manifold Approximation and Prediction

The goal of UMAP is to rebuild the data in a high $N$ space ${\mathbb{R}}^N$ as:

• Low-dimensional manifold
  • The data is first cast as a weighted graph (1-dimensional)
• Uniform sampling assumption
  • Dense clusters are spread apart and sparse areas contracted

UMAP process

We are given a data cloud $\{x_1,\dots ,x_n\}\in {\mathbb{R}}^N$, and a neighbor-count $k$.

(1) Create weighted partial graphs local to each data point:

For each point $x_i$, define weights as follows:

• Set $w(x_i,y_1)=1$.
• All $y_j$ are infinitely far from each other: $w(w_i,w_j)=0$ for $i\ne j$.
• For $j\ge 2$:
  • Require that $w(x_i,y_j)$ is proportional to $d(x_i,y_j)-d(x_i,y_1)$,
  • Require that ${\sum }_{j=2}^{k}w(x_i,y_j)={\log }_{2}k$.

That is, the nearest neighbor $y_1$ is placed at distance $0$ from $x_i$, and the other $k-1$ neighbors are made closer to $x_i$ by the distance removed. For each fixed $i$, the collection $\{w(x_i,y_j){\}}_{j=1,\dots ,k}$ encodes metric structure of the original data near $x_i$ but with the closest point $y_1$ substituted for $x_i$.

The weight $w(x_i,y_j)$ is supposed to be interpreted as the probability that the point $y_j$ will lie in the same cluster as the point $x_i$.

From these requirements it is possible to deduce a formula for $w(x_i,y_j)$, as follows:

Set $d_1=d(x_i,y_1)$. (Distance to the closest neighbor.) For each $i$, solve for ${\sigma }_i$ such that:

$$\sum _{j=1}^k\exp \left(\frac{-\max (0,d(x_i,y_j)-d_1}{{\sigma }_i}\right)={\log }_{2}k$$

The idea is that for the closest neighbor $y_1$, the weight $w(x_i,y_1)$ should be the highest; the weight should decrease for neighbors that are farther away.

---

(2) Glue partial metrics into a single weighted graph:

Now we define a single weighted graph with vertices the points $x_1,\dots ,x_n$ and weights coming from the set of partial graphs defined in Step (1).

Observe that a given pair of vertices $x_i,x_{i^{\prime }}$ could appear with finite distance in at most two partial graphs. The relation of being “nearest neighbor” is not in general symmetric:

Now, let us be given a pair of vertices $(x_i,x_{i^{\prime }})$.

If this pair appears (with finite weight) in only one partial graph, give the pair a weighted edge in the total graph with the same weight it had in that partial graph.

If this pair appears in two partial graphs, then $x_i$ is the center point in one of them and $x_{i^{\prime }}$ is the center in the other.

We combine the weights as follows:

• Let $p_1=w(x_i,x_{i^{\prime }})$
• Let $p_2=w(x_{i^{\prime }},x_i)$

Then the weight on the pair $(x_i,x_{i^{\prime }})$ shall be defined as:

$$1-(1-p_1)(1-p_2)=p_1+p_2-p_1{p}_2$$

Now we have defined a total weighted graph that combines the information from all the weighted partial (local) graphs.

---

(3) Embed the total weighted graph $G$ in a lower-dimensional space ${\mathbb{R}}^k$ as a weighted graph $H$.

This can be done with standard techniques that we don’t cover here. Briefly:

Start with the spectral graph embedding. Edge weights for edge $e$ are $p_e$ in $G$ and $q_e$ in $H$. Cross-entropy formula:

$$\sum _e{p}_e\log \left(\frac{p_e}{q_e}\right)+(1-p_e)\log \left(\frac{1-p_e}{1-q_e}\right)$$

Use this cross-entropy as a cost function and perform stochastic gradient descent to minimize the cost.

Gradient descent

Suppose we are given a cost function $f:M\to \mathbb{R}$.

Given any $x\in M$, the gradient of $f$, written $D_{\mathbf{v}}(f)$, is the direction of the largest rate of change of $f$.

$$\mathbf{v}=\nabla f=⟨\frac{\partial f}{\partial x_1},\dots ,\frac{\partial f}{\partial x_n}⟩$$

Smallest rate of change is $-\nabla f$.

Illustration - uniform sampling assumption

UMAP is based on an assumption that the data samples uniformly from a manifold.

Illustration - UMAP figure from Böhm et al 2022

(Böhm et al. 2022)