UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction

Motivation

• Dimension reduction supports visualization and machine-learning preprocessing, motivating methods that scale to massive, diverse datasets while balancing global and local distance preservation.PCA, MDS, and Sammon mapping favor pairwise global structure, whereas t-SNE, Isomap, LargeVis [54], Laplacian eigenmaps, and diffusion maps favor local distances.Source: §1 · pp. 1–2

Contribution

• UMAP introduces a mathematically grounded manifold-learning technique combining Riemannian geometry and fuzzy simplicial sets with a practical scalable algorithm for real-world data.Its design decisions are theoretically justified rather than derived from task-specific experimentation.Source: §1 · pp. 2–3
• UMAP is competitive with t-SNE for visualization quality, arguably preserves more global structure, offers superior runtime performance, and scales to larger datasets.The paper identifies t-SNE as the current state of the art for visualization and presents UMAP as a scalable alternative.Source: §1 · p. 2

Scope

• UMAP has no computational restriction on embedding dimension, making it suitable as a general-purpose dimension-reduction technique for machine learning.Preliminary software releases had already found use in bioinformatics, materials science [34] [23], and machine learning [20] [24] [19].Source: §1 · p. 2

Paper structure

• The paper covers UMAP’s theory, computational formulation, implementation and hyperparameters, practical and scaling results, limitations, and potential extensions including semi-supervised, metric, and heterogeneous-data embedding.Section 6 discusses cases where UMAP may not be the best choice, while Section 7 develops future directions enabled by its mathematical construction.Source: §1 · pp. 2–3

2 Teoretical Foundations for UMAP

• UMAP patches local fuzzy simplicial-set representations of the high-dimensional data, then minimizes cross-entropy between this topology and that of a low-dimensional embedding.The source representation is built from local manifold approximations, while the target manifold is chosen in advance, usually as R^d.Source: §2 · p. 4, §2.3 · pp. 11–12

2.1 Uniform distribution of data on a manifold and geodesic approximation

• UMAP normalizes distances to each point’s kth nearest neighbor to approximate geodesic distance, while allowing a point-specific metric that makes local data approximately uniform on the manifold.This produces a family of potentially incompatible local metric spaces, which are subsequently merged through fuzzy simplicial sets.Source: §2.1 · pp. 4–5

2.2 Fuzzy topological representation

• Local metric spaces are converted into fuzzy simplicial sets and merged by fuzzy union, producing one structure that retains the manifold’s relevant topological and underlying metric information.The FinReal and FinSing functors form an adjunction, enabling translation between finite fuzzy simplicial sets and finite extended-pseudo-metric spaces.Source: §2.2 · pp. 10–11
• The construction uses extended-pseudo-metric neighborhoods: distances between noncentral neighbor pairs are set to infinity, while local connectivity is enforced by assigning the nearest-neighbor distance zero.The local geodesic approximation is valid only for distances measured from the neighborhood center, motivating this relaxed metric structure.Source: §2.2 · p. 10

2.3 Optimizing a low dimensional representation

• The current algorithm compares only the 1-skeletons of fuzzy simplicial sets; higher-dimensional skeleta could better capture topology but incur non-negligible computational cost.Optimization uses stochastic gradient descent on fuzzy-set cross-entropy, with differentiable approximations required when the expected minimum embedded distance is nonzero.Source: §2.3 · p. 12

3 A Computational View of UMAP

• UMAP’s computational pipeline has two phases: constructing a weighted k-neighbour graph and computing its low-dimensional layout.The theoretical framework motivates the choices made in both phases.Source: §3 · p. 13

3.1 Graph Construction

• For each data point, UMAP finds k nearest neighbors under a metric and uses local parameters to define weighted directed edges.Nearest-neighbor or approximate nearest-neighbor search can perform this computation.Source: §3.1 · pp. 14–15
• UMAP represents the data using a weighted graph whose construction reflects local connectivity, local metric scaling, and fuzzy topological structure.Its assumptions include a uniformly distributed manifold, local connectivity, and topology preservation as the primary goal.Source: §3 · p. 13, §3.1 · p. 15
• UMAP combines directed edge weights into an undirected graph, interpreting each combined weight as the probability that at least one direction exists.This union operation yields a fuzzy topological representation intended to capture the data’s underlying geometric structure.Source: §3.1 · pp. 15–16

