TriMap: Large-scale Dimensionality Reduction Using Triplets

Ehsan Amid, Manfred K. Warmuth

Introduction

Dimensionality reduction (DR) is a cornerstone of data visualization, transforming high-dimensional datasets into interpretable 2D or 3D maps. While classical linear methods like Principal Component Analysis (PCA) are adept at preserving the global "shape" of data, they often fail to capture intricate local clusters. Conversely, modern non-linear techniques like t-SNE and UMAP excel at local grouping but frequently "shatter" the global structure, leading to visualizations where the relative distances between distant clusters are essentially arbitrary.

TriMap addresses this fundamental trade-off by prioritizing the "big picture" without sacrificing local detail. By utilizing triplet constraints rather than pairwise distances, TriMap provides a more robust representation of the underlying data manifold, scaling efficiently to datasets with millions of points.

Methodology: The Power of Triplets

TriMap departs from standard DR approaches by using triplets $(i, j, k)$ to define the logic: "point $i$ is closer to point $j$ than it is to point $k$." This relative context is significantly more effective at defining a manifold's global layout than simple pairwise distances.

Key Components

  • Triplet Selection: To maintain linear computational complexity $O(n)$, TriMap samples a sparse, informative subset of triplets (approximately 55 per point). These include nearest neighbors for local detail and random distant points for global context.
  • Tempered Loss: The algorithm employs a tempered log transformation on triplet weights. This prevents outliers from dominating the optimization, resulting in smoother, more stable embeddings.
  • PCA Initialization: TriMap initializes with a scaled PCA projection. This provides a mathematically sound starting point for the global layout, which the non-linear triplet constraints then refine.
Comparison of t-SNE and TriMap on CIFAR-10 features. TriMap (right) shows a higher Global Score (GS) and better semantic grouping (e.g., animals vs. vehicles) compared to t-SNE (left).

Quantifying Global Accuracy

A significant contribution of this work is the introduction of the Global Score (GS). Existing metrics like nearest-neighbor (NN) accuracy primarily measure local preservation. The GS uses Minimum Reconstruction Error (MRE) to evaluate how well the original high-dimensional data can be linearly reconstructed from the 2D embedding. Normalized against PCA (the theoretical optimum for linear reconstruction), the GS provides a rigorous way to measure "global accuracy."

Key Results and Scalability

TriMap demonstrates superior performance across a wide range of benchmarks, from standard datasets like MNIST to massive-scale datasets like the 11-million-point HIGGS dataset.

The "Unveiling" Effect

In manifold learning benchmarks like the S-curve, TriMap is uniquely capable of "unrolling" the curve into a flat 2D shape while maintaining the global relationship between the ends of the "S." In contrast, t-SNE and UMAP often collapse the global structure into a dense clump.

Evaluation on the S-curve dataset. TriMap is the only non-linear method that successfully "unrolls" the manifold while maintaining a high Global Score (0.80).

Speed and Efficiency

TriMap is consistently faster and more memory-efficient than its competitors. On the 1.7-million-point Font dataset, TriMap completed the embedding in 1.3 hours, whereas UMAP failed to finish within a 12-hour limit. Furthermore, TriMap successfully processed 11 million points on a standard 16GB RAM machine, a feat that typically causes other modern methods to crash.

Conclusion

TriMap represents a significant step forward in dimensionality reduction, offering a robust solution for researchers needing to visualize large-scale data without losing global context. While it may show a slight trade-off in local nearest-neighbor accuracy compared to t-SNE, its superior speed, scalability, and global fidelity make it a powerful tool for modern data science. Future work aims to parallelize the implementation and explore hybrid models that combine triplet and pairwise constraints to further bridge the gap between local and global accuracy.

Summary updated

Abstract

We introduce "TriMap"; a dimensionality reduction technique based on triplet constraints, which preserves the global structure of the data better than the other commonly used methods such as t-SNE, LargeVis, and UMAP. To quantify the global accuracy of the embedding, we introduce a score that roughly reflects the relative placement of the clusters rather than the individual points. We empirically show the excellent performance of TriMap on a large variety of datasets in terms of the quality of the embedding as well as the runtime. On our performance benchmarks, TriMap easily scales to millions of points without depleting the memory and clearly outperforms t-SNE, LargeVis, and UMAP in terms of runtime.
BibTeX
@misc{amid2019trimap,
  author = {Ehsan Amid and Manfred K. Warmuth},
  title = {{TriMap: Large-scale Dimensionality Reduction Using Triplets}},
  year = {2019},
  eprint = {1910.00204},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1910.00204},
}
Figure