A Unifying Perspective on Neighbor Embeddings along the Attraction-Repulsion Spectrum
Authors: Niklas Böhm
Philipp Berens
Dmitry Kobak
Venue:  (2021)
Keywords: visualization
t-SNE
UMAP
dimensionality reduction
nonlinear dimensionality reduction

Abstract: Neighbor embeddings are a family of methods for visualizing complex high-dimensional datasets using kNN graphs. To find the low-dimensional embedding, these algorithms combine an attractive force between neighboring pairs of points with a repulsive force between all points. One of the most popular examples of such algorithms is t-SNE. Here we empirically show that changing the balance between the attractive and the repulsive forces in t-SNE yields a spectrum of embeddings, which is characterized by a simple trade-off: stronger attraction can better represent continuous manifold structures, while stronger repulsion can better represent discrete cluster structures. We find that UMAP embeddings correspond to t-SNE with increased attraction; mathematical analysis shows that this is because the negative sampling optimisation strategy employed by UMAP strongly lowers the effective repulsion. Likewise, ForceAtlas2, commonly used for visualizing developmental single-cell transcriptomic data, yields embeddings corresponding to t-SNE with the attraction increased even more. At the extreme of this spectrum lies Laplacian Eigenmaps, corresponding to zero repulsion. Our results demonstrate that many prominent neighbor embedding algorithms can be placed onto this attraction-repulsion spectrum, and highlight the inherent trade-offs between them. 

Under review as a conference paper at ICLR 2021
A UNIFYING PERSPECTIVE ON NEIGHBOR EMBEDDINGS ALONG THE ATTRACTION-REPULSION SPECTRUM
Anonymous authors Paper under double-blind review
ABSTRACT
Neighbor embeddings are a family of methods for visualizing complex high- dimensional datasets using kNN graphs. To find the low-dimensional embedding, these algorithms combine an attractive force between neighboring pairs of points with repulsive force between all points. One of the most popular examples of such algorithms is t-SNE. Here we empirically show that changing the balance between the attractive and the repulsive forces in t-SNE yields a spectrum of embeddings, which is characterized by a simple trade-off: stronger attraction can better represent continuous manifold structures, while stronger repulsion can better represent discrete cluster structures. We find that UMAP embeddings correspond to t-SNE with increased attraction; mathematical analysis shows that this is because the negative sampling optimisation strategy employed by UMAP strongly lowers the effective repulsion. Likewise, ForceAtlas2,, commonly used for visualizing developmental single-cell transcriptomic data, yields embeddings corresponding to t-SNE with the attraction increased even more. At the extreme of this spectrum lies Laplacian Figenmaps, corresponding to zero repulsion. Our results demonstrate that many prominent neighbor embedding algorithms can be placed onto this attraction-repullion spectrum, and highlight the inherent trade-offs between them.
INTRODUCTION
T-distributed stochastic neighbor embedding (t-SNE) (van der Maaten & Hinton, 2008) arguably among the most popular methods for low-dimensional visualizations of complex high-dimensional datasets. defines pairwise similarities called affinities between points in the high-dimensional space and aims to arrange the points in low-dimensional space to match these affinitics (Hinton & Roweis, 2003). Affinities decay exponentially with high- nigh-diimessonal distance, making them infinitesimal for most pairs of points and making the n affinity matrix effectively sparse. Efficient implementations of t-SNE suitable for large sample sizes n (van der Maaten, 2014; Linderman et al., 2019) explicitly truncate the affinities and use the d-nearost-neighhoor (kNN) graph of the data with k < n as the input.
We use the term neighbor embeddling (NE) to refer to all dimensionality reduction methods that operate the kNN graph of the data and aim preserve neighborhood relationships (Yang et al., 2013; 2014). A prominent recent example of this class of algorithms is UMAP (McInnes et al., 2018). which has become popular in applied fields such as single-cell transcriptomies (Becht al., 2019). is based on stochastic optimization and typically produces more compact clusters than t-SNE.
Another example of neighbor embeddings are force-directed graph layouts (Noack, 2007: 2009), originally developed for graph drawing. One specific algorithm called ForceAtlas2 (Jacomy et al., 2014) has recently gained popularity the single-cell transcriptomic community to visualize datasets capturing cells at different stages of development (Weinreb et al., 2018; 8; 2020; Wagner et al., 201 Sa; Tusi et al., 2018; Kanton et al., 2019; Sharma et al., 2020).
Here we provide a unifying account of these algorithms. We studied the spectrum of t-SNE embeddings that are obtained when increasing/decrrasinng the attractive forces between kNN graph neighbors, thereby changing the balance between attraction and repulsion. This led to trade-off between faithful representations of continuous and discrete structures (Figure 1). Remarkably, we found that ForceAtlas2 and UMAP could both be accurately positioned on this spectrum (Figure 1). For UMAP, we used mathematical analysis and Barnes-Hoe Hut re-implementation to show that increased attraction is due to the negative sampling optimisation strategy.

---

Under review as a conference paper at ICLR 2021
Laplacian Eigenmaps
Stronger sttraction
Stronger repulsion
I-SNE (p= 1)
100
p 30
Be
Eig 1
ForceAtlas2
UMAP
Eig 7
Eig
Figure 1: Attraction-repulsion spectrum for the MNIST data. Different embeddings of the full MNIST dataset of hand-written digits (n 70 000); colors correspond the digit value as shown in the t-SNE panel. Multiplying all attractive forces by an exaggeration factor yields spectrum of embeddings. Values below 1 yield inflated clusters. Small values above yield more compact clusters. Higher values make multiple clusters merge, with p Insets show two subsets of digits separated in higher Laplacian eigenvectors. UMAP is very similar p 4. ForceAtlas2 is very similar to p = 30.
corresponding to Laplacian Eigenmaps.
2 RELATED WORK
Various trade-offs in t-SNE generalizations have been studied previously (Yang et al., 2009; Kobak al., 2020; Venna et al., 2010; Amid et al., 2015; Amid & Warmuth, 2019; Narayan et al., 2015; Im et al., 2018), but our work is the first to study the innggeration-inducee trade-off. Prior work used 'early exaggeration" only as an optimisation trick (van der Maaten & Hinton, 2008) that allows to separate well-defined clusters (Linderman & Steinerberger, 2019; Arora et al., 2018).
Perreira-Perpinnn (2010) introduced elastic embeddiing algorithm that has an explicit parameter controlling the attraction repulsion balance. However, that paper suggests slowly increasing À during optimization, as an optimisation trick similar to the early exaggeration, and does not discuss tradeoffs between high and low values of X.
Our results on UMAP go against the common wisdom on what makes UMAP perform as does (MeInnes et al., 2018 8; Becht et al., 2019). No previous work suggested that negative sampling may have a drastic effect on the resulting embedding.
3 NEIGHBOR EMBEDDINGS
We first cast t-SNE, UMAP, and ForceAtlas2 in a common mathematical framework, using consistent notation and highlighting the similarities between the algorithms, before investigate the relationships between them empirically and analytically in more detail. We denote the original high-dimensional points x; and their low-dimensional positions y:.
3.1 T-SNE
T-SNE measures similarities between points by affinities vi and normalized affinities Piy:
Palj + + 2
||x: x1
Pij
0ig
PIR
Σ ΣkSt Ukjs
Uziec = exp
20
(1)
For fixed i, Pyje is probability distribution all points j * (all Piji are zero), and the variance of the Gaussian kernel of is chosen to yield pre-specified value of the perplexity
2

---

