Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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:

1. 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. 
2. 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
3. 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. 
review_title: results are not convincing

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Strengths:
The 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).

Weaknesses:
1. 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.
2. 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.
3. 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.
4. 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.
5. 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?

Questions during rebuttal period:
Please address #2 and #5 in the weaknesses above.
review_title: Interesting visualization, but the algorithm description can be clearer

final_score: rating: 5: Marginally below acceptance threshold
review_content: ### Summary: 

This 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. 

On 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. 

### Strengths & Originality: 

The 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. 

Outlier detection is explicitly included in this proposed UMATO, this is good & as robustness is an important aspect for a practical manifold learning algorithm.     

In 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.    

### Weakness: 

The 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. 

The 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. 

Initialization: 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. 

Appendix 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. 

Similarly, 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. 

### Reference:
This 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. 

1. Laurens van der Maaten. Accelerating t-SNE using Tree-Based Algorithms. Journal of Machine Learning Research, 2014.

2. James Cook, Ilya Sutskever, Andriy Mnih and Geoffrey Hinton. Visualizing similarity data with a mixture of maps. AISTATS 2007.

3. Leland McInnes, John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:1802.03426, 2018.

4. Dian Gong, Xuemei Zhao, Gérard G. Medioni, Robust Multiple Manifold Structure Learning. ICML 2012.
review_title: A marginally improved version of UMAP for dimension reduction with reasonable experimental results but also some concerns for the method formulation. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

Quality, clarity, originality and significance:
Pro: 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.

Due 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?
  
Isomap 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. 

Would 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?

As 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.

Sect. 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?

Sect. 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.

Sect. 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$?

Sect. 5: How many connected components are identified in each of the experiments?

-----------------------------

Rebuttal: 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.

Related 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? 

What is the difference between y_i and y_i' used in eq (8)? Are they the same?

Second line on page 2: Should it be UMATO instead of UMAP?  
review_title: Manifold embedding technique for clustered data relying on UMAP

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