A more globally accurate dimensionality reduction method using triplets

Ehsan Amid, Manfred K. Warmuth

Abstract

Dimensionality reduction (DR) is a cornerstone of data visualization, yet popular methods like t-SNE and LargeVis often prioritize local neighborhood preservation at the expense of global structure. This paper introduces TriMap, a DR method that leverages triplet constraints to capture the "big picture" of high-dimensional datasets. By focusing on relative similarity (e.g., "point A is closer to B than to C") and employing a robust loss function, TriMap preserves global cluster relationships and accurately identifies outliers. Furthermore, TriMap maintains linear scalability, making it suitable for massive, modern datasets.

Introduction

Visualizing high-dimensional data, such as images or genomic sequences, requires squashing information into two or three dimensions. For years, t-SNE has been the industry standard due to its ability to create tight, visually distinct clusters. However, t-SNE and its faster counterpart, LargeVis, suffer from a significant "local bias." They excel at keeping similar points together but often fail to represent the true global layout of the data. This leads to arbitrary cluster positioning, the "sucking in" of outliers into unrelated clusters, and instability when data is slightly perturbed.

Baseline comparison of t-SNE, LargeVis, and TriMap. TriMap provides a more globally coherent layout while maintaining competitive local clustering.

Methods: From Pairs to Triplets

The fundamental shift in TriMap is the move from pairwise distances to triplet constraints. Instead of matching exact distances, TriMap optimizes for the relative order: "point $i$ is more similar to $j$ than to $k$."

Robust Loss and Heuristic Sampling

To handle the complexity of large datasets, TriMap introduces two key technical innovations:

  1. Generalized $log_t$ Transformation: Standard loss functions can be overwhelmed by "unsatisfiable" triplets—constraints that cannot be perfectly met in 2D. By setting $t > 1$, TriMap caps the influence of these outliers, preventing them from distorting the entire map.
  2. Efficient Sampling: Considering all possible triplets is computationally prohibitive ($O(N^3)$). TriMap intelligently samples nearest-neighbor triplets to maintain local structure and random triplets to establish the global "skeleton" of the data. This approach ensures the algorithm scales linearly ($O(N)$) with the number of data points.

Key Results and Insights

TriMap was evaluated against t-SNE and LargeVis across diverse benchmarks, including MNIST, Fashion MNIST, and large-scale text datasets.

Global Coherence and Stability

In "Partial Observation" tests, TriMap demonstrates remarkable stability. While t-SNE often shatters clusters into spurious sub-groups when data is sparse, TriMap's layout remains consistent even when 90% of the data is removed. This suggests that TriMap captures the underlying manifold more robustly than its predecessors.

The Outlier Test

A critical failure of local-bias methods is "outlier blindness." If a point is moved far from all others in high-dimensional space, t-SNE and LargeVis often force it into the center of a nearby cluster to satisfy local constraints. As shown in the experimental results, TriMap is the only method that correctly identifies and places such points as distant outliers.

Comparative analysis of stability (rows 2.1.a, 2.1.b) and outlier detection (row 2.2). TriMap successfully isolates the artificial outlier (marked with 'X' in row 2.2), whereas t-SNE and LargeVis embed it within existing clusters.

Discussion and Conclusion

The authors argue that traditional evaluation metrics, such as precision-recall for neighborhoods, overvalue local accuracy. While t-SNE often achieves higher scores on these metrics, the resulting global maps can be misleading. TriMap offers a compelling alternative that balances local detail with global truth.

While TriMap's current implementation could be further optimized for raw speed, its linear scalability and superior handling of global structure and outliers make it a powerful tool for exploratory data analysis. Future work remains in developing standardized quantitative metrics for global embedding quality, moving beyond visual intuition to more rigorous benchmarks.

Summary updated

Abstract

We first show that the commonly used dimensionality reduction (DR) methods such as t-SNE and LargeVis poorly capture the global structure of the data in the low dimensional embedding. We show this via a number of tests for the DR methods that can be easily applied by any practitioner to the dataset at hand. Surprisingly enough, t-SNE performs the best w.r.t. the commonly used measures that reward the local neighborhood accuracy such as precision-recall while having the worst performance in our tests for global structure. We then contrast the performance of these two DR method against our new method called TriMap. The main idea behind TriMap is to capture higher orders of structure with triplet information (instead of pairwise information used by t-SNE and LargeVis), and to minimize a robust loss function for satisfying the chosen triplets. We provide compelling experimental evidence on large natural datasets for the clear advantage of the TriMap DR results. As LargeVis, TriMap scales linearly with the number of data points.
BibTeX
@misc{amid2018more,
  author = {Ehsan Amid and Manfred K. Warmuth},
  title = {{A more globally accurate dimensionality reduction method using triplets}},
  year = {2018},
  eprint = {1803.00854},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1803.00854},
}
Figure