Under review as a conference paper at ICLR 2021
of this probability distribution, P = 2 where H. - Piji log2 Pyji- The affinities Vij normalized by for Pij form probability distribution the set of all pairs of points (i. Modern implementations (van der Maaten, 2014; Linderman et al., 2019) construct KNN graph with 3P neighbors and only consider affinities between connected nodes non-zero. The default perplexity value in most implementations is p = 30.
Similarities in the low www-dimensional space are defined as
Wij Z
1 Wij
1 1+ d
dij Ily: 1151-, Z
Σ legh
wkl,
with all qu set to O. The points are then rearranged in order to minimise the Kullback-Leibler (KL) divergence DKL ((pi)) {qs))) = =E Eig Pij log (pts/qs) between Pij and giz²
LNNEE
Σ Pij log
Wij
Σ Pij log way log Σ Wejs
where we dropped constant terms and took into account that Σps = 1. The first term can be interpreted as contributing attractive forces to the gradient while the second term yields repulsive forces. Using owiy S0ug/0y. /0y, -2wfy (y: -y;), the gradient, up to a constant factor, can be written as:
0h. SNE
Σ Vigwnlyy - ys) z
n Σ
nh wf -y)-
(4)
oy,
3.2 EXAGGERATION IN T-SNE
standard optimisation trick for I-SNE called early exaggeration (van der Maaten & Hinton, 2008;
van der Maaten, 2014) is to multiply the first sum in the gradient by factor م = 12 during the initial iterations of gradient descent. This increases the attractive forces and allows similar points to gather into clusters more effectively. Carreira-Perpinaa (2010) and Linderman & Steinerberger (2019) noticed that the attractive term the t-SNE loss function related to the loss function of Laplacian eigenmaps (LE) (Belkin & Niyogi, 2002: Coifman & Lafon, 2006). Indeed, if p -> co, the relative repulsion strength goes to zero and the embedding shrinks to a point with all Wiy + 1. This implies that, asymptotically, gradient descent becomes equivalent to Markov chain iterations with the transition matrix closely related to the graph Laplacian (here D is diagonal matrix with sums of V; Appendix). The entire embedding shrinks to single point, but the leading eigenvectors of the Laplacian shrink the slowest. This makes t-SNE with P do produce embeddings very similar LE, which computes the leading eigenvectors of the normalized Laplacian (see Appendix and Figure 1).
V of the affinity matrix V = [Wiy]
This theoretical finding immediately suggests that it might be interesting to study t-SNE with exaggeration p > 1 not only as an optimisation trick, but in itself, as an intermediate method between LE and standard t-SNE. The gradient of (-SNE with exaggeration can be written
@LssNE(P) Qy:
Σ
Vig w - y,)
Σ w (y:
y,)
(5)
pz
and the corresponding loss function is
(P)NE(p) DRL (1pi) (wg//
Σ
Più
log Pij Wij/ Wiz/ 7
(6)
2.
3.3 UMAP
Using the same notation as above, UMAP optimizes the cross-entropy loss between Vig and wij. without normalizing them into probabilities:
LUMAP
Σ
Uig log Wij
Vij
+ (1 V1z) log Ukj
1 Wij
3

---

Under review as a conference paper at ICLR 2021
where the 1 - May term is approximated by 1 most Uay O. Note that UMAP differs from t-SNE in how exactly it defines tij but this difference is negligible, at least for the data considered here.
Dropping constant terms, obtain
LUMAP Σ Vig log wij - Σ log(1 way), 1.
which is the same loss function as the one introduced earlier by LargeVis (Tang et al., 2016). The first term, corresponding to attractive forces, is the same as in t-SNE, but the second, repulsive, term is different. Taking Wij = 1/(1 + d2y) as in t-SNE,2 the UMAP gradient is given by
tLUMAP oy:
Σ Digwinll - y,) - Σ
di + wis(y; -y)),
(9)
where e = 0.001 is added to the denominator to prevent numerical problems for dy R 0. cf 1 (which does not strongly affect the result; Figure S1). the gradient becomes identical to the t-SNE gradient, up to the n/Z factor in front of the repulsive forces. Moreover, UMAP allows to use an arbitrary y factor in front of the repulsive forces, which makes it easier to compare the loss functions
@LUmAP(7)
Σ Usyung (y: - y2)
Σ
Wey Wey(y: (y: - -j))
(10)
oy,
d + 3
Whereas it is possible to approximate the full repulsive term with the same techniques used in t-SNE (van der Maaten, 2014; Linderman et al., 2019), UMAP took a different approach and followed LargeVis in using negative sampling (Mikolov et al., 2013) of repulsive forces: on each gradient descent iteration, only a small number v of randomly picked repulsive forces are applied to each point for each of the ~ attractive forces that it feels. Other repulsive terms are ignored. The default value is V = 5. The effect of this negative sampling on the resulting embedding has not been studied before.
3.4 FORCEATLAS2
Force-direes directed graph layouts are usually introduced directly via attractive and repulsive forces, even though it is easy to write down suitable loss function (Noack, 2007). ForceAtlas2 (FA2) has attractive forces proportional to diy and repulsive forces proportional to 1/ds (Jacomy et al., 2014):
ŌLrAZ oy:
(h: + 1) 1) (y, (y),
Σ Uisly: - -y) Σ
(11)
&
where h; denotes the degree of node in the input graph. This is known as edge repulsion in the graph layout literature (Noack, 2007; 2009) and is important for embedding graphs that have nodes of very different degrees. For symmetrized KNN graphs, h₁ Re k, so (h; + 1)(h, + 1) term contributes a roughly constant factor of ~i to the repulsive forces.
3.5 IMPLEMENTATION
All experiments performed in Python. We ran all packages with default parameters, unless specified. We used openTSNE 0.4.4 (Policar et al., 2019), a Python reimplementation of FIt-SNE (Linderman et al., 2019). When using p < 12, we used the default early exaggeration with Pearly 12, and exaggeration for all subsequent iterations. For 2 12 no early exaggeration was used and exaggeration P was applied throughout. The learning rate was set 11 nt/ max(p, Pearly) (Belkina et al., 2019). We used UMAP 0.4.0 with Cauchy similarity kernel (i.c. setting a=b=1). For
'T-SN uses an adaptive Gaussian kernel with default P = 30 and A: = 90. UMAP uses an adaptive Laplacian kernel with default & = 15. We found that for both algorithms one can use binary affinities with h = 15 without noticeably changing the outcome. Specifically, we used the kNN (k- 15) adjacency matrix A [a.y] to construct symmetric binary affinities Vij (a:, a,x)/k. k. When using these values, the S-SNE
UMAP embeddings stayed almost the same (Figure S1).
2UMAP uses wi = 1/(1 + ad?)) as output kernel with R 1.6 and b as 0.9 by default. Setting
b 1 does not qualitatively affect the result (Figure S1).
$ LargeVis used 7 7 but UMAP sets 7 by default, follows from its cross-entropy loss.
4

---

