Abstract: tSNE and UMAP are popular dimensionality reduction algorithms due to their speed and interpretable low-dimensional embeddings. Despite their popularity, however, little work has been done to study their full span of differences. We theoretically and experimentally evaluate the space of parameters in both tSNE and UMAP and observe that a single one -- the normalization -- is responsible for switching between them. This, in turn, implies that a majority of the algorithmic differences can be toggled without affecting the embeddings. We discuss the implications this has on several theoretic claims behind UMAP, as well as how to reconcile them with existing tSNE interpretations. Based on our analysis, we provide a method (GDR) that combines previously incompatible techniques from tSNE and UMAP and can replicate the results of either algorithm. This allows our method to incorporate further improvements, such as an acceleration that obtains either method's outputs faster than UMAP.
Introduction: The Gap Between t-SNE and UMAP
In the field of data visualization, t-SNE and UMAP are the undisputed heavyweights. t-SNE is widely recognized for its probabilistic foundations and its ability to highlight local cluster structures. Conversely, UMAP, rooted in category theory and topology, is often preferred for its computational efficiency and its perceived ability to preserve global structure (inter-cluster distances).
Despite their ubiquity, the fundamental differences between these two algorithms have remained poorly understood. Researchers have long debated whether their distinct outputs arise from UMAP’s exotic mathematical foundations or merely from implementation details. This work aims to bridge this gap by distilling the specific algorithmic choices—among dozens of hyperparameters—that dictate the final embedding's appearance and performance.
Methodology: Gradient Dimensionality Reduction (GDR)
By performing a "first principles" derivation of both algorithms, we stripped away theoretical jargon to compare their underlying gradients. We introduced GDR (Gradient Dimensionality Reduction), a unified optimization framework that isolates variables such as initialization, distance metrics, and symmetrization.
GDR offers a flexible approach by:
- Toggling Normalization: It can treat similarity matrices as normalized (summing to 1, as in t-SNE) or unnormalized (as in UMAP).
- Unifying Sampling: It adopts UMAP’s efficient $O(1)$ per-point repulsion sampling but applies it to the t-SNE loss function.
- Accelerating Optimization: Through momentum-based gradient descent and optimized parallelization, GDR produces t-SNE-style embeddings at UMAP speeds—and UMAP-style embeddings faster than the original UMAP library.
Key Insights: The Role of Normalization
Our most striking finding is that normalization is the primary factor responsible for the qualitative differences between t-SNE and UMAP. When UMAP's similarity matrices are normalized, the resulting embeddings resemble t-SNE. Conversely, unnormalized t-SNE produces outputs characteristic of UMAP.
This discovery challenges several theoretical myths. For instance, UMAP’s "pseudo-distance" metric—a cornerstone of its topological foundation—was found to have negligible effect on the final embedding. This suggests that UMAP’s success is driven more by clever optimization heuristics than by its category theory roots. Furthermore, we demonstrated that the computationally expensive Barnes-Hut trees typically used in t-SNE are unnecessary; UMAP-style uniform sampling for repulsive forces can achieve identical results with significantly lower complexity.
Experimental Results
We evaluated GDR across diverse benchmarks, including image data (MNIST, Fashion-MNIST, Coil-100), biological data (single-cell mRNA), and text data (Google News word vectors).
Key results include:
- Speed: GDR is approximately 2x faster than the fastest existing UMAP implementations and an order of magnitude faster than standard t-SNE libraries.
- Fidelity: Quantitative metrics like kNN-accuracy and V-score confirm that GDR replicates the "flavor" of both algorithms. On MNIST, GDR-tsne achieved a V-score of ~70.9, nearly identical to the original t-SNE.
- Loss Function Flexibility: Replacing the standard KL-divergence loss with a simpler Frobenius norm produces nearly identical unnormalized embeddings, suggesting paths for even simpler optimization strategies.
Conclusion and Future Work
While we have unified the computational aspects of these algorithms, the "manifold learning" claims remain fragile. Neither algorithm can "unroll" synthetic datasets like the Swiss Roll without specific initializations (e.g., Laplacian Eigenmaps), indicating that initialization performs much of the heavy lifting for global structure.
Future research will explore why the Frobenius norm is so effective in unnormalized settings and seek to formally reconcile UMAP’s theoretical framework with t-SNE’s normalization. Our consolidated framework and plug-and-play library are available at https://github.com/Andrew-Draganov/GiDR-DUN.
Summary updated