TriMap: Large-scale Dimensionality Reduction Using Triplets
Authors: Ehsan Amid
Manfred K. Warmuth
Venue:  (2020)
Keywords: Dimensionality Reduction
Triplets
Data Visualization
t-SNE
LargeVis
UMAP

Abstract: We introduce ``TriMap''; a dimensionality reduction technique based on triplet constraints that preserves the global accuracy of the data  better than the other commonly used methods such as t-SNE, LargeVis, and UMAP. To quantify the global accuracy, we introduce a score which 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.

Under review as a conference paper
TRIMAP: LARGE-SCALE DIMENSIONALITY REDUCTION USING TRIPLETS
ABSTRACT
We introduce "TriMap"; a dimensionality reduction technique based on triplet constraints that preserves the global accuracy of the data better than the other com- monly used methods such as t-SNE, Large Vis, and UMAP. To quantify the global accuracy, we introduce a score which roughly reflects the relative placement of the clusters rather than the individual points. We empirically show the excellent performance of TriMap the embedding as well as the runtime. On our performance benchmarks, TriMap easily scales millions of points without depleting the memory and clearly out- performs t-SNE, Large Vis, and UMAP in terms of runtime.
a large variety of datasets in terms of the quality of
INTRODUCTION
Data visualization based on dimensionality reduction (DR) core problem data analysis and machine learning. The aim of DR is provide low-dimensional representation (typically in 2D or 3D) a given high-dimensional dataset that preserves the overall structure of the data as much possible. The earlier approaches for DR involve linear methods such PCA (Pearson 1901). PCA aims to maintain the second-order statistics of the data by projecting the points into the low dimensional space that preserves the maximum amount of variance among all such projections. As a result, PCA has been shown to be effective in preserving the global structure of the data (Silva & Tenenbaum 2003). The global structure includes the overall shape of the dataset, placement of the clusters, and existence of potential outliers. Unlike PCA, much of the focus of the more recent non-linear methods including t-SNE (Maaten Hinton 2008). Large Vis (Tang al. 2016), and UMAP (Mclnnes et al., (218)) has been on preserving the local neighborhood structure of each individual point. Similarly,
common performance measures of DR such as trustworthiness. continuity (Venna & Kaskil 2005). precision-recall (i.e. AUC) (Venna et al., 2010). and nearest- neighbor accuracy have also been developed by retaining the same focus on reflecting the local accuracy of the embedding. Thus, there has been lack of attention developing methods that focus on preserving the global structure of the data and likewise, practical performance measures to assess the global accuracy.
We first introduce the global score, quantitative measure which reflects the closeness of given embedding to the PCA embedding (which is optimal by means of preserving the data variance). The purpose of this score is to measure the accuracy of an embedding in reflecting the overall placement of the clusters of points relative their original representation high-dimension. By design, PCA yields the highest global score among all the DR methods and high values of global score indicates the efficacy of DR method in reflecting the global structure.
Next, we introduce TriMap, DR method which focuses on preserving the global structure of the data in the embedding. Pairwise (dis similaaiisssss between points (used by the previous DR methods) seem to be insufficient in capturing the global structure. Instead, TriMap incorporates a higher order of structure to construct the embedding by means of triplets:
(i,j. k) < point is closer to point j than point k.
The key idea behind TriMap stems from semi-supervised metric learning Amid et al. 2016): Given an initial low- dimeeniiiii representation for the data points, the triplet information from the high- dimensional representation of the points is used to enhance the quality of the embedding. Similarly, TriMap is initialized with the low dimensional PCA embedding, and this embedding is then modified using a set of carefully selected triplets from the high-dimensional representation.

---