Under review as a conference paper at ICLR 2021
Laplacian Eigenmaps
b p 30
p=2
d
I-SNE
10
ForceAtias2
UMAP
step
step 10
stop 20
10000
Figure 2: Simulated data emulating a developmental trajectory. The points were sampled from 20 isotropic 50-dimensional Gaussians, equally spaced along axis such that only few inter-cluster edges exist in the kNN graph. Panels (b-f) used a shared random initialization.
FA2, we used fa2 package (Chippada, 2017) that employs a Barnes-Hut approximation to speed up computation of the repulsive forces. The input FA2 was the unweighted symmetrized approximate KNN graph A V A where is the kNN adjacency matrix constructed with Annoy (Bernhardsson, 2013) with i 15. All algorithms were optimized for 750 iterations, unless stated otherwise.
Unless stated otherwise, we used principal component analysis (PCA) initialisation to remove any differences due initialization strategies (Kobak & Linderman, 2019) and make all embeddings of the same dataset aligned to each other (Kobak & Berens, 2019). PCs 1/2 were scaled to standard deviation 0.0001 for t-SNE and span 10 for UMAP to match the initialization scalings used the respective implementations, and to standard deviation of 10 000 for ForceAtlas2 to approximately match its final scale. Figure uses random initialization. LE was computed using scikit Walkit-leand tllearn (Pedregosa et al., 2011) implementation (Spectral Entttrainmmeddding)..... The input was the same the input to FA2. No initialisation was needed for LE. We flipped the signs of LE eigenvectors to orient them similarly to other embeddings, whenever necessary.
4 THE ATTRACTION-REPULSION SPECTRUM
We first investigated the relationships between the NE algorithms using the MNIST dataset of hand-written digits (sample size n 70 000; dimensionality 28 x 28 784, reduced to 50 with PCA: Figure 1). T-SNE produced an embedding where all digits were clearly separated into clusters with little white space between them, making it difficult to assess relationships between digits. Increasing attraction to p = 4 shrank the clusters and strongly increased the amount white space; it also identified two groups of graphically similar digits: "4/7/9" and "3/5/8"". Further increasing the attraction p 30 made all clusters connect together via some poorly written digits: e.g. cluster "6" connects to "5" and to "O". Even higher exaggeration made the embedding similar to Laplacian eigenmaps, in agreement with the theoretical prediction discussed above (I.nneerman et al., 2019). Here similar digit groups like "4/7/9" were entirely overlapping, and could only be separated using higher eigenvectors (Figure 1, insets). On the other side the spectrum, exaggeration values 0 p resulted in inflated coalescing clusters.
Interestingly, we observed that FA2 produced an embedding nearly identical to the one at = 30, while UMAP produced embedding nearly identical to the one p 4. Decreasing the value in UMAP had the same effect as increasing the p in t-SNE, and moved the UMAP result towards the LE part of the spectrum (Figure S2).
5

---

Under review as a conference paper at ICLR 2021
Laplacian Eigenmaps
b p= 30
p=4
d
I-SNE
10
ForceAtias2
UMAP
0 days
4 days
days
days
month
2 months
monthss
10000
Figure 3: Neighbor embeddings of the single-cell RNA-seq developmental data. Cells were sampled from human brain organoids (cell line 409b2) seven time points between 0 days and months into the development (Kanton et al., 2019). Sample size n = 20 272. Data were reduced with PCA to 50 dimensions. See Appendix for transcriptomic data preprocessing steps.
The MNIST example suggests that high attraction emphasizes connections between clusters at the cost of within-cluster structure, whereas high repulsion emphasizes the cluster structure at the expense of between-cluster connections. We interpreted this finding as a continuity continuity-diccrtteess discreteness trade-off. We developed simple toy example to illustrate this trade-off in more detail (Figure 2). For this, we generated data draws from 20 standard isotropic Gaussians in 50 dimensions, each shifted by standard deviation units from the previous one along one axis (1000 points per Gaussian, so 20 000 overall). For this analysis we used random initialization and turned the early exaggeration off, to isolate the effect of each loss function on the "unwrapping' of the random initial configuration.
We found that t-SNE with strong exaggeration (p 30) recovered the underlying one-dimensional manifold structure the data almost as well as LE (Figure 2a.b), and produced an embedding very similar to that of FA2 (Figure 2c). In both cases, the individual clusters were almost invisible. In contrast, embeddings with weaker attraction and stronger repulsion (t-SNE with exaggeration p and UMAP) showed individual clusters but were unable fully recover the 1-dimensional structure and only found some chunks of it (Figure 2c.f). Finally, standard t-SNE clearly showed 20 individual clusters but with the continuous structure entirely lost (Figure 2d).
Further, we analyzed a developmental single-cell transcriptomic dataset, where cells were collected from human brain organoids seven time points between 0 days and 4 months into the development (Kanton et al., 2019). In this kind of data, one expects to find rich cluster structure as well as a strong time-dependent trajectory. As in the other datasets. found that stronger attraction (LE, FA2, t-SNE with p 30) better represented the developmental trajectory, whereas stronger repulsion (standard t-SNE) better represented the cluster structure (Figure 3). Using much higher A for the kNN graph construction made the developmental trajectory in high-attraction methods even clearer (Figure S3), agreement with the FA2-based analysis performed in the original publication. We observed the same pattern in separate dataset obtained from chimpanzee brain organoids (Figures $4, S5).
To quantify our observations, we computed distance correlations (Szekely et al., 2007) between UMAP & FA2 embeddings and t-SNE embeddings with various values of p E [1, 100), using the three datasets analyzed above (Figure 4a). For UMAP, the best matches were at 3 < p < 8; for FA2, the best matches were 25 < p 65. The corresponding correlations were all above 0.97, indicating very similar layouts.
We confirmed all these findings using six other datasets (Table 1): Fashion MNIST (Figure S6), Kannada MNIST (Figure S7). Kuzushiji MNIST (Figure S8), single-cell data from hydra (Figure S9), from zebrafish embryo (Figure S10), and from mouse cortex (Figure $11), In most cases, UMAP

---

