Uniform Manifold Approximation with Two-phase Optimization
Authors: Hyung-Kwon Ko
Jaemin Jo
Yung-Kyun Noh
Jinwook Seo
Venue:  (2021)
Keywords: Dimensionality Reduction
Manifold Learning
Visualization
Topological Data Analysis
UMAP

Abstract: We present a dimensionality reduction algorithm called Uniform Manifold Approximation with Two-phase Optimization (UMATO) which produces less biased global structures in the embedding results and is robust over diverse initialization methods than previous methods such as $t$-SNE and UMAP. We divide the optimization into two phases to alleviate the bias by establishing the global structure early using the representatives of the high-dimensional structures. The phases are 1) global optimization to obtain the overall skeleton of data and 2) local optimization to identify the regional characteristics of local areas. In our experiments with one synthetic and three real-world datasets, UMATO outperformed widely-used baseline algorithms, such as PCA, red, $t$-SNE, UMAP, topological autoencoders and Anchor $t$-SNE, in terms of quality metrics and 2D projection results.

Under review as a conference paper at ICLR 2021
UNIFORM MANIFOLD APPROXIMATION WITH TWO-PHASE OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
We present dimensionality reduction algorithm called Uniform Manifold Ap- proximation with Two-phase Optimization (UMATO) which produces less biased global structures the embedding results and is robust over diverse initialization methods than previous methods such as t-SNE and UMAP. We divide the opti- mization into two phases to alleviate the bias by establishing the global structure early using the representatives of the high-dimensional structures. The phases are 1) global optimization to obtain the overall skeleton of data and 2) local optimiza- tion to identify the regional characteristics of local areas. In our experiments with one synthetic and three real-worke datasets, UMATO outperformed widely-used baseline algorithms, such as PCA, Isomap, t-SNE, UMAP, topological autoen- coders and Anchor t-SNE, in terms of quality metrics and 2D projection results.
INTRODUCTION
We present a novel dimensionality reduction method, Uniform Manifold Approximation with Two- phase Optimization (UMATO) to obtain less biased and robust embedding over diverse initialization methods. One effective way of understanding high-dimensional data in various domains is to reduce its dimensionality and investigate the projection in a lower-dimensional space. The limitation of previous approaches such as (-Stochastic Neighbor Embedding (I-SNE, Maaten & Hinton (2008) ) and Uniform Manifold Approximation and Projection (UMAP, McInnes et (2018)) is that they are susceptible to different initialization methods, generating considerably different embedding results [Section 5.5).
t-SNE adopts Kullback-Leibler (KL) divergence as its loss function. The fundamental limitation of the KI. divergence that the penalty for the points that are distant in the original space being close in the projected space is too little (Appendix B). This results in only the local manifolds being captured, while clusters that are far apart change their relative locations from run to run. Meanwhile, UMAP leverages the cross-entropy loss function, which is known to charge penalty for points that are distant the original space being close in the projection space and for points that are close the original space being distant in the projection space (Appendix B). UMAP considers all points in the optimization at once with diverse sampling techniques (i.e., negative sampling and edge sampling). Although the approximation technique in UMAP optimization makes the computation much faster, this raises another problem that the clusters in the embedding become dispersed as the number of epochs increases (Appendix K), which can lead to misinterpretation. UMAP tried alleviate this by using a fixed number (e.g., 200), which is ad hoc, and by applying a learning rate decay. However, the optimal number of epochs and decay schedule for each initialization method needs to be found in practice.
To solve the aforementioned problems, we avoid using approximation during the optimization pro- cess, which normally would result in greatly increased computational cost. Instead, we first run optimization only with a small number of points that represent the data (i.e., hub points). Finding the optimal projection for a small number of points using cross-entropy function is relatively easy and robust, making the additional techniques employed in UMAP unnecessary. Furthermore, it is less sensitive to the initialization method used (Section 5.5). After capturing the overall skeleton of the high- sigh--imensional structure, we gradually append the rest of the points in subsequent phases. Although the same approximation technique as UMAP is used for these points, embedded the hub points and use them as anchors, the projections become more robust and unbi- ased. The gradual addition of points can in fact be done in single phase; we found additional phases
have already

---

Under review as a conference paper at ICLR 2021
do not result in meaningful improvements in the performance but only in the increased computation time (Section 4.5). Therefore, we used only two phases in UMAP: global optimization to capture the global structures (i.e., the pairwise distances in digh-dimensional space) and local optimization to retain the local structures (i.e., the relationships between neighboring points in a high-dimensional space) of the data.
We compared UMATO with popular dimensionality reduction techniques including PCA, Isomap (Tenenbaum et al. (2000), I-SNE, UMAP, topological autoencoders (Moor al. (2020) and AI-SNE (Fu et al. (2019). We used one synthetic (101-dimensional spheres) and three real- world (MNIST, Fashion MNIST, and Kuzushiji MNIST) datasets and analyzed the projection re- sults with several quality metrics. In conclusion, UMATO demonstrated better performance than the baseline techniques in all datasets in terms of KI,,, with different a values, meaning that reasonably preserved the density of data over diverse length scales. Finally, we presented the 2D projections of each dataset, including the replication of an experiment using the synthetic Spheres dataset introduced by MMoor et al. (2200) where data points locally constitute multiple small balls globally contained larger sphere. Here, we demonstrate that UMATO can better preserve both structures compared to the baseline algorithms (Figure 3).
2 RELATED WORK
Dimensionality reduction. Most previous dimensionality reduction algorithms focused on pre- serving the data's local structures. For example, Maaten & Hinton (2008) proposed t-SNE, focus- ing on the crowding problem with which the previous attempts (Hinton & Roweis (2002: Cook et al. (2007)) have struggled, to visualize high-dimensional data through projection produced by performing stochastic gradient descent on the KL divergence between two density functions in the
original and projection spaces. |Van Der Maaten (2014) accelcrated t-SNE developing variant of the Barnes-Hut algorithm (Barnes & Hut (1966) and reduced the computational complexity from O(N2) into ON log N). After that, grounded in Riemannian geometry and algebraic topology, McInnes et al. (2018) introduced UMAP as an alternative to i-SNE. Leveraging the cross-entropy function its loss function, UMAP reduced the computation time by employing negative sampling from Word2Vec (Mikolov et al.] (2013) and edge sampling from Large Vis (Tang et al. (2015)
Table D). Moreover, they showed that UMAP can generate stable projection results compared to E-NE over repetition.
On the other hand, there also exist algorithms that aim to capture the global structures of data. Isomap (Tenenbaum et al.) (2000)) was proposed to approximate the geodesic distance of high- dimensional data and embed onto the lower dimension. Global t-SNE (Zhou & Sharpee (2018) converted the joint probability distribution, P. in the high-dimensional space from Gaussian to Student's- s-t distribution, and proposed a variant of KL divergence. By adding it with the original loss function of t-SNE, Global (-SNE assigns a relatively large penalty for pair of distant data points high-dimensional space being close in the projection space. Another example is topolog- ical autoencoders (Moor et al. (2020)) deep-learning approach that uses generative model to make the latent space resemble the high-dimensional space by appending a topological loss to the original reconstruction loss of autoencoders. However, they required a huge amount of time for hyperparameter exploration and training for a dataset, and only focused on the global aspect of data. Unlike other techniques that presented a variation of loss functions in a single pipeline, UMATO is novel as it preserves both structures by dividing the optimization into two phases; this makes it outperform the baselines with respect to quality metrics in our experiments.
Hubs, landmarks, and anchors. Many dimensionality reduction techniques have tried to draw sample points to better model the original space: these points are usually called hubs, landmarks, or anchors. Silva & Tenenbaum (2003) proposed Landmark Isomap. landmark version of classical multidimensional scaling (MDS) to alleviate its computation cost. Based on the Landmark Isomap, Yan et al. (2018) tried to retain the topological structures (i.e., homology) of high-dimensional data by approximating the geodesic distances of all data points. However, both techniques have the limitation that landmarks were chosen randomly without considering their importance. UMATO uses a ne-eersst neighbor graph to extract significant hubs that can represent the overall skeleton of dige-iimensional data. The most similar work ours is At- (Fu et al. (2019)) which optimized the anchor points and all other points with two different loss functions. However, since the anchors wander during the optimization and the KI. divergence does not care about distant points, it hardly
2

---

Under review as a conference paper at ICLR 2021
captures the global structure. UMATO separates the optimization process into two phases that the hubs barely moves but guides other points so that the subareas manifest the shape the high- dimensional manifold in the projection. Applying different cross-entropy functions to each phase also helps preserve both structures.
3 UMAP
Since UMATO shares the overall pipeline of UMAP (McInnes et al. (2018)) we briefly introduce UMAP in this section. Although UMAP is grounded sophisticated mathematical foundation, its computation can be simply divided into two steps, graph construction and layout optimization, configuration similar t-SNE. In this section, we succinctly explain the computation an abstract manner. For more details about UMAP, please consult the original paper (Meinnes et al. (2018)).
Graph Construction. UMAP starts by generating weighted k-nearest neighbor graph that repre- sents the distances between data points in the high-dimensional space. Given input dataset X {31..... In ). the number of neighbors UMAP first computes N,. the k-nearest neighbors of with respect to d. Then, UMAP computes two parameters, Pt and o, for each data point x; to identify its local metric space. Pj is a nonzero distance from 2; to its nearest neighbor:
consider and distance metric d X x X [0, oo),
Pj = min (d(zi, (5),,,,)) 0}.
(1)
jEN,
Using binary search, UMAP finds o; that satisfies:
Σ JEM
exp( max(0, (0,(((,))))))) pi)/ (k))
Next, UMAP computes:
Uz = exp(- d(, - pi)/
(3)
the weight of the edge from point T; another point zy. To make it symmetric, UMAP computes
Uij = Ugji + Ualy "yyli" Bipi a single edge with combined weight using U/ji and enj. Note that Vty indicates the similarity between points I; and 2y the original space. Let y; be the projection of x; in a www-dimessional projection space. The similarity between two projected points y; and yj is Wiy (1 + allv: yı ) where and b are positive constants defined by the user. Setting both a and to is identical to using Student's !-distribution to measure the similarity between two points in the projection space in t-SNE (Maaten & Hinton (2008).
Layout Optimization. The goal of layout optimization is to find the y; that minimizes the difference (or loss) between vij and Wij. Unlike (-SNE, UMAP employs the cross entropy:
CUMAP=
(vy (as(ve///w))) (1 -az)) log((11 v11)/(1 ( )))
(4)
between Usy and Why as the loss function. UMAP initializes y; through spectral embedding (Belkin & Niyogi (2002)) and iteratively optimize its position to minimize CUMAP. Given the output weight Wij as 17(1 + ad?)), ), the attractive gradient is:
2abdd 2(b-1)
CUMAR
Vig (1 Vi),
(5)
y1
+ ad?0
and the repulsive gradient is:
CUMAR
2b
(e+ + d1 Rbb (1 v1y)(ss 1z),
(6)
y1
where é is a small value added to prevent division by zero and dy is a Euclidean distance be- tween 3/: and y,. For efficient optimization, UMAP leverages the negative sampling technique from Word2Vec (Mikolov et al. (2013)). After choosing a target point and its negative samples, the posi- tion of the target is updated with the attractive gradient, while the positions of the latter do with
3

---

Under review as a conference paper at ICLR 2021
the repulsive gradient. Moreover, UMAP utilizes edge sampling (Tang al. (2015 2016)) to
celerate and simplify the optimization process (Table I). In other words, UMAP randomly samples edges with a probability proportional to their weights, and subsequently treats the selected ones as binary edges. Considering the previous sampling techniques, the modified objective function is:
M
O=
Σ (ig(lo((we)) (FJ)EE
+ > Ej.-P,00)7 log(1 -0:1)) w.s.))
k=1
Here, Viy and way are the similarities in the high and low-dimensional spaces respectively, M is the number of negative samples and En indicates that js is sampled according to a noisy distribution, P. ()), from Word2Vec (Mikolov et al. (2013).
UMATO
Figure 2 illustrates the computation pipeline of UMATO, which delineates the two-phase optimiza- tion (see Figure 9 for a detailed illustration of the overall pipeline). As a novel approach, we split the optimization into global and local so that it could generate dow-dimensional projection keeping both structures well-maintained. We present the pseudocode of UMATO in [Appendix A] and made the source codes of it publicly available
4.1 POINTS CLASSIFICATION
In the big picture, UMATO follows the pipeline of UMAP. We first find the k-nearest neighbors in the same way as UMAP, by assum- ing the local connectivity constraint, i.e., no single point is isolated and each point is connected to at least a user-defined number of points. After calculating م (Equation I) and a (Equation 2) for each point, we obtain the pairwise similarity for every pair of points. Once the k-nearest neighbor indices are established, we unfold it and check the frequency of each point to sort them into descending order that the index of the popular points come the front.
4dam
Then, we build a k-nearest neighbor graph by repeating the fol- lowing steps until no points remain unconnected: 1) choose the most frequent point as a hub among points that are not already connected, 2) retrieve the k--earestt neighbors of the chosen point (i.e., hub), and the points selected from steps and 2 will become connected component. The gist is that we divide the points into three disjoint sets: hubs, expanded nearest neighbors, and outliers (Figure l). Thanks to the sorted indices, the most popular point in each iteration but not too densely located becomes the hub point. Once the hub points are determined, we recursively seek out their nearest neighbors and again look for the nearest neighbors of those neighbors, until there are no points to be newly appended. other words, we find all connected points that are expanded from the original hub points, which, in turn, is called the expanded nearest neighbors. Any remaining point that is neither a hub point nor part of any expanded nearest neighbors is classified outliers is, similar to the previous approach (Gong et al. (2012), to achieve the robustness of the practical manifold learning algorithm. As the characteristics of these classes differ significantly, take different approach for each class of points to obtain both structures. That is, we run global
Figure 1: Points classifica- tion using Spheres dataset. Each point is classified into hub (red circles), an expanded nearest neighbor (green squares), or an outlier (blue triangles). Best viewed in color.
outlier. The main reason to rule out the
optimization for the hub points (Section 4.2), local optimization for the expanded nearest neighbors (Section 4.3), and no optimization for the outliers (Section 4.4). In the next section we explain each detail.
4.2 GLOBAL OPTIMIZATION
After identifying hub points, run the global optimization to retrieve the skeletal layout of the data. First, we initialize the positions of hub points using PCA, which makes the optimization process

---

Under review as a conference paper at ICLR 2021
(A) Hub points
(8) After optimizing
(C) After embeddling
(D) Fioal
Intrializationn
posittons of baba points
expanded nearest neighbors
Figure 2: An illustration of UMATO pipeline using 10,000 data points (101 dimensions) of the Spheres. (A) UMATO first initializes hub points using PCA, (B) then optimize their positions using the cross entropy function. (C) Next, we embed the expanded nearest neighbors to the projection and optimize their positions using sampling techniques for acceleration. (D) Lastly, we append the outliers and achieve the final projection result. Best viewed in color.
faster and more stable than using random initial positions. Next, we optimize the positions of hub points by minimizing the cross eoosoyy function (Equation 4). Let f(X) = {f 2; 3x)),r; E }} and g(Y)= = {g(u, Yj Ilue y/ E Y) be two adjacency matrices in high- and low-dimensional spaces. If X represents set of points selected as hubs in high-dimensional space, and Yn is a set of corresponding points in the projection, we minimize the cross -utropyCCE(f(a. (X between (Xx,) and g(Y)).
UMAP computes the cross-entropy between all existing points using two sampling techniques, edge sampling and negative sampling, for speed (Table 1}. However, this often ends up capturing only the local properties of data because of the sampling biases and thus it cannot be used for cases that require comprehensive understanding of the data. On the other hand, in its first phase, UMATO only optimizes for rep- resentatives (i.e., the hub points) of data, which takes much less time but can still approximate the manifold effectively.
Table 1: The runtime for each algorithm using MNIST dataset. UMAP and UMATO take much less time than MulticoreT- SNE (Ulyanov (2016) when tested on a Linux server with 40-core Intel Xeon Silver 4210 CPUs. The runtimes are averaged over 10 runs. Isomap [Tenebbuum et al. 2000 took more than 3 hours to get the embedding result.
4.3 LOCAL OPTIMIZATION
In the second phase, UMATO embeds the expanded nearest neighbors to the projection that is computed using only the hub points from the first phase. For each point in the expanded nearest neighbors, we retrieve its nearest m (e.g.. 10) hubs in the original high-dimensional space and set its initial position in the projection the average positions of the hubs in the projection with small random perturbations. We follow a similar optimization process as UMAP in the local optimization with small differences. As explained in /Sectiion 3| UMAP first constructs the graph structure; we perform the same task but only with the hubs and expanded nearest neighbors. While doing this, since some points are excluded as outliers, we need update the k-nearest neigh- bor indices. This is fast because we recycle the already-built k-nearest neighbor indices by updating the outliers to the new nearest neighbor.
Algorithm
Runtime (s)
Isomap I-SNE
hours >
374.85 + 11.38
UMAP
26.10 + 3.97
UMATO
73.32 + 8.39
Once we compute the similarity between points (Equation 3), to optimize the positions of points, similar UMAP, we use the cross-entropy loss function with edge sampling and negative sampling (Equation 7). Here, we try to avoid moving the hubs as much as possible since they have already formed the global structure. Thus, we only sample a point p among the expanded nearest neigh- bors as one end of an edge, while the point q at the other end of the edge can be chosen from all points except outliers. UMAP implementation, when pulls in p. p also drags q to facilitate the optimization (Equation 5). When updating the position of q, only give penalty to this (e.g.. 0.1), if q is a hub point, not letting its position excessively be affected by p. In addition, because the repulsive force can disperse the local attachment. making the point veer off for each epoch and even- tually destroying the well-shaped global layout, we multiply a penalty (c.g., 0.1) when calculating the repulsive gradient (Equaation 6) for the points selected negative samples.
5

---

Under review as a conference paper at ICLR 2021
4.4 OUTLIERS ARRANGEMENT
Since the isolated points, which we call outliers, mostly have the same distance to all the other data points in high-dimensional space, due to the curse of dimensionality, they both sabotage the global structure we have already made and try to mingle with all other points, thus distorting the overall projection. We do not optimize these points but instead simply append them using the already- projected points (e.g., hubs expanded nearest neighbors). that belong to each outlier's ' connected component of the nearest neighbor graph. That is, if v; E Cn where 2; is the target outlier and CN is the connected component to which æ; belongs, we find zj E Cn that has already been projected space using the
and is closest to T₁- We arrange y which corresponds to T; in low-dimension position of yy in the same component offset by a random noise. In this way, we can benefit from the comprchensive composition of the projection that we have already optimized when arranging the outliers. We can ensure that all outliers can find a point as its neighbor since we picked hubs from each connected component of the nearest neighbor graph and thus at least one point is already located and has an optimized position [Section 4.2
4.5 MULTI-PHASE OPTIMIZATION
The optimization of UMATO can be easily expanded to multiple phases (e.g., three or more phases). Since we have recursive procedure to expand the nearest neighbors, we can insert the optimization process each time we expand the neighbors to create multi-phase algorithm. However, our experi- ment with three- and four-phase optimization with the Fashion MNIST dataset showed that there no big difference between two-phase optimization and that with more than two phases. [Appendix C contains the quantitative and qualitative results of the experiment for multi-phase optimization.
EXPERIMENTS
We conducted experiments to evaluate UMATO's ability to capture the global and local structures of high-dimensional data. We compared UMATO with six baseline algorithms, PCA, Isomap, I-SNE, UMAP, topological autoencoders, and At-SNE in terms of global (i.e., DTM and KL,) and local (i.e., trustworthiness, continuity, and MRREs) quality metries.
5.1 DATASETS
We used four datasets for the experiments: Spheres, MNIST LeCun & Cortes (2100), Fashion MNIST (Xiao al. (2177), and Kuzushiji MNIST (Clanuwat et al. (2018)). Spheres synthetic dataset that has 10,000 rows of 101 dimensions. It has high-dimensional structure in which ten small spheres are contained in a larger sphere. Specifically, the dataset's first 5,000 rows are the points sampled from a sphere of radius 25 and 500 points are sampled for each of the ten smaller spheres of radius shifted to a random direction from the origin. This dataset is the one used for the original experiment with topological autoencoders (Moor et al. (2020)). Other datasets images of digits, fashion items, and Japanese characters, each of which consists of 60,000 784-dimensional (28 28) images from 10 classes.
5.2 EXPERIMENTAL SETTING
Evaluation Metrics. To assess how well projections preserve the global structures of high- dimensional data, we computed the density estimates (Chazal et al. (201 2017)) the so-called Distance To a Measure (DTM), between the original data and the projections. Moor et al. (2020) adopted the Kullback-Leible evaluate the global structure preservation. To follow the original experimental setup by Moor et al. (200)), we found the projections with the lowest KL-0.1 from all algorithms by adjusting their hy- perparameters. Next, to evaluate the local structure preservation of projections, relative rank errors (MRREs, Lee & Verleysen (2007)). trustworthiness, and continuity (Venna & Kaski (200T)). All of these local quality metries estimate how well the nearest neighbors in one space (e.g., high- or low-dimensional space) are preserved in the other space. For more information on the quality metrics, we refer readers to Apppendix E
divergence between density estimates with different scales (KL,) to
used the mean
Baselines. We set the most widely used dimensionality reduction techniques as our base- lines, including PCA, Isomap (Tenenbaum al. (2000)), 1-SNE (Maaten & Hinton (008)).

---

Under review as a conference paper at ICLR 2021
Table 2: Quantitative results of UMATO and six baseline algorithms. The hyperparameters of the algorithms are chosen to minimize LL The best one is in bold and underlined, and the runner-up is in bold. Only first four digits are shown for conciseness.
Global quality metrics
Local quality metrics
Dataset
Method
DTM
Kl.o.01
Kl.0.1
KI.1
Cont
Trust
MRREx
MRREg
PCA
0.9950
0.7568
0.6525
0.0153
0.7983
0.6088
0.7985
0.6078
Isomap
0.7784
0.4492
0.4267
0.0095
0.9041
0.6266
0.9039
0.6268
1-SNE
0,9116
0.6070
0.5365
0.0128
0.8903
0.7073
0.9032
0.7261
Spheres
UMAP
0,9209
0.6100
0.5383
0.0134
0.8760
0.6499
0.8805
0.6494
TopoAE
0.6890
0.2063
0.3340
0.0076
0.8317
0.6339
0.8317
0.6326
At-SNE
0,9448
0.6584
0,5712
0,0138
0.8721
0.6433
0.8768
0,6424
UMATO
0.3888
0.1341
0.1434
0.0014
0.7884
0.6558
0.7887
0.6557
PCA
0.2315
0.6929
0.0455
0.0006
0.9843
0.9117
0.9853
0.9115
Isomap
0,2272
0.6668
0.0446
0,0010
0.9865
0.9195
0.9872
0.9196
1-SNE
0.2768
0,8079
0.0663
0.0017
0.9899
0,9949
0.9919
0,9955
Fashion
MNIST
UMAP
0,2755
0.8396
0.0641
0.0016
0.9950
0.9584
0.9955
0,9584
TopoAE
0.2329
0.7301
0.0446
0.0008
0.9908
0.9591
0.9913
0.9590
At-SNE
0.2973
0.8389
0.0702
0.0017
0.9826
0.9847
0.9849
0.9848
UMATO
0.2035
0.6852
0.0342
0.0008
0.9911
0.9500
0.9919
0,9502
PCA
0.4104
1.4981
0.1349
0.0014
0.9573
0.7340
0.9605
0.7342
Isomap
0.3358
1.0361
0.0857
0.0012
0.9743
0.7527
0.976
0.7528
t-SNE
0.4263
1,4964
0.1523
0.0024
0.9833
0.9954
0.9869
0.9963
MNIST
UMAP
0,4172
1.5734
0.1430
0.0026
0.9891
0.9547
0.9907
0.9547
TopoAE
0.3686
1.3818
0.1088
0.0011
0.9716
0.9429
0.9732
0.9429
At-SNE
0.4328
1 1.5623
0.12
0.0018
0.9768
0.9765
0.9830
0.9777
UMATO
0.3525
1.2785
0.1017
0.0014
0.9792
0.8421
0.9813
0.8422
PCA
0.4215
0.1710
0.1317
0.0014
0.9380
0.7213
0.9420
0.7211
Isomap
0.3458
0.2171
0.0906
0,0012
0.9573
0.7638
0.9589
0.7635
*-SNE
0.4254
0.0483
0.1369
0.0025
0.9843
0.9688
0.9871
0.9693
Kuzushiji
UMAP
0.3873
0.0417
0.1148
0.0026
0.9893
0.9563
0.9908
0,9564
MNIST
TopoAE
0.3730
0.1495
0.20
0.0011
0.9755
0.9442
0.9768
0,9440
AI-SNE
0.3505
0.0807
0.0978
0.0013
0.9786
0.9671
0.9824
0.9676
UMATO
0.3231
0.1365
0.0815
0.0016
0.9865
0.8888
0.9881
0.8895
UMAP (MeInnes al. 2018)) ). and At-SNE (Fu et al. (2019)). In the case of t-SNE, we lever- aged Multicore i-SNE (Ulanov 2016)) for fast computation. To initialize the points" position, we
used PCA for t-SNE, following the recommendation in the previous work (Linderman et al. (209)). and spectral embedding for UMAP which was set to default. In addition, we compared with topo- logical autoencoders (Moor et al. (2020)) that were developed to capture the global properties of the data using a deep learning- generative model. Following the convention of visualization in dimensionality reduction, determined our result projected onto 2D space. We tuned the hyper- parameters of each technique to minimize the kLo. Appendix Ffurhhrr describes the details of the hyperparameters settings.
5.3 QUANTITATIVE RESULTS
Table 2 displays the experiment results. In most cases, UMATO was the only method that has shown performance both in the global and local quality metrics in most datasets. For local metrics, I-SNE, AI-SNE, and UMAP generally had the upper-hand, but UMATO showed comparable MRREx and continuity in Spheres, Fashion MNIST, and Kuzushiji MNIST datasets. Meanwhile, Isomap and topological autoencoders were mostly good global quality metrics, although UMATO had the lowest (best) KLo.1 and DTM except for the MNIST dataset.
5.4 QUALITATIVE RESULTS
Among the five algorithms, only UMATO could preserve both the global and local structure of the Spheres dataset. If we look at the figure made by UMATO, the outer sphere encircles the inner spheres in a circular form, which is the most intuitive to understand the relationship among different classes and the local linkage in detail. In the results from Isomap, (-SNE, UMAP, and AI-SNE,
7

---

Under review as a conference paper at ICLR 2021
Spberes
DCR
ISOMAR
YIDE U0AA7 TORCAE ATRSE
LEGATOO
Figure 3: 2D projections produced by UMATO and six baseline algorithms. t-SNE, At-SNE, and UMAP showed as if the points from a surrounding sphere were attached to inner spheres, not reflecting the data's global structures. PCA, Isomap and topological autoencoders attempted to pre- serve the global structures, but failed to manifest the complicated hierarchical structures. UMATO was the only algorithm capture both the global and local structures among all different sphere classes; this is best viewed in color.
the points representing the surrounding giant sphere mix with those representing the other small inner spheres, thus failing to capture the nested relationships among different classes. Meanwhile, topological autoencoders
able realize the global relationship between classes in incomplete manner, the points for the outer sphere are too spread out, thus losing the local characteristics of the class. From this result, we can acknowledge how UMATO can work with high-dimensional data effectively to reveal both global and local structures. 2D visualization results on other datasets (MNIST, Fashion MNIST, Kuzushiji MNIST) can be found in Appendix additional experiment the mouse neocortex dataset (Tasic al. (2018) in Appendix N which shows the relationship between classes much better than the baseline algorithms like I-SNE and UMAP.
Lastly, we report an
5.5 PROJECTION ROBUSTNESS OVER DIVERSE INITIALIZATION METHODS
We experimented with the robustness of each dimensionality reduction technique with different initialization methods such as PCA, spectral embedding, random position, and class-wise separation. In class-wise separation, we initialized each class with non-overlapping random position in 2- dimensional space, adding random Gaussian noise. In our results, UMATO embeddings were almost the same on the real-world datasets, while the UMAP and t-SNE results relied highly upon the initialization method. We report this Table 3 with quantitative comparison using Procrustes distance. Specifically, given two datasets X Ø1, 22. , Fn and Y {31 V2..... ... vn) where of corresponds to 2,, the Procrustes distance defined as
dp(X,Y)=
(a vl)
For all cases, we ran optimal translation, uniform scaling, and rotation to minimize the Procrustes distance between the two distributions. the case of the Spheres dataset, as defined in in/Apendiix Gj the clusters were equidistant from each other. The embedding results have to be different due to the limitation of the 2-dimensional space since there is no way to express this relationship. However, as we report in Figuree 4| the global and local structures of the Spheres data are manifested with UMATO with all different initialization methods.
Table 3: The average value of normalized Procrustes distance between diverse dimensionality reduction techniques over four datasets. In all real-world datasets, UMATO has shown the most robust embedding results different initialization methods. Although the UMATO results in the highest normalized Procrustes distance the Spheres dataset, the embedding results look quite similar Figure 4b. The winner in bold.
Sample (%)
Spheres
MNIST
FMNIST
KMNIST
t-SNE
0.7878
0.8665
0.8284
0.8668
UMAP
0.7726
0.7767
0.7793
0.8213
UMATO
0.9504
0.4808
0.0120
0.2037
8

---

Under review as a conference paper at ICLR 2021
class-wise separation
PCA
Random
Spectral embbedding
UMATO results on the Spheres dataset using different initialization methods. Al- though the average value the normalized Procrustes distance of UMATO results is higher than the baselines because of the equidistant clusters of inner spheres, both global and local structures are well-captured with all different initialization methods. Best viewed in color.
Figure 4:
CONCLUSION
We present two-phase dimensionality reduction algorithm called UMATO that can effectively preserve the global and local properties of high-dimensional data. In our experiments with diverse datasets, we have proven that UMATO can outperform previous widely used baselines (e.g., (-SNE and UMAP) both quantitatively and qualitatively. As future work, plan to accelerate UMATO, as in previous attempts with other dimensionality reduction techniques (Pezzotti et al. (2019); Nolet heterogeneous system (e.g., GPU) for speedups.
lt al. (2020), by implementing
REFERENCES
Josh Barnes and Piet Hut. hicrarchical o (n log n) force-calculation algorithm. nature, 324(6096): 449, 1986.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in neural information processing systems, pp. 585-5915 2002.
Tess Brodie, Elena Brenna, and Federica Sallusto. Omip-018: Chemokine receptor expression on human helper cells. Cytometry Part A, 83(6):530-533 2013.
Frédéric Chazal, David Cohen-Steiner, and Quentin Mérigot. Geometric inference for probability measures. Foundations of Computational Mathematics, 11(6):733-751, 2011.
Frédéric Chazal, Brittany Fasy, Fabrizio Lecci, Bertrand Michel, Alessandro Rinaldo, Alessandro Rinaldo, and Larry Wasserman. Robust topological inference: Distance measure and kernel distance. The Journal of Machine Learning Research, 18(1):5845-588 2017.
Tarin Clanuwat, Mikel Brizar,rizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical japanese literature, 2018.
James Cook, Ilya Sutskever, Andriy Mnih, and Geoffrey Hinton. Visualizing similarity data with mixture of maps. In Artificial Intelligence and Stutistics, pp. 67-74, 2007.
Cong Fu, Yonghui Zhang, Deng Cai, and Xiang Ren. Atsne: Efficient robust visualization on gpu through hierarchical optimization. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 176-186, 2019.
Dian Gong, Xuemei Zhao, and Gerard Medioni. Robust multiple manifolds structure learning. In Proceedings of the 29th International Conference on Machine Learning, pp. 25-32, 2012.
Carmen Bravo González-Blan Blas, Liesbeth Minnoye, Dafni Papasokrati, Sara Aibar, Gert Hulselmans, Valerie Christiaens, Kristofer Davie, Jasper Wouters, and Stein Aerts. cistopic: cis- cis-regulatory topic modeling single-cell atac-seq data. Nature methods, 16(5):397-400, 2019.

---

Under review as a conference paper at ICLR 2021
Antonio Gracia, Santiago González, Victor Robles, and Ernestina Menasalvas. A methodology to compare dimensionality reduction algorithms in terms of loss of quality. Information Sciences, 270:1-27, 2014.
Tim Head, MechCoder, Gilles Louppe, laroslav Shcherbatyi, fcharras, Zé Vinícius, emmalone, Christopher Schröder, nel215, Nuno Campos, Todd Young, Stefano Cereda, Thomas Fan, rene rex, Kejia (KJ) Shi, Justus Schwabedal, carlosdanielcsantos, Hvass-Labs, Mikhail Pak, So- ManyUsermamesTaken, Fred Callaway, Loic Estève, Lilian Besson, Mehdi Cherti, Karlson Pfannschmidt, Fabian Linzberger, Christophe Cauet, Anna Gut, Andreas Mueller, and Alexan- der Fabisch. sülkit-ppiimie/sssiiittopiiiiiii v0.5.2, March 2018. URL httttt://ddod
zenodo. 1207017
Geoffrey E Hinton and Sam Roweis. Stochastic neighbor embedding. Advances in neural informa- fion processing systems, 15:857-864, 2002.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http::/ttaaa lecun. wttp://b////cctt//////c/m////
John A Lee and Michel Verleysen. Nonlinear dimensionality reduction. Springer Science & Busi-
ness Media, 2007.
John A Lee and Michel Verleysen. Quality assessment of dimensionality reduction: Rank-based criteria. Neurocomputing, 72(7-99::431-1443, 2009.
George C Linderman, Manas Rachh, Jeremy Hoskins, Stefan Steinerberger, and Yuval Kluger. Fast interpolation-buseed t-sne for improved visualization of single-cell ma-seq data. Nature meth- ods, 16(3):243-245, 2019.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(No))25579-265, 2008.
Leland Mclnnes, John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:180.003426, 2018.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations of words and phrases and their compositionality. In Advances neural information pro- cessing systems, pp. 31 3111-1331 111111119, 2013.
Michael Moor, Max Hor,, Bastian Rieck, and Karsten Borgwardt. Topological autoencoders. In Proceedings of the 37th International Conference Machine Learning (ICML), Proceedings of Machine Learning Research. PMLR, 2020.
Corey J Nolet, Victor Lafargue, Edward Raff, Thejaswi Nanditale, Tim Oates, John Zedlewski, and Joshua Patterson. Bringing umap closer to the speed of light with gpu acceleration. arXiv preprint arXiv:2008.00 0033: 2020.
Nicola Pezzotti, Julian Thijssen, Alexander Mordvintsev, Thomas Höllt, Baldur Van Lew, Boudewijn PF Lelieveldt, Elmar Eisemann, and Anna Vilanova. Gpgpu linear complexity sne optimization. IEEE transactions visualization and computer graphics, 1771)11172-1888 2019.
Vin D Silva and Joshua B Tenenbaum. Global versus local methods in nonlinear dimensionality reduction. In Advances in neural information processing systems, pp. 721-728 2003.
Josef Spidlen, Karin Breuer, Chad Rosenberg, Nikesh Kotecha, and Ryan Brinkman. Flowreposi- tory: A resource of annotated flow cytometry datasets associated with peer-reviewed publications. Cytometry Purt A, 8777)1777733, 2012.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: information network embedding. Proceedings of the 24th international conference on world wide web, pp. 1067-1077, 2015.
Large-scale
10

---

Under review as a conference paper at ICLR 2021
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, 2016.
Bosiljka Tasic, Zizhen Yao, Lucas T Graybuck, Kimberly A Smith, Thue Nghi Nguyen, Darren Bertagnolli, Jeff Goldy, Emma Garren, Michael N Economo, Sarada Viswanathan, et al. Shared and distinet transcriptomic cell types across neocortical areas. Nature, 563(7729):72-778 2018.
Joshua Tenenbaum, Vin De Silva, and John C Langford. global geometric framework for nonlinear dimensionality reduction. science, 29065500);2319-23333.2222 2000.
Dmitry Ulyanov.
Multicore-tsne.
httt:s//ggttabb...ccmm//mttttttp
Multicore-TSNE 2016.
Koen Van den Berge, Hector Roux De Bezieux, Kelly Street, Wouter Saelens, Robrecht Cannoodt,
Yvan Sacys, Sandrine Dudoit, and Lieven Clement. Trajectory-based differential expression anal- ysis for single-cell sequencing data. Nature communications, 11(1):1-13, 2020.
Laurens Van Der Maaten. Accelerating t-sne using tree-based algorithms. The Journal of Machine Learning Research, 15(1):3221-3244 2014.
Jarkko Venna and Samuel Kaski. Neighborhood preservation in nonlinear projection methods: An experimental study. In International Conference Artificial Neural Networks, pp. 485-491. Springer, 2001.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms, 2017.
Lin Yan, Yaodong Zhao, Paul Rosen, Carlos Scheidegger, and Bei Wang. cemology-preserving dimensionality reduction via manifold landmarking and tearing. In Visualization in Data Science (VDS), 2018. httsstps::// /ttppiss///a.vvo.oo/oo org. wttp/bg////...o...////// 08460
Yuansheng Zhou and Tatyana O Sharpee. Using global t-sne to preserve inter-cluster data structure. bioRxiv, 2018. doi: 10.1101/33161.

---

Under review as a conference paper at ICLR 2021
A UMATO ALGORITHM PSEUDOCODE
The pseudocode of UMATO is as below:
Algorithm Uniform Manifold Approximation with Two-phase Optimization
I: procedure UMATO(X, Ax. d, min dist, nu., Eg. et)
Input: fiigh-dimensional data X, number of nearest neighbors k. projection dimension d. minimum distance in projection result min_dist, number of hub points na. epochs for global and local optimization eg. et
Output: Low-dimeensioall projection Y
Compute k-nearest neighbors of
3:
Obtain sorted list using indices' frequency of k-nearest neighbors
4: Build k-ncarest neighbor graph structure
5:
Classify points into hubs, expanded nearest neighbors. and outliers
Optimize (E(((xx)ll9(1)
to preserve global configuration (Equation
7:
Initialize expanded nearest neighbors using hub locations
8:
Update k-ncarest neighbors & compute weights (Equation 3)
9:
Optimize CE (Y)) )) preserve local configuration (Equation
10:
Position outliers
return
12:
end procedure
B THE MEANING OF USING DIFFERENT Loss FUNCTIONS IN DIMENSIONALITY REDUCTION
Following the notations from above, set the similarity between points in high-dimensional space H; and z; as Vay and the low-dimensional space y/: and y/ as way- Then we can write the KL divergence and cross entropy loss function as:
KL
Σ Vig log(vis/wig) (
(9)
CE CE= = Σvs CE=Ewy vig log(tis/wi))
= vit) 1og((111g)/(t wiy)).
(10)
Table 4: Analysis of the KL divergence and cross-entropy loss function for imposing penalties when updating the positions of points in low-dimensional space. (Upper table) The KL diver- gence and the first term of the cross-entropy function impose big penalty when wij is small but uyj large. (Lower table) contrast, the second term of cross-entropy function imposes big penalty when My is small but wa is large.
Low
Large Mis
Small Wis
Large the
a. Small penalty
b. Big penalty (preserves local structures)
High
Small Usj
Small penalty (ignores global structures)
d. Small penalty
Low d
Large Wiy
Small way
Large Usy
Small penalty
f. Small penalty (ignores local structures)
High
Small Bay
g. Big penalty (preserves global structures)
h. Small penalty
If we use the same probability distributions, Vi and waj. the KL divergence and the first term of cross-entropy are exactly the same. If viy and Wij are both large (Table 4 a.) or both small (Table 4 d.). this means that the relationship between points in digensiinns space is well-retained in the projection. Thus, the positions of points in the now-dimensional space do not have to move. As Vi and wi similar, log(v.//ug /w:;) becomes zero, producing small cost in the end.
12

---

Under review as a conference paper at ICLR 2021
However, need to modify the position of Wij if there exists gap between By and Wij- The KL divergence imposes a big penalty when Bij is large but Wij is small (Table 4 b.). That is, the neighboring points in nigh-dimensional space divergence imposes a high penalty to move the point (wiy) into the right position. Thus, we can understand why 1-SNE is able capture the local characteristics of high-dimensional space, but not the global ones. However, the second term of cross-entropy imposes big penalty when Vi is small but Wij is large (Table 4 g.). Therefore, it moves points that are close together in the high- dimensional space but far apart in the projection.
not captured well in the projection, the KL
C MULTI-PHASE OPTIMIZATION
We report the result of multi-phase optimization (e.g., three and four-phase) using the Fashion MNIST dataset both quantitatively (Table 5) and qualitatively (Figure 5). As in Figure 5 we were unable to find any significant differences between the 2D projections, although some outliers were located in different places. Moreover, the quality metrics were almost the same for all three results. The original UMATO other quality metrics. In addition, the gap in metrics between UMATO and the multi-phase optimiza- tions indicated a trivial difference. Thus, we concluded that developing multi-phase optimization for UMATO does not bring about any notable improvement in the projection result.
the winner in DTM, KL..1, KL.,, continuity, and MRREz but came last in
Table 5: Quantitative evaluation of UMATO and UMATO with multi-phase optimizations. Although the optimization process of UMATO can be simply expandable for multiple phases, no apparent distinctions are found in the the results with different numbers of optimization phases. The winner is in bold.
Dataset
Method
DTM
KT.0.01
KL
KT.1
Cont
Trust
MRREx
MRRE,
UMATO
0.2035
0.6852
0.0342
0.0008
0.9911
0.9500
0.9919
0,9502
Fashion MNIST
3 Phases
0.2058
0.6546
0.0343
0.0008
0.9900
0.9556
0,9909
0,9561
4-Phases
0.2095
0.6533
0.0359
0.0008
0.9895
0.9532
0.9904
0.9536
UMATO
UMATO 3- --PASSES
UMATO 4- PHASES
Figure 5: 2D projections the Fashion MNIST dataset using UMATO and UMATO with multi-phase optimizations. Although there small difference such as the locations of outliers, we observed that the projection results were quite similar to each other.
D PROJECTION STABILITY
Table 6 denotes the results of our experiment on the projection stability of UMATO and other mensionality reduction techniques. When the data size grows, we want to sample portion of it to speed up the visualization. However, the concern is whether the projection run with the sampled indices is consistent with the part of the projection result with indices selected from the full dataset. the algorithm can generate stable and consistent results, the two projections should contain the least bias possible. To compute the projection stability of dimensionality reduction techniques,
13

---

Under review as a conference paper at ICLR 2021
used the normalized Procrustes distance (Equation 8) measure the distance between two compa- rable distributions. To replicate the experiment by McInnes et al. (2018). we used the same Flow Cytometry dataset (Spidlen et al. (2012); Brodie et al. (2013)) and ran optimal translation, uniform scaling, and rotation to minimize the Procrustes distance between the two distributions. As we can in Table 6, UMATO outperformed I-SNE and A/-SNE for all sub-sample sizes. Moreover, al- though UMAP is known as stable among existing algorithms, UMATO showed even better (lower) Procrustes distance except for one sub-sample size (60%). From this result, we can acknowledge that UMATO can generate the more stable and consistent results regardless of sub- sub-sample size than many other dimensionality reduction techniques.
Table 6: The normalized Procrustes distance between two projection results by the percentage of sub-samples. From four dimensionality reduction techniques, we measured the normalized Pro- crustes distance to check the projection stability using the Flow Cytometry dataset. The winner is in bold.
Sample (%)
2
5
10
20
30
50
60
80
100
f-SNE
0.9835
0.9944
0,9544
0,9736
0,9824
0,9924
0.9959
0.9819
0,9944
0.9765
UMAP
0.4002
0.3319
0.2341
0.1324
0.1327
0.1577
0.1109
0.0713
0.0951
0.0597
At-SNE
0.8958
0.9510
0.7593
0.7980
0,9062
0,9376
0.9999
0.9460
0,9599
0,9999
UMATO
0.3153
0.1528
0.1206
0.0988
0.0520
0.1411
0.0526
0.1732
0.0529
0.0535
E QUALITY METRICS
As UMATO presents a dimensionality reduction technique that can capture both the global and local structures of high- dimensional data, we used several quality metrics to evaluate each aspect respectively. We have referred to some review papers (Gracia et al. [2014);[ee & Verleysen (2009)
for the best use and implementation. Among many quality metrics, we leveraged 1) Distance To Measure (DTM. Chazal et al. (2011; 2017)) ). 2) KL divergence between two density functions, 3) trustworthiness and continuity [Venna & Kaski (200I)). and 4) mean relative rank errors (MRREs, Lee & Verleysen 20077). The first two metrics are used to test the preservation of global structures and the last two metrics are suggested for the preservation of the local structures.
Distance To Measure considers the dispersion of high- and now-dimensional data, where it is defined for a given point as fø (x) := Evex cxp (
By summing up the element- wise absolute values between two distributions, Σzex, fo (x) - f² (z) where is the point in high-dimensional space X and the is the corresponding projected point in low-dimensional space Z. we can examines the similarity of two datasets. In our experiments, we used the Euclidean distance and the values were normalized between O and 1. The a R which represents the length scale parameter, was set to 0.1. Moor et al.] (2020) proposed the KL divergence of two probability distributions, KI., == KL_(J² I[]6 ) variation of DTTM. Changing a normalizing factor of the distribution, the authors investigated if the algorithms can preserve the global structure of the high-dimensional data, Following the same notion as the experiment in the paper (Moor al. 22020), we used three a values, 1.0, 0.1, and 0.01, to test whether each algorithm can capture the global aspect with respect to diverse density estimates.
fx)(x)
Trustworthiness and continuity measure how much the nearest neighbors are preserved in space (i.e.. high- or low-dimensional space) compared to the other space by analyzing the ranks of k- nearest neighbors in both spaces. The difference between trustworthiness and continuity comes from which space is held as the base space. Specifically, we first need to find the k-nearest neighbors in both high- and low-dimensional space. Then, we compute the trustworthiness by checking whether the ranks of nearest neighbors in low-dimensional space resemble those of high-dimensional space. If so, we can achieve a high score in trustworthiness. Meanwhile, we achieve a high score in conti- nuity if the ranks of nearest neighbors in high- nigh-dimensional space resemble those of dindesenniioall space. MRREs take similar approach to trustworthiness and continuity it calculates and com- pares the ranks of the k-nearest neighbors in both spaces, but the normalizing factor is slightly different. Originally, it was better if MRREs had lower values. However, for the ease of comparing
14

---

Under review as a conference paper at ICLR 2021
local quality metrics, defined it MRREs MRREs, higher MRREs mean that they have better retained the k-nearest neighbors like trustworthiness and continuity.
F HYPERPARAMETER SETTING
As explained in Section 5.2 we generated projections for each dimensionality reduction algorithm that had the lowest kl.0.1 measure. To tune each algorithm's hyperparameters,, employed the grid search for 1-SNE, UMAP, and At-SNE. For I-SNE and Ad-SNE, we changed the perplexity from to 50 with an interval of 5, and the learning rate from 0.1 1.0 with log-uniform scale. In the case of UMAP, we changed the number of nearest neighbors from 5 to 50 with an interval of 5, and the minimum distance between points in the projection from 0.1 1.0 with an interval of 0.1. We used the Python library scikit-opimizee (Head et al. (2018)) to find the best hyperparameters for topological autoencoders. UMATO has several hyperparameters such as the number of hub points, the number of epochs, and the learning rate for global and local optimization. In our experiments, we configured everything except the number hub points to the same setting for UMATO. We used 200 hub points for the Spheres dataset and had 300 hubs for others. We used fewer hub points for the Spheres since it has only 10,000 data points in total, while the other datasets have 60,000 data points. We set the number of epochs to 100 for global optimization and to 50 for local optimization. Lastly, the global learning rate was set to 0.0065, and the local learning rate was set to 0.01.
G SYNTHETIC SPHERES DATASET
We leveraged the same Spheres dataset that Moor et al. (2020) used in their experiments of topo- logical antoencoders. The Spheres dataset contains eleven high-dimensional spheres which reside in 101-dimensional space. We first generated ten spheres of radius of 5, and shifted each sphere by adding the same Gaussian noise random direction. For this aim, we created d-dimensional Gaussian vectors X (O, [(10/ dd)), where 101. As embed an interesting geometrical structure to the dataset, the ten spheres of relatively small radii of 5 were enclosed by another larger sphere of radius of 25.
H MORE EXPERIMENTS ON SYNTHETIC DATASETS
scuree
Swissroll
PCA
150MAR
TSNE
UNKP
UNAAZO
Figure 6: 2D projections produced by UMATO and four baseline algorithms. 3-dimensional S-curve and Swiss roll datasets are used for five different algorithms. While PCA and UMATO can capture both the global and local structures of original datasets, other algorithms such Isomap, i-SNE, and UMAP can only preserve the local manifolds of original datasets.
We leveraged the 3-dimensional S-curve and Swiss roll datasets to test whether UMATO can pre- serve both the global and local structures of original datasets. As the visualization shows (Fiuure 6).
15

---

Under review as a conference paper at ICLR 2021
only PCA and UMATO were able to capture the global and local structures of original datasets. Isomap, t-SNE and UMAP could capture the local manifolds of original datasets, but high-level manifolds of the original datasets were not reflected to the embedding.
I LOCAL QUALITY METRICS WITH DIFFERENT VALUES OF HYPERPARAMETER
We report the result of local quality metrics with diverse hyperparameters (Table 7.. We changed the number of nearest neighbors (k) from 5 to 15 with an interval of 5. As we have already reported when the k = 5 (Table 2. below are the cases where k = 10, 15. As we can check from the result, while the values fluctuate little bit, the ranks mostly robust over diverse & values.
Table 7: Local quality metries of UMATO and the baseline algorithms. Although the values are changing a little bit depending on the number of nearest neighbors, when comparing the result of k 10 and i = 15, the ranks barely change. The winner is in bold and underlined, and the runner-up in bold.
Dalavet
Method
Cout
Trust
MRREx
MRREa
Dataset
Method
Cunt
Trust
MRREx
MRRE2
PCA
0.7965
0.6111
0.7976
0.6089
PCA
0.9519
0.7341
0.9574
0.7342
Isomap
0.8847
0.6268
0.8953
0.6267
Isomap
0.9713
0.7531
0.9743
0.7530
Spheres
UMAP
1-SNE
0.8752
0.8688
0.6508
0.6803
0,8944
0.8764
0.6497
0,7082
MNIST À = 10
UMAP
(-SNE
0.9779
0.9858
0,9543
0,9930
0.9838
0.9889
0.9951
0.9545
& 10
TopoAE
0.8309
0.6354
0,8312
0.6335
TopoAF
0,9686
0,9429
0.9429
Ar-SNE
0.8645
0.6453
0.8724
0.6434
At-SNE
0.9688
0,9734
0.9782
0.9761
UMATO
0.7875
0.6564
0.7881
0.6559
UMATO
0.9753
0.8422
0.9792
0.8422
PCA
0.7952
0.6120
0.7969
0.6094
PCA
0.9481
0.7341
0,9555
0.7342
Isomap
0.8774
0.6282
0.8914
0.6271
Isemap
0.9692
0,7529
0.9732
0.7529
Spheres
L-SNE
0.8668
0.6723
0.8891
0.7021
MNIST A 15
I-SNE
0.9746
0.9908
0.9819
0,9940
& 15
UMAP
0.8639
0.6534
0,8737
0.6506
UMAP
0,9834
0,9542
0.9877
0.9545
TopoAE
0.8304
0.6364
0.8309
0.6339
TopoAE
0.9666
0,9429
0.9705
0 0.9429
AI-SNE
0.8603
0.6461
0.8699
0.6438
AL-SNE
0.9642
0,9707
0.9755
0.9749
UMATO
0.7875
0.6568
0.7879
0.6560
UMATO
0.9728
0.8417
0.9778
0.8420
0.9827
0.9120
0.9843
0.9116
0,9313
0.7218
0.7214
Isomap
0.9854
0.9196
0.9865
0.9196
Isomap
0.9546
0.7639
0.9574
0.7636
Fashion
1-SNE
0,9873
0.9936
0.9903
0.9948
Kuzushiji
t-SNE
0.9794
0.9677
0.9844
0.9687
MNIST
UMAP
0.9941
0.9586
0.9950
0.9585
MNIST k = 10
UMAP
0.9861
0,9556
0.9891
0.9561
10
TopoAE
0,9898
0.9591
0,9908
0.9590
TopoAE
0.9732
0,9442
0.9755
0,9441
Ac-NNE
0.9792
0.9843
0.9829
0.9846
AL-SNE
0.9723
0,9689
0.9789
0.9670
UMATO
0.9897
0.9498
0.9911
0.9500
UMATO
0.9836
0.8880
0.9864
0.8890
PCA
0,9815
0.9121
0,9837
0.9117
PCA
0.9266
0.7220
0.9358
0.7215
Isamap
0.9838
0.9197
0.9858
0.9196
Isomap
0.9497
0.7640
0.9553
0.7636
Fashion MNIST
t-NNE
0.9858
0.9894
0.9944
0.9927
Kuzushiji MNIST & = 15
t-SNE
0.9758
0.9668
0.9825
0.9683
UMAP
0.9934
0.9585
0.9946
0.9584
UMAP
0.9836
0,9551
0.9558
& = 15
TopoAE
0.9892
0.9591
0.9904
0.9590
TopoAF
0.9715
0,9442
0.9746
0.9441
Ar-SNE 0.9769
0,9840
0.9817
0.9845
At-SNE
0.9678
0.9648
0.9765
0.9665
UMATO
0.9888
0.9495
0.9906
0.9499
UMATO
0.9814
0,8876
0.9853
0.8887
J 2D EMBEDDING RESULTS OF UMATO AND BASELINE ALGORIHTMSS ON REAL-WORLD DATASETS
For the real-world datasets, UMATO showed a similar projection to PCA but with better captured local characteristics. The results from topological autoencoders showed some points detached far apart from their centers, even though the best hyperparameters were used for each. Although At- SNE claimed that could capture both structures, the results were not significantly different from those of the original t-SNE algorithm when projecting the Spheres and Fashion MNIST datasets.
16

---

Under review as a conference paper at ICLR 2021
Emmnze
Romnis
Figure 7: 2D projections produced by UMATO and six baseline algorithms UMATO generated similar projections PCA but with the points more locally connected; this is best viewed in color.
K EMBEDDING ROBUSTNESS OVER NUMBER OF EPOCHS
We report the experimental result Figure As we explained, the UMAP embedding results are susceptible to the number of epochs so that the distance between clusters get dispersed. This can induce misinterpretation that the user considers the distance between clusters as something meaningful. The two-phase optimization of UMATO can solve the problem since the global opti- mization (first phase) is easy to converge as it runs only with small portion of points. Therefore, the increasing number of epochs in the global optimization does not harm the final embedding.
epochs
UMAP epochs
UMAP 5000 epochs
UMATO epochs
UMATO 1000 epochs
UMATO epochs
Figure 8: Comparing result of UMATO and UMAP with varying number of epochs (Top row) UMAP is susceptible to the number of epochs so that the clusters get dispersed as the epochs increases. (Bottom row) On the other hand, regardless of the number of epochs in the global opti- mization, UMATO results in almost the same embedding result.
17

---

Under review as a conference paper at ICLR 2021
L ILLUSTRATION OF UMATO PIPELINE
For the ease of understanding, we provide an illustration of UMATO pipeline detailed explanation for UMATO can be found Section 4
Figure
The
kneggherr
Man- c00
Peel er 144
rom
rowN
Ximxx
Raci it
PachM X/1
Couat Eequency nearest neighbers and sort by decressing coler
points into clesses: bubs, expanded nearest weightoos, outlieus
Find K-nearest aeighbors
Figh-dimessicnal data
d+t wug
Initiatioe expended nearest neighbors and ran local op imiimizaiion
Initiallize iub points and run global optimization
Embed linish embedding
Figure 9: The illustration of overall UMATO pipeline.
M EFFECT OF LOCAL LEARNING RATE OF UMATO
By manipulating one of UMATO's hyperparameters, local_lle www.eaainnngaaaaaeeeeee the user can deter- mine where focus the embedding result; to reveal more the global structures, the user should apply lower value (e.g., 0.005), while using higher (e.g., 0.1) would generate more like UMAP embedding which prefers to show the local manifolds.
MNIST LR=01
EMNIST LR=0.1
KMNIST LR=0.1
Figure 10: The effect of manipulating local learning rate of UMATO. Local learning rate was set to 0.1 for all cases. Unlike previous embedding results in Figure 7 UMATO reveals more of the local aspects.
18

---

Under review as a conference paper at ICLR 2021
N UMATO ON REAL-WORLD BIOLOGICAL DATASET
To test UMATO on the real-world biological dataset, we took professional advice from an expert who has Ph.D. in Bioinformatics. We have run UMATO and the baseline algorithms (t-SNE, UMAP) on 23,822 single-cell transcriptomes from two areas at distant poles of the mouse neocortex Tasic al. (2018). Each cell belongs to one of 133 clusters defined by Jaccard-Louu tering (for more than 4,000 cells) or a combination of k-means and Ward's hierarchical clustering. Likewise, each cluster belongs one of 4 classes: GABAergic (red/purple), Endothelial (brown), Glutamatergic (blue/green), Non-Neuronal (dark green).
clus-
The embedding result for each method is given in Figure In the case of t-SNE, clusters are well-captured, but the classes are much dispersed, while UMAP adequately separates both classes and clusters. Compared to these baseline algorithms, UMATO able to capture the relationship between classes much better, retaining some of the local manifolds as well. This means that UMATO focuses more on the manifold at a higher level than the baselines that the hub points worked as the representatives that explain well about the overall dataset. Moreover, there cases in biological data analysis where the researchers want to know the distance between samples (González-Bla et al. (2019); Van den Berge al. (2020). As the UMAP embedding results susceptible to the number of epochs, this may cause a negative impact to interpret the results accurately. On the other hand, as UMATO is robust over the number of epochs, we do not have to worry about such biases.
TSNE
UMAP 200 epochs (default)
UMAP 2000 epachs (fox)
UMATO 100 EPOCHS (DEFAULT)
UMATO 1000 EPOCHS (10X)
Figure 11: 2D visualization of UMATO, UMAP and i-SNE on mouse neocortex dataset Tasic et al. 2018)). (-SNE separates clusters well but does not show class information: GABAergic (red/purple), Endothelial (brown), Glutamatergic (blue/green), Non-Neuronal (dark green). UMAP moderately captures both the clusters and classes. In the case of UMATO, it demonstrates the rela- tionship between classes much better than (-SNE and UMAP, retaining some of the local manifolds well.
19


Reviews:
[{"review_id": "qzfb5KlYXcc", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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 authors attempt to address an important problem of preserving both the global and local structures of  high-dimensional data by applying two-step optimization approach to UMAP. The paper is well written and this is an interesting direction, but unfortunately the results don't look convincing at all:\n\n1. Results from Table 2 demonstrate that UMATO performs better on global quality metrics, but looks like it achieves it by reducing local quality metrics. Figure 3 doesn't really help in convincing that the method is useful - if I will remove the labels, I will only see a blob and no separate clusters. I don't think that preservation of global metrics at this price is useful. It would be much more interesting to see that the clusters are still preserved, but they are positions relative one to another also correspond to a global structure. \n2. MNIST and Fashion MNIST are certainly more realistic than simulated data, but would be nice to see the results on some real world datasets. For example, the authors give examples from biology in the introduction. Maybe they could show the performance and advantages of their method on one of these datasets. For example, a list of datasets for inspiration could be found here: https://genomebiology.biomedcentral.com/articles/10.1186/s13059-020-02128-7\n3. In real world applications, UMAP or tSNE are rarely used with random initializations: https://www.biorxiv.org/content/10.1101/2019.12.19.877522v1. Therefore, I think it would be more fair to compare the proposed method with non-random initializations used in practice. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "ih50tBUXvl", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "### Summary: \n\nThis work proposed a dimensionality reduction algorithm called Uniform Manifold Approximation with Two-phase Optimization (UMATO), which is an improved version of UMAP (Ref. [3] see below). UMATO has a two-phase optimization approach: global optimization to obtain the overall skeleton of data & local optimization to identify the local structures. \n\nOn synthetic and three real-world datasets, UMATO achieved comparable and sometimes better results, compared to baseline method PCA, and alternative non-linear methods such as t-SNE, UMAP, topological autoencoders and Anchor t-SNE. \n\n### Strengths & Originality: \n\nThe idea of splitting the optimization from all points in UMAP (Ref. [3]) into 3 parts, and only performing global optimization for hubs (selected from the original data) is interesting and reasonable. \n\nOutlier detection is explicitly included in this proposed UMATO, this is good & as robustness is an important aspect for a practical manifold learning algorithm.     \n\nIn section 1 \"At-SNE inherits the conventional limitations of t-SNE ...... KL divergence exerts little effect on distant points in a high-dimensional space .....\". For distribution p and q, once p is fixed (i,e., the encoding from original space X), as cross entropy H(p,q) = H(p) + KL(p,q), so these 2 become the same for optimizing y (associated q) from the embedding space. From equation 4, or appendix B equation 9, the claimed cross entropy function (leveraged from UMAP) is provided, and this is not the standard cross entropy defined in information theory. In fact, equation 4 = 0 when p = q, so this is more similar to KL & not cross entropy. Despite the terminology is unclear, the key difference between eq. 4 and KL is real, and seems reasonable to use eq. 4 as the objective function in the global optimization step.    \n\n### Weakness: \n\nThe first step of this proposed UMATO method is the points classification, i.e., assign each point into one of the 3 categories: hubs, expanded nearest neighbors, and outliers. This is an interesting concept, and related to previous works such as Ref. [4], which utilize the manifold ranking method to detect outliers. The main concern for this part, i.e., section 4.1, is the lack of formal formulation. Can we have some sort of objective function for this points classification step? It seems the quality of this step is quite important for the overall performance of UMATO, and seems no clear evidence to support the robustness here, from the experimental results in section 5. \n\nThe local optimization for each point in the \"expanded NN\" is also kind of Ad-hoc. There are several choices for this local optimization after the global optimization step, not exactly sure what is the key advantage of this proposed algo in section 4.3. For example, we can also use local alignment techniques to embed \"expanded nearest neighbors\", based on nearby hubs. \n\nInitialization: as mentioned in section 3 (page 3), Laplacian eigenmap is applied as the initialization step for UAMP. For UMATO, the points classification step can be also viewed as an initialization (plus PCA initialization in the UMATO global optimization stage). However, it is unclear what is the corresponding step of t-SNE in experiments (section 5.2 & Appendix E). If there is no careful consideration, then it seems kind of unfair to say t-SNE perform worse than UMAP or UMATO. As all these methods are non-convex in terms of optimization, it is important to address this part more clearly. \n\nAppendix B, page 12 \"The KL divergence imposes a big penalty when v_{ij} is small but w_{ij} is large (Table 3 b.)\", this seems to be a typo, as KL imposes a big penalty for \"large v + small w\" from Table 3 or equation 8. \n\nSimilarly, page 12 \"the second term of cross-entropy imposes a big penalty when v_{ij} is large but w_{ij} is small (Table 3 g.)\", however, Table 3.g seems to be \"small v + large w\", maybe a typo again. \n\n### Reference:\nThis submission cited related works in manifold learning & dimension reduction & visualization such as Ref. [3], however, feel several related works are missing, for example Ref. [1] and Ref. [4] listed here. \n\n1. Laurens van der Maaten. Accelerating t-SNE using Tree-Based Algorithms. Journal of Machine Learning Research, 2014.\n\n2. James Cook, Ilya Sutskever, Andriy Mnih and Geoffrey Hinton. Visualizing similarity data with a mixture of maps. AISTATS 2007.\n\n3. Leland McInnes, John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:1802.03426, 2018.\n\n4. Dian Gong, Xuemei Zhao, Gérard G. Medioni, Robust Multiple Manifold Structure Learning. ICML 2012.", "extra_scores": {}, "extra_text": {}}, {"review_id": "hQ13L4J9jyN", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "Summary: This paper applies Uniform Manifold Approximation and Projection (UMAP) recursively to a high-dimensional dataset to preserve both global and local structures for visualization. The proposed algorithm has two levels for the recursion: first run UMAP on the selected hubs, and then run UMAP for the nearest neighbors for each hub. I vote for marginally reject because the overall contribution looks incremental and the algorithm description is not super clear.\n\nStrengths:\nThe paper presents a substantially improved visualization of the synthetic Spheres dataset, where the original global structure is preserved in the visualization, as well as quantitative results on four datasets (Spheres plus 3 real-world datasets).\n\nWeaknesses:\n1. By looking at the table of the quantitative results (Table 2), it seems hard to draw a conclusion at first sight, and the description of the results in Section 5.3 is not helpful either. It may be better if it is clearly called out that t-SNE and UMAP are good at local quality metrics, topological autoencoder and At-SNE are good at global quality metrics, while UMATO is good at both global and local metrics.\n2. The visualization in Fig. 3 is interesting but I am not sure what information is conveyed or what conclusion is drawn for the three non-synthetic datasets. If the authors decide to keep these figures, more interpretations will be helpful for readers.\n3. The algorithm description can be clearer by using some illustrative examples, besides using the actual Spheres data in Fig. 1 and Fig. 2. For example, building a graph, sort the data points in descending order of connectivity, and selecting the hubs: these steps can be well explained with an illustration, while using actual data such as Fig. 1 and Fig. 2 would make readers guess what is happening.\n4. In Section 4.3, there are many descriptive steps in words that are vague (e.g. the description of an edge with point $p$ and $q$), and I don't precisely know what they refer to without a picture.\n5. In Fig. 2(C), it shows \"LOCAL INIT\" which looks like the state before running the local optimization, while (A) (B) (D) show the states after the corresponding steps, but the descriptions in the figure title haven't clarified their meanings. In particular, what do (B) and (C) refer to exactly?\n\nQuestions during rebuttal period:\nPlease address #2 and #5 in the weaknesses above.", "extra_scores": {}, "extra_text": {}}, {"review_id": "d-eMbVE1L_B", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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 proposes UMATO, a low-dimensional embedding technique based on a two-phase optimization, the first phase embeds representative points (called hubs) for global structure preservation, and the second phase embeds the rest of the points for local structure preservation.\n\nQuality, clarity, originality and significance:\nPro: The paper is well written and most aspects are clearly explained. It seems to me that the method is mostly designed for clustered data which is significant in many real world applications, but this is not emphasized in the paper, see also comments below. Overall, I found the paper clear, and I like that the authors show the connection to UMAP. Cons: As discussed below I find that there are some details missing, that have the potential to better explain why and how the method works. As the method borrows ideas from other methods, clearly discussing all the details is very important in order to increase its strengths.\n\nDue to the two-phase approach to the embedding it seems that the method is much more adapted to clustered data than to the standard manifold embedding. How would the method perform for a continuous manifold that is fairly uniformly sampled such as the Swiss roll, would it create holes because of the two-phase structure? The results also show that UMATO performs best in the case of the Spheres dataset where the clusters are clearly separated. Could the authors extend on this?\n  \nIsomap has proven to be fairly good at embedding both the global and local structure of the data, I believe a comparison would be relevant and needed. More so, since from Table 2 it seems that UMATO is better at capturing the global rather than the local structure which is in line with what Isomap (not Landmark Isomap) is trying to do. \n\nWould it be possible to define a score that combines the global structure and local structure preservation? For comparing the different methods that would be easier. What are the parameters of the different quality metrics used? The local quality metrics probably depend on a number of nearest neighbours. How was this chosen and are the results robust to the choice of parameters?\n\nAs UMATO follows the same line as UMAP, could the authors explain why did they choose to use a different initialization (PCA) and not the initialization in UMAP (spectral embedding)? What happens actually for different initializations? Does the stability of UMATO discussed in the paper depend on the stability of PCA or is independent of it? If PCA does not work, then the hubs will be wrongly embedded and the global structure will suffer.\n\nSect. 4.1.: “the most popular point … but not too densely connected” – How is the density estimated and controlled?; “we unfold it” – what does “it” refer to?\n\nSect. 4.2: p and q refer to points but the notation is often used for probabilities. A different notation might make things easier to read.\n\nSect. 4.4.: “we arrange $x_i$ using the position of $x_j$” – I might be missing smth, but should it be $y_i$ and $y_j$?\n\nSect. 5: How many connected components are identified in each of the experiments?\n\n-----------------------------\n\nRebuttal: Thank you to the authors for addressing the comments and for the changes to the paper, and thank you for adding the examples on Scurve and Swiss Roll and the comparison with Isomap. I find it slightly surprising that Isomap performs very well for local metrics on the spheres dataset, because Isomap tends to preserve larger distances. Not sure I fully understand why.\n\nRelated to my initial concern about clustered data, my impression would be that in addition to the spheres visual example in the main paper, it would have been good to add the Scurve or the Swiss roll to emphasize that UMATO is not specifically designed for clustered data (all the examples in Table 2 are for data with implicit clusters). How do the methods perform in terms of the local and global metrics for the Scurve and Swiss roll datasets? Would zooming in on PCA reveal similar local structures to UMATO? \n\nWhat is the difference between y_i and y_i' used in eq (8)? Are they the same?\n\nSecond line on page 2: Should it be UMATO instead of UMAP?  ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers generally agree that the proposed method UMATO, a two-phase optimization dimensionality reduction algorithm based on UMAP, is interesting and has potential, and that the paper is well-written. However, there are several concerns with the current paper. In particular, R1 is not convinced by the performance of UMATO on real-world datasets compared with previous methods such as t-SNE (see the linked papers). Both R1 and R2 are concerned that given the 2-phase approach, UMATO might be much more adapted to clustered data than standard manifold embedding. They pointed out that in the Swiss  roll/S-curve examples, UMATO stays very close to PCA, which is used for initialization, instead of globally unfolding the manifold as Isomap. These issues should be clarified/explored further for a better understanding and/or improvement of the current work.
Decision: Reject