UMAP (Uniform Manifold Approximation and Projection)

In 2018, Leland McInnes, John Healy, and James Melville introduced Uniform Manifold Approximation and Projection (UMAP)—an algorithm that would fundamentally transform how practitioners approach high-dimensional data visualization and analysis. UMAP emerged not merely as an incremental improvement over existing methods, but as a paradigm shift grounded in rigorous mathematical foundations from algebraic topology and category theory.

What makes UMAP remarkable is its ability to simultaneously achieve what seemed like incompatible goals: preserving both local and global structure, scaling efficiently to massive datasets, and providing a theoretically principled framework that extends beyond mere heuristics. Where t-SNE pioneered the use of heavy-tailed distributions for dimensionality reduction, UMAP constructs a fundamentally different mathematical object—a weighted graph derived from fuzzy simplicial sets—that captures the topological essence of high-dimensional data.

This page establishes the theoretical foundations necessary to understand not just how UMAP works, but why it works so effectively. We will build intuition from first principles, connecting abstract mathematical concepts to practical algorithmic decisions.

Before diving into UMAP's specifics, we must precisely articulate the problem it solves. The manifold hypothesis posits that high-dimensional data often lies on or near a low-dimensional manifold embedded in the ambient space. This isn't merely a convenient assumption—it reflects deep structure in how real-world data is generated.

Consider a dataset of face images. Each image might contain millions of pixels, placing it in a correspondingly high-dimensional space. Yet the degrees of freedom generating these images—head pose, lighting angle, expression, identity—number far fewer. The data lies on a manifold whose intrinsic dimensionality matches these generative factors, not the pixel count.

The Central Challenge:

Given samples from an unknown manifold (\mathcal{M}) embedded in (\mathbb{R}^D), we seek a mapping (f: \mathcal{M} \rightarrow \mathbb{R}^d) (where (d \ll D)) that preserves essential structural properties. But what exactly should be preserved?

Classical approaches like PCA focus on variance preservation—a global criterion that ignores manifold curvature entirely. Methods like Isomap attempt to preserve geodesic distances but struggle with non-convex manifolds. LLE preserves local linear relationships but provides no guarantees about global structure. t-SNE revolutionized the field by optimizing for local neighborhood preservation using probability distributions, but sacrifices global structure and lacks theoretical grounding beyond empirical success.

UMAP's Innovation:

UMAP approaches this problem from a fundamentally different angle: rather than defining what to preserve in terms of distances or probabilities, it asks: What is the topological structure of the data, and how can we find an embedding that has equivalent topology?

This shift from metric-centric to topology-centric thinking is the key insight underlying UMAP's effectiveness.

UMAP's theoretical framework rests on a profound assumption: the data is uniformly distributed on a Riemannian manifold. This might seem restrictive, but it leads to a powerful construction that handles arbitrary data distributions through local metric adaptation.

Riemannian Manifolds and Local Metrics:

A Riemannian manifold is a smooth manifold equipped with a metric tensor that defines inner products on tangent spaces at each point. This metric determines how we measure distances and angles locally. Crucially, the metric can vary from point to point—allowing the geometry to "bend" and "stretch."

For a manifold (\mathcal{M}) with metric tensor (g), the distance between infinitesimally close points is given by:

$$ds^2 = \sum_{i,j} g_{ij}(x) , dx^i , dx^j$$

In Euclidean space, (g_{ij} = \delta_{ij}) (the identity), so (ds^2 = \sum_i (dx^i)^2)—the familiar Pythagorean theorem. On a curved manifold, (g_{ij}) varies with position, creating non-Euclidean geometry.

Local Distance Normalization:

Given data points sampled from an unknown manifold, UMAP cannot directly compute the true Riemannian metric. Instead, it infers a locally adapted metric that would make the data appear uniformly distributed.

For each point (x_i), UMAP defines a local distance function:

$$d_i(x_j) = \frac{d(x_i, x_j) - \rho_i}{\sigma_i}$$

where:

• (d(x_i, x_j)) is the ambient Euclidean distance
• (\rho_i) is the distance to the nearest neighbor (ensuring connectivity)
• (\sigma_i) is a normalization factor determined by perplexity/local density

This transformation is conceptually similar to defining a local metric at each point that expands or contracts distances based on local data density. In dense regions, (\sigma_i) is small, making distances larger; in sparse regions, (\sigma_i) is large, making distances smaller.

The Exponential Map Connection:

In Riemannian geometry, the exponential map transforms tangent vectors at a point into points on the manifold by "shooting" along geodesics. UMAP's local distance normalization can be understood as implicitly constructing coordinates in the tangent space at each point, where distances respect the local Riemannian metric induced by the uniform distribution assumption.

This geometric perspective explains why UMAP handles varying densities more gracefully than methods assuming a fixed global metric. Each point effectively lives in its own locally-adapted coordinate system, and UMAP's fuzzy set formulation provides a principled way to reconcile these different local views into a coherent global structure.

The second pillar of UMAP's theoretical foundation is algebraic topology—specifically, the theory of simplicial sets added with a "fuzzy" extension. This provides the mathematical machinery to define and manipulate the topological structure we wish to preserve.

From Point Clouds to Topology:

Given a finite set of data points, we need to construct a mathematical object that captures their topological relationships. The classical approach uses simplicial complexes:

• 0-simplices: Individual points (vertices)
• 1-simplices: Edges connecting pairs of points
• 2-simplices: Triangles (faces) connecting triples
• n-simplices: Higher-dimensional generalizations

A simplicial complex is a collection of simplices satisfying closure under taking faces (every face of a simplex is also in the complex).

The Čech Complex:

For point cloud data, a natural construction is the Čech complex: place a ball of radius (\epsilon) around each point, and form simplices whenever balls intersect. The Nerve Theorem guarantees this captures manifold topology—if we choose (\epsilon) correctly.

The problem: there is no single "correct" (\epsilon). Too small, and the complex is disconnected; too large, and we lose topological detail. Persistent homology addresses this by studying how topology changes across all scales, but this is computationally expensive.

UMAP's Solution: Fuzzy Simplicial Sets

Rather than choosing a single threshold, UMAP introduces fuzzy simplicial sets where simplices have membership strengths in ([0, 1]) rather than binary presence/absence. This elegantly handles the multi-scale nature of real data.

A fuzzy simplicial set assigns to each potential simplex a degree of membership. For UMAP's purposes, we focus primarily on 0-simplices (points, always with membership 1) and 1-simplices (edges with fuzzy weights).

Mathematical Formulation:

For each data point (x_i), UMAP constructs a local fuzzy simplicial set. The membership strength of the edge ((x_i, x_j)) in (x_i)'s local set is:

$$\mu_i(x_j) = \exp\left( -\frac{\max(0, d(x_i, x_j) - \rho_i)}{\sigma_i} \right)$$

Note that this is asymmetric: (\mu_i(x_j) eq \mu_j(x_i)) in general, because (\rho) and (\sigma) differ for each point. This asymmetry reflects the different local geometries at each point.

Each data point's local neighborhood defines an asymmetric fuzzy simplicial set. To obtain a global representation of the entire dataset, we must combine these local views. This is where UMAP's fuzzy set theory comes into play.

Reconciling Asymmetric Views:

Consider points (x_i) and (x_j). From (x_i)'s perspective, the edge ((x_i, x_j)) might have strength 0.8 (they're close in (x_i)'s local metric). From (x_j)'s perspective, the same edge might have strength 0.2 ((x_j) is in a denser region, so distances are larger).

How do we reconcile these views? UMAP uses a probabilistic t-conorm (fuzzy union):

$$\mu(x_i, x_j) = \mu_i(x_j) + \mu_j(x_i) - \mu_i(x_j) \cdot \mu_j(x_i)$$

This is equivalent to the probability of at least one event occurring if we treat membership strengths as independent probabilities.

Why Fuzzy Union Works:

The fuzzy union operation has several desirable properties:

1. Symmetry: The result (\mu(x_i, x_j)) equals (\mu(x_j, x_i)), essential for undirected graph optimization.

2. Preservation of Strong Connections: If either (\mu_i(x_j)) or (\mu_j(x_i)) is close to 1, the combined strength is close to 1. Strong relationships are preserved.

3. Weak Connection Handling: If both strengths are small, their combination is even smaller (since (a + b - ab < a + b)). Noise doesn't accumulate.

4. Idempotence: Combining a set with itself yields the same set: (\mu + \mu - \mu^2 = \mu(2 - \mu)) when (\mu \in {0, 1}).

The Result: A Weighted k-NN Graph

After fuzzy union, we have a symmetric weighted graph where edge weights represent "topological similarity" between points. This graph is the high-dimensional fuzzy simplicial set that UMAP will seek to reproduce in low-dimensional space.

With the high-dimensional fuzzy simplicial set constructed, we can now state UMAP's fundamental optimization principle:

UMAP's Core Objective:

Find a low-dimensional embedding such that the fuzzy simplicial set constructed from the embedding is as close as possible to the fuzzy simplicial set from the high-dimensional data.

Mathematically, if we denote:

• (G^h): The high-dimensional fuzzy simplicial set (edge weights from original data)
• (G^l): The low-dimensional fuzzy simplicial set (edge weights from embedding)

Then UMAP minimizes a measure of divergence between (G^h) and (G^l).

Contrast with t-SNE:

Both t-SNE and UMAP can be viewed as optimizing for agreement between high-dimensional and low-dimensional representations. The key differences are:

While the practical outcomes often look similar, UMAP's theoretical foundations provide stronger guarantees and enable principled extensions (e.g., supervised UMAP, metric learning).

To complete the theoretical picture, we must define how UMAP constructs the low-dimensional fuzzy simplicial set (G^l) from an embedding (Y = {y_1, ..., y_n} \subset \mathbb{R}^d).

The Low-Dimensional Affinity Function:

In low-dimensional space, UMAP uses a parametric family of functions to define edge weights:

$$ u(y_i, y_j) = \left(1 + a |y_i - y_j|^{2b}\right)^{-1}$$

where (a) and (b) are parameters (typically (a \approx 1.93), (b \approx 0.79) for the default min_dist of 0.1).

When (a = b = 1), this simplifies to:

$$ u(y_i, y_j) = \frac{1}{1 + |y_i - y_j|^2}$$

which is exactly the Student-t distribution with 1 degree of freedom—the same heavy-tailed distribution used by t-SNE!

The min_dist Parameter:

UMAP's distinctive (a) and (b) parameters are derived from the user-specified min_dist hyperparameter, which controls the minimum distance at which points are allowed to separate. The relationship is found by fitting:

$$\psi(d) = \begin{cases} 1 & \text{if } d \leq \text{min_dist} \ e^{-(d - \text{min_dist})} & \text{otherwise} \end{cases}$$

with the parametric family (\left(1 + a \cdot d^{2b}\right)^{-1}).

Effect of min_dist:

Lower min_dist values create tighter, more distinct clusters; higher values produce more uniform, spread-out embeddings.

We have now established the complete theoretical foundation for UMAP. Let's consolidate the key concepts:

What's Next:

With the theoretical foundations established, the next page explores the fuzzy topological representation in greater depth—examining how UMAP's category-theoretic foundations lead to specific algorithmic choices and how the fuzzy simplicial set captures manifold topology through weighted graphs.