Under review as conference paper at ICLR 2021
Distarce correlatio
1.00
UMAP
10
Exop. (e)
10
1.00
ni(oz)
7-
Det. con.
nl(oz)
10"
0.95
Human organed Chirp organsid
10"
p=2
0.96
10
10
10
10
10
10"
5K
38k
70k
70k
Exeggeration factor (p)
Exag. factor (p)
Semple #ize
Semple size
Figure 4: (a) Distance correlation (Szekely et al., 2007) between UMAP/FA2 and t-SNE with various exaggeration values p [1, 100] (50 evenly distributed values a log scale). Distance correlation was computed using dcor package (Carreño, 2017) on random subset (n = 5 000) of data. Dots mark the maximum of each curve. (b) The n/(p factor in the end of optimisation when using t-SNE with & E 100] on full MNIST. (c) Distance correlations between t-SNE with E [1, 10] and UMAP depending on the sample size, for MNIST subsets of size n E [5 000, 70 000). Black line indicates best matching values. (d) The (/Z) factor in the end of optimisation when using t-SNE with p E {1, 2,3, 4] on MNIST subsets size n E 000, 70 000).
was similar to t-SNE with exaggeration p R and FA2 was similar to t-SNE with exaggeration p 30. Increasing attraction strength made the continuous structures increasingly prominent in the embeddings. See Figure S11 for the case when kNN graph had disconnected components.
INCREASED ATTRACTION IN UMAP DUE TO NEGATIVE SAMPLING
As shown above, the gradient of UMAP (Eq. 9) is very similar to the gradient of t-SNE (Eq. 4) but does not contain the 'normalizing' n/Z term front of the repulsive forces. What are the typical values of this coefficient? The Z term in t-SNE evolves during optimisation: it starts at Z x n² due to all dej Rs at initialization and decreases towards n as the embedding expands (for a perfect embedding with all P.j Øs and V/y Waj. the Z would equal n; in reality Z usually still exceeds n.. For MNIST, the final Z value was ~100n corresponding to the final n/Z = 0.01 (Figure 4b). Increasing the exaggeration shrinks the embedding and increases the final Z: it also changes the repulsive factor to np(p (Eq. 5). For
4, the final Z was 22100, corresponding to final n/ 0.0001 (Figure 4b). This means that UMAP matched t-SNE results with the repulsive factor 0.0001 better than it matched t-SNE results with the repulsive factor 0.01, even though UMAP itself repulsive factor : (Eq. 9). How is this possible?
We hypothesized that this mismatch arises because the UMAP implementation is based on negative sampling and does fact optimize its stated loss (Eq. 7). Instead, the negative sampling decreases the repulsion strength, creating an effective Yeal (v) < 1. We verified that increasing the value of
Table 1: Distance correlation values (R) between UMAP/FA2 and t-SNE.
UMAP
FA2
Dataset
=
max R
arg max, p R
30
max R
arg max, R
MNIST
0.985
0.985
3.7
0.982
0.983
26.8
Fashion MNIST
0.991
0.996
7.2
0.992
0.995
75.4
Kuzushiji MNIST
0.944
0.95
12.6
0.974
0.982
68.7
Kannada MNIST
0.936
0.952
11.5
0.976
0.978
12.6
Chimpanzee organoid
0.979
0.983
7.2
0.988
0.993
62.5
Human organoid
0.972
0.979
7.9
0.995
0.997
51.8
Hydra
0.98
0.986
16.8
0.981
0.993
22.2
Mouse cortex
0.95
0.957
12.6
0.985
0.986
29.5
Zebrafish embryo
0.974
0.982
8.7
0.995
0.996
42.9

---

Under review as a conference paper at ICLR 2021
y = 0.0001
b y= 0.01
C
y=1
y=0.01.E
e
Y= 1, EE
10
100
100
100
100
Figure 5: Barnes-Hut UMAP without negative sampling. (a-c) Embeddings with gamma values E {0.0001, 1). (d-e) Embeddings with gamma values y E (0.01,1) initialized with the embedding with 7 0.0001 [panel (a)], in an analogy early exaggeration in t-SNE.
increased the repulsion strength in UMAP (Figure S12): embeddings grew size and the amount of between-cluster white space decreased. We observed the same effect when setting e (Figure S13), which makes the UMAP gradient (Eq. 9) equivalent to the t-SNE gradient, up to the repulsion factor.
It is difficult to compute (v) analytically, but qualitatively the number of repulsive forces per one attractive force is ~n/k in the full gradient but y with negative sampling. This suggests that the "eff induced by the negative sampling should decrease with the sample size. To check this prediction, we looked at the behaviour of the n/(pZ) term as a function of sample size, for the best 000, 70 000),
matching P value. Using MNIST subsets of different sizes gave the t-SNE embedding best matching to the UMAP embedding for all considered sample sizes (Figure 4d). Looking now at the final n/ (pZ) values with p approximately as ~0(1/ T1) (Figure 4d), qualitatively confirming our prediction about "eff-
found that o 4
found that they decreased with
To confirm our interpretation, we developed Barnes-Hut UMAP implementation (based on openTSNE) that optimizes the full UMAP loss without any negative sampling (Figure 5). On full MNIST, y = 0.0001 yielded an embedding that resembled the standard seggatiee-smmlling-bbee UMAP (Figure 5a), while larger values of yielded over-repulsed embeddings (Figure 5b-c) and required early exaggeration to produce meaningful results (Figure 5d-e), with 7 = 0.01 resembling t-SNE and ? being over-repulsed compared to t-SNE. This suggests that directly optimizing the cross-entropy loss (Eq. 7) is not a viable NE strategy. Therefore, the more condensed clusters typically observed in UMAP compared to t-SNE are accidental by-product of UMAP's negative sampling strategy, and not a consequence of the cross-entropy loss function itself or the mathematical apparatus of the original paper (Mclnnes et al., 2018).
6 INCREASED ATTRACTION IN FA2 DUE TO NON-DECAYING ATTRACTIVE FORCES
The attractive forces in t-SNE scale as di5/(1 (1 + d. When all di are small, this becomes an approximately linear dependency on dij, which the reason why t-SNE with high exaggeration >>> 1 replicates Laplacian eigenmaps (see Section 3.2 and Appendix). For large distances dij. attractive forces in t-SNE decay zero, making default t-SNE very different from LE. In contrast, in FA2, attractive forces always scale as dij. Thus, the larger the embedding distance between points, the stronger the attractive force between them. This strong non- con-decaying attractive force makes FA2 behave similar to Laplacian eigenmaps on the attraction-repulsion spectrum.
Note that is not possible to move FA2 embeddings along the attraction-repulsion spectrum by multiplying the attractive repulsive forces by a constant factor (such as r in UMAP or in t-SNE). Multiplying attractive forces by any factor a or repulsive forces by any factor 1/a only leads to rescaling of the embedding by 1/ Va. Indeed, if all forces are in equilibrium before such multiplication and rescaling, they will stay in equilibrium afterwards. This is a general property of force-directed layouts where both attractive and repulsive forces scale as powers of the embedding distance. This argument also implies that removing the (h; + 1) + 1) x k22 factor from the FA2 gradient (Eq. 11) rescales the entire embedding by ~1 1/k; but does not change it otherwise (Figure S1).
8

---

Under review as conference paper at ICLR 2021
7 DISCUSSION
We showed that changing the balance between attractive and repulsive forces in t-SNE directly affects the trade-off between preserving continuous or discrete structures. Increasingly strong repulsion "brings out' information from higher Laplacian eigenvectors into the two embedding dimensions (Figure 1). It is remarkable that the repulsive forces, which are data-agnostic and do not depend on the input data (Carreira-Perpinán, 2010), have so much qualitative influence.
Our results suggest that should be beneficial for high-repulsion embeddings to begin optimization with lower repulsion strength, in order to better preserve global structure. This explains how UMAP benefits from its default initialization with Laplacian eigenmaps (Kobak & Linderman, 2019) and how t-SNE benefits from early exaggeration (Linderman & Steinerberger, 2019) (see Figure 514 for a demonstration of the importance of early exaggeration). Similarly, elastic embedding gradually increases repulsion strength during optimisation (Carreira-Perpinán, 2010).
Our treatment provided unified perspective on several well-known NE algorithms that have scalable implementations and that have been shown to successfully embed datasets such MNIST without coarse-graining the kNN graph. Methods based on coarse-grainin goarse-graining, such as c.g. PHATE (Moon al., 2019) latent variable NE method in Saul (2020) may behave differently. We believe that treatment may allow to position other NE algorithms on the same spectrum. For example, a recently suggested TriMap algorithm (Amid & Warmuth, 2019), which uses negative sampling similar to UMAP, appears to have stronger attractive forces than UMAP (cf. Figure in the original paper), with some TriMap embeddings, e.g. of the Fashion MNIST dataset, looking similar the ForceAtlas2 embeddings shown in our work.
We argued that negative sampling (Mikolov al., 2013) used by LargeVis/UMAP strongly lowers the effective repulsion. Negative sampling is closely related to the contraccneee estimation (NCE) framework (Gutmann Hyvärinen, 2012). NCE was recently applied to t-SNE under the name of NCVis (Artemenkov & Panov, 2020), and the general NCE theory asserts that it should be asymptotically equivalent to optimizing the full gradient (Gutmann Hyvärinen, 2012). We consider it very interesting research direction to study the relationship between negative sampling and NCE and their effect on 2D embeddings as well as on dimees-dimensional embeddings used in methods like word2vec (Mikolov et al., 2013).

---

Under review as conference paper at ICLR 2021
REFERENCES
Ehsan Amid and Manfred K Warmuth. Trimap: Large-scale dimensionality reduction using triplets. arXiv preprint 19Xi::1110.0000 2019.
Ehsan Amid, Onur Dikmen, and Erkki Oja. Optimizing the information retrieval trade-off in data visualization using a-divergence. arXiv preprint arXiv: 1505.0582. 2015.
Sanjeev Arora, Wei Hu, and Pravesh K Kothari. An analysis of the t-sne algorithm for data visualization. In Conference On Learning Theory, pp. 1455-1462, 2018.
Aleksandr Artemenkov and Maxim Panov. NCVis: Noise contrastive approach for scalable visualiza- tion. In The Web Conference, pp. 2941-2947, 2020.
Etienne Becht, Leland McInnes, John Healy, Charles-Antoine Dutertre, Immanuel WH Kwok, Lai Guan Ng, Florent Ginhoux, and Evan W Newell. Dimensionality reduction for visualizing single-cell data using UMAP. Nature Biotechnology, 37(1):38, 2019.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for emhedding and clustering. In Advances in Neural Information Processing Systems, pp. 585-591, 2002.
Anna C Belkina, Christopher O Ciccolella, Rina Anno, Richard Halpert. Josef Spidlen, and Jennifer E Mnyder-Cappione Automated optimized parameters for T-distributed stochastic neighbor embedding improve visualization and analysis of large datasets. Nature Communications, 10(1):1-12, 2019.
Erik Bernhardsson. Annoy. https://git thub. cow/ coom//potiff/aanoonoe 2013.
Miguel A Carreira-Perpinán. The elastic embedding algorithm for dimensionality reduction. In
International Conference on Machine Learning, volume 10, pp. 167-174, 2010.
Carlos Ramos Carreño. dcor: distance correlation and related E-statistics in Python. https: thub. com.uuuooooo/ooooo /wwaabusddoorr 2017.
Bhargav Chippada. forceatlas2: Fastest Gephi's ForceAtlas2 graph layout algorithm implemented for hww.arrgawccipppaaafoooee..e
Python and NetworkX. https://gi thubbbb...uub.....
2017.
Tarin Clanuwat, Mikel Bober- Irizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical japanese literature. arXiv preprint arxiv:1812.01718, 2018
Ronald R Coifman and Stéphane Lafon. Diffusson maps. Applied and Computational Harmonic Analysis, 21(1):5-30. 2006.
Michael U. Gutmann and Aapo Hyvärinen. Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. Journal of Machine Learning Research, 13 (11):307-361, 2012. 2012.
Geoffrey E Hinton and Sam T Roweis. Stochastic neighbor embedding. In Advances in Neural Information Processing Systems, pp. 857-864, 2003.
Daniel Jiwoong Im, Nakul Verma, and Kristin Branson. Stochastic neighbor embedding under f-divergences. arXiv preprini arXiv: 18//.04 2018.
Mathieu Jacomy, Tommaso Venturini, Sebastien Heymann, and Mathieu Bastian. ForceAtlas2, continuous graph layout algorithm for handy network visualization designed for the Gephi software. PloS One, 9(6), 2014.
Sabina Kanton, Michael James Boyle, Zhisong He, Malgorzata Santel, Anne Weigert, Fátima Minchís-Calleja Patricia Guijarro, Leila Sidow, Jonas Simon Fleck, Dingding Han, et al. Organoid single-cell genomic atlas uncovers human-specific features of brain development. Nature, 574 (7778):418 422, 2019.
Dmitry Kobak and Philipp Berens. The art of using t-SNE for single-cell transcriptomics. Nature Communications, 10:5416, 2019.
10

---

Under review as a conference paper at ICLR 2021
Dmitry Kobak and George C Linderman. UMAP does not preserve global structure any better than t-SNE when using the same initialization. bioRxiv, 2019.
Dmitry Kobak, George Linderman, Stefan Steinerberger, Yuval Kluger, and Philipp Berens. Heavy- tailed kernels reveal finer cluster structure in I-SNE visualisations. In Machine Learning and Knowledge Discovery in Databases, pp. 124-139. Springer International Publishing, 2020.
George C Linderman and Stefan Steinerberger. Clustering with t-SNE, provably. SIAM Journal on Mathematics of Data Science, 1(2):313-32, 2019.
George C Linderman, Manas Rachh, Jeremy G Hoskins, Stefan Steinerberger, and Yuval Kluger. Fast interpolation- t-SNE for improved visualization of single-cell RNA-seq data. Nature Methods, 16(3):243, 2019.
Leland McInnes, John Healy, and James Melville. UMAP: Uniform manifold approximation and projection for dimension reduction. arXiv: 080.00022460 2018
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems, pp. 3111-3119, 2013.
Kevin R Moon, David van Dijk, Zheng Wang, Scott Gigante, Daniel B Burkhardt, William S Chen, Kristina Yim, Antonia van den Elzen, Matthew Hirn, Ronald Coifman, et al. Visualizing structure and transitions in high-dimensional biological data. Nature Biotechnology. 37(12): 1482-1492, 2019.
Karthik S Narayan, Ali Punjani, and Pieter Abbeel. Alpha-beta divergences discover micro and macro structures in data. In International Conference on Machine Learning, pp. 796-804, 2015.
Andreas Noack. Energy models for graph clustering. Journal of Graph Algorithms and Applications, 11(2):453-480, 2007.
Andreas Noack. Modularity clustering is force-directed layout. Physical Review E, 79(2):226102, 2009.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, al. Scikit-learn: Machine learning in Python. The Journal of Machine Learning Research, 12:2825-2833 2011.
Pavlin Gregor Policar, Martin Strazar, and Blaz Zupan. opEnTSNE: modular Python library for t-SNE dimensionality reduction and embedding. bioRttiv:31877,. 2019.
Vinay Uday Prabhu. Kannada-mnist: A new handwritten digits dataset for the kannada language. arXiv preprint arXiv:1908.02220 012422, 2019.
Lawrence K Saul. A tractable latent variable model nonlinear dimensionality reduction. Proceedings of the National Academy of Sciences, 11((7)) 5403--55400 2020.
Nikhil Sharma, Kali Flaherty, Karina Lezgiyeva, Daniel E Wagner, Allon M Klein, and David D Ginty. The emergence of transcriptional identity in somatosensory neurons. Nature, pp. 1-7, 2020.
Stefan Siebert, Jeffrey A. Farrell, Jack F. Cazet, Yashodara Abeykoon, Abby S. Primack, Christine Schnitzler, and Celina E. Juliano. Stem cell differentiation trajectories in hydra resolved single-cell resolution, Science, 365(6451), 2019.
Gabor Szekely, Maria Rizzo, and Nail Bakirov. Mcasuring and testing dependence by correlation of distances. The Annals of Statistics, 35:2769-2794, 2007.
Jian Tang, Jingzhou Liu, Ming Zhang, and Qiaozhu Mei. Visualizing large-scale and high-dimensional data. In 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 Economo, Sarada Viswanathan, et al. Shared and distinct transcriptomic cell types across neocortical areas. Nature, 563(7729):72-788. 2018.

---

Under review as conference paper at ICLR 2021
Betsabeh Khoramian Tusi, Samuel L Wolock, Caleb Weinreb, Yung Hwang, Daniel Hidalgo, Rapolas Zilionis, Ari Waisman, Jun Huh, Allon M Klein, and Merav Socolovsky, Population snapshots predict early haematopoictic and erythroid hierarchies. Nature, 555(7694):54 60, 2018.
Laurens van der Maaten. Accelerating t-SNE using tree-based algorithms. The Journal of Machine Learning Research, 15(1):3221-3245, 2014.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9(Nov):2579 2605, 2008.
Jarkko Venna, Jaakko Peltonen, Kristian Nybo, Helena Aidos, and Samuel Kaski. Information retrieval perspective to nonlinear dimensionality reduction for data visualization. Journal of Machine Learning Research, :1445-490,, March 2010.
Ulrike Von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering. The Annals of Statistics, pp. 555-586, 2008.
Daniel E Wagner, Caleb Weinreb, Zach Collins, James Briggs, Sean Megason, and Allon M Klein. Single-cell mapping of gene expression landscapes and lineage in the zebrafish embryo. Science, 360(6392):981-988,, 2018a.
Daniel E. Wagner, Caleb Weinreb, Zach M. Collins, James A. Briggs, Sean G. Megason, and Allon M. Klein. Single-cell mapping of gene expression landscapes and lineage in the zebrafish embryo. Science, 360(6392 2018b. ISSN 0036-8075.
Caleb Weinreb, Samuel Wolock, and Allon M Klein. SPRING: a kinetic interface for visualizing high dimensional single-cell expression data. Bioinformatics, 34(7):1246-1245 2018.
Caleb Weinreb, Alejo Catriguez-Fraticelll Fernando Camargo, and Allon Klein. Lineage tracing on transcriptional landscapes links state fate during differentiation. Science, 367(6499), 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.077477 2017.
Zhirong Yang. Irwin King, Zenglin Xu, and Erkki Oja. Heavy-tailed symmetric stochastic neighbor
embedding. In Advances in Neural Information Processing Systems, pp. 2169-2177, 2009.
Zhirong Yang, Jaakko Peltonen, and Samuel Kaski. Scalable optimization of neighbor embedding for visualization. International Conference on Machine Learning, pp. 127-135, 2013.
Zhirong Yang. Jaakko Peltonen, and Samuel Kaski. Optimization equivalence divergences improves neighbor embedding. In International Conference Machine Learning, pp. 460-468. 2014.
12

---

Under review as a conference paper at ICLR 2021
APPENDIX
APPENDIX A. RELATIONSHIP TO LAPLACIAN EIGENMAPS
Laplacian eigenmaps Let a X symmetric matrix V contain pairwise affinities between n. points (or edge weights between nodes in an undirected graph). Let diagonal matrix D contain row (or, equivalently, column) sums of V, i.e. Da E, Vij. Then L = D V is known as (unnormalized) graph Laplacian, and Laplacian eigenmaps (Belkin & Niyogi, 2002) can be formulated as solving the generalized eigenvector problem
La = ADa
(12)
and taking the cigenvectors corresponding to the smallest eigenvalues (after discarding the trivial eigenvector [1, 1, ......1] 1] with eigenvalue zero). By multiplying both sides of this equation by D-1, the problem can be reformulated as finding the eigenvectors of D D-VV corresponding to the largest eigenvectors:
D-
A)a.
(13)
The matrix D D-VV not symmetric and has rows normalized the diffusion operator on the graph, making Laplacian eigenmaps equivalent to Diffusion maps (Coifman & Lafon, 2006). Another equivalent way to rewrite it, is to define normalized Laplacian Imorm = D-1/2DD 1/2 and solve an eigenvector problem Loorm b = Ab, where 1
can be interpreted as
t-SNE without repulsion In the limit of p - oo, the repulsive term in the t-SNE gradient can be dropped, all Wy + 1, and hence the gradient descent update rule becomes (Linderman & Steinerberger, 2019)
y = y: - Σ Cig(ys
(14)
where É indexes the iteration number and 7) is the learning rate (including all constant factors in the gradient). Denoting by Y the n x 2 matrix of the embedding coordinates, this can be rewritten as
y = (I - [I- + vV)Y
(15)
= -YY
(16)
M is the transition matrix of this Markov chain (note that it is symmetric and its rows and columns sum to I; its values are all non-negative for small enough 11). According to the general theory of Markov chains, the largest eigenvalue of M is 1, and the corresponding eigenvector is [1, 1,... 1]T meaning that the embedding shrinks to a single point (as expected without repulsion). The slowest shrinking eigenvectors correspond to the next eigenvalues. This means that when - co, the embedding (if rescaled, to avoid shrinking to zero) will converge to the leading nontrivial eigenvectors of M. This becomes equivalent to a power iteration algorithm. The eigenvectors of M are the same as of = D V, which is the unnormalized graph Laplacian of the symmetric affinity matrix.
Note that this is not precisely what LE computes: explained above, finds eigenvectors of the normalized graph Laplacian (c.f. Von Luxburg et al., 2008). However, in practice D is often approximately proportional to the identity matrix, because V obtained via symmetrization of directed affinities, and those have rows summing to I by construction. We can therefore expect that the leading eigenvectors of L and of Laym are not too different. We verified that for MNIST data they were almost exactly the same.
Note also that nothing prevents different columns of Y to converge to the same leading eigenvector: each column independently follows its Markov chain. Indeed, we observed that for large enough values of p and large enough number of gradient descent iterations, the rescaled two-dimensional embedding collapsed to one dimension. This is the expected limiting behaviour when م -> co. However, for moderate values columns of Y resemble the two leading non-trivial eigenvectors of the Laplacian. The repulsive force prevents the embedding from collapsing to the leading Laplacian eigenvector. At the same time, a weak repulsive force will only be able to 'bring out' the second LE eigenvector. The stronger the contribution of repulsive forces, the more LE eigenvectors it would be able to 'bring out' (remember that the attractive force acts stronger the higher eigenvectors).
(as shown in this manuscript), this typically does not happen, and
13

---

Under review as a conference paper at ICLR 2021
Loss function of LE The original Laplacian eigenmaps paper (Belkin & Niyogi, 2002) motivated the eigenvector problem by considering
LLE Σ biy oilll: y; -
(17)
This expression can trivially minimized by setting all y: = O, so the authors introduced a quadratic constraint Y DY I, yielding the generalized eigenvector problem. We note that different quadratic constraint Y would yield simple eigenvector problem for L. In any case, the constraint plays the role of the repulsion in t-SNE framework.
APPENDIX B. DATA SOURCES AND TRANSCRIPTOMIC DATA PREPROCESSING
Transcriptomic datasets The brain organoid datasets (Kanton et al., 2019) were downloaded form of UMI counts and metadata tables. The metadata table for the chimpanzee dataset was taken from the supple- mentary materials the original publication. We used gene counts mapped to the consensus genome, and selected all cells that passed quality control by the original authors (in FullLineage-RRUE in metadata tables). For human organoid data, we only used cells from the 409b2 cell line, to simplify the analysis (the original publication combined cells from two cell lines and needed perform batch correction).
from https://www ebi ac uk/ surraayepress/exxerineeet -ETAAItt//EE-----SS-- M-A--TTAB2
The hydra dataset (Siebert et al., 2019) (Figure S9) was downloaded in form of UMI counts from http:acc.ccccccccccee1..
https://www.nchl. nlm.nih. www...o....e.eee
The zebrafish dataset (Wagner al., 2018b) (Figure S10) downloaded in form of UMI counts from https://kleinttolls hms harvard.
haadd
The adult mouse cortex dataset (Tasic et al., 2018) (Figure S11) was downloaded in form of read counts from http://cellttyps.. brainn-app prg/api/v2/werr
694413985 and http:://ceely//eeeeeeee watpppeesbbaiinn-ee brain-map org/api /v2p /t/wwellwwlee wel_/oooooooooo_____e wwwooonnoillllooooeoollloollllle www.eedwwlleleeeeeeeeeeellelelea lownload/ 694413179 for the VISp and ALM cortical areas, respectively. Only exon counts were used here. The cluster labels and cluster colors were retrieved from http://celltypes. brain-map org/ rnaseq/mouse/vl-
To preprocess each dataset, we selected 1000 most variable genes using procedure from Kobak Berens (2019) with default parameters (for the mouse cortex dataset we used 3000 genes and threshold=32 (Kobak & Berens, 2019)) and followed the preprocessing pipeline from the same paper: normalized all counts by cell sequencing depth (sum gene counts in each cell), multiplied by the median cell depth (or million in case of mouse cortex data), applied log2(1 + 1) transformation, did PCA, and retained 50 leading PCs.
MNIST-like datasets The datasets used in Figures S6, S7, and S8 have been published explicitly to function as drop in replacements for the handwritten MNIST dataset. The dataset variants that used here all consist of total classes. The input has been preprocessed like the original MNIST dataset, i.c. reduced to 50 dimensions via PCA. Fashion and Kuzushiji MNIST were downloaded via OpenML. with the keys Fashi Mushion-MNISS (https:// org.e/4191g////1 respectively. Kannada MNIST was downloaded from https: //github wwtp://ayaaaaaabaaaaaaaaaaaaaa MNIST.
70 000 images of 28 28 pixels, 10 balanced
wttp////gg/////// and Kuzushi ji -NIIST (https:
14

---

Under review as a conference paper at ICLR 2021
SUPPLEMENTARY FIGURES
a
Default I-SNE
b
I-SNE, KNN affin. = 15)
FA2. Repulsion by degree
FA2. Fixed repulsion
10
10
10000
1000
e
Default UMAP
f
UMAP. b
UMAP, a == = 1, KNN affin.
UMAP, a = b= 1, KNN affin., == 1
10
10
10
Figure S1: Different algorithmic choices, demonstrated using MNIST. (a) Default t-SNE embed- ding, perplexity 30. (b) T-SNE embedding with binary kNN affinities, k 15. All non-zero affinities have equal size. The Pij values were normalized as always in I-SNE, and sum to one. (c) Default ForceAtlas2, using binary symmetrized KNN adjacency matrix (k 15) as input. ForceAtlas2 uses so-called repulsion by degree by default. (d) ForceAtlas2 without repulsion by degree. (e) Defaut
UMAP embedding. This uses default values for and b parameters, and LE initialization. (f) UMAP embedding with PCA initialization and Cauchy kernel (a b = 1). (g) UMAP embedding with PCA initialization, Cauchy kernel, and binary kNN affinities (k: 15). (h) UMAP embedding with PCA initialization, Cauchy kernel, binary kNN affinities, and 1.
y=1
y= 0.1
y= 0.01
d
y= 0.001
10
Figure S2: Decreasing the repulsion in UMAP. (a) UMAP embedding of MNIST with 7 (default). (b-d) Decreasing produces the same effect as increasing the exaggeration p in t-SNE. Values y 1 are not shown because we found that it was difficult achieve well-converged embedding for y >> 1.
15

---

Under review as conference paper at ICLR 2021
Laplacian Eigenmaps
b p= 20
p p=
1-SNE
10
ForceAtias2
UMAP
0 days
4 days
days
days
month
2 months
10000
Figure S3: Neighbor embeddings the single-cell RNA-seq developmental data (human, high k). Cells were sampled from human brain organoids (cell line 409b2) at seven time points between 0 days and 4 months into the development (Kanton et al., 2019). Sample size n 272 Data were reduced with PCA to 50 dimensions. See Appendix for transcriptomic data preprocessing steps. LE, FA2, and UMAP used = 150 (instead of our default k = 15), while t-SNE used perplexity 300 (instead of our default 30).
Laplacian Eigenmaps
b
p 40
p=7
t-SNE
12
e
ForceAtlas2
UMAP
0 days
4 days
days
days
month
2 months
months
months
10000
10
Figure $4: Neighbor embeddings of the single-cell RNA-seq developmental data (chimpanzee). Cells were sampled from chimpanzee brain organoids at eight time points between days and months into the development (Kanton et al., 2019). Sample size 36 884. Data were reduced with PCA to 50 dimensions. See Appendix for transcriptomic data preprocessing steps.
16

---

Under review as conference paper at ICLR 2021
Laplacian Eigenmaps
b p=
p=
t-SNE
10
10
e
ForceAllas2
UMAP
days
4 days
10 days
15 days
2 months
3 months
months
10000
10
Figure S5: Neighbor embeddings of the single-cell RNA-seq developmental data (chimpanzee, high k). Cells were sampled from chimpanzee brain organoids at eight time points between 0 days and months into the development (Kanton et al., 2019). Sample size n 36 884. Data were reduced with PCA to 50 dimensions. See Appendix for transcriptomic data preprocessing steps. LE, FA2, and UMAP used 150 (instead of our default k: 15), while t-SNE used perplexity 300 (instead of our default 30).
a Laplacian Eigenmaps
==
==4
d
I-SNE
ForceAlias2
UMAP
Distance baton 1
1.00
T-shirt
bation
Pullover
Dress
0.95
Coal
Shirt
UMAP
Sweater
0.90
Bag
10
10
10
Ankle
10000
10
Exaggamation factor (p)
Figure S6: Fashion MNIST dataset (Xiao et al., 2017). Sample size 70 000. Dimensionality was reduced to 50 with PCA. Colors correspond to 10 classes, see legend.
17

---

Under review as conference paper at ICLR 2021
Laplacian Eigenmaps
p= 30
p
d
t-SNE
10
ForceAtias2
UMAP
1.00
Distanne carrelation
0.95
FA2
UMAP
0.90
10"
10
10
1O000
10
Exaggeration factor (p)
Figure S7: Kannada MNIST dataset Prabhu (2019). Sample size = 70 000. Dimensionality
was reduced 50 with PCA. Colors correspond 10 Kannada digits shown in panel (d).
Laplacian Eigenmaps
p=
p
t-SNE
ForceAtias2
UMAP
1.00
Distunce correbation
FA2
0.95
0.90
10
10
10000
Exaggeration factor (p)
Figure S8: Kuzushiji MNIST dataset (Clanuwat et al., 2018). Sample size 70000. Dimen-
sionality was reduced to 50 with PCA. Colors correspond to 10 Kanji characters shown in panel (d).
18

---

Under review as conference paper at ICLR 2021
Laplacian Eigenmaps
3=
p=4
t-SNE
ForceAtias2
UMAP
1.00
Distance correlation
0.95
endodemm
ectoderm
inie
0.90
10"
10"
10000
Exaggeration factor (p)
Figure S9: Single-cell RNA-seq data of hydra (Siebert et al., 2019). Sample size 24 985. Dimensionality was reduced to 50 with PCA. See Appendix for transcriptomic data preprocessing steps. Color corresponds cell classes.
a Laplacian Eigenmaps
p = 30
p
d
t-SNE
ForceAtlas2
UMAP
1.00
Distance correlation
hpt
hof
0.85
hpt
10 hpt
UMAP
18 hpf
0.90
24 hpf
10
10'
Exaggaration factor (p)
Figure S10: Single-cell RNA-seq data of a zebrafish embryo (Wagner et al., 2018b). Sample size 63 530. Dimensionality was reduced to 50 with PCA. See Appendix for transcriptomic data preprocessing steps. Color corresponds to the developmental stage, indicating the hours post fertilization (hpf).
19

---

Under review as conference paper at ICLR 2021
a Laplacian Eigenmaps
p= 30
p=4
t-SNE
10
ForceAtias2
UMAP
Distance correlation
0.85
FA2
UMAP
0.90
10
10
10000
10
Exaggeration factor (p)
Figure S11: Single-cell RNA-seq data of adult mouse cortex (Tasic et al., 2018). Sample size 23 822. Dimensionality was reduced to 50 with PCA. See Appendix for transcriptomic data preprocessing steps. Colors are taken from the original publication (warm colors: inhibitory neurons; cold colors: excitatory neurons; grey/brown: non-neural cells). We added Gaussian noise to the LE embedding panel (a) to make the clusters more visible. In this dataset, the kNN graph is disconnected and has components, resulting in distinct points in the LE embedding.
a t-SNE, p=
b
UMAP, v=
UMAP, V = 500
d UMAP, == 2000
e
--NE
Figure S12: The effect of negative sampling rate on UMAP embeddings. (a) T-SNE embedding with p MNIST subsample with 6000. (b-d) UMAP embeddings with (5, 500, 2000]. We used a 6000 subset of MNIST as it would take prohibitively long to run optimisation with high v on the full MNIST dataset. We increased the number of iterations to ensure convergence (n_epochs=3000) and initialized UMAP runs with the default UMAP embedding (in analogy to early exaggeration in t-SNE). (e) Standard t-SNE of the same data.
Exag. L-SNE,
b
UMAP, v=
UMAP, U= 500,
UMAP, == 2000.
e
t-NE
p
10
100
100
10
Figure S13: The effect of negative sampling rate UMAP embeddings with c= 1. (a) t-SNE embedding with = 4 of MNIST subsample with n 6000. (b-d) UMAP embeddings with E (5, 500, 2000) and e 1. Here UMAP was run for 3000 epochs to ensure convergence, and was initialized with the default UMAP embedding (v 5 with 500 epochs). (e) Standard t-SNE of the same data.
20

---

Under review as a conference paper at ICLR 2021
a
With early exaggeration Initial std 0.0001
b Without early exaggeration Initial std 0.0001
c
With early exaggeration Initial = 25
ai
Figure S14: The effect of early exaggeration t-SNE. (a) Default t-SNE embedding of MNIST. This uses early exaggeration and sets the standard deviation of PCA initialization to 0.0001. (b) T-SNE embedding without early exaggeration. This embedding is stuck in suboptimal local minimum with some clusters split into multiple parts. (c) T-SNE embedding with early exaggeration, but with initial standard deviation set to 25. The attractive forces too weak pull the clusters together during the early exaggeration phase.
21


Reviews:
[{"review_id": "hpF4F3Ru7Qs", "reviewer": "AnonReviewer3", "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": "Summary: the authors study a number of neighbor embedding methods in terms of attraction-repulsion forces. The authors show that t-SNE, UMAP, FA2, and LE can be (approximately) unified as a common approach that use different levels of tradeoff between these two terms. They also discuss the increased attraction in UMAP as a result of negative sampling.\n\n\nReview: a main portion of the technical contribution of the paper is simply writing down the gradients of the commonly used DR methods and providing an intuitive comparison of gradient terms. However, there is not much rigorous mathematical result to support the claim. I am aware of the complexity of such a strong theoretical result (e.g. the work of (Arora et al. 2018)). However, the current version of the paper does not offer any concrete result and remains on an intuition level observation. The experiments partially support the claims, but similar observations have been made before in related work. For instance, (Amid and Warmuth 2019) qualitatively sort DR methods by means of their \"global score\" (which is a notion of how well a method preserves cluster information).\n\nA minor note on the experiments: in order to eliminate the bias in initializing some methods with PCA, I encourage the authors to also consider random (shared) initialization for all methods (Kobak and Linderman 2019). Also, since the paper is mainly experimental, (larger scale) experiments on a more diverse set of datasets would improve the paper. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "fs3rsMxolh8", "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 paper studies an early-exagerration constant \\rho that trades-off the attraction vs repulsion parts of the manifold learning algorithms at the early steps of optimization.\n\nThe paper provides a comparative analysis of objective functions for several manifold learning algorithm through the lights of effect of \\rho. It shows that the embedding of UMAP and ForceAtlas2 could be roughly recovered using t-SNE with a special choice of \\rho. The paper also proposes an explanation why UMAP works better when initialized from LE and why t-SNE gets better results from early exaggeration. All the analysis is done on a single MNIST dataset .\n\nThe paper seem very incremental in nature, since Elastic Embedding (Carreira-Perpiñan, 2010) already studied the effect of \\rho in a very similar manner to the findings proposed in the paper. The paper, however, only briefly covers that paper, mentioning the algorithm only in he Discussion section.\n\nThe authors added the analysis between t-SNE and most recent UMAP and ForceAtlas2 algorithms, but most of the novelty about the effect of \\rho and the connections to LE and early exaggeration are quite apparent. Most importantly, the paper doesn't propose any new algorithm or any improvements beyond insights. Even those are defined very vaguely. For example, it is not clear to me, ho the authors define \"high-repulsion embeddings\" and how much lower the repulsion strength should be.\n\nFinally, the result on a single MNIST dataset are not very general nor conclusive. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "WtN4Vw7aT02", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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:\nIn this paper, a unified view of embedding methods for visualization is presented. The main message is that, Laplacian eigenmaps and t-SNE are governed by a single formula, and the difference of them can be seen as a difference of a hyperparameter value. We can also approximately recover two different embedding methods --- UMAP and ForceAtlas2. Using a few benchmark data sets, the relationships of these methods are visualized.\n\n\nDetailed comments:\nFirst of all, I have almost no experience to study visualization methods, and my assessments, especially towards non-technical parts, could be biased. \n\nThe main result --- a general equation that covers several embedding methods --- is technically interesting. However, it would be not clarified what kind of benefits we can get from the finding. A possible direction is to tune $\\rho$ so that we can get the most effective visualization. Is it possible to do something like this?\n\nAnother concern is that it is not easy to judge the visualization results (e.g. Fig 2) because they are qualitative and subjective. To prove the significance of this study, more quantitative results that everyone can understand would be necessary.\n\n\nMinor comments:\n- $\\sim$ in Eq. (3) seems to mean the equality up to constant but such usage would be not common. It would be better to add an explanation. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ca1UUOJ07L", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Authors of this paper conducted study on existing neighbor embedding methods from the perspective of the attraction-replusion spectrum. \n\nPros:\n1)\tExtensive experiments demonstrate the phenomena that neighbor embedding methods can achieve the continuous manifold structures or discrete clustering structures by varying the balance parameter.\n2)\tDetailed implementations of existing methods are taken into account for the analysis, so it is a good guideline for users of these methods on real applications.\n\nCons:\n1)\tThe novelty of this paper seems limited. The attraction-replusion property is not new to the existing neighbor embedding methods. \n2)\tAuthors conducted various experiments to show the property, but the conclusion is only empirical.\n3)\tAuthors may need to demonstrate how these observations can make improvement over the existing methods or motivate new models.\n4)\tTo better demonstrate the continuous manifold or discrete clustering structures, authors can take various real data with clear underlying manifold structures that have been studied in the literature. Simulation data is good, but it is less real since the noise may significantly affect the experimental results.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: 
This paper analyzes several neighbor embedding methods-- t-SNE, UMAP, and ForceAtlas2-- by considering their objectives as consisting of attractive and repulsive terms. The main hypothesis is that stronger repulsive terms contribute towards learning discrete structures, while stronger attractive terms contribute towards learning continuous/manifold structures. The paper empirically explored the space parameterized by the relative weighting of the attractive and repulsive terms for the t-SNE and UMAP algorithms, using several data sets, and qualitatively confirmed their conclusions about the impact of the attractive and repulsion terms as the relative weights vary. 

The experimental validation of the paper's main hypothesis is thorough and the use of diverse data sets and neighbor embedding methods is appreciated-- as the authors point out, several reviewers missed this contribution. However, several reviewers point out that the insight presented in the paper is already largely present in the literature, and that beyond its analysis the paper does not present new algorithms based on this insight. The authors rebut this claim by arguing that the novelty of the paper lies in it: (1) showing the contrary to the established opinion, UMAP works despite, instead of because, it uses cross-entropy loss, and (2) the paper offers for the first time a theoretical understanding of why ForceAtlas2 highlights continuous developmental trajectories, and (3) prior work has not made the connection between UMAP, ForceAtlas2, and t-SNE or suggested using exaggeration throughout the optimization process for t-SNE rather than simply as a warm-up. The paper does indeed present intuitions for (1)-(3) based on the attraction-repulsion ideas, and makes the connection between these neighbor embedding algorithms by viewing them as variations on the theme of attraction-repulsion, but these intuitions are not significant steps forward with respect to what is already known about how neighbor embeddings balance attraction and repulsion. The mathematical analyses consist of stating the gradient for the algorithms and explaining how weighing the attraction and repulsion terms differently lead to different qualitative observations. The use of exaggeration throughout the optimization process is straightforward, and no strong mathematical characterization of the properties of the resulting algorithm is given.

It is recommended that this paper be rejected, as it consists of a thorough empirical validation of an understanding of the trade-off between attractive and repulsive forces in neighbor embedding methods that was already present in the literature, along with some straightforward arguments connecting several popular neighbor embedding methods, but does not introduce any significantly new actionable insights or novel algorithms.

Decision: Reject