UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction

t-SNE solved the visualization problem brilliantly — it produces maps where local clusters are crisp and clearly separated. But practitioners quickly discovered its blind spots:

Speed: t-SNE's pairwise probability computation is $O(n^2)$. Even with the Barnes-Hut approximation ($O(n \log n)$), datasets above a few hundred thousand points become impractical.

Global structure: t-SNE's KL divergence cost is asymmetric — it heavily penalizes pulling nearby points apart but barely penalizes pushing distant points together. This means the relative positions and sizes of clusters in a t-SNE plot carry no reliable information.

No out-of-sample embedding: if new data arrives, t-SNE must re-run from scratch. There is no learned transformation to apply to unseen points.

Restricted to 2D/3D: t-SNE was designed for visualization. Using it to produce 50-dimensional embeddings for downstream ML is not practical.

UMAP addresses all four of these limitations while matching or exceeding t-SNE's local cluster quality.

UMAP starts from a powerful assumption: the data does not fill its high-dimensional space uniformly. Instead, it lies on or near a low-dimensional manifold — a curved surface embedded in higher dimensions. Think of the surface of the Earth: it is a 2D surface embedded in 3D space. Even though the ambient space is 3D, you only need two coordinates (latitude and longitude) to locate any point.

The same idea applies to image data: a collection of face images may live in a space with thousands of pixel dimensions, but the meaningful variation (pose, lighting, expression) spans only a handful of dimensions. The images lie on a curved surface in pixel space.

UMAP's mathematical framework formalizes this intuition using Riemannian geometry: it assumes that around each data point, the manifold looks approximately flat (like a small patch of the Earth's surface), and that data is uniformly distributed on this manifold. This uniformity assumption is the "U" in UMAP.

Here is the core insight of UMAP, explained without category theory. Imagine each data point drawing a circle around its $k$ nearest neighbors. Because the manifold stretches differently in different regions, each point's circle has a different radius. Points in dense regions have small circles; points in sparse regions have large circles.

Now, each point assigns a "connection strength" to every neighbor: the nearest neighbor gets strength 1, and the strength decays exponentially with distance. This is exactly like t-SNE's Gaussian kernel, but with a critical twist: the decay rate is set so that the nearest neighbor's distance is subtracted first. This means the connection strength depends on relative distance, not absolute distance — automatically adapting to local density.

The result is a fuzzy graph: each edge has a weight between 0 and 1, representing how "connected" two points are. In topology, this structure is called a fuzzy simplicial set. "Fuzzy" because connections are graded (not binary), and "simplicial" because it builds from the simplest building blocks: points and edges.

UMAP computes the connection strength between point xᵢ and each of its $k$ nearest neighbors $x_j$ using a modified exponential kernel. The key innovation is subtracting ρᵢ — the distance to xᵢ's nearest neighbor — before applying the exponential decay. This ensures that every point has at least one neighbor with full connection strength, regardless of local density.

Each point xᵢ produces its own directed view of the world. To combine all these views into a single undirected graph, UMAP uses a fuzzy set union (probabilistic t-conorm) instead of simple averaging. The intuition: if either point considers the other a neighbor, they should be connected.

In the low-dimensional space, UMAP needs a smooth function that maps distances between embedded points to connection strengths. It uses a family of curves parameterized by two constants $a$ and $b$ (fitted to match the desired min_dist parameter).

When min_dist is small, the curve approximates the Student-t kernel familiar from t-SNE. When min_dist is larger, the curve plateaus near 1 for small distances, then drops — ensuring that closely packed points are spread apart for better visualization.

Here is where UMAP departs most visibly from t-SNE. Both algorithms want the low-dimensional similarities to match the high-dimensional ones. But t-SNE uses KL divergence, which only penalizes one kind of mismatch: pulling close points apart (large $p$, small $q$). It does not penalize pushing far points together.

UMAP uses cross-entropy, which penalizes both directions. If two points should be connected ($v_{ij}$ high) but aren't in the embedding ($w_{ij}$ low), the first term pushes them together. If two points should not be connected ($v_{ij}$ low) but are too close in the embedding ($w_{ij}$ high), the second term pushes them apart.

