  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.
