Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Authors tries to reveal the true loss function of UMAP projection given its success in data visualization and dimensionality reduction.
main_review: Authors demonstrated that UMAP didn't preserve the high-dimensional similarity based on a toy dataset (2D-to-2D UMAP transformation). This provides a neat example to reveal the discrepancy between theory and the empirical behavior. Authors derived the true updating function for UMAP in a close form which shed light in understanding the behavior of UMAP in depth.
limitations_and_societal_impact: 1) In Fig.2(a), the projections of seam cells is tightly clustered but still has non-zero variance along two different directions which is not a line in 2D space. Authors stated that the embeddings are locally one-dimensional which is ambiguous.
2) In Fig.3, the curve corresponding to "purported total" is missing due to the compressed y-axis based on the range of "purported total" and "purported attractive".
3) Authors extensively experimented using the C.elegans dataset and it would be helpful to include at least one more scRNA-seq dataset as demonstration.
4) This manuscript didn’t answer the question that why balanced attraction and repulsion would lead to a “good” embedding. This is beyond the scope of this paper as stated in the discussion section. The quantitative metric related to “good” embedding authors frequently used was similarity. Authors could report similarity values for the C.elegans dataset to see if the similarity values are in concordance with visual impressions of good UMAP embeddings.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper addresses the effects of the negative sampling strategy during UMAP’s optimization procedure. The authors provide a theoretical explanation of how this procedure distorts the objective function portrayed in UMAP’s original paper. The paper derives the actual objective function being optimized when using negative sampling, showing how it corresponds to lower repulsive forces that the ones intended in the cross-entropy loss function. Such behavior causes over contracted embeddings, which do not consider connectivity beyond the Knn neighbors.  
main_review: The paper leverages the empirical observations found in [3], giving a concise analysis for several previous claims. In particular, the paper answers various questions, such that:
-	Why does using binarized affinities not lead to noticeable changes in the embedding?
-	What is the exact repercussion of using negative sampling in the final embeddings produced by UMAP?

The paper is well-written and clear. It does provide good insight into UMAP. However, the results do feel somewhat incremental and thus limited in its significance. Are their implications of these results that go beyond UMAP, perhaps to other visualization methods? I.e., can these results be used to either improve UMAP or other visualization methods?

Other comments:

Theorem 5.1 seems out of place. At least a brief comment about parametric UMAP and the notation in the theorem is needed. For instance, there is no definition of f(x), u_{tot}.

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper investigated the UMAP's sampling-based optimization. The paper derived the effective objective function and found it to be different from the one proposed in the original paper. The difference is due to using SGD with non-uniformly-sampled positive and negative data points. The paper further derived the actual similarities which UMAP is trying to approximate. Those findings have several important implications: 1) UMAP does not try to reproduce the similarities in the original high dimensional space, 2) instead, it tries to approximate the similarities captured by the KNN graph, 3) points (1) and (2) are more so for large n (# of data points), small m (# of negative samples), and small k (# of neighbors on KNN graph). 

--------------------------------
I thank the authors for providing a careful and thorough response to my review. The response has addressed most of my questions and led to new interesting ideas. 

main_review: The paper studies an important problem because UMAP is one of the most widely used data visualization algorithms and it is important to understand what it is trying to optimize. The theoretical analysis and empirical results are solid, and the interpretations derived from them provide a reasonable explanation on the behavior of UMAP. Overall, I think the paper is technically sound, well-written. The conclusions are useful and well-supported by both the theoretical and empirical results. 

Major: 

- The paper hasn't focused on how the behavior of UMAP changes with the data size n, which I think is an important aspect. Eq. (15) implies that UMAP can more faithfully recover the similarities in the high-dimensional data when the data size n is small. I think this is consistent with empirical observation of applying UMAP on real-world single-cell data. It would be nice to have a discussion on this. Specifically, at what values of (n,m,k) are the UMAP embedding close to the high-dimensional similarities, and at what values of (n,m,k) do the UMAP embedding only capture the binary KNN similarities? 

- According to Eq. (15), when we further increase n, Fig. 1c will look totally random where the distances between any two points are the same. Is this what the authors observed empirically? 