3.2 Graph Layout

• UMAP lays out the graph with a force-directed algorithm that iteratively applies attractive and sampled repulsive forces in a non-convex optimization.The forces optimize edge-wise cross-entropy between the source graph and the graph induced by the low-dimensional points.Source: §3.2 · pp. 16–17

4.1 Algorithm description

• UMAP constructs local fuzzy simplicial sets, combines them with a probabilistic t-conorm, initializes spectrally, and optimizes fuzzy-set cross entropy.The implementation uses the 1-skeleton rather than higher-order simplices; optimization uses stochastic gradient descent with negative sampling.Source: §4.1 · p. 17, # Perform optimization of the graph… · pp. 18, 20, 21

# Perform optimization of the graph layout

• UMAP’s practical realization requires approximate k-nearest-neighbor computation and efficient stochastic gradient descent, with optimization scaling as O(kN) for a fixed negative-sampling rate.The normalized-Laplacian eigenvectors provide initialization, while probabilistic edge sampling and negative sampling avoid normalization requirements [54] [41].Source: §4.2 · pp. 21–22

4.2 Implementation

• The overall implementation is empirically approximately O(N1.14), using Nearest-Neighbor-Descent, while the reported experiments used a single core despite available parallelization.Nearest-Neighbor-Descent supports arbitrary valid dissimilarities and high-dimensional data; both it and stochastic gradient descent had been parallelized.Source: §4.2 · p. 22

4.3 Hyper-parameters

• UMAP has four hyperparameters—n, d, min-dist, and n-epochs—with n trading fine-scale detail against large-scale structure when approximating the manifold.Smaller n captures finer structure but can fragment the manifold, whereas larger n captures broader structure while averaging away detail.Source: §4.3 · pp. 22–23
• min-dist controls point packing: lower values can densely pack points and more faithfully represent structure, whereas higher values spread points for visualization; its effect depends on dataset structure.Small-to-medium n is favored for clustered PenDigits and MNIST data, while large min-dist can obscure cluster distinctions; low n can spuriously model noise in a random color-cube.Source: §4.3 · pp. 23, 25, Figure 1 · p. 24

5 Practical Efficacy

• The practical evaluation covered diverse datasets spanning images, single-cell expression, flow cytometry, shuttle measurements, and millions of word vectors.Datasets ranged from 1,440 COIL20 images and 1,797 PenDigits images to 3 million GoogleNews vectors and 20,921 mouse cells.Source: §5 · pp. 25, 28

5.1 Qalitative Comparison of Multiple Algorithms

• UMAP produced embeddings comparable to t-SNE in two or three dimensions, distinguished the same structures as t-SNE and LargeVis across four datasets, and captured more global structure than t-SNE.Figure 4 indicates that UMAP reflects large-scale structure represented by Laplacian Eigenmaps and PCA while preserving local fine structure similar to t-SNE and LargeVis.Source: §5.1 · pp. 28, 30, Figure 4 · p. 29

5.2 Qantitative Comparison of Multiple Algorithms

• UMAP provided comparable embedding quality to t-SNE and LargeVis locally, but markedly better performance at non-local scales across the evaluated datasets.The kNN classifier varied k to probe structure from local to more global scales.Source: §5.2 · pp. 30–31

5.3 Embedding Stability

• UMAP achieved more stable subsample embeddings than t-SNE, with per-point error below every t-SNE result after sampling 5% of one million Flow Cytometry points.The comparison used normalized Procrustes distance and increased t-SNE iterations to 1500 for better convergence.Source: §5.3 · pp. 35–36

5.4 Computational Performance Comparisons

• UMAP consistently ran faster than the other algorithms except on the very small PenDigits dataset, where Laplacian Eigenmaps and Isomap had a small edge.Some benchmarks used subsampling or PCA reduction to enable broader algorithmic comparison.Source: §5.4 · p. 36, Table 3 · p. 38

