On UMAP's True Loss Function
Authors: Sebastian Damrich
Fred A Hamprecht
Venue: NeurIPS 2021 Poster (2021)
Keywords: UMAP
t-SNE
negative sampling
scRNA-seq
unsupervised learning
visualization
non-linear dimension reduction
manifold learning

Abstract: UMAP has supplanted $t$-SNE as state-of-the-art for visualizing high-dimensional datasets in many disciplines, but the reason for its success is not well understood. In this work, we investigate UMAP's sampling based optimization scheme in detail. We derive UMAP's true loss function in closed form and find that it differs from the published one in a dataset size dependent way. As a consequence, we show that UMAP does not aim to reproduce its theoretically motivated high-dimensional UMAP similarities. Instead, it tries to reproduce  similarities that only encode the $k$ nearest neighbor graph, thereby challenging the previous understanding of UMAP's effectiveness. Alternatively, we consider the implicit balancing of attraction and repulsion due to the negative sampling to be key to UMAP's success. We corroborate our theoretical findings on toy and single cell RNA sequencing data.

On UMAP's True Loss Function
Sebastian Damrich Fred A. Hamprecht
HCI/IWR Heidelberg University, 69120 Heidelberg, Germany {sebastian an. damrich, fred. hamprecht)@ivr uni uni-heidelberg....
Abstract
UMAP has supplanted (-SNE as state-of-the-ar for visualizing high-dimensional datasets in many disciplines, but the reason for its success is not well understood. In this work, we investigate UMAP's sampling based optimization scheme in detail. We derive UMAP's true loss function in closed form and find that differs from the published one in dataset size dependent way. As a consequence, we show theoretically motivated high-dimensional
that UMAP does not aim to reproduce UMAP similarities. Instead, it tries to reproduce similarities that only encode the & nearest neighbor graph, thereby challenging the previous understanding UMAP's s effectiveness. Alternatively, we consider the implicit balancing of attrac- tion and repulsion due to the negative sampling to be key to UMAP's success, We corroborate our theoretical findings on toy and single cell RNA sequencing data.
Introduction
Today's most prominent methods for non-parametric, non-linear dimension reduction I-Distributed Stochastic Neighbor Embedding (L-SNE) [20] 19] and Uniform Manifold Approx- imation and Projection for Dimension Reduction (UMAP) [3] The heart of UMAP is claimed to be its sophisticated method for extracting the high- dibe-siinnsional similarities. However, the reason for UMAP's excellent visualizations is not immediately obvious from this approach. In particular, UMAP's eponymous uniformity assumption, see Section 3 is arguably difficult to defend for the wide range of datasets on which UMAP performs well. Therefore, it is not well understood what aspect of UMAP is responsible for its great visualizations.
Both t-SNE and UMAP have overcome the computational obstacle of considering the quadratic number of interactions between all pairs of points. The breakthrough for t-SNE came with a Barnes-Hut approximation [19]. Instead, UMAP employs a sampling based approach avoid quadratic number of repulsive interactions. Other than [4] little attention has been paid to this sampling based optimization scheme. In this work, we fill this gap and analyze UMAP's optimization method in detail. In particular, we derive the effective, closed form loss function which is truly minimized by UMAP's optimization scheme. While UMAP's use of negative sampling was intended to avoid quadratic complexity, we find, surprisingly. that the resulting effective loss function differs significantly from UMAP's purported loss function. The weight of the loss function's repulsive term is drastically reduced. As consequence, UMAP is not actually geared towards reproducing the clever -igh--iinnsional similarities. In fact, we show that most information beyond the shared kNN graph connectivity is essentially ignored UMAP actually approximates binarized version of the high-dimensional similarities. These theoretical findings underpin some empirical observations and demonstrate that the gist of UMAP is not its high-dimensional similarities. This resolves the disconnect between UMAP's uniformity assumption and its success on datasets of varying density.
From user's perspective it is important to gain an intuition for deciding which features of a visualization can be attributed the data and which ones are more likely artifacts of the visualization method. With our analysis, we can explain UMAP's tendency to produce crisp, over-contracted substructures, which increases with the dataset size, as a side effect of its optimization.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Without the motivation of reproducing sophisticated high-dimensional similarities in embedding space, it seems unclear why UMAP performs well. We propose an alternative explanation for UMAP's success: The sampling based optimization scheme balances the attractive and repulsive loss terms despite the sparse high-dimensional attraction. Consequently, UMAP can leverage the connectivity information of the shared kNN graph via gradient descent effectively.
2 Related work
For most of the past decade t-SNE 20 19 was considered state-of-the-ar for non-linear dimension reduction. In the last years UMAP [3 at least ties with t-SNE. In both methods, points are embedded so to reproduce high-dimensional similarities. Different from (-SNE, the high-dimensional similar- ities are sparse for UMAP and do not need to be normalized over the entire dataset. Additionally, t-SNE adapts the local scale of high- sish-dimnssionll similarities by achieving a predefined perplexity, while UMAP uses its uniformity assumption. The oow-dimesiiona similarity functions also differ. Recently, Böhm et al. [4] placed both UMAP and t-SNE on spectrum of dimension reduction methods that mainly differ in the amount of repulsion employed. They argue that UMAP uses less repulsion than t-SNE. A parametric version of UMAP was proposed in 17..
UMAP's success, in particular in the biological community 2 16), sparked interest in understanding UMAP more deeply. The original paper [33 motivates the choice of the high-dimensional similarities using concepts from algebraic topology and thus justifies UMAP's transition from local similarities Mi-zj to global similarities (lg. The authors find that while the algorithm focuses on reproducing the local similarity pattern similar to I-SNE, it achieves better global results. In contrast, Kobak and Linderman
[10] attribute the better global properties of UMAP visualizations to the more informative initialization and show that t-SNE manages to capture more global structure if initialized in a similar way. Wang al. [1] also analyze the local and global properties of t- SNE, UMAP and TriMAP M
Narayan et al. denser regions are more spread out while sparser regions get overly contracted. They propose an additional loss term that aims to reproduce the local density around each point and thus spaces sparser regions out. We provide not reproduce the high-dimensional similarities but exaggerates the attractive forces over the repulsive ones, which can result in overly crisp visualizations, see Figures 1b
observe that UMAP's uniformity assumption leads to visualizations in which
additional explanation for overly contracted visualizations: UMAP does
1c
and 2a
Our work aligns with Böhm et al. 4.. The authors conjecture that the sampling based optimization procedure of UMAP prevents the minimization of the supposed loss function, thus not reproducing the high-dimensional similarities in embedding space. They substantiate this hypothesis by qualitatively estimating the relative size of attractive and repulsive forces. In addition, they implement Barnes- Hut approximation to the loss function (6) and find that it yields a diverged embedding. We analyze UMAP's sampling procedure in depth, compute UMAP's true loss function in closed form and contrast against the supposed loss in Section 5 Based on this analytic effective loss function, we can further explain Böhm et al. (''s 's's empirical finding that the specific high-dimensional similarities provide little gain over the binary weights of a shared &NN graph [ see Section 6 Finally, our theoretical framework leads to new tentative explanation for UMAP's success in Section 7
3 Background on UMAP
UMAP assumes that the data lies low-dimensional Riemannian manifold (R.g) in ambient high-dimensional space. Moreover, the data is assumed to be uniformly distributed with respect to the metric tensor g. put simply, with respect to the distance along the manifold. The metric tensor g in turn is assumed to be locally constant. The key idea of UMAP [13] is to compute pairwise similarities in nigh-dimensiooal space which inform the optimization of the low-dimensional embedding. Let I1. .... Fy E 1 be high- -igeesiinnsinnl,, mutually distinct data points for which low-dimensional embeddings C, ..... C,2 Rd shall be found, where d < D, often d = = or
First, UMAP extracts high-dimensional similarities between the data points. To do so, the nearest neighbor graph is computed. Let é1, & denote the indices of Jr 's k nearest neighbors in increasing order of distance to I,. Then, using its uniformity assumption, UMAP fits a local notion of similarity
'The shared & nearest neighbor graph contains edge ij if i is among j's k nearest neighbors vice versa.

---

for each data point by selecting scale o; such that the total similarity of each point to its h nearest neighbors is normalized, iec find o, such that
exp - (d(2), d(z, 21,)) -d(;,, = ll))
(I)
This defines the directed high-dimensional similarities
P4-j exp (d(x), d(z,, ((,,, for fir...,,ik
(2)
else.
Finally, these are symmetrized to obtain undirected high-dimennionall similarities or input similarities between items and j
Jij Mi-ッ + pyーi - ドーー [0, 1].
(3)
While each node has exactly I: non-zero directed similarities (4i-2j to other nodes which sum to log2 (k), this does hold exactly after symmetrization. Nevertheless, typically the fly highly sparse, each node has positive similarity to about k other nodes and the degree of each node
d, Σド= May is approximately constant and close lkg2(k), see Supp. Fig. and 6 Appendix
For convenience of notation, we set μui = 0 and define the total similarity as Port
E==14 de
Distance in embedding space is transformed to dow-dimensional similarity by smooth approximation to the high- high-dimensional similarity function, @(d; a, b) = (1 + ad for all pairs of points. The shape parameters a, 6 are essentially hyperparameters of UMAP. We will overload notation and write
Vij <(lle esll) p eÿ)
(4)
for the low-dimensional or embedding similarities and usually suppress their dependence on and b. Supposedly, UMAP approximately optimizes the following objective function with respect to the embeddings 61,..., Gn:
((tei)KpH)) --2
(pij log(uss) Isicisn
Σ
+(1 p-s) log(1 v2s))
(5)
= - Σ IgijjSn
(mig
(45) log(1 o(Et,)))))
(6)
While the high- nigh-dimensional similarities May symmetric, UMAP's implementation does consider their direction during optimization. For this reason, our losses in equations (5) and (6) differ by factor of 2 from the one given in 13) Viewed through the lens of force-directed model, the derivative of the first term each summand of the loss function, - / / captures the attraction of e to ej due to the high- dibbnsiinnii similarity Pıj and the derivative of the second term, -OCT, represents the repulsion that ej exerts e; due to lack of similarity in high dimension, 1 pij- Alternatively. the loss can be seen as the sum of binary cross entropy losses for each pairwise similarity. Thus, is minimized if the low-dimensional similarities Vig exactly match their nigh-dimensional counterparts Pij. that is. if UMAP manages to reproduce the input similarities in embedding space.
UMAP uses a sampling based stochastic gradient descent optimize the low-dimensional embedding typically starting from a Laplacian Eigenmap layout B [0). Our main contribution is to show that the sampling based optimization in fact leads different objective function, that UMAP does not reproduce the digh--iiensional similarities low-dimensional space, see Sections to
UMAP does not reproduce high-dimensional similarities
UMAP produces scientifically useful visualizations in many domains and is fairly robust to its
hyperparameters. Since any visualization of intrinsically -igh-dimensional data must be somehow unfaithful, it is not straightforward to check the visualization quality other than by its downstream use. Some quantitative metrics such as the correlation between high- and low-dimensional distances [I0 exist. We follow a different route to show unexpected properties of UMAP. Consider the toy example of applying UMAP to data that is already low-dimensional, so that no reduction in dimension is
3

---

(a) Original data
(b) UMAP
(c) UMAP on larger dataset
(d) UMAP from dense similarities
la Origi- nal data consisting of 1000 points sampled uniformly from ring in 2D. All optimizations ran for 10000 epochs and were initialized at the input data. Tb; Result of UMAP. The circular shape is visible but the ring width is nearly completely contracted. Icp Result of UMAP on dataset consisting of twenty rings as in Ia] spaced so they do not interact in the input similarity computation. Only the embedding of one ring shown. There should not be a significant difference from Fig. Tb Yet, the ring width is completely contracted. [d] Result of UMAP for dense input similarities computed from the original data in Fig. with the similarity function o from Section 3 No change from the initialization would be optimal in this setting. Instead the output has spurious curves and larger width. More figures with the default number of epochs and initialization can be found in Supp. Fig. 20
Figure 1: UMAP does not preserve the data even when no dimension reduction is required.
required: D = d = 2. Ideally, the data would be preserved in this situation. One might also expect that UMAP achieves its aim of perfectly reproducing the input similarities. Surprisingly, neither of these expectations is met. In Figure [ we depict 2D UMAP visualizations of a 2D uniform ring dataset. To ease UMAP's task, we initialized the embedding with the original data, hoping that UMAP's optimization would just deem this layout to be optimal. We also used longer run time to ensure convergence of UMAP's optimization procedure. Otherwise, The results with default initialization and run time are qualitatively similar and shown in Supp. Fig. 20 UMAP manages to capture the ring shape of the data, but changes its appearance significantly. It contracts the width of the ring nearly to a line, see Figure [b a phenomenon also observed on real-world datasets, see Figure 2a Whether this exaggeration of the ring shape is useful depends on the use case. This finding goes beyond Narayan et al. [14] 's observation that over-contraction happens in regions of low density since our toy dataset is sampled uniformly from circular ring.
used the default hyperparameters.
Moreover, we embedded the same ring with UMAP as part of a larger dataset of twenty such rings, spaced that the input similarities for each ring Section 3. we would expect a qualitatively similar embedding as for the individual ring. However, we in Tc
influenced by the other rings. According to
UMAP produces an even crisper embedding. In another experiment, we varied the number of samples from single ring and observed again that the tendency for over-contraction increases with the dataset size. For more information on UMAP's dependence on the dataset size confer Appendix H The dataset size dependence is particularly noteworthy, as computing UMAP embeddings of subsets or subsamples of a dataset is common practice.
As described in Section 3] UMAP employs different methods in input and embedding space to transform distances to similarities. In particular, in input space similarities zero for all but the closest neighbors, while in embedding space they are computed with the heavy-tailed function ø. To test whether this prevents the reproduction of the input data, we also computed the dense similarities on the original data with @ and used these as input similarities for the embedding in Figure Tdl Since we also initialize with the original dataset, a global optimum of the objective function (6) for this choice of input similarity, one would expect no change by UMAP's optimization scheme. However, we observe that in this setting UMAP produces spurious curves and increases the width of the ring.
Böhm et al. 4 implemented a Barnes-Hur Hut approximation of UMAP's objective function (6). which produced a diverged embedding. Inspired by this finding, we compute the loss values according to equation (5) for various input and embedding similarities Mij and Vij in our toy example, see Table []
Consider the row with the usual input similarities (14j = p((aa),..., ...)). In completely diverged embedding, all self similarities are one and all others zero (Vij 1i == j)). We find that the loss for such an embedding is lower than for the optimized UMAP embedding. This is in

---

Table UMAP loss value for various combinations of input and embedding similarities, Higs Pij. of the toy example in Figure []] The loss for the UMAP embedding in Figure Ib (middle column) is always higher than for another wooddimensional layout (bold). Hence, UMAP does not minimize its purported loss. Results are averaged over 7 runs and one standard deviation is given, see also Appendix F.T
Embedding similarities Vij
(i===) j)
(f .......... en (UMAP result)
o ( (input layout)
Input similarities Mij
(diverged layout)
p(fx1,.... -2, zn o((x1,..., kn))
62959 + 82
70235 + 1301 331666 = 1308
136329 + 721
902757 + 2788
224584 + 8104
accordance with Böhm et al. 's Barnes-Hut experiment and shows that UMAP does not optimize its supposed objective function (6) as a diverged embedding is approximately feasible in two dimensions. This discrepancy is not just due to the fact that input and embedding similarities are computed differently: The second row of [aalee[]cotaaall
loss values for the setting in which we use the dense similarities as input similarities, as in Figure ld We initialize the embedding at the optimal loss value (Vi o( (Z Fn Hky), but UMAP optimization moves away from this layout and towards an embedding with higher loss (vi, o(fe1.... en )) although we always compute similarity in the same manner. Clearly, UMAP's optimization yields unexpected results.
5 UMAP's sampling strategy and effective loss function
UMAP uses sampling based approach to optimize its loss function, to reduce complexity. A simplified version of the sampling procedure can be found in Algorithm [ Briefly put, an edge ij is sampled according to its high-dimensione similarity and the embeddings e; and ej of the incident nodes are pulled towards each other. For each such sampled edge ij, the algorithm next samples m negative samples uniformly from all nodes and the embedding of i is repelled from that of each negative sample. Note that the embeddings of the negative samples are not repelled from that of i, So there are three types of gradient applied to an embedding during epoch:
see Alg. [ line 10
1. 6 is pulled towards ey when edge ij is sampled (Alg line
2. e is pulled towards ej when edge ji is sampled (Alg line 6)
3. is pushed away from negative sample embeddings when some edge ij is sampled (Alg ine 9.
The full update of embedding e, during epoch t is, according to UMAP's implementation, given by
ac De:
ac de,
OCT
+ X
X
(7)
Oe,
where Xa is the binary random variable indicating whether edge ab sampled in epoch f and Yo, is the random variable for the number of times s was sampled as negative sample for edge ab in epoch z if ab was sampled in epoch i and zero otherwise. By construction, E(X,, (b) = Mas and E(Y 1r....X1, = 1) = m/ n. Taking the expectation over the random events in an epoch, we obtain the expected update of UMAP's optimization procedure, see Appendix for more details:
n
aCi, d.m
0C, 0e:
E (g
Pij
(8)
j=1 Deg
2n
Comparing the above closed formula for the expectation of the UMAP updates of the low-dimensional embeddings, to the gradient of UMAP's loss function 6
Oc De, = Σ Pij
OCP
0
+ - (1-1u))
De;
de:
j=1
we find that the sampling procedure yields the correct weight for the attractive term expectation, as designed. However, as noticed by Böhm et al. [4, the negative sampling changes the weight for the
5

---

seam cells
seam cells
seam cells
(a) UMAP
(b) Inverted weights UMAP
(c) PCA
Figure 2: UMAP C. elegans data from 16
14
2a UMAP visualization. Several parts of the
embedding appear locally one-dimensional. for instance the seam cells F
2b; Same as 2a but with inverted positive nigh-dimensional similarities. The result is qualitatively similar, if not better. 2c: Two dimensional PCA of the dataset. Highlighted seam cells clearly have two dimensional variance in the PCA plot, but are overly contracted to nearly line in the UMAP plots 2a and 2b The full legend with all cell types and further information can be found in Supp. Fig.
We report quantitative metrics in Appendix G Figure best viewed in color.
repulsive term significantly. Our closed formula helps to make their qualitative arguments precise: Instead of Mag. we have term d,m which depends on the number of negative samples m per sam- pled edge. Contrary to the intention of McInnes et al. [33, the repulsive weights are not uniform but vary with the degree of each point d,, which, however, is typically close to (kg2(k), see Appendix B More practically, since the non-zero high-dimensional similarities are sparse, - f4y is equal to 1 for most ij. In contrast, the expected repulsive weight is small for large datasets the numerator d,m is of the order of loga (k)m independent of the dataset size but the denominator scales with n.
Another effect of the negative sampling is that in general the expected update (8) does not correspond to any loss function, see Appendix [D] We remedy this by additionally pushing the embedding of a negative sample away from the embedding ey. whenever was sampled as negative sample to some This yields the following gradient at epoch
edge jk, see Alg line
10
acj. de,
0L, De,
OcJ.
Φ
X
X
Y
Σ
xt Yt
(10)
de,
skis de:
;=1 corresponding to a loss in epoch t of
n
E
Σ
X/y.
Lij +
Σ X YiJ..
Ci
(11)
15tjSn
Using the symmetry of pij, CG and Ci in and j. we compute the effective loss
(d, + d,)m
E= -2
Σ ISi<iSn
Mig (ig
Lig
(12)
2n
In fact, the above remedy of also pushing the negative samples does not affect the behavior of UMAP qualitatively, see for instance Supp. Figs. 21 and 15 In this light, we can treat L as the effective objec- tive function that is optimized via SGD by UMAP's optimization procedure. differs from UMAP's
loss function O by having drastically reduced repulsive weight of (d,+d;;)m instead of 1 M4j-
We illustrate our analysis on gene expression measurements of 86024 cells of C. elegans 16 14 We start out with a 100 dimensional PCA of the date and use the cosine metric in high digh--iimessonal space,
2 Near the tip of the seam cells, the points seem to lie on a one- dinensiinni manifold. Closer to the middle of the seam cells the spread appears wider. But there are actually two dense parallel lines of points.
In fact, the Parametric UMAP [17] does include the update of negative samples. obtained from http:///b.. csail mit, edu/ chtp///ddensvii...eee datasstts//////////aa/ We informed the authors of our
of the dataset, which they license under CC BY-NC 2.0.

---

consider k = 30 neighbors and optimize for 750 epochs, similar to [14. The resulting visualization depicted in Figure Za On this dataset the average value Mey is 0.9999 but the maximal effective repulsive weight maxij
(d is 0.0043, showing the dramatic reduction of repulsion 2n
due to negative sampling. After each optimization epoch, we log our effective loss É (22) the actual loss L (11) of each epoch computed based on the sampled (negative) pairs as well the purported UMAP loss C (6) We always consider the embeddings at the end of each epoch. Note that UMAP's implementation updates each embedding e; not just once at the end of the epoch but as soon as incident to sampled edge sampled
negative sample. This difference does not change the actual loss much, see Appendix FF) The loss curves are plotted in Figure 3 We can see that our predicted loss matches its actual counterpart nearly perfectly. While both, L and ćt, agree with the attractive part of the supposed UMAP loss, its repulsive part and thus the total loss two orders of magnitude larger. Furthermore, driven by the repulsive part, the total intended UMAP loss increases during much of the optimization process, while the actual and effective losses decrease, exemplifying
that UMAP really optimizes effective loss C (12) instead of its purported loss L 6 Additional loss curves for UMAP on other scRNA-seq datasets and CIFAR-10 10 can be found in Appendix !
Recently, parametric version of UMAP was proposed [7 Here, neural network is trained to perform the mapping from high to low dimension. Its effective loss function differs slightly from the one for Non- -on-Parametric UMAP as negative samples only come for the training batch:
Theorem 5.1. The effective loss function of Parametric UMAP with neural network So. butch size b and total similarity Prot
Ei= di is
b-1 d,dj log (1 (11-((o((2)) ([oo)))
Σn mag log (((o(()) + m b 2/hrot
(m + 1)/rot 1sissSn
(13)
Proof. The proof can be found in Appendix A
While Parametric UMAP's loss differs slightly from È (12) the same analysis holds unless explicitly mentioned. We mention a relation of Parametric UMAP modularity clustering in Appendix A.
Algorithm 1: UMAP's optimization
input
:imput similarities Pij- initial embeddings é1 c1.-.., Cn. number of epochs T, learning rate
6-
4-
ectual attraclive
actual repulsive
number of negative samples m
output: :final embeddings e Cn
eftective attractive
repulsive
for to do
effective total
for ij E (1, n do
1.25
purparted attractive
3
r Uniiorm((01)
1.00
purported total
purported repulsive
ifr < jkg then
0.75
8C3
0.50
=
De
0.25
ac
ej e Dej
0.00
0
100
200
300
400
500
600
700
for | = to m do
Fpoch
Uniform
Figure 3: Loss curves for the optimization lead- ing to Figure 2a Our effective loss (12) closely matches the actual loss (TI), while the purported UMAP loss (6 is two orders of magnitude higher. The total overlays the repulsive purported loss. An average over 7 runs is plotted with shaded areas of one standard deviation, see also Appendix F. Figure best viewed in color.
dcr De:
6,
// Next line is omitted in UMAP implementation but included for our analysis
ac De.
10
1 e, =
OOur code is publicly available at httpss httpt/ggtttttttt/// www/eoomocceeeeeeeeee www.hhwww..//hhiiiuuaa////aAaaa -rreeess----tttt-eee true-loss
7

---

True target similarities
Since the effective objective function C (2) that UMAP optimizes is different from L 6 we cannot hope that UMAP truly tries to find a low-dimensional embedding whose similarities reproduce the high-dimennional similarities. Nevertheless, using the effective loss L, we can compute the true target similarities Vij which UMAP tries to achieve in embedding space. The effective loss É is a sum of non-normalized binary cross entropy loss functions
Mis log(u + (d: + d )m
log(1 vss))
(14)
2n
which are minimal for
Of pij =
Vig
(15)
Paj
[d. +d, Jm
2n
2
1 if pig > O.
The approximation holds in the typical case in which (d+tdy)m 2n x O. discussed above. In other words, compared to the massively reduced repulsion weight even the smallest high-dimensional similarity appears maximal. Thus, the negative sampling essentially binarizes the input similarities. UMAP's high-dimensional similarities are non-zero exactly on the shared nearest neighbor graph edges of the high-dimensional data. Therefore, the binarization explains why Böhm et al. [4] find that using the binary weights of the shared & nearest neighbor graph does not deteriorate UMAP's performance much [ The binarization even helps UMAP to overcome disrupted high-dimennsonal similarities, as long as only the edges of the shared ANN graph have non-zero weight. In Figure 2b we invert the original positive high-dimensional weights the C. elegans dataset. That means that the k-th nearest neighhor will have higher weight than the nearest neighbor. The resulting visualization even improves on the original by keeping the layout more compact. This underpins Böhm et al. 44's claim that the elaborate theory used to compute the high-dimensional similarities is not the reason for UMAP's practical success. In fact, we show that UMAP's optimization scheme even actively ignores most information beyond the shared ANN graph. In Figure 4 we show histograms of the various notions of similarity for the C. elegans dataset. We see in panel how the binarization equalizes the positive target similarities for the original and the inverted high dimensional similarities.
UMAP's tendency for over-contraction is already strong for small datasets. Consider UMAP's default setting of k = 15 and m = 5. Then for datasets with n = 500 points each input similarity (4j > 0.2 is mapped to target similarity viJ > 0.83, see Appendix H.4
The binary cross entropy terms in the effective loss C [2) are not normalized. This leads to a different weighing of the binary cross entropy terms for each pair ij
Mig Cig + (de + d,)m
==
E ISKjjšn
Lig
(16)
2n.
(d: d.ym)
Σ
(nt log(uss) + (1-vz) log(1 vw)))
(17)
2n
IsicjEn
(de (d.+d,)n )m 2n
very small for large datasets, the term Pkj + (dedd)m is dominated by jag. Hence, 2n
As the reduced repulsion not only binarizes the high-dimensional similarities, it also puts higher weight on the positive than the zero target similarities. Therefore, we can expect that the positive target similarities are better approximated by the embedding similarities than the zero ones. Indeed, panel 4a| shows that the low- din-eiinnsional similarities match the positive target similarities very well, as expected from the weighted BCE reading of the effective loss function
6.1 Explaining artifacts in UMAP visualizations
We conclude this section by explaining the observed artifacts of UMAP's visualization in Figures I and 2 in the light of the above analysis. The normal UMAP optimization contracts the ring in Figure Th even when initialized at the original layout because the reduced repulsion yields nearly binary target similarities. All pairs that are part of the ANN graph not only want to be sufficiently
BBöhm et al. 4 used scaled version of the &NN graph, but the scaling factor cancels for the target weights
8

---

1e6
1e6
3
3
My
Vij
My
Hij
inverted Hij
Vj
Vij for inverted μij
1
6.0
8.0
0.2
0.4
0.8
1.0
0.2
0.4
0.6
0.8
1.0
(a) Similarities for A4j >
(b) Original and inverted similarities for μaj >> 0
Figure 4: Histograms of nigh-dimensional (Jsz). target (Vf,) and low-dimensional (14) similarities on the C. clegans dataset [16] [4] for pairs with positive high- high-dimensional similarity. 4a The similar-
ities of UMAP's low-dimensional embedding reproduce the target similarities instead of the high- dimensional ones. The target similarities are heavily skewed towards one. [b;; Comparison of positive input and target similarities for the original and inverted input similarities. While the histograms of the input similarities differ noticeably, their target similarities do not and neither do the embedding similarities (not shown). The binarization essentially ignores all information beyond the NNN graph.
close that their high-dimensional similarity is reproduced, but so close that their similarity is nearly one. The fact that the effective loss weighs the terms with target similarity near one much more than those with target similarity near zero reinforces this trend. As result, the ring gets contracted. The same argument applies to the over-contracted parts the UMAP visualization of the C. elegans dataset in Figure 2 When we increase the dataset size by adding more rings as in Figure Ic negative sample pairs can come from different rings, reducing the frequency that a pair of points from the same ring is sampled. This reduces the repulsion further. Thus, there is stronger binarization and the embedding looks crisper. we sample a single ring more densely, over-contraction is also increased. But the visual appearance is more nuanced over-contraction can appear in the form of densely clustered and line-like substructures within the ring width, see Appendix H.3
Our framework can also explain the opposite behavior of UMAP when the dense similarities are used as input similarities in Figure ld] In this setting, the average degree node is about 100. With a negative sample rate m = and a dataset size n 1000 this yields repulsive weights (d:+dd)m ss 0.5. 2n. Thus, we increase the repulsion on pairs with high input similarity, but decrease on pairs with low input similarity. Now, the target similarities are not binarization of the input similarities, but instead skewed towards 0.5. Hence, we can expect embedding points increase their distance to nearest neighbors, but distant points to move closer towards each other. This is what we observe in Figure ld where the width of the ring has increased and the ring curves to bring distant points closer together.
7 Discussion
7.1 Negative sampling in Lirge
The visualization method Vis [8] uses negative sampling to optimize its objective function, too. Thus, analysis of the loss function and the target similarities applies to Large and helps to ex- plain why UMAP and Large visualizations are often similar. For more details confer Appendix
7.2 Balancing attraction and repulsion
By deriving UMAP's true loss function and target similarities, we are able to explain several peculiar properties of UMAP visualizations. According to our analysis, UMAP does not aim to reproduce the high-dimensional UMAP similarities in low dimension but rather the binary weights of the shared ANN graph of the input data. This raises the question just what part of UMAP's optimization leads to its excellent visualization results. Apparently, the exact formula for the repulsive weights is not crucial as differs for Non- non-Parametric UMAP and Parametric UMAP while both produce similarly high quality embeddings. A first tentative step towards an explanation might be the different weighing

---

of the BCE terms in the effective loss function (17). Focusing more on the similar rather than the dissimilar pairs might help to overcome the imbalance between an essentially linear number of attractive and a quadratic number of repuisive pairs. Inflated attraction was found beneficial for I-SNE as well, in the form of early exaggeration [12
Put another way, the decreased repulsive weights result in comparable total attractive and repulsive weights, which might facilitate the SGD based optimization. Indeed, the total attractive weight in UMAP's effective loss function is 2//tor 2i.j=1 =1.j=1 Mij and the total repulsive weight amounts to
2m/ Eij=1 (de+dy)m for Non- Non-marrmet UMAP. For Parametric UMAP the total attractive and 2n repulsive weights are 1/(m+1) and m/(m++1 + 1- (-(b-1)//, respectively. For the default value of m 5, the total attractive and repulsive weights are of roughly the same order of magnitude. Moreover, we observe in Figure that the resulting attractive and repulsive losses are also of comparable size. Using UMAP's purported loss function, however, would yield dominating repulsion.
7.3 Improved UMAP
The reason for the binarization of the input similarities is the reduced repulsion on the pairs of points that are linked the shared I-NN graph. As discussed above, might not be desirable to increase the repulsion on all pairs of points to paj- But it might be useful to change the optimization procedure of UMAP so as to decrease the repulsion per edge only on the non-kNN graph edges and not on the
ENN graph edges. In addition to the positive and negative sampling of UMAP, we suggest to explicitly sample the shared ANN graph edges for repulsion with probability 1 - Pij (d, + dz )m/mmm), This would correct the repulsion weight for edges in the shared kNN graph. The loss function would read
-2 Σ
(uigoo((vs) miz) log( log(1-
Σ ijENNN graph
(14
(d. [dc+dd) +djm
1og(1-15))
log(1 -mss) (18)
2n
iJENNN graph
Now the target similarities are precisely the high- sigh-dimensional similarities μ4y for all pairs i. Hence, in an optimal embedding. all pay 's are exactly reproduced and not just binary version of them. We hope that this will improve the embedding quality and decrease the observation of over-contraction. Crucially, the amount of repulsion per data point is kept constant and is not increasing with n. For the quadratic number of non-kNN graph edges, the individual repulsion pre-factors still decrease with 1/n. The total loss function is sum of normalized cross-entropy terms for the edges in the ANN graph and of non-normalized and drastically down-weighted cross-entropy terms for the edges not in the ANN graph. Since not all ((n²) negative pairs considered explicitly and the additional sampling of the kNN graph edges for repulsion only scales with (n)). the complexity of computing the embedding would still scale linearly as O(kmn numepochs) and not quadratically in n.
more in-depth investigation as to why exactly balanced attraction and repulsion is beneficial for a useful embedding and the implementation of the improved sampling scheme are left for future work.
8 Conclusion
In this work, we investigated UMAP's optimization procedure in depth. In particular, we computed UMAP's effective loss function analytically and found that it differs slightly between the non- parametric and parametric versions of UMAP and significantly from UMAP's alleged loss function. The optimal solution of the effective loss function is typically binarized version of the high- dimensional similarities. This shows why the sophisticated form of the high-dimensional UMAP similarities does not add much benefit over the shared &NN graph. Instead, we conjecture that the resulting balance between attraction and repulsion is the main reason for UMAP's great visualization capability. Our analysis can explain some artifacts of UMAP visualizations, particular its tendency to produce over-contracted embeddings which gets stronger for larger datasets.
10

---

Acknowledgments and Disclosure of Funding
We would like to thank Dmitry Kobak, Quentin Garrido and the anonymous reviewers for useful discussions and helpful feedback. Moreover, we thank Ashwin Narayan for making the scRNA-seq datasets available.
This work is supported in part by the Deutsche Forschungsgermeinschff (DFG, German Research Foundation) Projektnummer 240245660 SFB 1129, the Deutsche Forschungsgemeinschatf (DFG, German Research Foundation) under Germany's 's Excellence Strategy EXC 218 1/1 390900948 (the Heidelberg STRUCTURES Excellence Cluster) and Informaties for Life funded by the Klaus Tschira Foundation.
References
[1] E. Amid and M. K. Warmuth. TriMap: Large-scale Dimensionality Reduction Using Triplets. arXiv preprint
2019.
[2] E. Becht, L. McInnes, J. Healy, C.-A. Dutertre, W. Kwok, L. G. Ng. F. Ginhoux, and E. W. Newell. Dimensionality reduction for visualizing single-cell data using UMAP. Nature Biotechnology, 37(1):38-444 2019.
[3] M. Belkin and Niyogi. Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering. In T. Dietterich, S. Becker, and Z. Ghahramani. editors, Advances in Neural Information Processsing Systems, volume 14. MIT Press, 2002. URL Utthsttp://prreeeednng neurips.cc/
[4] J. N. Böhm, P. Berens, and D. Kobak. A Unifying Perspective on Neighbor Embeddings along the Attraction-Repulsion Spectrum. arXiv preprint arXiv:2007.08902 2020.
[5] B. Charlier, J. Feydy. J. Glaunès, F.-D. Collin, and Durif. Kernel Operations on the GPU, with Autodiff,, without Memory Overflows. Journal of Machine Learning Research, 22(74):1-6, 2021. URL URL http::/jmmm ptg/papers///22200 275. html
[6] E. Davis, S. Sethuraman, et al. Consistency of modularity clustering random geometric graphs. Annals of Applied Probability, 28(4):2003 2062, 2018
[7] W. Dong, C. Moses, and K. Li. Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures. Proceedings of the 20th International Conference on World Wide Web, pages 577-586, 2011.
[8] K. He, X. Zhang, S. Ren, and Sun. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
[9] D. Kobak and P. Berens. The art of using t-SNE for single-cell transcriptomics. Nature Communications, 10(1):1-14, 2019.
[10] D. Kobak and G. C. Linderman. Initialization is critical for preserving global data structure in both I-SNE and UMAP. Nature Biotechnology, pages 1-2, 2021.
[11] A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[12] G. C. Linderman and S. Steinerberger. Clustering with t-SNE, Provably. SIAM Journal Mathematics of Data Science, 1(2):313-332, 2019.
[13] L. McInnes, J. Healy, and J. Melville. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. arXiv preprint arXiv: 2018.
[14] A. Narayan, B. Berger, and H. Cho. Assessing single-cell transcriptomic variability through density- data visualization. Nature Biotechnology, pages 1-10, 2021.
[15] M. E. Newman. Analysis of weighted networks. Physical Review E, 70(5)005113, 2004.

---

[16] J. S. Packer. Q. Zhu, C. Huynh, P. Sivaramakrishnan, E. Preston, H. Dueck, D. Stefanik, K. Tan, C. Trapnell, Kim, al. A lineage-resolved molecular atlas of C. elegans embryogenesis single-cell resolution. Science, 365(6459), 2019.
[17] T. Sainburg, L. McInnes, and T. Q. Gentner. Parametric UMAP: learning embeddings with deep neural networks for representation and semi-supervised learning. arXiv preprint a009: 12981, 2020.
[18] J. Tang, J. Liu, M. Zhang, and Q. Mei. Visualizing large-scale and high-dimensional data. In Proceedings of the 25th International Conference on World Wide Web, pages 287-297, 2016.
[19] L. Van Der Maaten, Accelerating t-SNE using Tree-Based Algorithms. Journal of Machine Learning Research, 15(1):3221-3245 2014.
[20] I.. Van der Maaten and G. Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9(11), 2008.
[21] Y. Wang, H. Huang, C. Rudin, and Y. Shaposhnik. Understanding How Dimension Reduction Tools Work: An Empirical Approach to Deciphering t-SNE, UMAP, TriMAP, and PaCMAP for Data Visualization. Journal of Machine Learning Research, 22:1-73, 2021.
[22] G. X. Zheng, M. Terry, Belgrader, P. Ryvkin, Z. W. Bent, Wilson, S. B. Ziraldo, D. Wheeler, G. P. McDermott, J. Zhu, et al. Massively parallel digital transcriptional profiling of single cells. Nature Communications, 8(1):1-12, 2017.
[23] R. Zilionis, C. Engblom, C. Pfirschke, V. Savova, Zemmour, H. Saatcioglu, Krishnan, G. Maroni, C. V. Meyerovitz, C. M. Kerwin, et al. Single-cell transcriptomics of human and mouse lung cancers reveals conserved myeloid populations across individuals and species. Immunity, 5015):1377-1334, 2019.
12


Reviews:
[{"review_id": "XuKleW_5iYb", "reviewer": "Reviewer_kpki", "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). \n\n--------------------------------\nI 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. \n", "questions": "", "limitations": "", "rating": 7, "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": "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. \n\nMajor: \n\n- 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? \n\n- 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? \n\n- 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? \n\n- 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.    \n\n- 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.\n\n\n\nMinor: \n\n- Line 168: \"line 5\" --> \"Alg. 1 line 5\" for clarity and similar for others. \n\n- Equations: add parentheses to clarify which terms are inside summation. \n\n- Supp. Figures: Please reference Supplementary Figures by \"Supp. Fig.\" instead of just \"Figure\".  \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "LHpz7KCE5Y", "reviewer": "Reviewer_8grW", "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.  ", "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": "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:\n-\tWhy does using binarized affinities not lead to noticeable changes in the embedding?\n-\tWhat is the exact repercussion of using negative sampling in the final embeddings produced by UMAP?\n\nThe 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?\n\nOther comments:\n\nTheorem 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}.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "BrXPq-xTEc", "reviewer": "Reviewer_oNq1", "summary": "Authors tries to reveal the true loss function of UMAP projection given its success in data visualization and dimensionality reduction.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n2) 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\".\n3) Authors extensively experimented using the C.elegans dataset and it would be helpful to include at least one more scRNA-seq dataset as demonstration.\n4) 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.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "-2bfWT7kDvm", "reviewer": "Reviewer_akpc", "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). ", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "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.\n\nThe 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 \n\n$$ \\mu_{i,j} \\log v_{i,j} + (1-\\mu_{i,j})\\log (1- v_{i,j})$$\n\nwhere $\\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.\n\nHowever 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. \n\nI thought this was a neat analysis. The fact that it was not particularly hard mathematically just added to its beauty. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n\nAnother 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

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)