- According to Eq. (15), the contraction phenomenon will be more pronounced when the data size n is larger. Is this what the authors observed empirically? 

- Given the different behavior of UMAP for different data sizes, it is desirable to have a version of UMAP whose behavior does not change with the data size n, either by adaptively choosing (m,k) for different n or by slightly modifying the objective function. I think the impact of the paper may be substantially improved by providing such a guideline/procedure.    

- Fig. 4b: I am curious how v_ij's look in this experiment, both for the original UMAP and the one with inverted \mu_ij.



Minor: 

- Line 168: "line 5" --> "Alg. 1 line 5" for clarity and similar for others. 

- Equations: add parentheses to clarify which terms are inside summation. 

- Supp. Figures: Please reference Supplementary Figures by "Supp. Fig." instead of just "Figure".  

limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: UMAP is a very popular algorithm for dimensionality reduction and data visualisation. This paper analyzes the the sampling based optimisation of UMAP and show that the loss function UMAP implicitly optimises is different from the loss function it tries to optimise (because of the stochastic optimisation algorithm used). The authors derive the qualitative differences between the two and using this show that what UMAP tries to do is approximate binarised similarities of those obtained from the high dimensional setting (similarity 1 if the high dimensional similarity computed is non-zero and 0 otherwise). 
main_review: UMAP is a very popular technique for dimensionality reduction and data visualisation. As the authors point out, UMAP is derived under the assumption that the data is uniformly distributed on a low dimensional manifold in high dimensional space - which is untrue for a lot of datasets UMAP is known to perform well on. Sparse single cell RNA-seq data sets are a good example of such a dataset. Hence understanding what exactly the algorithm does is an important question - which this paper addresses.

The meat of the paper is in the authors showing that the stochastic optimisation algorithm used to optimise UMAP does not optimise the loss function it purportedly optimises. The Loss function of UMAP for a pair $i,j$ is given by 

$$ \mu_{i,j} \log v_{i,j} + (1-\mu_{i,j})\log (1- v_{i,j})$$

where $\mu_{i,j}$ is the high dimensional similarity and $v_{i,j}$ are the similarity of the low dimensional embedding; $ \log v_{i,j}$ being the attraction term and $ \log(1- v_{i,j})$ being the repulsion term. Due to the computation of $\mu_{i,j}$ (based on a k-NN in high dimensions), most of them are $0$. However, that means the pre-factor multiplying the rejection term is $1$ for most of the cases.

However on analysis of the stochastic optimisation used to optimise this loss one finds that pre-factor multiplying the repulsion term is much smaller. The authors derive this in closed form. They then use it come up with interpretations of what UMAP is optimising in reality - a binarised similarity score derived in high dimensions. 

I thought this was a neat analysis. The fact that it was not particularly hard mathematically just added to its beauty. 
limitations_and_societal_impact: One complaint I have to this paper is that the writing is not self contained in a few places. For example, the authors dont define what the uniformity assumption of UMAP is and use it in the first paragraph of the introduction.

Another complaint I have is that the authors are parsimonious in using of brackets in equations like (eq 7 where a bracket around the sum over j would make it much easily parsed.
review_title: null

Meta-review: Visualization with UMAP has become standard practice in multiple fields in recent years, originally presented as being derived from topological construction as an alternative to the popular tSNE visualization. However, over the past few years several studies have investigated its relation with tSNE (and other visualizations) and raised questions regarding the matching (or rather discrepancy) between its theoretical derivation and the implementation used in practice. This work provides an interesting in depth analysis on this topic, constructively providing a closed-form formulation of the loss function that is implemented by the UMAP algorithm (which is different from the loss it was purportedly supposed to optimize). In doing so, it provides concise insights into understanding of previous observations, and more generally the behavior of UMAP.

After discussion, the reviewers unanimously agree the paper should be accepted. Most concerns that have been raised by initial reviews have been addressed in the responses (authors: please follow up on these in revision of the manuscript itself). Therefore, I recommend accepting the paper and I am positively certain it will be of great interest to a significant portion of the NeurIPS community.
Decision: Accept (Poster)