UMAP

UMAP (Uniform Manifold Approximation and Projection) is a nonlinear dimensionality reduction algorithm grounded in Riemannian geometry and algebraic topology that constructs a fuzzy topological representation of high-dimensional data and optimizes a low-dimensional embedding to match it. It matters in modern AI and ML as the go-to technique for visualizing embeddings from large neural networks, single-cell genomics, and NLP pipelines — dramatically faster than t-SNE while better preserving global structure. The counterintuitive fact: UMAP's apparent "clusters" in 2D projections can be artifacts of its hyperparameters rather than true structure in the data, making interpretation a genuine statistical hazard.

The core insight

UMAP works by assuming data lies on a low-dimensional manifold embedded in high-dimensional space, building a weighted neighborhood graph that encodes local geometry, and then finding a low-dimensional layout that preserves that graph structure as faithfully as possible. The "aha moment" is that UMAP never thinks about distances in the ambient ℝⁿ — it thinks about fuzzy set membership: how likely is point B to be "in the neighborhood" of point A given the local density around A? By normalizing distances relative to each point's local neighborhood, UMAP handles non-uniform density elegantly, unlike methods that treat all distances globally.

Common trapCommon Misconception

The most dangerous mistake practitioners make is interpreting inter-cluster distances in a UMAP plot as meaningful — concluding that two clusters far apart in 2D are more dissimilar than clusters that appear close together. This is wrong because UMAP's optimization strongly emphasizes preserving local topology (neighbor relationships within a neighborhood) over global topology (relative positions of distant clusters). The attractive forces in the optimization pull neighbors together powerfully, but repulsive forces between non-neighbors are sampled stochastically, making global layout semi-arbitrary. The correct mental model: UMAP faithfully answers "who are my nearest neighbors?" but only partially answers "how far away is that other group of points?" — treat inter-cluster geometry as suggestive, never as ground truth.

How It Works

UMAP proceeds in two major phases: graph construction (high-dimensional) and graph layout optimization (low-dimensional).

Phase 1: Constructing the High-Dimensional Fuzzy Graph

For each point $x_i$ , UMAP finds its $k$ nearest neighbors and defines a local metric that normalizes for density. Let $\rho_i$ be the distance to $x_i$ 's nearest neighbor (the local connectivity correction) and $\sigma_i$ be a bandwidth parameter chosen so the fuzzy membership function sums to $\log_2(k)$ . The directed edge weight (fuzzy set membership) from $x_i$ to $x_j$ is:

\quad v_{i|j} = \exp\!\left(-\frac{d(x_i, x_j) - \rho_i}{\sigma_i}\right)

Explanation: This gives the probability that $x_j$ is "in the neighborhood" of $x_i$ , with the local offset $\rho_i$ ensuring at least one neighbor always has weight 1 regardless of the point's surrounding density.

Symbol guide:

$d(x_i, x_j)$ : distance between points $i$ and $j$ in the high-dimensional space
$\rho_i$ : distance from $x_i$ to its nearest neighbor (ensures local connectivity)
$\sigma_i$ : per-point bandwidth found by binary search to satisfy the soft normalization constraint

Because $v_{i|j} \neq v_{j|i}$ in general, UMAP symmetrizes to form undirected edge weights using the fuzzy union:

\quad w_{ij} = v_{i|j} + v_{j|i} - v_{i|j} \cdot v_{j|i}

Explanation: This is the probability that at least one of the two directed edges exists — the standard union rule for independent fuzzy sets — producing a symmetric affinity matrix.

Phase 2: Low-Dimensional Graph Layout

UMAP places each point into $\mathbb{R}^d$ (typically $d=2$ or $3$ ), then optimizes positions $y_i$ so the low-dimensional graph matches the high-dimensional one. Low-dimensional affinities are defined using a differentiable approximation to a Student- $t$ -like kernel with trainable parameters $a$ and $b$ (fit to a smooth curve):

\quad \hat{w}_{ij} = \left(1 + a\,\|y_i - y_j\|^{2b}\right)^{-1}

Explanation: This is the probability that $y_i$ and $y_j$ are connected in the low-dimensional embedding — its heavy tail (controlled by $b$ ) allows moderately distant points to remain separated without creating artificially tight clusters.

Symbol guide:

$y_i, y_j$ : low-dimensional coordinates being optimized
$a, b$ : hyperparameters fit by nonlinear least-squares to approximate a specific smooth curve; default values in the reference implementation are $a \approx 1.577$ , $b \approx 0.895$

The objective is the binary cross-entropy between high-dimensional and low-dimensional affinities — the fuzzy set cross-entropy:

\quad \mathcal{L} = \sum_{(i,j)}\Bigl[w_{ij}\log\frac{w_{ij}}{\hat{w}_{ij}} + (1-w_{ij})\log\frac{1-w_{ij}}{1-\hat{w}_{ij}}\Bigr]

Explanation: This penalizes both false attractions (putting distant pairs too close in 2D) and false repulsions (pushing nearby pairs too far apart), balancing local preservation against global separation. Because computing all pairs is $O(n^2)$ , UMAP approximates the second term using negative sampling: for each edge $(i,j)$ with weight $w_{ij}$ , it draws $m$ random "negative" pairs and repels them. The gradient update for an attractive force between $y_i$ and $y_j$ has closed form:

\quad \frac{\partial \mathcal{L}_{\text{attract}}}{\partial y_i} = -\frac{2ab\,\|y_i - y_j\|^{2(b-1)}}{1 + a\,\|y_i - y_j\|^{2b}}\,(y_i - y_j)