5.4.1 Scaling with Embedding Dimension

• UMAP scaled efficiently to embedding dimensions above two because its fuzzy-topological representation avoids the global normalization and space trees required by t-SNE.This makes UMAP practical for downstream tasks such as clustering and anomaly detection, not only visualization.Source: §5.4.1 · p. 39

5.4.2 Scaling with Ambient Dimension

• UMAP operated effectively on unreduced high-dimensional data, including an example with approximately 1.8 million ambient dimensions, using local connectivity and approximate nearest-neighbor search.These mechanisms allow raw-source manifold learning where PCA preprocessing might discard important structure.Source: §5.4.2 · pp. 39, 42

5.4.3 Scaling with the Number of Samples

• On GoogleNews, UMAP had superior scaling to Barnes-Hut t-SNE, comparable asymptotic scaling to FIt-SNE and LargeVis, and faster absolute performance than both alternatives.The full 3-million-vector embedding completed in around 200 minutes, versus several days for MulticoreTSNE even with multiple cores.Source: §5.4.3 · p. 42, Figure 11 · p. 43

Interpretability

• UMAP embedding dimensions lack specific meanings and factor loadings, so PCA, NMF, or pLSA are preferable when strong interpretability is critical.Unlike PCA, UMAP dimensions are not directions of greatest variance because UMAP is based on distances between observations rather than source features.Source: §6 · p. 45

Manifold assumptions

• With small noisy samples or only large-scale manifold structure, UMAP may fit spurious structure; robustness improves as more data are sampled.Detecting spurious embeddings remains an open research topic.Source: §6 · p. 45

Global structure

• When global structure is primary, MDS or hybrid PHATE may be better choices, although their greater computational cost requires landmarking for scalability.UMAP emphasizes local distances, whereas MDS preserves the full distance matrix and PHATE combines local information with MDS.Source: §6 · pp. 45, 49
• UMAP’s global-structure preservation partly comes from Laplacian Eigenmaps initialization and its cross-entropy objective, while similarly initialized t-SNE can match it on a particular measure.The objectives differ in how they penalize failures to preserve non-local and global structure.Source: §6 · p. 49

Metric structure

• Because UMAP preserves topology rather than pure metric structure and introduces reverse-nearest-neighbors, methods such as MDS can outperform it on metric-preservation measures.Users who trust ambient distances should prefer methods explicitly designed to preserve those distances, since UMAP can equalize regions with different local densities.Source: §6 · p. 49

Small datasets

• Approximate nearest neighbors and negative sampling can produce suboptimal embeddings for datasets smaller than 500 samples, so users should exercise caution.A slower exact implementation for small datasets is identified as future work.Source: §6 · pp. 49–50

Future empirical studies

• A comprehensive empirical study should assess how UMAP’s algorithmic components, choices, and hyper-parameters affect practical results.Such a study would connect the foundational mathematical framework to the practical consequences of its design decisions.Source: §7 · p. 50
• Systematic research should develop better metrics and evaluations for non-local and global structure preservation across manifold learning algorithms.Existing metrics are not comprehensive and are often tied to particular downstream tasks, limiting understanding of UMAP’s success.Source: §7 · p. 50

Extensions

• UMAP could support supervised or semi-supervised reduction and heterogeneous data by intersecting fuzzy simplicial sets generated from multiple views and metrics.Potential applications include semi-supervised clustering and interactive labelling tools; categorical data could use Jaccard or Dice distance, while ordinal data could use Manhattan distance.Source: §7 · p. 50
• The computational framework could add unseen points to existing embeddings, map embedded points back to high-dimensional space, and enable metric learning.These capabilities could support feature engineering for clustering or classification and generative-model-like use cases similar to autoencoders; metric-learning examples include or [8].Source: §7 · pp. 50–51

Robustness

• Future techniques should detect and mitigate spurious embeddings, particularly for small datasets, to make UMAP more robust for exploratory two-dimensional visualization.This would target a common use case in which dimensionality reduction supports exploratory data analysis.Source: §7 · p. 51