Under review as a conference paper
Original (&UC, GS1
I-SNE (0.18, 0.18)
UMAP (0.16, 0.13)
TriMap (0.15, 0.80)
PCA (0.03, 1.00)
(a)
(b)
(c)
(d)
(e)
Figure 1: 2-D Visualizations of the S-curve dataset: (a) original dataset in 3-D, (b) t-SNE, (c) UMAP, (d) TriMap, and (e) PCA. The values of AUC and global score, for respectively measuring local and global accuracy, are shown in order as a pair (AUC, GS) for each embedding. Despite having higher AUC values, t-SNE and UMAP both fail to reflect the overall shape of the S-curve. On the other hand, TriMap successfully unveils the underlying structure in the original dataset. Note that GS is the only DR performance measure that can reflect this property.
With an extensive set of experiments, we show that TriMap produces excellent results on a variety of real-worke as well as synthetic datasets. We show that in many cases TriMap outperforms all the competitor non-linear methods by means of global score and provides comparable local accuracy. While being significantly faster than t-SNE, TriMap provides comparable runtime to UMAP and LargeVis while scaling drastically better to larger datasets. On the Character Font Images dataset of 1..7M points, TriMap calculates the embedding in 1133 hours while Large Vis takes more than 3 hours and UMAP exceeds the 12 hours time limit. Our contributions can be summarized as follows:
We introduce global score to quantify the quality of a low-dimensional embedding in reflecting the global structure of the high-dimensional data such as placement of the clusters rather than the local neighborhood of individual points.
We introduce TriMap, a fast dimensionality reduction method which provides embeddings of the data that are globally more accurate than other non-linear DR methods such t-SNE, LargeVis, and UMAP.
We provide an efficient implementation' of TriMap that can easily scale to millions of points on commodity hardware and outperforms the competing methods in terms of run- time. We also perform many large-scale experiments various datasets show the effi- cacy of TriMap in terms of DR performance measures and runtime.
2 A MEASURE OF GLOBAL ACCURACY
Consider the S-curve dataset? which consists of 5000 points in 3-D uniformly sampled from an S-shaped manifold (Figure (a)). This dataset serves as a paradigmatic problem for evaluating the performance of DR methods. In Figure [ we show the results of 2-D embeddings of the S-curve dataset using t-SNE, UMAP, TriMap, and PCA. The top of each graph is laheled by the scoring pair (AUC, GS) where GS stands for global score (introduced below). Note that both t-SNE and UMAP provide higher values of the AUC score and locally preserve the continuity of the manifold. However, they both fail recover the global structure of the S-curve, which is naturally reflected in the PCA embedding. On the other hand, our TriMap method (formally defined later) successfully recovers the structure of the S-curve by "unveiling" the curved shape of the manifold at both ends. Overall, the 2-D TriMap embedding resembles the original 3-D representation as much as possible. Note also that GS is the only measure that can reflect the global accuracy of the embedding.
The previous example indicates that the local measures of DR performance (such as AUC) cannot reflect the global accuracy of a low-dimensional embedding. In fact, the low-granular structure of the data can only be estimated by considering the global statistics of the dataset, as regarded by the PCA method. PCA is a linear DR method that projects the high-dimensional data onto the top-d orthogonal directions having the highest variance. In order to calculate the mapping, PCA only considers the aggregate statistics of the dataset rather than the local information of each individual data point. As a result, PCA is extremely well suited retaining the global structure of the data, iee the overall shape of the dataset, placement of the clusters, and existence of potential outliers.
com
https::/scikitt 1earn.t-eearr...m Tearr org stabl lake_ aake_s_curvehhtr
learn. dattnnddattssss...
2

---

Under review as a conference paper
NIL (NN 0,906, 0.9277) ?
(NN-0.00 0.935, (NN 0,910, SS 0.916; 7
(4)
(c)
(d)
Figure 2: The Effect of the weight transformation on the MNIST dataset: (a) no weight transfor-
mation, (b) 7 = 50, (c) 7 500 (default), and (d) y 5000. The values of nearest neighbor accuracy and global score are shown as tuple (NN, GS) top of each figure. Larger values of emphasizes more on the local accuracy rather than the global accuracy.
However, by focusing on the global structure, PCA loses much of the local information such as the neighborhood structure of each data point.
Given a low-dimensional mapping produced by PCA, it is possible to calculate an optimal inverse mapping into the original high-dimensional space by means of minimizing the squared error. The optimal inverse map also corresponds to a linear mapping'. In order to quantify the global accuracy of DR result, we focus on the accuracy of the embedding in reflecting the global structure of the data similar to PCA. That is, we consider the minimum reconstruction error of the original dataset by means of a linear inverse map. Given n data points {æ, E R 1;=1, let X Rm denote the 2;. Similarly, let Y Rdxx
high-dimensional data matrix where the i-th column corresponds E H" Without loss of denote the matrix of the low-dimensional embedding of the points E generality, we assume both X and Y centered. We define the Minimum Reconstruction Error (MRE) from the embedding as
{Y
min AER"xd
X --
where ||. ||r denotes the Frobenius norm*. Note that PCA has the lowest possible MRE among all the DR methods. Thus, in order to obtain a normalized measure global accuracy of a given embedding Y for data X, we define the global score (GS) as
GS(Y = exp (- X(X) - EPCA
E [],
EPCA
where Erca == E(YCcAl X) denotes the MRE achieved by the PCA embedding YPCA on the same dataset X. Note that GS(Y X) = 1 and we claim that larger values of GS indicate a higher capacity of DR method to reflect the global structure of the data, as shown in the experiments.
In the remainder of the paper, we use GS as the global measure of performance. Due to the high computational complexity for caleulating the rustworthines--cominne and AUC scores for large data sets, we use neerest-neighhors accuracy as the local measure of performance henceforth.
3 THE TRIMAP METHOD
We now formally introduce the TriMap method. Recall that a triplet consists of three points (i. k) where point is closer point j than point k. TriMap chooses subset T = {(i, j. k)} of triplets and assigns a weight Wigk 2 0 for each triplet: a higher value of wijk implies that the pair (i, k) is located much farther than the pair (i.j). We define the loss of the triplet (i.j.k) as
s s yk)
lifk == wigk s Uj) + s yk)
where s(y., v;) (1 1 -,,113)
MMoee specifically, mapping to low-dimension corresponds projecting the data onto the top-d eigendi- rections of the data covariance matrix. The inverse mapping is induced by the transpose of the projection matrix. "The optimum value A" for the MRE can be calculated efficiently as
A = XY (YYT>-1
This also handles possible rotation and scaling of the emhedding.
3

---

Under review as a conference paper
[7] mo (80 10300, 22 (1883)
[f life O33 10 11787 25 (LMB))
[P] monn 1894 HUSHI) -1310)
[T] 2il6 (3E--1M4,, (2-M) 12-11
(7] InAAt 1532 BUSGN, GJ
(d)
(e)
Figure 3: Effect of changing the number of triplets on the quality of the embeddings of the MNIST
dataset. We consider (m, m',r) c (2, 1) for: (a) c= 1, (b) 2, (c) 5 (default), (d) 10. and (c) c 20. The values of nearest neighbor accuracy and global score are shown as tuple (NN, GS) on top of each figure. The quality of embedding does not improve significantly
after adding certain number of triplets.
a similarity function between y; and yj. The choice of s motivated by the good performance of Student t-distribution for similarities in low-dimension in the t-SNE method. Note that the loss of the triplet (f, j, k) approaches zero as y; - yyll decreases and ||9, yvel increases.
We first develop the weighing scheme for the triplets. To reflect the relative similarities in high-dimension, we define the unnormalized weight of the triplet ji, k)
"ysculed log: tngstraasformnnion
normalized cotpott wodgght
Wiyk exp(de
2 0,
0.6
in which, dy is any distance measure between æ; and øj in high- dimension. For Euclidean distances, use the scaling introduced in -Zlnni-Maaorr & Perona 2005).
0.
-NIL
Gell
x; 12
Oij
normolised Impest wright
where ozy O2 o, and 0, is set the average Euclidean distance between æ; and the set of nearest-neighhors of æ; from 4-th to 6-th neighbors. This choice of aij adaptively adjusts the scaling based on the density of the data.
Figure 7-scaled log- transformation with different values of 7 The value NIL corresponds to no transformation.
While the choice of weights Wiyk works well in practice, adjust the weights further by applying non-linear transformation that em- phasizes the smaller weights. Expanding the values of small weights has the effect of placing the nearest-neighbors closer to the point and pushing the remaining points farther away, thus improving the local accuracy (as shown in Figure 2 obtained by applying the 7-scaled log- taggtrrassooonioonn (see Figure
and discussed later). The final value of the weight wijk is
Wijk W
wiyk = C7
+ 5) where (u) log (1+yu),
in which W max Wyyne, 7 > O is scaling factor, and 5 is small constant. We use 7 500 and 10 in all our experiments.
To construct the embedding, we consider a small subset of all possible triplets (i.j, k) for which, the closer point j belongs to the set of nearest-neighbors of the point and the farther point k is among the points that are more distant from i than j. chosen uniformly at random. For each point we consider its m 10 nearest neighbors and sample m' 5 triplets per nearest-neighbor. This yields m X m² 50 nearest- triplets per point. In addition, we also add r 5 random triplets (i.j.k) per each point where j and i are sampled uniformly at random and their order is possibly switched based their nearness to i. This yields x m + r 55 triplets per point in total. Thus, the overall complexity of the optimization step is linear in number points n. The computational complexity is dominated by the nearest-neighhor search, which is shared among all the recent methods such as t-SNE, LargeVis, and UMAP. We use ANNOY for the approximate nearest-neighbor search" which is based random projection trees.
While a random initialization for the embedding also works well in practice, we initialize the embed- ding to the PCA solution YAca (scaled by small constant value for better convergence). The PCA
4

---

Under review as a conference paper
Dataset (size)
LNNE
LargeVis
UMAP
TriMap
Speecuu
COIL-20 (1440)
00:00:08
00:05:51
00:00:04
00:00:02
2.00x
USPS (IIK)
00:02:02
00:06:12
00:00:12
00:00:11 11
1.10x
Epileptic Scizure (11.5)
00:03:11
00:06:17
00:00:15
00:00: 12
1.25x
Newsgroup (18K)
00:05:34
00:06:57
00:00:26
00:00:21
1.24x
Tabula Muris (54K)
00:17:32
00:09:29
00:01:12
00:01:06
2.00x
(70K)
00:20:38
00:11:29
00:01:15
00:01:23
0.90x
Fashion MNIST (70K)
00:19:10
00:11:04
00:01:18
00:01:24
0.93x
TV News (~<129K)
00:38:59
00:16:26
00:02:57
00:02:45
1,07x
360+K Lyrics (~-300K)
08:50:49
00:44:16
00:25:23
00:13:49
1.84X
Covertype (~-81KK
00:44:54
02:59:41
00:24:42
1.82x
RCV1 (800K)
01:34:38
04:55:53
00:36:59
2.56x
Character Font Images (~117M)
03:16:19
01:17:50
2.52x
KDDCup99 (>4.9M)
04:17:01
HIGGS (1IM)
10:08:36
Table 1: Runtime of the methods in hh : mm s format on single machine with 2.6 GHz Intel Core i5 CPU and 16 GB of memory. We limit the runtime of each method to 12 hours. Also, UMAP runs out of memory on datasets larger than <44 points.
initialization for TriMap allows faster convergence while preserving much of the global structure discovered by PCA. Note that the other DR methods such as t-SNE are extremely sensitive to the initialization and do not converge well with any initial solution other than small random initialization around the origin.
We define the final loss as the sum of the losses of the sampled triplets in T
TriMap
Σ
Eigk
(i..ETT
The loss is minimized using the full-batch gradient descent with momentum using the delta-bar-ded method. all our experiments, we perform 400 iterations with the value of momentum parameter equal to 0.5 during the first 250 iterations and 0.8 afterwards.
Finally, note that there exists connections between TriMap and number of tripler (aka ordinal) embedding methods such as t-STE (Van Der Maaten & Weinberger 2012). The triplet embedding methods have been developed for a different setting where the goal is to find an embedding based on given pre-specified set of triplets obtained from human evaluators (or some form of implicit feedback). For instance, t-STE maximizes the sum of log of the satisfaction probabilities of the triplets to calculate the embedding. It is worth mentioning that TriMap is DR method that is designed to sample the informative triplets from the high-dimensional representation of a set of points and assign weights to these triplets reflect the relative similarities of these points. Although TriMap can also be used for the triplet embedding task, we only focus on the DR results
3.1 EFFECT OF DIFFERENT PARAMETERS
We briefly discuss the effect of different parameters, namely the total number of triplets |T| and the y-scaled log-transformation, on the quality of the embedding. TriMap is particularly robust to the number of sampled triplet for constructing the embedding. This can explained by the high amount of redundancy in the triplets (the triplets (i,j. k) and (i, k') convey the same information & and K' are nearest neighbors and also mapped nearby). Figure B we consider various values for m, m', and for the MNIST dataset while fixing the remaining parameters. In fact, using large number of triplets can sometimes introduce an overhead and require larger number of iterations to converge.
A more important parameter is y which controls the trade-off between the local and global accuracy. Larger values of y increases the relative importance of triplets with smaller weights This causes the method to focus on the nearest-neighhor points rather than the points that are far away, thus improving the local accuracy. On the other hand, improving the local accuracy can impair the global accuracy. In Figure 2 we plot the 7-scaled ingtrannfformaionn for various values and illustrate the results on MNIST without the log- tre-ssfrrfoom larger values of ry the clusters tend to become more compressed and as a result, the nearest neighbo accuracy is improved.
well as the results with different 7 values. For
the other hand, the global score starts to decrease for larger y values.
Also, the embeddings obtained by simply applying these methods to our set of sampled triplets are quite subpar (see the MNIST result in (Van Der Maaten & Weinberger 2012)) and are shown here.
5

---

Under review as a conference paper
COIL 20 SNE (1000,066))
COIL-20- UMAP (0.9,0.50)
COIL-20- MriMa (0.90,000)
COI--20 PCA (0.67, L.0)
USPS 1-NE (0.96,0.80)
USPS (0.90,0.00) 0.90)
USPS - Triap (0.91, 0.50)
(0.56, 1,00)
Epileptic . GSNE (0.58, 0.91)
Epilpticc UMAP (0.12,0.90)
Dpileptcc TriMap (0. (0.47)0.11)
Epdeptic PCA (0.35,
20 News t-SNE 0.900
Nows TriMap (0.96.0.0))
News PCA (0.08, L.00)
Tahnlo M. 1-NE 00.69,0.05)
Tabals M. UMAP (0.57, 0.00)
Tahmls TriMap (0.42,0.17)
Tabala M. PCA (0.20,1.00) 1.00)
MNIST- - LNNK (0.97, 0.90)
MNIST UMAP (0.35.0.91)
MNIST TriMap (0.94,
(0.38, LOU)
Figure 5: Visualizations of different datasets using t-SNE, UMAP, TriMap, and PCA. Each row corresponds to one dataset and each column represents one method. The values of nearest neighbor accuracy and global score are shown as pair (NN, GS) on top of each figure.
4 EXPERIMENTS
In this section, we apply TriMap set of real-world well synthetic datasets and compare the results to t-SNE, Large Vis. UMAP, and PCA methods. The datasets used in our experiments are listed in Table and short description is given in the appendix. All experiments conducted

---

Under review as a conference paper
F. MNIST 1-NE (0578,
F. MINIS UMAP (0.73, 0.75)
MNIST TriMpp (0.88, 087)
MNIST PCA (0:45, 100)
News (0
UMAP (0.83,0.14)
TV News TriMap (0.71,0.12)
TV News PCA (0.87,
36IK++ Lyrics LSNE (0.31.0.85) 390K+ Lyries
UMAP (0.27, 0.81)
BKIK Lyrics - Pullower (0.34.0.44)
890K+ Lycio- PCA (0.27, 1.00)
Figure 5: Visualizations of different datasets (continued) using t-SNE, UMAP, TriMap, and PCA. Each row corresponds to one dataset and each column represents one method. The values of nearest neighbor accuracy and global score are shown as tuple (NN, GS) top of each figure.
single machine with 2.6 GHz Intel Core i5 CPU and 16 GB of memory. We limit the runtime of each algorithm to 12 hours. For implementations, we use the default sklearn implementation for t-SNE and the official implementations of Large Vis and UMAP provided by the authors?.8. Due to lack of space, we provide the comparison to the Large Vis results as well additional TriMap results on the larger datasets in the appendix.
In order to have a fair comparison, we use the default parameter values for all methods, including r 5. 7 500, and 400 iterations). Also to reduce the overhead
ours (m 10, m' induced by the dimensionality of the data in the nearest-neighhor search step, we reduce the number of dimensions of the dataset to 100 necessary, using the PCA method. To evaluate the local performance, we show the nearest-neighhte accuracy of each result. We also show the GS as measure of global performance. The performance measures are shown on top of each figure pair (NN, GS).
4.1 RUNTIME
The runtime the methods are provided in Table I in the hh mm: ss format. We limit the runtime of each method to 12 hours. As can be seen from the results, TriMap provides excellent runtime and outperforms all the other methods in most cases. Also, TriMap easily scales to millions of points while the other methods exceed the time limit or run out of memory. For instance, UMAP causes an out of memory error for datasets larger than 4M points.
4.2 VISUALIZATIONS
The visualizations of the datasets using TriMap as well as the other competing methods are shown in Figure FurreFaand and For some results, we provide zoomed in snippet over the main figure provide more detailed illustration. Overall, TriMap preserves the underlying global structure of the data better than the other competing methods. This is reflected by the larger GS values for TriMap as well as visually comparing the embeddings to the PCA result. For example, TriMap recovers the
7

---

Under review as a conference paper
Covtype UMAP (0.74,4e-04)
Covtype TrMap (0.62,6e-05) 05)
Covtype - PCA (0.44, 1.00)
RCV1- - UMAP (0.69,0.80
RCV1 TriMap (0.58, 0.92)
RCVI PCA (0.32, 1.00)
Fonts VirgeVis 00.91,
Fonts TriMap (0.77, 0.76)
Fonts PCA (0.98, 1.00)
Figure 6: Visualizations of Covertype and RCVI datasets using UMAP, TriMap, and PCA, and visualizations of the Character Font Images dataset using Large TriMap, and PCA. The values of nearest neighbor accuracy and global score are shown as a tuple (NN, GS) on top of each figure.
continuous structure of the TV news dataset and separates the remaining outliers in the data which are also identified by the PCA method. This can be verified by comparing the placement of an example outlier point, marked with a red x, by the different methods: TriMap shows this point among other outliers whereas t-SNE and UMAP fail to uncover this information. Also, the global score TriMap on this dataset is much higher than the other methods. Further discussion given in the appendix.
5 CONCLUSION AND FUTURE WORK
TriMap is fast and efficient method that be easily applied to large datasets. While TriMap is extremely effective for uncovering the global structure of the data, other methods such as t-SNE can provide additional insight about the local neighborhood individual points. As future research direction, we consider using pairwise constraints along with triplet constraints to improve the local accuracy. The current implementation of TriMap utilizes a single core. Parallel implementation of the method that can exploit multiple cores is another future direction. Furthermore, the global accuracy is measured in terms the global score which based on the assumption that linear projection obtained by PCA is globally optimal. While our global score can provide insight about the global accuracy of the embedding in many cases, it appears to be ineffective when the data is highly non-linear contains large amount of outliers. Developing non-linear and more robust global performance measures could significantly improve the assessment of the DR results and provide guidelines for developing more accurate DR techniques.
8

---

Under review as a conference paper
REFERENCES
Ehsan Amid, Aristides Gionis, and Antti Ukkonen. Semi-supervised kernel metric learning using relative comparisons. arXiv preprint arXiv:1612.00086. 2016.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, (Nov))2579-26055 2008.
Leland McInnes, John Healy, and James Melville. Umap:
Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv: 2018.
Karl Pearson. Lii. on lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2(11):559-572, 1901.
Vin Silva and Joshua B Tenenbaum. Global versus local methods nonlinear dimensionality reduction. In Advances in neural information processing systems, pp. 721-728, 2003.
Jian Tang, Jingzhou Liu, Ming Zhang, and Qiaozhu Mei. Visualizing large-scale and high- dimensional data. In Proceedings of the 25th international conference on world wide web, pp. 287-297. International World Wide Web Conferences Steering Committee, 2016.
Laurens Van Der Maaten and Kilian Weinberger. Stochastic triplet embedding. In 2012 IEEE International Workshop on Machine Learning for Signal Processing, pp. 1-6. IEEE, 2012.
Jarkko Venna and Samuel Kaski. Local multidimensional scaling with controlled tradeoff between trustworthiness and continuity. In Proceedings of 5th Workshop on Self-Organizing Maps, pp- 695-702. Citeseer, 2005.
Jarkko Venna, Jaakko Peltonen, Kristian Nybo, Helena Aidos, and Samuel Kaski. Information retrieval perspective to nonlinear dimensionality reduction for data visualization. Journal of Ma- chine Learning Research, 11(Feb):451-49) 2010.
Lihi Zelnik-Manor and Pietro Perona. Self-tuning spectral clustering. In Advances in neural infor- mation processing systems, pp. 1601-1608, 2005.

---

Under review as a conference paper
A DATASETS
The datasets used in the experiments are listed below. All datasets are publicly available online and download link is provided.
COIL-20" (1440): gray-scale images of 20 objects in uniformly sampled orientations (5 degrees of rotation, 72 images per object). Each image is pre-processed by having the background removed and cropped into size 128 x 128.
USPS (1IK): images of handwritten digits (0-9) of size 16 16.
Epileptic Seizure" (11.5K): EEG signal recordings of brain activity for seizure recogni- tion. It contains di8ddimeel vectors belonging to categories.
20 Newsgroup" ! (18K): newsgroup posts categorized into 20 topics. We use TF-IDF representation of the words in each document as the features.
Tabula Muris (~54K): single cell transcriptome data from the mouse from 20 organs.
MNIST (70K): images of handwritten digits (0-9) of size 28 28.
Fashion MNIST (70K): gray-scale images of clothing items such as t-shirt, pullover, bag, etc. of size 28 28.
TV News" (~ 29K): audio-visual features from TV news broadcast categorized into com- mercial and non-commercial.
360K+ Lyrics (~362K)): lyrics of songs from 12 different genres. We group similar
genres together (metal-rock, R&B- R&B-pop. etc.) to form 7 groups. We use the TF-IDF repre- sentation of the words the song the features.
Covertype" (~581K)): cartographic features for forest cover type prediction.
RCV1 16 (800K): Reuters Corpus Volume archive of categorized newswire stories.
Character Font Images"! (~1..7M): images character from scanned and computer gen- erated fonts.
KDDCup99" (~4.9M); computer network intrusion detection.
HIGGS" (11M); Higgs bosons recognition from background process.
B MORE VISUALIZATIOONS
We compare the results of TriMap to LargeVis in Figure and We also provide more visualiza- tions obtained using TriMap in Figure
C DISCUSSION
We briefly discuss the results of TriMap and draw comparison to the other methods.
TriMap generally provides better global accuracy compared to the competing methods. It also suc- cessfully maintains the continuity of the underlying manifold. This can be seen from the COIL-20 result where certain clusters are located farther away from the remaining clusters. However, the underlying structure for the main cluster resembles the one provided by the other methods. TriMap also preserves the continuous structure in the Fashion MNIST and the TV News datasets.
TriMap is also efficient in uncovering the possible outliers in the data. For instance, PCA reveals a large number of outliers in the Tabula Muris and the 360+K Lyrics datasets. These outliers are
10

---

Under review as a conference paper
COIL-20 LirgeVis (0.96,0.72
COIL-20 TriMap (0.90, 0.69)
COIL-20 PCA (0.67, 1.00)
USPS LargeVes Vis (0.94.0.8)
USPS TriMap (0.91, 0.933
USPS PCA (0.36, 1.00)
Epileptic- Lirgo (0.51, 0.92)
Epileptic TriMap (0.47, 0.91)
Epileptic PCA (0.35,
20 News Vis (0.59, 0.89)
20 News TriMap (0.36, 0.90)
20 News PCA (0.09, 1.00)
Tabula M. LargeVis (0.58, 0.01)
Tabula M. TriMap (0.42,0.11
Tabula PCA (0.0
Figure 7: Visualizations different datasets using LirgeVis, TriMap, and PCA. Each row corre- sponds to dataset and each column represents method. The values of nearest neighbor accuracy and global score are shown as pair (NN, GS) on top each figure.

---

Under review as a conference paper
MNIST - LargeVis (0.95,0.51
MNIST TriMap (0.91.0.92)
MNIST PCA (0.38, 1.00)
F. MNIST LargeVia (0.75,0.cm 0.49)
F. MNIST TriMap (0.69,0.8)
F. MNIST- PCA (0.45,
TV News Virge (0.81. 0.01)
TV News TriMap (0.71.0.42)
TV News- PCA (0.87, 1.00)
X
360K Lyrics- UMAP 00.27,0.81)
360K+ Lyrics Pullover (0.34,0.84)
360K+ Lyrics PCA (0.27,
Figure 7: Visualizations of different datasets (continued) using Large Vis, TriMap, and PCA. Each row corresponds to one dataset and each column represents one method. The values of nearest neighbor accuracy and global score are shown as a tuple (NN, GS) on top of each figure.
located far away from the main clusters in the TriMap results. However, the same points are located very close the remaining points in the t-SNE results.
Additionally, both t-SNE and Large Vis tend to form spurious clusters by splitting the underlying connected manifold. This can be seen from the TV News results and the result of Large on the Covertype dataset.
Finally, notice that in some cases GS fails to reflect the global accuracy of the embeddings. This can be seen from the low GS values for all methods on the Covertype dataset. GS may become uninformative when there exists a high degree of non-linearity in the data that cannot be reflected using PCA. GS also cannot reflect the accuracy of the embedding in uncovering single outliers. Developing more accurate global measures for these scenarios a future research direction.
12

---

Under review as a conference paper
Coviype- LirgeVis (0.82, 0.00)
Covtype TrMap (0. 6e-05)
Covtype - PCA (0.44, 1.00)
RCV1 LirgeVis (0.71,0.88)
RCVI TriMap (0.58. 0.92)
RCVI PCA (0.32, 1.00)
Figure 8: Visualizations of Covertype and RCVI datasets using Large TriMap, and PCA, and visualizations of the Character Font Images dataset using Large TriMap, and PCA. The values of nearest neighbor accuracy and global score are shown as a tuple (NN, GS) on top of each figure.
KDDCup09 TriMap (0.97, 0.00)
KDDCup99 PCA (0.88, 1.00)
HIGGS TriMap (0.53, 0.94)
HIGGS- PCA (0.54, 1.00)
Figure 9: Visualizations of KKDCup99 and HIGGS datasets TriMap and PCA. Each row corre- sponds one dataset and each column represents one method. The values of nearest neighbor ac- curacy and global score are shown as tuple (NN, GS) on top of each figure. TriMap shows more structure for both datasets than PCA. Note that GS uninformative for the KDDCup99 dataset.
13


Reviews:
[{"review_id": "Skg9yjLTtB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors introduce TriMap based on triplet constraints that preserves the global accuracy of the data. A measure of global accuracy is proposed to reflect the global accuracy of the embedding. Experiments on various datasets the better performance than baselines.\n\nAuthors define the minimum reconstruction error from the embedding as the global measure in reflecting the global structure of the data similar to PCA. From the definition, this measure has preferences to the linear projection model such as PCA, so the score becomes lower for non-linear projection methods such as t-SNE and UMAP.  The illustrated S-shape example in Figure 1 somehow demonstrate the difference of the proposed method with PCA, t-SNE and UMAP, but the usage of the embedding is not clear since Figure 1(d) looks like a 2-d visualizing of the original 3-d data visualized from certain angle. In addition, the initialization of the proposed method is the PCA method, which prefers the GS measure. It is interesting to see how the GS measure will change if the random initialization is used. \n\nAuthors demonstrate GS and AUS for all the tested data. It might be interesting and more important to see how to get the better embedding with a balanced score for a given data since GS and AUC seems always opposite measures.\n\nThe TriMap method defines the loss of triplet based on unnormalized weighting schema and the weights are adjusted by applying a non-linear transformation that emphasizes the small weights. These formulations are quite heuristic and constructive. It is better to have some formal explanation on the proposed method.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hyxc7IaSKS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors suggest a new technique for embedding point to low-dimensional space. The technique is reminiscent of t-SNE, with the difference that it get weighted triplets (i,j,k) as inputs (meaning that j is closer to i thank). Further a loss function is defined which directly follows t-SNE ideology.\n\nA paper is purely experimental. The only way to judge the quality of its results is to compare 2D pictures of TriMap with other pictures. I did not see any evidence that images of TriMap somehow give a new insight into data (in comparison with other methods).", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "H1lZAv27YH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposed ``TriMap’’---a novel dimensionality reduction technique that learns to preserve relative distances among points in a triplet. The paper has done extensive experiments and presents the results in very nice visualizations. The paper is clearly written. \n\nMajor merits of this paper are: \n\n1. The proposed method seems effective. \n\nOn some datasets (e.g., S-curve), the learned low-dimensional embeddings indeed look very good. And the proposed method has much less runtime than other baselines as shown in table-1. \n\n2. The paper is well written. \n\nHowever, I am still leaning towards rejecting this submission because the proposed method is lack of necessary justification. \n\n1. Many important technical decisions on this method seem arbitrary, including the parametrization of functions (e.g., s, \\omega, \\zeta, etc) and values of hyperparameters (e.g., \\gamma and \\delta). For function forms, the authors should justify why particular parametrization has been chosen; for the hyperparameters, the authors should clearly explain how they are picked---maybe using domain knowledge or tuned on data? \n\n2. The argument for ``global score’’ is not clear enough. There are at least two points that need clarification. \n\nFirst, ``non-local’’ is not equal to ``global’’. The proposed method indeed considers non-local (or non-near) points while learning embeddings, which helps preserve non-local information. But I am not convinced that the preserved information is actually global. Maybe what helps is to first define ``global’’ in a dimensionality reduction context. \n\nSecond, the definition of ``global score’’ depends on another baseline method (i.e. PCA), which seems odd. A principled evaluation (or a score) should be method-independent. What seems right to me is to compute global score (i.e. how much global information has been preserved) by comparing to some statistics in the (high-dim) x space, not to another method. \n\nMoreover, the authors had a strong claim that the proposed ``GS is the only DR performance measure that can reflect this property’’---it doesn’t sound right and why one can’t just use another score which is monotonic wrt the proposed score? The authors mentioned that ``PCA has the lowest possible MRE’’---but this is only right up to the use of a linear transformation and F-norm, so this shouldn’t be a justification for my questions above. \n\n3. What is the reason for the successful runtime? \n\nThe authors didn’t clarify why the proposed method is theoretically faster than the baselines. \n\nWhat I noted is: the authors chose a subset \\mathcal{T} for the TriMap method and used \\mathcal{T} throughout the paper---is it a typo or is a subset always chosen? If the latter holds, then how was it chosen and how large is it compared to the training data used by other methods? In the end, is the proposed method faster because it uses less data? \n\nBesides the weakness above, I also suggest the authors evaluate their method with some extrinsic evaluations. What’s currently used is only intrinsic---the embeddings are trained to preserve relative distances and are evaluated on a trade-off between local accuracy and the defined global score. It is fine because extensive visualizations are provided and readers can subjectively judge the quality of the learned embeddings. However, the experimental section can be stronger if the authors can show the learned embeddings are better at helping some downstream tasks than other baselines (by preserving non-local information?). \n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new dimensionality reduction technique that tries to preserve the global structure of the data as measured by the relative distances between triplets. As Reviewer 1 noted, the construction of the TriMap algorithm is fairly heuristic, making it difficult to determine how TriMap ought to behave “better” than existing dimensionality reduction approaches other than through qualitative assessment. Here, I share Reviewer 2’s concern that the qualitative behavior of TriMap is difficult to distinguish from existing methods in many of the figures. 

Decision: Reject