Explanation: The attractive gradient pulls $y_i$ toward $y_j$ proportionally to how much their current low-dimensional distance exceeds what the embedding kernel predicts — vanishing when they are already close. Optimization runs via stochastic gradient descent with a decaying learning rate, typically for 200–500 epochs.

researcher · Leland McInnes | b. 1983 | Inventor of UMAP

Leland McInnes is a mathematician at the Tutte Institute for Mathematics and Computing in Ottawa, with expertise in topological data analysis and computational mathematics. He published UMAP in 2018 with John Healy and James Melville, grounding what had been largely heuristic dimensionality-reduction practice in rigorous algebraic topology and Riemannian geometry. Surprisingly, the original UMAP preprint was posted on arXiv without peer review and spread virally through the bioinformatics and machine learning communities before any formal publication, becoming one of the most-cited arXiv papers of 2018.

Figure

UMAP Two-Phase Pipeline

Figure

High-Dimensional Fuzzy Membership Geometry

Intuition

The Mental Model

Imagine you are a cartographer tasked with drawing a 2D map of a social network where people are clustered in cities, but the cities are scattered across a continent. Your first step is not to measure global distances between cities — it's to ask each person: "Who are your ten closest friends, and roughly how far away are they?" In a dense city, "close friend" might mean someone two blocks away; in a rural area, it might mean someone twenty miles away. UMAP does exactly this: it measures neighborhood relationships relative to local density, so that "close" means something consistent everywhere on the manifold, regardless of whether that region of data is crowded or sparse. Once you have everyone's local friendship list (the fuzzy graph), your second task is to draw the map (the 2D embedding) so that friends remain near each other on paper. You pull connected nodes together like rubber bands (attractive forces) and nudge disconnected nodes apart like magnets (repulsive forces), iterating until the map stabilizes. The result is a layout where tight friend-groups collapse into visible clusters — but the distances between those clusters on paper depend heavily on how strong your repulsive magnets were, not purely on how dissimilar the groups actually are. That is why UMAP excels at revealing local cluster structure but should not be used to judge global topology without caution.

Historical Development

Origins · 1 minhow this was discovered

History

1901

Karl Pearson introduces Principal Component Analysis (PCA), the foundational linear dimensionality reduction method that UMAP generalizes beyond.

2000

Sam Roweis & Lawrence Saul (LLE) and Joshua Tenenbaum et al. (Isomap) publish landmark nonlinear manifold learning methods, establishing the manifold hypothesis as a practical framework for ML.

2002

Mikhail Belkin & Partha Niyogi publish Laplacian Eigenmaps, introducing graph-based representations of local geometry — a direct conceptual precursor to UMAP's affinity graph.

2008

Laurens van der Maaten & Geoffrey Hinton publish t-SNE, which becomes the dominant visualization technique and the primary benchmark UMAP later surpasses on speed and global structure preservation.

2015

Gunnar Carlsson and collaborators popularize topological data analysis (TDA) tools including persistent homology and simplicial complexes — the mathematical language McInnes would recast UMAP into.

2018

Leland McInnes, John Healy, and James Melville post the UMAP preprint on arXiv ("UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction"), combining Riemannian geometry, fuzzy simplicial sets, and stochastic gradient descent into a single algorithm.

2018

The UMAP Python library (`umap-learn`) is released on PyPI; within months it becomes standard in single-cell RNA-seq analysis pipelines (Seurat, Scanpy), displacing t-SNE for large genomic datasets.

2019

Parametric UMAP is introduced, replacing SGD layout with a neural network encoder, enabling out-of-sample projection and integration with deep learning pipelines.

2020–2022

GPU-accelerated implementations (`cuML` RAPIDS, `cuUMAP`) reduce runtime on millions of points from hours to seconds; UMAP becomes routine for inspecting embeddings from BERT, CLIP, and other large language/vision models.

Why It Matters

Real-World Impact

Single-Cell RNA Sequencing (scRNA-seq)UMAP is the standard visualization for tools like Scanpy and Seurat; it reduces 20,000-gene expression vectors per cell to 2D, revealing cell type clusters and developmental trajectories that were invisible with PCA or t-SNE at scale (millions of cells).

Large Language Model Embedding InspectionML engineers routinely apply UMAP to visualize BERT, Sentence-BERT, and OpenAI embedding spaces, diagnosing whether semantic clusters (e.g., topics, sentiments) are geometrically separated before downstream classification.

Anomaly Detection PipelinesUMAP projections of system log embeddings or network traffic features allow human-in-the-loop review of suspicious clusters; points that fall in low-density gaps in 2D frequently correspond to genuine novel attack patterns.

Drug DiscoveryPharmaceutical ML pipelines use UMAP on molecular fingerprint vectors (Morgan fingerprints, graph neural network embeddings) to navigate chemical space, identifying structurally similar compound clusters for lead optimization.

Semi-Supervised Learning via UMAP Initialization`umap-learn` supports label propagation in embedding space; partially labeled datasets can use UMAP's metric to propagate labels through dense clusters, providing a competitive semi-supervised baseline without deep learning.

Recommendation Systems DebuggingCompanies including Spotify and Netflix apply UMAP to user and item embedding spaces from collaborative filtering models to qualitatively verify that genre/style clusters emerge, auditing embedding quality before A/B testing.

Parametric UMAP for Streaming DataBy training a neural encoder to approximate UMAP's objective, production systems can project new data points without re-running the full algorithm — enabling real-time visualization of live feature streams.

UMAP

How It Works

Phase 1: Constructing the High-Dimensional Fuzzy Graph

Phase 2: Low-Dimensional Graph Layout

Intuition

Historical Development

Why It Matters

Prerequisites

What This Leads To

See Also

Before this