This symmetric penalty is exactly why UMAP preserves global structure better than t-SNE.

UMAP has two main hyperparameters that are worth understanding deeply:

n_neighbors (typically 5–50, default 15): controls how many neighbors define "local." Small values emphasize fine-grained local structure — you see sub-clusters and fine detail. Large values capture broader, more global patterns — sub-clusters merge into larger groups. This is analogous to t-SNE's perplexity parameter.

min_dist (typically 0.0–0.99, default 0.1): controls how tightly UMAP packs points in the embedding. Small values produce dense, tightly packed clusters ideal for identifying fine structure. Large values spread points out, producing a more uniform embedding that avoids overplotting.

Think of it this way: n_neighbors controls what UMAP sees (the scale of structure), while min_dist controls what the output looks like (the aesthetic of the plot).

t-SNE computes forces between all pairs of points every iteration — this is the bottleneck that makes it slow. UMAP takes a radically different approach by borrowing a trick from word embedding training (Word2Vec's negative sampling).

In each iteration, UMAP samples a batch of edges from the fuzzy graph. For each sampled edge (an "attractive" pair), it also samples a few random non-neighbors ("negative" pairs). It then applies stochastic gradient descent: attractive pairs are pulled closer, negative pairs are pushed apart.

This means each iteration only touches a small fraction of all pairs, making the computational cost per iteration $O(k \cdot n)$ instead of $O(n^2)$. Combined with approximate nearest neighbor search (using algorithms like NN-Descent) for the initial graph construction, UMAP achieves dramatic speedups.

The complete UMAP algorithm consists of two phases: constructing the fuzzy topological representation of the high-dimensional data, and then optimizing the low-dimensional embedding to match it.

Both UMAP and t-SNE optimize a neighborhood-based objective, but their differences are consequential:

Mathematical foundation: t-SNE is motivated by probability matching. UMAP is grounded in Riemannian geometry and algebraic topology — the fuzzy simplicial set framework provides theoretical guarantees about manifold preservation.

Cost function: t-SNE uses KL divergence (penalizes only false separation). UMAP uses cross-entropy (penalizes false separation and false proximity). This is why UMAP preserves global structure.

Symmetrization: t-SNE averages directional probabilities. UMAP takes their fuzzy union. The union preserves connectivity of sparse regions better.

Optimization: t-SNE uses full-batch gradient descent over all pairs. UMAP uses SGD with negative sampling over edges. This is the source of UMAP's speed advantage.

Scalability: t-SNE is practical up to ~100K–1M points with Barnes-Hut. UMAP handles millions comfortably.

Embedding dimensions: t-SNE degrades in dimensions above 3. UMAP works well in 10, 50, or 100 dimensions — making it useful as a general preprocessing step.

Out-of-sample: t-SNE has no mechanism. UMAP can embed new points using the learned graph structure.

Reading UMAP plots: unlike t-SNE, the relative positions and distances between clusters in UMAP carry some meaning. Clusters that are close in UMAP space tend to be more similar in the original space. However, exact inter-cluster distances should still be interpreted with caution.

Choosing n_neighbors: start with the default (15). If you want to see fine-grained sub-clusters, reduce to 5–10. If you want a global overview, increase to 30–50. Run at multiple values to separate real structure from artifact — just like perplexity in t-SNE.

Choosing min_dist: for exploratory visualization, 0.1 is a good default. For clustering downstream tasks, try 0.0 to get the tightest clusters. For publication-quality plots, 0.25–0.5 avoids overplotting.

Use as preprocessing: UMAP is not just for visualization. Reducing to 10–50 dimensions before running k-means, HDBSCAN, or a classifier often improves results and dramatically reduces computation time.

Reproducibility: set random_state for deterministic results. UMAP is more stable across runs than t-SNE, but randomness in initialization and SGD still affects output.

UMAP's contribution extends beyond being a faster t-SNE. By grounding dimension reduction in topology, it established the principle that the right way to compare neighborhoods is not through pairwise distances but through connectivity — which points are connected at all, and how strongly. This topological perspective influenced subsequent work in geometric deep learning and representation analysis.