8 Conclusions

• UMAP is a mathematically grounded, general-purpose dimension reduction technique whose implementation is faster than t-SNE and scales better.These properties enable high-quality embeddings for larger datasets than previously attainable.Source: §8 · p. 51
• UMAP’s use and effectiveness across various scientific fields demonstrate the strength of the algorithm.Source: §8 · p. 51

• The lemma assumes a Riemannian manifold embedded in Rn with a metric that is locally constant and diagonal near p.The argument restricts attention to a ball B contained in the neighborhood U where the metric remains constant.Source: A Proof of Lemma 1 · pp. 51–52
• The resulting geodesic distance is simplified using the constant metric and the ambient-coordinate representation of curves.The proof relates the geodesic expression to the ambient distance dRn, with r denoting the ambient ball radius.Source: A Proof of Lemma 1 · p. 52
• The ball volume is expressed by integrating the Riemannian volume form, with constant det(g) factored outside the integral.This reduces the volume calculation to the ambient-coordinate ball and the determinant of the metric.Source: A Proof of Lemma 1 · p. 52
• Fixing the ball volume to π^(n/2) / Γ(n/2+1) yields the determinant requirement det(g) = 1/r^(2n).Here r is the radius of the corresponding ball in ambient Rn.Source: A Proof of Lemma 1 · p. 52
• Because g has constant diagonal entries, the determinant condition can be solved for g itself.The proof then substitutes this metric into the definition of geodesic distance between p and q in B.Source: A Proof of Lemma 1 · p. 52

• FinReal : Fin-sFuzz → FinEPMet and FinSing : FinEPMet → Fin-sFuzz form an adjunction, with FinReal the left adjoint and FinSing the right adjoint.Source: B Proof that FinReal and FinSing are… · p. 53
• FinSing(Y) is defined levelwise by hom_FinEPMet(F([n], [0, a)), Y), with face maps induced by pre-composition and functoriality by postcomposition.Source: B Proof that FinReal and FinSing are… · p. 53
• FinReal is constructed as the left Kan extension of F along the Yoneda embedding, explicitly yielding the colimit FinReal(X) = colim y([n],[0,a))→X F([n]).Source: B Proof that FinReal and FinSing are… · p. 53
• The adjunction follows from Yoneda isomorphisms on standard simplices, while canonical colimit decompositions of simplicial sets extend this isomorphism to all objects.Source: B Proof that FinReal and FinSing are… · pp. 53–54

Comparison with t-SNE

• t-SNE uses perplexity-calibrated Gaussian input similarities, Student t-distributed output similarities, and a Kullback-Leibler divergence objective.Its probability construction includes symmetrization and matrix-wise normalization, while efficiency relies on nearest-neighbor and output-space approximations.Source: C From t-SNE to UMAP · pp. 54–55

UMAP cost function

• UMAP’s cross-entropy cost resembles LargeVis without a repulsion-weight parameter or high-dimensional matrix normalization, enabling stochastic-gradient optimization.The optimizable terms have a similar form, but UMAP minimizes the cost and omits LargeVis’s γ weighting term.Source: C From t-SNE to UMAP · pp. 56–57

High-dimensional similarities

• UMAP defines high-dimensional similarities as local fuzzy simplicial set memberships over approximate nearest neighbors, allowing non-Euclidean distances.Memberships are zero outside the n approximate nearest neighbors; σ_i is calibrated by an algorithm playing a role similar to t-SNE’s perplexity-based calibration.Source: C From t-SNE to UMAP · p. 57
• Unlike t-SNE, UMAP symmetrizes similarities by fuzzy-set union and performs no further normalization.The symmetrization uses the probabilistic t-conorm.Source: C From t-SNE to UMAP · p. 57

Low-dimensional similarities

• UMAP’s low-dimensional similarities use user-defined positive parameters a and b, with defaults approximately a ≈1.929 and b ≈0.7915.Setting a = 1 and b = 1 yields the Student t-distribution used in t-SNE.Source: C From t-SNE to UMAP · p. 57