Source-linked AI summary
UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction
Leland McInnes, John Healy, James Melville
TL;DR
Dimension reduction needs methods that scale to large, diverse datasets while balancing local and global structure. UMAP combines mathematical foundations with a scalable algorithm, achieving comparable local embedding quality to t-SNE and LargeVis while performing markedly better at non-local scales.
Problem
Dimension reduction requires methods that scale to massive, diverse datasets while managing the trade-off between preserving local and global structure.
Method
UMAP combines Riemannian geometry and fuzzy simplicial sets to construct a mathematically grounded, practical scalable manifold-learning algorithm.
Results
UMAP provides largely comparable embedding quality to t-SNE and LargeVis at local scales, but performs markedly better at non-local scales.
Takeaways & Limitations
UMAP is a general-purpose dimension-reduction technique that is faster than t-SNE and scales better to larger datasets.
Takeaways & Limitations
UMAP may not be the best choice when preserving global structure is the primary objective.
Abstract
from arXiv · showhide
UMAP (Uniform Manifold Approximation and Projection) is a novel manifold learning technique for dimension reduction. UMAP is constructed from a theoretical framework based in Riemannian geometry and algebraic topology. The result is a practical scalable algorithm that applies to real world data. The UMAP algorithm is competitive with t-SNE for visualization quality, and arguably preserves more of the global structure with superior run time performance. Furthermore, UMAP has no computational restrictions on embedding dimension, making it viable as a general purpose dimension reduction technique for machine learning.
1 Introduction
The paper introduces UMAP as a theoretically grounded, practical scalable manifold-learning technique for dimension reduction, motivated by the need to handle massive and diverse datasets. It emphasizes mathematically justified design decisions and evaluates UMAP on real-world data and scaling experiments while discussing limitations and extensions.
- Motivation: Dimension reduction supports visualization and machine-learning preprocessing, but growing dataset sizes and data diversity demand scalable algorithms.Existing methods generally prioritize preserving either pairwise global distances or local distances.
- Contribution: The paper introduces UMAP, a novel manifold-learning technique grounded in mathematical theory and implemented as a practical scalable algorithm for real-world data.Its foundations relate to Laplacian eigenmaps, Riemannian geometry, and algebraic-topological treatment of uniform data distributions on manifolds.
- Contribution: UMAP’s design decisions are selected from a solid theoretical foundation rather than experimentation with a task-specific objective function.The paper argues that theoretically grounded choices are advantageous for the fundamental components shared by neighborhood-based manifold-learning algorithms.
- Paper organization: The paper presents UMAP’s theory, computational formulation, implementation details, hyper-parameters, practical results, and scaling comparisons with other dimension-reduction algorithms.It also contrasts UMAP with t-SNE and LargeVis to aid understanding of the algorithm.
- Limitations and extensions: The paper discusses UMAP’s relative weaknesses and applications for which it may not be the best choice, then outlines extensions including semi-supervised learning, metric learning, and heterogeneous data embedding.These extensions are enabled by UMAP’s mathematical construction.
2 Teoretical Foundations for UMAP
UMAP’s theoretical foundations combine manifold theory, Riemannian geometry, and topological data analysis. Its algorithm approximates local manifold structure, merges local fuzzy simplicial-set representations, and optimizes a low-dimensional layout by minimizing topological-representation error.
- Manifold and topological representation: UMAP uses local manifold approximations and patches their fuzzy simplicial-set representations into a topological representation of high-dimensional data.The construction addresses manifold approximation and fuzzy simplicial-set representation as its two main problems.
- Layout optimization: UMAP optimizes the low-dimensional layout to minimize the error between the high- and low-dimensional topological representations.The paper describes this objective as minimizing cross-entropy between the two representations.
- Manifold approximation: Custom distances for each data point enforce the uniform-distribution assumption, then incompatible local metric spaces are merged through fuzzy simplicial sets.Each point receives an independent distance notion, whose incompatibilities are resolved by converting the metric spaces into fuzzy simplicial sets.
- Functorial construction: Functors convert metric spaces into fuzzy topological representations, allowing local views to be merged while retaining metric information in the fuzzy structure.The fuzzy singular set functor translates each extended-pseudo-metric space into a fuzzy simplicial set, after which a fuzzy union combines the family.
- Limitations and implementation: The local geodesic approximation is limited to distances measured from each Xi, so UMAP uses extended-pseudo-metric spaces and, in practice, restricts representations to the 1-skeleton.Higher-dimensional simplices better capture overall topology but impose non-negligible computational costs.
3 A Computational View of UMAP
UMAP’s computational procedure has two phases: constructing a weighted k-neighbour graph and computing a low-dimensional layout of that graph. Its theoretical foundation motivates novel choices in both phases.
- Overview: UMAP first constructs a weighted k-neighbour graph, then computes a low-dimensional layout of that graph.These two phases distinguish graph-based dimension-reduction algorithms through their graph-construction and layout choices.
- Graph Construction: For each data point, UMAP finds its k nearest neighbors under a chosen metric using exact or approximate nearest-neighbor search.The input hyperparameter k determines the number of neighbors selected for each point.
- Graph Construction: UMAP assigns edge weights from local parameters ρ_i and σ_i, with ρ_i ensuring each point connects to at least one other point at weight 1.These parameters encode local connectivity and a locally defined Riemannian metric.
- Graph Construction: The directed fuzzy-simplicial graph is symmetrized into an undirected weighted graph, where each edge represents the probability that at least one directed edge exists.The symmetrization uses a probabilistic t-conorm applied to the directed adjacency matrix.
- Graph Layout: UMAP computes the embedding with a force-directed layout using iterative attractive and sampled repulsive forces, forming a non-convex optimization problem.The forces optimize edge-wise cross-entropy between the high-dimensional weighted graph and the graph induced by the embedding.
4 Implementation and Hyper-parameters
UMAP is implemented as a sequence of local fuzzy simplicial-set construction, spectral initialization, and fuzzy-set cross-entropy optimization. Its practical design uses approximate nearest-neighbor search, stochastic optimization, and four hyper-parameters controlling neighborhood size, embedding dimension, point separation, and training duration.
- Algorithm implementation: UMAP constructs local fuzzy simplicial sets from nearest neighbors, combines them with a probabilistic t-conorm, and represents only the 1-skeleton in the current implementation.The local construction uses a normalized manifold distance and converts it into fuzzy membership strengths.
- Algorithm implementation: Spectral initialization treats the global fuzzy representation’s 1-skeleton as a weighted graph and applies standard methods to its symmetric normalized Laplacian.The weighted adjacency matrix is formed from the 1-skeleton of the topological representation.
- Algorithm implementation: Embedding optimization minimizes fuzzy-set cross entropy using probabilistic edge sampling, negative sampling, and stochastic gradient descent without a normalization requirement.The membership-strength approximation is differentiable, enabling gradient-based optimization.
- Practical efficiency: The overall complexity is empirically approximately O(N1.14), bounded by approximate nearest-neighbor search, while parallelized nearest-neighbor descent and SGD can accelerate the implementation.The experiments used a single-core version, although both components had been parallelized at publication.
- Hyper-parameters: UMAP has four hyper-parameters: n for neighborhood size, d for target dimension, min-dist for close-point separation, and n-epochs for optimization duration.The effects of d and n-epochs are largely self-evident, whereas n and min-dist require more discussion; low min-dist values can produce densely packed regions.
5 Practical Efficacy
UMAP provides embedding quality comparable to t-SNE and LargeVis locally while better preserving global and topological structure and often outperforming them at non-local scales. It also offers strong computational performance, scaling to millions of high-dimensional data points and embedding dimensions beyond visualization.
- Embedding quality: UMAP preserves local fine structure similarly to t-SNE and LargeVis while reflecting large-scale global structure represented by Laplacian Eigenmaps and PCA.This pattern is reported across COIL20, MNIST, Fashion-MNIST, and GoogleNews embeddings.
- Embedding quality: UMAP captures more global and topological structure than t-SNE, retaining more COIL20 loops and separating global MNIST digit relationships more clearly.The reported examples include intertwined COIL20 loops and distinct MNIST digit groupings.
- Embedding quality: UMAP matches or exceeds t-SNE and LargeVis accuracy at local scales, with significantly higher accuracy at larger k on COIL-20, PenDigits, and Shuttle and evidence of higher accuracy on MNIST.UMAP notably underperforms on Fashion-MNIST in the stated k range.
- Computational performance: UMAP is significantly more performant than t-SNE for embedding dimensions above 2 and remains more efficient even for dimensions of 6 or 8.The passage connects this advantage to downstream machine-learning uses such as clustering and anomaly detection.
- Computational performance: 200 minutes completed UMAP's embedding of 3 million GoogleNews word vectors, compared with several days for MulticoreTSNE even using multiple cores.Benchmarking also found superior scaling to Barnes-Hut t-SNE, comparable asymptotic scaling to FIt-SNE and LargeVis, and faster absolute performance than both in the reported comparison.
6 Weaknesses
UMAP has important limitations involving interpretability, noisy or small datasets, and its emphasis on local structure over ambient or global distances. Alternative methods may be preferable when preserving interpretable dimensions, full-distance relationships, or exact results is critical.
- Interpretability: UMAP embeddings lack the strong interpretability of PCA and NMF because their dimensions have no specific meaning.PCA dimensions represent directions of greatest variance, unlike UMAP embedding dimensions.
- Noise and sample size: UMAP can discover manifold structure in noise, especially with small noisy samples or data containing only large-scale manifold structure.More data generally reduces apparent noise structure and makes UMAP more robust.
- Distance structure: Because UMAP prioritizes local distances, it may be unsuitable when global structure or equal importance across all distance scales is primary.Multidimensional scaling preserves the full distance matrix, while PHATE combines local information with an attempt to preserve long-range distances.
- Metric preservation: UMAP’s topology-focused construction does not explicitly preserve pure nearest-neighbor or ambient metric structure, reducing its suitability when those distances are trusted.Reverse-nearest-neighbors are introduced into the classical knn-graph, and methods explicitly preserving ambient distances may be preferable.
- Computational approximations: Approximate nearest-neighbor search and negative sampling can produce suboptimal embeddings on datasets with fewer than 500 samples.The paper recommends caution with particularly small datasets and identifies a slower exact implementation as future work.
7 Future Work
Future work for UMAP includes evaluating algorithmic choices and global-structure preservation, extending the method to supervised and heterogeneous data, and improving robustness and machine-learning integration.
- Empirical evaluation: A comprehensive empirical study should examine how UMAP’s algorithmic components, choices, and hyper-parameters affect practical results.The paper identifies this evaluation as a significant contribution to the literature.
- Structure preservation: Future work should systematically study metrics for non-local and global structure preservation, whose definitions and objective measures remain uncertain and incomplete.Existing metrics are described as non-comprehensive and often specific to downstream tasks.
- Method extensions: UMAP could support (semi-)supervised dimension reduction and heterogeneous data by treating data types or prediction variables as alternative views with distinct metrics.Examples include Jaccard or Dice distance for categorical data and Manhattan distance for ordinal data.
- Method extensions: Adding unseen samples to existing embeddings could enable metric learning, feature engineering, and clustering or classification within general machine-learning pipelines.The framework also allows generating high-dimensional representations of arbitrary points in the embedded space.
- Robustness and implementation: Techniques to detect and mitigate spurious embeddings, particularly for small datasets, would improve UMAP’s robustness for exploratory two-dimensional visualization.The paper notes that experimental versions of some future-work developments are already available in referenced implementations.
8 Conclusions
UMAP is presented as a mathematically grounded, general-purpose dimension reduction technique whose algorithm is faster than t-SNE and scales better. These properties enable high-quality embeddings of larger datasets, with effectiveness demonstrated across scientific fields.
- UMAP provides a general-purpose dimension reduction technique grounded in strong mathematical foundations.The conclusion characterizes the method as broadly applicable and theoretically grounded.
- UMAP is demonstrably faster than t-SNE and provides better scaling.The conclusion links these algorithmic properties to improved handling of larger datasets.
- UMAP enables high-quality embeddings of larger datasets than previously attainable, and its effectiveness across scientific fields demonstrates the algorithm’s strength.The conclusion attributes this capability to UMAP’s speed and scaling, while citing use across scientific fields as evidence of effectiveness.
A Proof of Lemma 1
The proof establishes Lemma 1 by computing the volume of a metric ball when the Riemannian metric is locally constant and diagonal, then deriving the corresponding metric and geodesic distance.
- Assumptions: The lemma assumes a Riemannian manifold embedded in R^n with a locally constant diagonal metric near p, and considers a ball B centered at p.The ball lies within an open neighborhood U where the metric is constant.
- Volume computation: The proof computes the volume of B using ambient coordinates and the Riemannian volume element involving det(g).Because det(g) is constant, it can be taken outside the integral.
- Volume normalization: Fixing the ball volume to πn/2 Γ(n/2+1) yields the requirement det(g) = 1/r2n.Here r is the radius of the ball in the ambient R^n.
- Metric determination: Since g has constant diagonal entries, the determinant condition allows solving for g itself.The argument uses the diagonal structure of the metric.
- Geodesic distance: The proof then defines geodesic distance on M between p and q as the infimum over smooth curves joining them and simplifies it using the derived metric.Both p and q lie in B, and the simplification uses the specified constant diagonal form of g.
B Proof that FinReal and FinSing are adjoint
The paper proves that FinReal and FinSing form an adjunction, with FinReal as the left adjoint and FinSing as the right adjoint. The proof constructs both functors explicitly and derives the required hom-set isomorphism using Kan extensions and Yoneda lemmas.
- FinReal : Fin-sFuzz → FinEPMet and FinSing : FinEPMet → Fin-sFuzz form an adjunction, with FinReal left adjoint and FinSing right adjoint.
- FinSing is defined by mapping ([n], [0, a)) to homFinEPMet(F([n], [0, a)), Y), with face maps induced by pre-composition.Postcomposition with F level-wise for each a defines maps of fuzzy simplicial sets, making FinSing a functor.
- FinReal is constructed as the left Kan extension of F along the Yoneda embedding, yielding the colimit FinReal(X) = colim y([n],[0,a))→X F([n]).This left Kan extension agrees with Definition 7.
- The adjunction follows from homFinEPMet(F([n], [0, a)), Y) ∼= homFinEPMet(FinReal(∆n<a), Y), using the Yoneda lemma and the colimit construction.Because simplicial sets are colimits of standard simplices and FinReal commutes with colimits, the isomorphism extends to the required adjunction.
C From t-SNE to UMAP
UMAP’s cross-entropy cost has a form similar to LargeVis but omits LargeVis’s repulsive-weight parameter and high-dimensional matrix-wise normalization, enabling stochastic-gradient optimization. Its similarities nevertheless differ from those of t-SNE and LargeVis in both high- and low-dimensional spaces.
- LargeVis: LargeVis approximates high-dimensional similarities with approximate nearest neighbors, abandons low-dimensional normalization, and maximizes a likelihood rather than minimizing KL divergence.Its user-chosen γ controls repulsive contributions relative to attractive contributions.
- UMAP cost function: UMAP’s cost function resembles LargeVis’s after constant terms are removed, but lacks γ weighting of repulsion and high-dimensional matrix-wise normalization.UMAP minimizes this cost with stochastic gradient descent, as LargeVis optimizes its analogous objective.
- High-dimensional similarities: UMAP computes high-dimensional similarities only for n approximate nearest neighbors, assigning zero similarity to all other points.Its distance function need not be Euclidean, and σi is calibrated by Algorithm 3 similarly to t-SNE’s perplexity-based calibration.
- High-dimensional similarities: UMAP symmetrizes similarities through fuzzy-set union using the probabilistic t-conorm, without further normalization.This corresponds to forming top-rep in Algorithm 1.
- Low-dimensional similarities: UMAP’s low-dimensional similarities use user-defined positive a and b; default values give a ≈1.929 and b ≈0.7915, while a = 1 and b = 1 yields t-SNE’s Student t-distribution.The procedure for finding a and b is given in Definition 11.