From $t$-SNE to UMAP with contrastive learning
Authors: Sebastian Damrich
Niklas Böhm
Fred A Hamprecht
Dmitry Kobak
Venue: ICLR 2023 poster (2023)
Keywords: visualization
dimensionality reduction
t-SNE
UMAP

Abstract: Neighbor embedding methods $t$-SNE and UMAP are the de facto standard for visualizing high-dimensional datasets. Motivated from entirely different viewpoints, their loss functions appear to be unrelated. In practice, they yield strongly differing embeddings and can suggest conflicting interpretations of the same data. The fundamental reasons for this and, more generally, the exact relationship between $t$-SNE and UMAP have remained unclear. In this work, we uncover their conceptual connection via a new insight into contrastive learning methods. Noise-contrastive estimation can be used to optimize $t$-SNE, while UMAP relies on negative sampling, another contrastive method. We find the precise relationship between these two contrastive methods, and provide a mathematical characterization of the distortion introduced by negative sampling. Visually, this distortion results in UMAP generating more compact embeddings with tighter clusters compared to $t$-SNE. We exploit this new conceptual connection to propose and implement a generalization of negative sampling, allowing us to interpolate between (and even extrapolate beyond) $t$-SNE and UMAP and their respective embeddings. Moving along this spectrum of embeddings leads to a trade-off between discrete / local and continuous / global structures, mitigating the risk of over-interpreting ostensible features of any single embedding. We provide a PyTorch implementation.

Published as a conference paper at ICLR 2023
FROM t-SNE TO UMAP WITH CONTRASTIVE LEARNING
Sebastian Damrich
Jan Niklas Böhm
IWR at Heidelberg University
University of Tübingen
sebast ain. daw.diiiiae caarrichunis - tuebi ngen.
jan-niklas bww.m@unt tuubi ingennnn.
Fred A. Hamprecht
Dmitry Kobak
IWR at Heidelberg University
University of Tübingen dmitry www.kkknn---ueiingeeeeennn
fred. hamprecht Biwr. uni ani-heidelberg
ABSTRACT
Neighbor embedding methods t-SNE and UMAP are the de facto standard for visualizing high-dimensional datasets. Motivated from entirely different view- points, their loss functions appear to be unrelated. In practice, they yield strongly differing embeddings and can suggest conflicting interpretations the same data. The fundamental reasons for this and, more generally. the exact relationship be- tween t-SNE and UMAP have remained unclear. In this work, we uncover their conceptual connection via new insight into contrastive learning methods. Noise- contrastive estimation can be used to optimize 1-SNE, while UMAP relies on neg- ative sampling, another contrastive method. We find the precise relationship be- tween these two contrastive methods and provide mathematical characterization of the distortion introduced by negative sampling. Visually, this distortion results in UMAP generating more compact embeddings with tighter clusters compared to I-SNE. We exploit this new conceptual connection to propose and implement a generalization of negative sampling, allowing us to interpolate between (and even extrapolate beyond) t-SNE and UMAP and their respective embeddings. Moving along this spectrum of embeddings leads to trade-off between discrete / local and continuous global structures, mitigating the risk of over- over-interpreting ostensible features of any single embedding. We provide PyTorch implementation.
INTRODUCTION
Low-dimensional visualization of nigh-dimensional data is ubiquitous step in exploratory data analysis, and the toolbox of visualization methods has been rapidly growing in the last years (Mclnnes al. 2018 Amid & Warmuth] 2019; (Szueert al. 2019 Wang al.) 2021). Since all of these methods necessarily distort the true data layout (Chari et al. 2021). it is beneficial have various tools one's disposal. But only equipped with a theoretic understanding of the aims of and relationships between different methods, can practitioners make informed decisions about which visualization use for which purpose and how to interpret the results.
The state of the art for non paramaaraeec non- non-lineat linear dimensionality reduction relies on the neighbor embedding framework (Hinton & Roweis 2002). Its two most popular examples are t-SNE (van der Maaten & Hinton 2008 vaa der Maaten 2014) and UMAP (McInnes et al. 2018). Both can produce insightful, but qualitatively distinct embeddings. However, why their embeddings are different and what exactly is the conceptual relation between their loss functions, has remained clusive.
Here, we answer this question and thus explain the mathematical underpinnings of the relationship between i-SNE and UMAP. Our conceptual insight naturally suggests spectrum of embedding methods complementary to that of Böhm et al. (2022), along which the focus of the visualization shifts from local to global structure (Fig. 1). On this spectrum, UMAP and t-SNE are simply two instances and inspecting various embeddings helps to guard against ever-interpretation of apparent structure. As practical corollary, analysis identifies and remedies instability in UMAP.

---

Published as a conference paper at ICLR 2023
Default NEG
(a) Z -
(b) Z -
(c) Z NCVs
(d) Z |
(e) 2
> |x/mm
10
10
10'
10
10'
10"
Z
6
(c)
(0)
9
10
(8)
(b)
10
10
10
(f) t-SNE
(g) NCVis
(h) UMAP
(i) Partition function
Figure 1: (a-e) Neg-t-SNE embedding spectrum of the MNIST dataset for various values of the fixed normalization constant Z, see Sec. 5 As Z increases, the scale of the embedding decreases, clusters become more compact and separated before eventually starting to merge. The Neg-t-SNE spectrum produces embeddings very similar to those of (f) i-SNE, (g) NCVis, and (h) UMAP, when 2 equals the partition function of I-SNE, the learned normalization parameter Z of NCVis, or |X|/m /m (22) /mm used by UMAP, as predicted Sec. 4 (i) The partition function (1+
tries to match Z and grows with it. Here, we initialized all Neg-t-SNE runs using = [ with-
this 'early exaggeration', low values of Z yield fragmented clusters (Fig. S11
We provide the new connection between t-SNE and UMAP via deeper understanding of contrastive learning methods. used optimize t-SNE (Artemenkov & Panov] 2020 while UMAP relies on another contrastive method, negative sampling (NEG) (Mikolov et al. 2013). We investigate the discrepancy between NCE and NEG, show that NEG introduces distortion, and this distortion explains how UMAP and (-SNE embeddings differ. Finally, we discuss the relationship between neighbor embeddings and
estimation (NCE) Gutmann & Hyvärinen, 2010: 2012) can be
self-supervised learning (Wu et al. 2018 He et al. 2020 Chen et al. 2020
Le-Khac et al. 2020).
In summary, contributions are
a new connection between the contrastive methods NCE and NEG (Sec.
2. the exact relation of t-SNE and UMAP and remedy for instability in UMAP (Sec. 6
'contrastive' neighbor embeddings encompassing UMAP and t-SNE (Sec. 5). 4. a connection between neighbor embeddings and self supervuee learning (Sec.
a spectrum
5. a unified Py Torch framework for contrastive (prammmariietrric neighte embedding methods.
Our code is available at httpss///gtthbbb.cm//rrrrrss https: http:////tttbbbbb http:/hciiuuiihhhh------ll
ivv and
2 RELATED WORK
One of the most popular methods for data visualization is t-SNE van der Maaten Hinton 2008
van der Maaten 2014). Recently developed NCVis (Artemenkov & Panov] (0220) employs noise-
contrastive estimation (Gutmann & Hyvärinen] 2010 2012) to approximate I-SNE in a sampling- based way. Therefore, will often refer to the NCVis algorithm as 'NC-t-SNE' UMAP (MeInnes
cet al., 2018) has matched t-SNE's popularity at least in computational biology (Becht et al. 2019) and uses another sampling-based also employed by LargeVis Vis (Tang et al. 2016). Other recent sampling- based visualization methods include TriMap (Amid & Warmuth 2019) and PaCMAP (Wang al. (02T).
optimization method, negative sampling (Mikolov et al. 2013).
Given their success, t-SNE and UMAP have been scrutinized to find out which aspects are essen- tial to their performance. Initialization found to be strongly influencing the global structure
2

---

Published as a conference paper at ICLR 2023
in both methods (Kobak & Linderman 2021). The exact choice of the low-dimensional similarity kernel (Böhm et al.] 2022) or the weights of the n-ieabrst-neighhor graph (Damrich & Hamprecht, 2021 were shown to be largely inconsequential. Both algorithms have similar relevant hyperpa- rameters such as, e.g., the heavy-tailedness of the similarity kernel Yang et al. 2009 Kobak et al. 2019).
While not obvious from the original presentations, the central difference between t-SNE and UMAP can therefore only be in their loss functions, which have been studied by [Damrich & Hamprecht [202T]: Böhh et al. 22022;; ; Wang et al. (2021). but never conceptually connected. We achieve this by deepening the link between negative sampling (NEG) and conse-contrastive estimation (NCE).
NEG was introduced as an ad hoc replacement for NCE in the context of learning word embed- dings (Mikolov et al., 2013). The relationship between NEG and NCE has been discussed be- fore (Dyer [014]] & Goldberg [2014) Ruder 2016) Ma & Collins 2018 Ke-Khac et al. 2020), but here we go further and provide precise meaning of NEG: We show that, unlike NCE, NEG learns model proportional but not equal to the true data distribution.
Both I-SNE and UMAP have parametric versions (van der Maaten 2009 Sainburg et al. 2021) with very different logic and implementations. Here we present unified Py PyTorch framework for non- parametric and parametric contrastive neighbor embeddings. As special cases, includes UMAP
and t-SNE approximations with NCE (like NCVis) and the InfoNCE loss (Jozefowicz et al. 2016 van den Oord et al. 2018), which has not yet been applied to neighbor embeddings.
Our resulting InfoNC-I-SNE elucidates the relationship between SimCLR (Chen et al. 2020) and neighbor embeddings. The parallel work of et al. (2023) makes a qualitatively similar argument, but does not discuss negative samples. Balestriero & LeCun (2022) show how SimCLR recovers Isomap (Tenenbaum et al. 2000), while we connect SimCLR to more modern neighbor embeddings.
3 BACKGROUND
3.1
NOISE-CONTRASTIVE ESTIMATION (NCE)
The goal of parametric density estimation to a parametric model qa to iid samples $1,..., S.N from an unknown data distribution over space X. For maximum likelihood estimation (MLE) the parameters 0 are chosen to maximize the log-likelihood of the observed samples
N
0t arg max
> log (s)().
t=1
This approach crucially requires Qo be a normalized model. It is otherwise trivial to increase the likelihood arbitrarily by scaling qg. To circumvent the expensive computation of the partition function (00) Exex (0(x). Gutmann & Hyvärinen (201 2012) introduced NCE. It turns the unsupervised problem of density estimation into a supervised problem in which the data samples need to be identified from set containing the N data samples and times many noise sam- ples ti,... f1,...tm. inN drawn from a noise distribution &, c.g., the uniform distribution over X. Briefly, NCE fits by minimizing the binary cross-entropy between the true class assignment and posterior probabilities P(data| | .r) = /0(x)/ (goll)//)())))))) + mmf(x) and P(noise| xx) = 1 - P(data .x) (Supp. A.1
go(3))
m/
log (1-
ge(t)) qu(l.) + (
0" arg min
Σ log g0(3;) +
(2)
The key advantage of NCE is that the model does not need to be explicitly normalized by the partition function, but nevertheless learns to equal the data distribution p and hence be normalized:
Theorem (Gutmann& & Hyvärinen (2010, 2012)). Let & have full support and suppose there exists some 0* such that qa- = p. Then 6" a minimum of
NCE (0) = - log (0(()) + mE(s)
go(s)
En log (1
go())
(3)
40 (1) + mm(l))
and the only other extrema of CNC are minima Ô which also satisfy 48 p.
3

---

Published as a conference paper at ICLR 2023
In NCE, the model typically includes an optimizable normalization parameter Z which we empha- size by writing qe = ge/Z. But importantly, Thm. applies to any model qo that is able to match the data distribution p. even if it does not contain a learnable normalization parameter.
In the setting of learning language models, Jozefowiez et al. (2016) proposed a different version of NCE, called InfoNCE. Instead of classifying samples data noise, the aim here is to predict the position of a data sample in an (m + -tuple containing m noise samples and one data sample (Supp. A.2 For the uniform noise distribution E, this yields the expected loss function
(0
C InfooNCF (0)
log
(0(x))
E.=1 go(m;)
Ma & Collins 2018 showed that an analogue of Thm. 1 applies to InfoNCE.
3.2 NEIGHBOR EMBEDDINGS
Neighbor embeddings (NE) (Hinton Roweis 2002) are a group of dimensionality reduction methods, including UMAP, NCVis, and I-SNE that aim to find a low-dimensional embedding el....,Ey En E Rd of high-dimg high-dimensional input points Ii,..... In E RP, with D > d and usually d 2 for visualization. NE methods define notion of similarity over pairs of input points which encodes the neighborhood structure and informs the low-dimensional embedding.
The exact high- -igheemeenion similarity distribution differs between the NE algorithms, but recent work (Böhm et al., 2022; Damrich& & Hamprecht (202I) showed that t-SNE and UMAP results stay practically the same when using the binary symmetric k-nnearest-neighbor graph (skNN) instead of I-SNE's Gaussian or UMAP's Laplacian similarities. An edge ij is in s&NN if x; is among the nearest neighbors of n, or vice versa. The high-dimensional similarity function is then given by p(ij) = ((j E skNN)/ is the indicator function. NCVis uses the same similarities. We will always use 15.
skNN)/|sANN; | where |sKNN denotes the number of edges in the skNN graph and
There are further differences in the choice of low-dimensional similarity between t-SNE and UMAP, but Böhm et al. (2022) showed that they are negligible. Therefore, here we use the Cauchy kernel p(des) = L/dd + +1) for all NE methods to transform distances du = lle; eyll in the embedding space into ciw-dimensional similarities. We abuse notation slightly by also writing ((i)) = o(dr)).
All NE methods in this work can be cast in the framework of parametric density estimation. Here, is the data distribution to be approximated with model go. meaning that the space X on which both p and yo live is the set of all pairs ij with S j S n. The embedding positions ét, EI,..... en become the learnable parameters 0 of the model qo- For I-SNE, NC-I-SNE (NCVis), and UMAP, go is proportional to @([le, - e, but the proportionality factor and the loss function are different.
(-SNE uses MLE and therefore requires normalized model (ij) (it)//((0) where (00) = Ekyt @kl) is the partition function. The loss function
CI.SNB(0) (0) -EEgpp log (ge (it) - (pli)) log (o(ij)) log (E,, kedel (kll)
(5)
is the expected negative log likelihodo of the embedding positions 6, making t-SNE an instance of MLE. Usually t-SNE's loss function is introduced as the Kullback-Leible divergence between p and go. which is equivalent as the entropy of p does not depend on A.
NC-+-SNE uses NCE and optimizes the expected loss function
(ij)
-mEejr log 1 (1))
[ CNC-I-SNE (0, 00 -Bjssp log
(0,)( + mi(i))
q9, (0)) +
(6)
where q9.z ( = ((i))/Z with learnable Z and is approximately uniform (see Supp. D
According to Thm. [ NC-I-SNE has the same optimum as I-SNE and can hence be seen as a sampling-basse based approximation of t-SNE. Indeed, we found that in NC-+-SNE and the partition function Z00) in t tNE converge approximately to the same value (Fig. S10).
UMAP's expected loss function is derived in Damrich Hamprecht (021
UMAP (0) - Enjop log (go (i)) -m..rj-s log (1 90 (i)).
4

---

Published as a conference paper at ICLR 2023
with go())) o(ij) and & is approximately uniform, see Supp. D This is the effective loss function actually implemented in the UMAP algorithm, but note that has only about m/n of the repulsion compared to the loss stated in the original UMAP paper (Melnnes et al. 2018), as shown in Böhm
et al. 2022) and Damrich & Hamprecht (021) (Supp.
In practice, the expectations in UMAP's and NC-I-SNE's loss functions evaluated via sampling, like in Eq. (2) This leads to a fast, (n), stochastic gradient descent optimization scheme. Both loss functions are composed of an attractive term pulling similar points (edges of the s&NN graph) closer together and a repulsive term pushing random pairs of points further apart. Similarly, L-SNE's loss yields attraction along the graph edges while repulsion arises through the normalization term.
FROM NOISE-CONTRASTIVE ESTIMATION TO NEGATIVE SAMPLING
In this section we work out the precise relationship between NCE and NEG, going beyond prior work (Dyer, 2014; Goldberg & Levy, 2014; [evy & Goldberg 2014, Ruder 2016). NEG differs from NCE by its loss function and by the lack of the learnable normalization parameter Z. In our setting, NEG's loss function amounts tc]
[g(x) (0(x)) (0(())+)== mIE log (1- go(x))
(x( +1 )
C. NBG (0) = -uzup log
(8)
In order to relate it to NCE's loss function, our key insight is to generalize the latter by allowing to learn model that is not equal but proportional to the true data distribution.
Corollary 2. Let Z, m E R... Let & have full support and suppose there exist some 8 such that qe- Zp. Then 0* is a minimum of the generalized NCE loss function
(o(x)) ZmE(x)) ) -mEuw log (1-
go (x)
go(x))
(2) = (0)= -Eewp log
(9)
2o (0(x)) + Zme(x))
and the only other extrema of C are minima 0 which also satisfy qB = Zp.
Proof. The result follows from Thm. applied to the model distribution qa :- /0/ 22
Dyer (2014) and Ruder (2016) pointed out that for a uniform noise distribution {(z) 1/|x| and as many noise samples as the size of X (m = |X]), the loss functions of NCE and NEG coincide, since (x) = 1. However, the main point of NCE and NEG to use far fewer noise samples in order to attain speed-up over MLE. Our Cor. 2 for the first time explains NEG's behavior in this more realistic setting (m < [X). If the noise distribution uniform, the generalized NCE loss function with Z X equals the NEG loss function since (IXI/m)mE(a = 1. By Cor. 2 any minimum 8* of the NEG loss function yields qe- = ([X) //. assuming that there are parameters that make this equation hold. In other words, NEG aims find model qo that is proportional to the data distribution with the proportionality factor ||/m which is typically huge. This different from NCE, which aims learn model equal to the data distribution.
Choosing m < | does not only offer a computational speed-up but is necessary when optimizing NEG for neural network with SGD, like we do in Sec Only one single mini-batch passed through the neural network during each iteration and is thus available for computing the loss. Hence, all noise samples must come from the current mini-batch and their number is upper-bounded by the mini- batch size b. bini-batches are typically much smaller than X Thus, this common training procedure necessitates m & |X| highlighting the relevance of Cor.
While NCE uses model qo /Z with learnable Z, we can interpret NEG as using model go 7 with fixed and very large normalization constant Z = | As a result, qo in NEG needs to attain much larger values to match the large Z. This can be illustrated in the setting of neighbor embeddings. Applying NEG to the neighbor embedding framework yields an algorithm that we call 'Neg-t-SNE'. Recall that in this setting, XX| (2) is the number of pairs of points. [öhhm et al. (2022) found empirically that (-SNE's partition function Z0) is typically between 50n and 100n, while in Neg-t-SNE, 7- (n²) is much larger for modern big datasets. To attain the larger values of o(ij) required by NEG, points that are connected in the s&NN graph have to move much closer
We focus the loss function, ignoring Mikalov al. 2013 s choices specific word embeddings.
5

---

Published as a conference paper at ICLR 2023
10
10
10
(a) UMAP, no annealing (b) UMAP with annealing
(c) Neg-I-SNE, no ann.
(d) Neg-I-SNE with ann.
Figure 2: Embeddings of the MNIST dataset with UMAP and Neg-t-SNE with and without learning rate annealing in our implementation. UMAP does not work well without annealing because it im- plicitly uses the diverging 1/d kernel in NEG, while Neg-t-SNE uses the more numerically stable Cauchy kernel (Sec. 6 UMAP's reference implementation also requires annealing, see Figs. Sla
together in the embedding than in t-SNE. Indeed, using our PyTorch implementation of Neg-t-SNE on the MNIST dataset, we confirmed that Neg-t-SNE (Fig. Id] produced more compact clusters than tNE (Fig. [r.. See Supp. K and Alg. for implementation details.
We emphasize that our analysis only holds because NEG has learnable normalization parameter Z. If did, then such a Z could absorb the term 7 in Eq. (9. leaving the parameters 0" unchanged.
5 NEGATIVE SAMPLING SPECTRUM
Varying the fixed normalization constant 2 in Eq. (9) has important practical effects that lead to whole spectrum of embeddings in the NE setting. The original NEG loss function Eq. (8) corre- sponds to Eq. (9) with 2 = |X1/mm. We still refer to the more general case of using an arbitrary Z Eq. 99 as 'negative sampling' and 'Neg-I-SNE" the context of neighbor embeddings.
Figs. a show a spectrum of Neg-t-SNE visualizations of the MNIST dataset for varying Z. Per Cor. 2. higher values of Z induce higher values for ge. meaning that points move closer together. Indeed, the scale of the embedding decreases for higher Z as evident from the scale bars in the bottom-right corner of each plot. Moreover, clusters become increasingly compact and then even start to merge. For lower values of Z the embedding scale is larger and clusters more spread out. Eventually, clusters lose almost any separation and start to overlap for very small Z.
Cor. 2 implies that the partition function Σg (o(x) should grow with Z, and indeed this is what observed (Fig. lip. The match between the sum of Cauchy kernels Ee, <(ij) and Z was not perfect,
but that was expected: The Cauchy kernel is bounded by 1 from above, so values Z > (2) are not matchable. Similarly, very small values of Z are difficult to match because of the heavy tail of the Cauchy kernel. See Supp.[[for toy example where the match is perfect.
By adjusting the value, one can obtain Neg-t-SNE embeddings very similar to NC-I-SNE and I-SNE. If the NC-I-SNE loss function Eq. (6) has its minimum at some 0" and NNC---SNE then the Neg-t-SNE loss function Eq. 9 with Z NN--t-SNE is minimal at the same l" We con- firmed this experimentally: Setting Z NC---SNE yields a Neg-t-SNE embedding (Fig. [c] closely resembling that of NC-I-SNE (NCVis) (Fig. Ig.. Similarly, setting Z to the partition function ((05-SN)), obtained by running t-SNE, yields Neg-t-SNE embedding closely resembling that of t-SNE (Figs. lb i We used kNN recall and correlation between pairwise distances for quantitative
confirmation (Supp. H).
The SNE spectrum is strongly related to the attraction-repulsion spectrum of Böhm al. 20022. They introduced a prefactor ('exaggeration') to the attractive term in t-SNE's loss, which increases the attractive forces, and obtained embeddings similar to our spectrum when varying this parameter. We can explain this as follows. The repulsive term in the NCE loss Eq. ( has prefactor and our spectrum arises from the loss Eq. (9) by varying Z in the term Zm. Equivalently, our spectrum can be obtained by varying the m value (number of noise samples per spectrum arises from varying
one s&NN edge) while holding 2m fixed (Fig. S8). In other words, the repulsion strength in the contrastive setting, while Böhm et al. (2022) obtained the analogous spectrum by varying the repulsion strength in the I-SNE setting (see also Supp. B.2

---

Published as a conference paper at ICLR 2023
6 UMAP's CONCEPTUAL RELATION TO t-SNE
Our comparison of NEG and NCE in Sec. 4 allows us for the first time to conceptually relate UMAP and t-SNE. Originally, McInnes et al. 2018) motivated the UMAP algorithm by specific choice of weights on the skNN graph and the binary cross-entropy loss. Following LargeVis (Tang et al., 2016). they implemented a sampling-basee scheme which they referred to as 'negative sampling, although UMAP's loss function Eg. (7) does not look like the NEG loss Eq. (8) Thus, it has been unclear if UMAP actually uses Mikoloov et al. (2013)'s s NEG. Here, we settle this question:
Lemma 3. UMAP's loss function (Eq.
7 is NEG (Eq. with the parametric model ğo(it) 1/dfy Proof. Indeed, qo (it) = 1/(1 + d
+ = (1000o((()))) (o(i))/ +1).
L
Lem. tells us that UMAP uses NEG but not with a parametric model given by the Cauchy kernel.
Instead it uses a model qo. which equals the inverse squared distance between embedding points.
For large embedding distances dij both models behave alike, but for nearby points they strongly differ: The square kernel 1/df, diverges when di + 0. unlike the Cauchy kernel 1/(1+dff)) Despite this qualitative difference, we found empirically that UMAP embeddings look very similar to Neg-I-SNE embeddings at 2 |X|/m, see Figs. Id and h for the MNIST example.
To explain this observation, it is instructive to compare the loss terms of Neg-t-SNE and UMAP: The attractive term amounts to - log (1/(d) + 1)) = log(1 + df,)) for UMAP and loo [1/ + (1/ +) + 1)] = log d(j) for Neg-t-SNE, while the repulsive term equals log (11 dt df.)) and log ((2 + df (L)))(1 )f respectively. While the attractive terms are similar, the repulsive term for UMAP diverges at zero but that of Neg-t-SNE does not (Fig. S7 Supp. B.2). This divergence introduces numerical instability into the optimization process of UMAP.
We found that UMAP strongly depends on annealing its learning rate down to zero (Figs. 2a
Without it. clusters appear fuzzy noise pairs can experience very strong repulsion and get cat- apulted out of their cluster (Fig. 2a). While Neg-t-SNE also benefits from this annealing scheme (Fig. 2dl it produces very similar embedding even without any annealing (Fig. Thus, UMAP's effective choice of the 1/dł, kernel makes it less numerically stable and more dependent on opti-
mization tricks, compared to Neg-I-SNE 2 See Supp. E for more details.
Our conclusion is that at its heart, UMAP is NEG applied to the I-SNE framework. UMAP's sampling-bass based optimization is much more than mere optimization trick; it enables to con- nect it thcoretically to t-SNE. When UMAP's loss function is seen as an instance of NEG, UMAP does not the Cauchy kernel but rather the inverse-square kernel. However, this does not make strong difference due to the learning rate decay. As discussed in Sec. 4 the fixed normalization con- stant Z in Neg-t-SNE/ / UMAP is much larger than the learned Z in NC-t-SNE or t-SNE's partition function. This explains why UMAP pulls points closer together than both NC-I-SNE and i-SNE and the reason for the typically more compact clusters in UMAP plots (Böhm et al. 2022)
CONTRASTIVE NE AND CONTRASTIVE SELF-SUPERVISED LEARNING
Contrastive self ceffssuerriieed representation learning (van den Oord et al. 2018 Tian et al. 2020 He et al., 2020 Chen et al. 2020 Caron et al.) 2020) and 'contrastive neighbor embeddings' (a term we suggest for NC-I-SNE, Neg-t-SNE, UMAP, etc.) are conceptually very similar. The key difference is that the latter use a fixed ANN graph to find pairs of similar objects, while the former rely data augmentations or context to generate pairs of similar objects on the fly. Other differences include the representation dimension (~ 128 vs. 2), the use of a neural network for parametric mapping, the flavor of contrastive loss (InfoNCE vs. NCE/ / NEG), and the number of noise samples m. However, these other differences are not crucial, we establish here with unified Py Porch framework.
As an example, we demonstrate that t-SNE can also be optimized using the InfoNCE loss, re- sulting in 'InfoNC-I-SNE' (Supp. K and Alg. [S].. Its result on MNIST was similar to that of NC-I-SNE (Figs. 36 ch For the default number of noise samples, m = 5, the embeddings of both
RReeentyy, pull request to UMAP's GitHub repository effectively changed the kernel of parametric UMAP the Cauchy kernel, in order to overcome numerical instahilities via ad hoc fix, see Supp.
7

---

Published as a conference paper at ICLR 2023
10
10
10
(a) Neg-t-SNE
(b) NC-I-SNE
(c) InfoNC-4-SNE
10
T0X00
(d) Param. Neg-t-SNE
(c) Param. NC-E-SNE (f) Param. InfoNC-t-SNE
Figure 3: NE embeddings of MNIST are qualitatively similar in the non-parametric (top) and para- metric settings (bottom). We used our PyTorch framework with m = 5 and batch size = 1024.
algorithms were visibly different from t-SNE proper (Fig. If Recent work in self-supervised learn-
ing (Chen et al.) 2020) reports improved performance for more noise samples, in agreement with the theory of Gutmann & Hyvärinen 2012) and Ma & Collins (2018). We observed that both NC-t-SNE
and InfoNC-t-SNE with m 500 approximated t-SNE much better (Figs. [ST8K and [ST9k]. Like I-SNE, but unlike the m 5 setting, = 500 required early exaggeration to prevent cluster fragmentation (Figs. S18 and STT).. We discuss InfoNC-I-SNE's relation to TriMap in Supp. F
Next, we used our py PyTorch framework to obtain parametric versions of all contrastive NE algo- rithms discussed here (NC-I-SNE, InfoNC-I-SNE, Neg-t-SNE, UMAP). We used a fully connected neural network with three hidden layers parametric RD - I2 mapping and optimized its pa- rameters using Adam (Kingma & Ba 2015) (Supp. Kj. We used batch size = 1024 and sampled all m negative samples from within the batch: the dataset was shuffled each epoch before batch- ing. Using all four loss functions, we were able to get parametric embeddings MNIST that were qualitatively similar their non-parametric versions (Fig. 3 The parametric versions of NCE and InfoNCE produced much larger embeddings than their non-parametric counterparts, however the final loss values were very similar (Figs. [59a bj. For NCE, the larger scale of the parametric em- bedding was compensated by a smaller learned normalization parameter Z, so that both parametric and non-parametric versions were approximately normalized (Fig. (Sc).. Our parametric UMAP implementation is very similar to that of (Sannuug et al.] (2021). But our parametric, approximate t-SNE implementations strongly differ from the parametric t-SNE of van der Maaten (2009), which constructed separate kNN graphs within each batch and optimized the vanilla I-SNE loss function.
Neighbor embeddings methods achieve impressive results with only few noise samples, while exis- tent common practice in the self-supervised learning literature (Bachman et al.) 2019 Chen et al.) 2020 He et al. 2020) recommends very large m. As a proof of concept, we demonstrate that using only = 16 non-curated (Wu et al. 2017 Roth et al. 2020) noise samples can suffice for image- based self-supervised learning. We used a SimCLR setup (Chen et al.] 2020) to train representations of the CIFAR- 10 dataset (Krizhevsky) 2009) using ResNet18 (He et al.] 2016)) backbone, fixed batch size of = 1024 and varying number of noise samples m. Other implementation details
Table 1: Test set classification accuracies on CIFAR- 10 representations obtained with InfoNCE loss and batch size b 1024 saturate already at low number of noise samples m. common for neighbor embeddings. We used the Re output H e R and report mean + std across three seeds.
m =
m = 16
m = 128
m = 512
m = 2b 2
nNN classifier
86.9 + 0.2
91.7 + 0.1
92.0 + 0.3
92.2 + 0.2
91.9 + 0.1
Linear classifier
90.7 = 0.2
93.1 + 0.2
93.3 0.3
93.2 + 0.3
93.3 + 0.1
8

---

Published as a conference paper at ICLR 2023
follow Chen al. (2020)'s 's CIFAR-10 setup (Supp. K.4) The classification accuracy. measured on the ResNet output, saturates already at m = 16 noise samples (Tab. D. Note that, different from the original SimCLR setup, we decoupled the batch size from the number of noise samples. Re- cent work found conflicting evidence when varying m for a fixed batch size (Mitrovic et al., 20000 Nozawa & Sato, 202T] Ash al., 2022). Future research is needed to perform more systematic benchmarks into the importance of m. Here, we present these results only as proof of principle that a similarly low m as in neighbor embeddings (default m = 5) can work in a SimCLR setting.
DISCUSSION AND CONCLUSION
In this work, we studied the relationship between two popular unsupervised learning methods, noise- contrastive estimation (NCE) and negative sampling (NEG). We focused on their application to neighbor embeddings (NE) because this is an active and important application area, but also because NEs allow to directly visualize the NCE/ / NEG outcome and to form intuitive understanding of how different algorithm choices affect the result. Our study makes three conceptual advances.
First, we showed that NEG replaces NCE's learnable normalization parameter Z by large con- stant Z. forcing NEG to learn a scaled data distribution. While not explored here, this implies that NEG can be used to learn probabilistic models and is not only applicable for embedding learning as previously believed (Dyer 2014 Ruder 2016 Le-Khac et al. 2020). In the NE setting, NEG led to the method Neg-t-SNE that differs from NCVis NNC-t-NNE (Artemenkov Panov 2020) by a simple switch from the learnable to a fixed normalization constant. We argued that this can be use- ful hyperparameter because moves the embedding along the detraction-repuliiin spectrum similar to Böhh et al. (202)) and hence can either emphasize more discrete structure with higher repulsion (16) or more continuous structure with higher attraction (see Figs. S13/S14 for developmental single-cell datasets). Our quantitative evaluation in Supp. H corroborates this interpretation. We be- lieve that inspection of several embeddings along the spectrum can guard against over vverinterppeeinn any single embedding. Exploration of the spectrum does not require specialized knowledge. For UMAP, we always have ZUMAP = (²)mm: /m; for t-SNE, Böhm et al. (2022) found that the partition function Z typically lies in [50n, 100m]. Our PyTorch package allows the user to move along the spectrum with a slider parameter such that s=0 and s=1 correspond to Z Z and Z = ZUMA respectively, without a need for specifying Z directly.
A caveat that Thm. I and Cor. both assume the model to be rich enough to perfectly fit the data distribution. This is strong and unrealistic assumption. In the context of NEs, the data distribution zero for most pairs of points, which is impossible to match using the Cauchy kernel. Nevertheless, the consistency of MLE and thus t-SNE also depends on this assumption. Even without it, the gradients of MLE, NCE, and NEG are very similar (Supp. B). Finally, we validated our Cor. in a toy setting in which its assumptions do hold (Supp. M.
Second, we demonstrated that UMAP, which uses NEG, differs from Neg-I-SNE only in UMAP's implicit use of less numerically stable similarity function. This isolates the key aspect of UMAP's success: Instead of UMAP's s appraised (Oskolkov| 2022;Coenen Coenen & Pearce 2022) -igh-diimnsiooall similarities, the refined Cauchy kernel, its stated cross-entropy loss function, is the application of NEG that lets UMAP perform well and makes clusters in UMAP plats more compact and con- nections between them more continuous than in t-SNE, in agreement with Böhm et al. (2022). To the best of our knowledge, this is the first time UMAP's and t-SNE's loss functions, motivated very differently, have been conceptually connected.
Third, we argued that contrastive NEs are closely related to contrastive self-supervised learning (SSL) methods such as SimCLR (Chen al. 2020) which can be seen as parametric InfoNC-t-SNE for learning representations in ST25 based on the unobservable similarity graph implicitly con- structed via data augmentations. We feel that this connection has been underappreciated, with the lit- erature on NEs and on self-supervise contrastive learning staying mostly disconnected. Exceptions are the concurrent works of Hu et al. (2023) and Böhm et al. (2023). They propose to use t-SNE's Cauchy kernel for SSL. Instead, we bridge the gap between NE and SSL with our InfoNC-I-SNE, as well as with parametric versions of all considered NE methods, useful for adding saa-ple data to existing visualization. Moreover, we demonstrated that the feasibility of few noise samples in NE translates to the SimCLR setup. We developed a concise PyTorch framework optimizing all of the above, which we hope will facilitate future dialogue between the two research communities.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
We thank Philipp Berens for comments and support as well as James Melville for discussions.
This research was funded by the Deutsche Forschungsgemeinschat (DFG, Germany's Research Foundation) via SFB 1 112 (240245660; S.D., F.A.H.) well as via Excellence Clusters 2181/1 "STRUCTURES" (390900948; S.D., F.A.H.) and 2064 "Machine Learning: New Perspectives for Science" (390727645; J.N.B., D.K.), by the German Ministry of Education and Research (Tübingen AI Center, 011S18039A, J.N.B., D.K.), and by the Cyber Valley Research Fund (D.30.28739; J.N.B.).
The authors thank the International Max Planck Research School for Intelligent Systems (IMPRS- IS) for supporting J.N.B.
ETHICS STATEMENT
Our work analyses connections between popular contrastive learning methods and in particular vi- sualization methods. Visualization methods are fundamental in exploratory data analysis, e.g.. in computational biology. Given the basic nature of visualization can of course potentially be used for malicious goals, but we expect mostly positive societal effects such as more reliable exploration of biological data.
Similarly, contrastive euff-superiise learning has the potential to overcome the annotation bottle- neck that machine learning faces. This might free countless hours of labelling for more produc- tive use but could also enable institutions with sufficient resources to learn from larger and larger datasets, potentially concentrating power.
REPRODUCIBILITY
All of our results are reproducible. We included proofs for the theoretical statement Cor. and those in Supp. B aand The datasets used in the experiments including preprocessing steps are described in Supp. D We discuss the most important implementation details the main text, e.g., in See. An extensive discussion of our implementation is included in Supp. K and in Alg. ST
Our code and instructions for how to reproduce the experiments are publicly available. the implementation of contrastive neighbor embeddings from the scripts and notebooks needed to reproduce our results, to provide dedicated repositories for people interested in using our method and people wanting to reproduce our results. The contrastive neights embedding implementation can be found at fhtttps: //gi com http:////..rrrreaaaa///aaaaaaaa. books for reproducing results at httpp/////////gaooooo//////oo/aa The relevant commits in both repositories are tagged ic1r2023.
separated
and the scripts and note- umap
10

---

Published as a conference paper at ICLR 2023
REFERENCES
Ehsan Amid and Manfred K Warmuth. TriMap: Large-scale Dimensionality Reduction Using Triplets. arXiv preprint arxiv: 1910.00004, 2019.
Aleksandr Artemenkov and Maxim Panov. NCVis: Noise Contrastive Approach for Scalable Visu- alization. In Proceedings of The Web Conference 2020, pp. 2941-2947, 2020.
Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Dipendra Misra. Investigating the Role of
Negatives in Contrastive Representation Learning. In Proceedings of The 25th International Con- ference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, pp- 7187-7209, 2022.
Philip Bachman, R Devon Hjelm, and William Buchwalter. Learning Representations by Maximiz- ing Mutual Information across Views. In Advances in Neural Information Processing Systems, volume 32, pp. 35535-15544 2019.
Randall Balestriero and Yann LeCun. Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods. In Advances Neural Information Processing Systems, 2022.
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 44, 2019.
Jan Niklas Böhm, Philipp Berens, and Dmitry Kobak. Attraction Spectrum in Neighbor Embeddings. Journal of Machine Learning Research, 23(95): 2022.
Jan Niklas Böhm, Philipp Berens, and Dmitry Kobak. Unsupervised visualization of image datasets using contrastive learning. In International Conference on Learning Representations, 2023.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised Learning of Visual Features by Contrasting Cluster Assignments. In Advances in Neural Information Processing Systems, volume 33, pp. 9912-9924, 2020.
David M Chan, Roshan Rao, Forrest Huang, and John F Canny. t-SNE-CUDE GPU-Accelerated t-SNE and Applications to Modern Data. 2018 30th International Symposium on Computer Architecture and High Performance Computing, pp. 330-338. IEEE, 2018
Tara Chari, Joeyta Banerjee, and Lior Pachter. The Specious Art of Single- Cell Genomics. bioRxiv, 2021.
Benjamin Charlier, Jean Feydy, Joan Alexis Glaunès, Trançois-Davie Collin, and Ghislain Durif. Kernel Operations on the GPU, with Autodiff, without Memory Overflows. Journal of Machine Learning Research, 22(74): 2021.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A Simple Framework for Contrastive Learning of Visual Representations. In Proceedings of the International Conference on Machine Learning, Proceedings of Machine Learning Research, pp. 1597-1607,
Andy Coenen and Adam Pearce. A deeper dive into UMAP theory.
cote//errrrreee.../p b.tthub.io/undeesttannnd. uuap://sstaaaannnaaaaaaaaaaaaaaa hamaap/suppleemnn:: auwdddnnguuaapppupppeeeeeee.eee html 2022. Accessed: 2022-05-11.
Sebastian Damrich and Fred A Hamprecht. On UMAP's True Loss Function. In Advances in Neural
Information Processing Systems, volume 34, pp. 5798-5809, 2021.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Infor- mation Processing Systems, volume 27, 2014.
Andrew Draganov, Tyrus Berry, Jakob Rødsgaard Jørgensen, Katrine Scheel Nellemann, Ira Assent, and Davide Mottin. GiDR-DUN; Gradient Dimensionality Reduction DecuettionDDifferenees Differences and Unifica- tion. arXiv preprint arXiv:2206.09663 2022.

---

Published as a conference paper at ICLR 2023
Chris Dyer. Notes on Noise Contrastive Estimation and Negative Sampling. arXiv preprint arxiv: 1410.8251, 2014.
Peter Eisenmann. Fast Visualization High-Dimensional Data via Parallelized UMAP on GPUs. Master's thesis, Karlsruhe Institue of Technology, 2019.
Yoav Goldberg and Omer Levy. word2vec Explained: Deriving Mikolov et al.'s Negative-Sampae
Word Bord-Embeddding Method. arXiv preprint arxiv: 1402.3722, 2014.
Michael U Gutmann and Aapo Hyvärinen. Noiseecontrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 297-304, 2010.
Michael U Gutmann and Aapo Hyvärinen. Noise-Contee Contrasste Estimation of Unnormalized Statisti- cal Models, with Applications to Natural Image Statistics. Journal of Machine Learning Research, 13(2), 2012.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In Proceedings the IEEE Conference Computer Vision and Pattern Recogni- tion, pp. 770-778, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum Contrast for Unsupervised Visual Representation Learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 9729-9738, 2020.
Geoffrey E Hinton and Sam Roweis. Stochastic Neighbor Embedding. In Advances in Neural Information Processing Systems, volume 15, pp. 857-864, 2002.
Tianyang Hu, Zhili Liu, Fengwei Zhou, Wenjia Wang, and Weiran Huang. Your Contrastive Learn- ing Is Secretly Doing Stochastic Neighbor Embedding. In International Conference on Learning Representations, 2023.
Rafal Jozefowicz, Oriol Vinyals, Mike Schuster, Noam Shazeer, and Yonghui Wu. Exploring the Limits of Language Modeling. arXiv preprint arxiv: 1602.02410, 2016.
Sabina Kanton, Michael James Boyle, Zhisong He, Malgorzata Santel, Anne Weigert, Fátima Sanchís-Calleja Patricia Guijarro, Leila Sidow, Jonas Simon Fleck, Dingding Han, al. Organoid single-cell genomic atlas uncovers human-specific features of brain development. Na- ture, 474(7778):418-422 2019.
Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In Proceedings of the International Conference on Learning Representations, pp. 1-15, 2015.
Dmitry Kobak and Philipp Berens. The art of using t-SNE for single-cell transcriptomics. Nature Communications, 10(1): 2019.
Dmitry Kobak and George C Linderman. Initialization is critical for preserving global data structure in both t-SNE and UMAP. Nature Biotechnology, pp. 1-2, 2021.
Dmitry Kobak, George Linderman, Stefan Steinerberger, Yuval Kluger, and Philipp Berens. Heavy- Tailed Kernels Reveal Finer Cluster Structure in t-SNE Visualisations. In Joint European Con- ference on Machine Learning and Knowledge Discovery in Databases, pp. 124-139. Springer, 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, University of Toronto, 2009.
Phuc H Le-Khac, Graham Healy, and Alan Smeaton. Contrastive Representation Learning: A Framework and Review. IEEE Access, 8: 1999977-1,393,, 2020.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):22782333) 1998.
Omer Levy and Yoav Goldberg. Neural Word Embedding as Implicit Matrix Factorization. In Advances in Neural Information Processing Systems, volume 27, pp. 2177-2185, 2014.
12

---

Published as a conference paper at ICLR 2023
George C Linderman, Manas Rachh, Jeremy G Hoskins, Stefan Steinerberger, and Yuval Kluger. Fast interpolation-batt based t-SNE for improved visualization of single-cell RNA-seq data. Nature Methods, (6(3):243-2453 2019.
Ilya Loshchilov and Frank Hutter. SGDR: Stochastic Gradient Descent with Warm Restarts. Pro- ceedings of the International Conference on Learning Representations, pp. 1-16, 2017.
Zhuang Ma and Michael Collins. Noise Contrastive Estimation and Negative Sampling for Condi- tional Models: Consistency and Statistical Efficiency. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 3698-3707, 2018.
Leland Mclnnes, John Healy, and James Melville. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. arXiv preprint arXiv: /00.. 2018.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed Represen- tations of Words and Phrases and their Compositionality. In Advances in Neural Information Processing Systems, volume 26, pp. 3111-3119, 2013.
Jovana Mitrovic, Brian McWilliams, and Melanie Rey. Less can more contrastive learning. In Proceedings on "I Can't I Believe It's Not Better!" al NeurlPS Workshops, pp. 70-75, 2020.
Ashwin Narayan, fBonnic Berger, and Hyunghoon Cho. Assessing single-cell transcriptomic vari- ability through dersity--r data visualization. Nature Biotechnology, pp. 1-10, 2021.
Corey Nolet, Victor Lafargue, Edward Raff, Thejaswi Nanditale, Tim Oates, John Zedlewski, and Joshua Patterson. Bringing UMAP Closer to the Speed of Light with GPU Acceleration. In Proceedings of the AAA/ Conference on Artificial Intelligence, volume 35, pp. 418-426, 2021.
Kento Nozawa and Issei Sato. Understanding Negative Samples in Instance Discriminative Self- supervised Representation Learning. In Advances in Neural Information Processing Systems, volume 34, pp. 5784-5797, 2021.
Nikolay Oskolkov. How Exactly UMAP Works. bttss://ooaaddsstttsscsc.. com/
2022. Accessed: 2022-05-11.
Jonathan Packer, Qin Zhu, Chau Huynh, Priya Sivaramakrishnan. Elicia Preston, Hannah Dueck, Derek Stefanik, Kai Tan, Cole Trapnell, Junhyong Kim, Robert H. Waterston, and John I. Murray. A leneage-resolved molecular atlas of C. elegans embryogenesis at single-cell resolution. Science, 36516459):1265-11244 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTrrch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems 32, pp. 8024- 8035, 2019.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830 2011.
Pavlin G. Poličar, Martin Stražar, and Blaž Zupan. open TSNE: modular Python library for t-SNE dimensionality reduction and embedding. bioRxiv, 2019.
Karsten Roth, Timo Milbich, and Bjorn Ommer. PADS: Policy-Adapted Sampling for Visual Sim- ilarity Learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6568-6577, 2020.
Sebastian Ruder. On word embeddings Part 2: Approximating the Softmax. http://zuder.
softmax 2016. Accessed: 2022-05-17.
Tim Sainburg, Leland McInnes, and Timothy Q Gentner. Parametric UMAP Embeddings for Rep- resentation and Semisupervised Learning. Neural Computation, (3(11):288) 1-2907, 2021.
13

---

Published as a conference paper at ICLR 2023
Benjamin Szubert, Jennifer E Cole, Claudia Monaco, and Ignat Drozdov. Structure Structure-preservingg visualisation of high dimensional single-cell datasets. Scientific Reports, 9(1):1-10, 2019.
Jian Tang, Jingzhou Liu, Ming Zhang, and Qiaozhu Mei. Visualizing large-scale and high- dimensional data. In Proceedings of the 25th International Conference on World Wide Web, pp. 287-297, 2016.
Clanuwat Tarin, B Mikel, K Asanobu, L. Alex, Y Kazuaki, and H David. Deep Learning for Classical Japanese Literature. Proceedings of 2018 Workshop on Machine Learning for Creativity and Design (Thirty-second Conference Neural Information Processing Systems), volume 3, 2018.
Joshua B Tenenbaum, Vin De Silva, and John C Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science, 290(5500):2319-23333 2000.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive Multiview Coding. In Proceedings of the European Conference on Computer Vision, pp. 776-794. Springer, 2020.
Aäron van den Oord, Yazhe Li, and Oriol Vinyals. Representation Learning with Contrastive Pre- dictive Coding. arXiv e-prints, pp. arXiv-1807, 2018.
Laurens der Maaten. Learning Parametric Embedding by Preserving Local Structure. In Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, pp. 384-391, 2009.
Laurens van der Maaten. Accelerating t-SNE using Tree-Based Algorithms. Journal of Machine Learning Research, 15(1):3221-3244 2014.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using tSSNE. Journal of Machine Learning Research, 911))25799-66 2008.
Daniel E. Wagner, Caleb Weinreb, Zach M. Collins, James A. Briggs, Sean G. Megason, and Al- lon M. Klein. Single-cell mapping of gene expression landscapes and lineage in the zebrafish embryo. Science, 360(6392) 2018.
Yingfan Wang, Haiyang Huang, Cynthia Rudin, and Yaron Shaposhnik, Understanding How Dimen- sion Reduction Tools Work: An Empirical Approach Deciphering t-SNE, UMAP, TriMAP, and PaCMAP for Data Visualization. Journal of Machine Learning Research, 22:1-73, 2021.
Chao-Yuan Wu, R Manmatha, Alexander J Smola, and Philipp Krahenbuhl. Sampling Matters in Deep Embedding Learning. Proceedings of the IEEE International Conference on Computer Vision, pp. 2840-2844444 2017.
Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised Feature Learning via Non- Parametric Instance Discrimination. In Proceedings of the IEEESCVE Conference on Computer Vision and Pattern Recognition, pp. 3733-3742, 2018.
Zhirong Yang. Irwin King, Zenglin Xu, and Erkki Oja. Heavy-Tailed Symmetric Stochastic Neigh- bor Embedding. In Advances in Neural Information Processing Systems, pp. 2169-2177, 2177,2009 2009.
Zhirong Yang, Jaakko Peltonen, and Samuel Kaski. Scalable optimization of neighbor embedding for visualization. In International Conference on Machine Learning, pp. 127-135, 2013.
Zhirong Yang, Yuwei Chen, Denis Sedov, Samuel Kaski, and Jukka Corander. Stochastic cluster embedding. Statistics and Computing, 33(1):12, 2023.
14

---

Published as a conference paper at ICLR 2023
SUPPLEMENTARY TEXT
A PROBABILISTIC FRAMEWORKS OF NCE AND INFONCE
In this section we reeap the probabilistic frameworks of NCE (Gutmann Hyvärinen, 2010 2012)
and InfoNCE (Jozefowicz et al. 2016; van den Oord et al. 2018).
A.1 NCE
In NCE the unsupervised problem of parametric density estimation is turned into supervised prob- lem in which the data samples need to be identified in set containing N data samples $1,... , SN and m times as many noise samples , drawn from noise distribution &, which can be (but does not have to be) the uniform distribution. In other words, we are interested in the posterior probability (P(l(z) of element
S coming from the data (y data) rather than from the noise
distribution (y- = noise).
The probability of sampling from noise, P(z|noise), is just the noise distribution &. and similarly P(a|data) is the data distribution p. Since the latter unknown, is replaced by the model qa- times many noise samples as data samples, the prior class probabilities are P(data) = 1/(m + 1) and P(noise) = m/mmm + 1). Thus, the unconditional probability of an element of S is P(x) (40 (z) mε(x))/ + 1). The posterior probability for classifying some given element x of as data rather than noise is thus
Since S contains
P(data) x)) = [(x data)
qo (x)
(10)
P(r)
(0 + mE(r)
NCE optimizes the parameters by maximizing the oggliielihood of the posterior class distribu- tions, or, equivalently, by minimizing the negative logllikelssoods. This is the same as sum over binary cross-entropy losses (Eq. (2) in the main text):
N
(8:) log (8:) + mE(s:)
m.N
(1-
go(ts) go((;) + mE(li)
0" = arg min
Σ
log
(II)
In expectation, we have the loss function (Eq. in the main text)
(s(s)
qo (t)
CNC (8) = EEap log
MEE- log
(12)
(a((s) + mE(s)
(o(t) m
Since go (=)))(1o({x)) + mm(x)) = ( ( ". NCE's loss function can also be
seen as binary logistic regression loss function with log
20(x) me(ar)
as the input to the logistic function:
NCE (0) -ysp log (a (118 [og
mm(s) )))
qo(())
mm(() ))) (13)
(1)())
mlaan log 1 (log
where (x) = 11 + exp(-x)) is the logistic function.
A.2 INFONCE
Again, we are casting the unsupervised problem of density estimation as supervised classification problem. We consider tuple of m samples T (zo...., one of which comes from the data and the rest from the noise distribution. Instead of classifying each sample independently as noise data (as in Sec. A.I.. here are interested in identifying the position of the single data sample. This allows us to see the problem as a multi-class classification problem with m + classes.
Let Y be the random variable that holds the index of the data sample. A priori, we have P(Y = k) = 11(m= + 1) for all = 0,...,m. m. Moreover, conditioned on sample coming from the data distribution, all other samples must come from the noise distribution, i.e.,
15

---

Published as a conference paper at ICLR 2023
have P(x; ( k) = ((,)) for i + k. As the data distribution is unknown, we model it with
F( Y = k) = (Tk) as in Sec. A.1 This yields the likelihood of tuple T given the data in-
dex Y = k
yo (xrk) {(TR))
P(TY- = k) qo (xk))
II E(xi)= ig
((x)).
(14)
==
Marginalizing over Y, we obtain
m
m
qo (3rk)
P(T)
m + II ((x,)
(15)
El (xxx)
Finally, we can compute the posterior via Bayes' rule as
(a(
P(Y = k(7) P(T k)TP(Y k))
E(wx)
qo (Trk)
(16)
P(T)
Ex=
ga(me)
Ei (x;))
E(ze)
where the last equality only holds for the uniform noise distribution. The InfoNCE loss is the cross-
entropy loss with respect the true position of the data sample, i.c. in expectation and for uniform & it reads:
qe (x) log (o(x)) D g0(2;))
CInlONCE (0)
(17)
I1 E
Similar to how the NCE loss can be seen as binary logistic regression loss function (Sec. A.1 the InfoNCE loss can be viewed as multinomial logistic regression loss function with the terms
log ((x.)
go(m)) entering the softmax function.
B GRADIENTS
B.1 GRADIENTS OF MLE, NCE, AND NEG
Here, we compute the gradients of MLE, NCE, and NEG, claborating the discus- sion in Artemenkov Panov 2020).
Following the discussion in Secs. 3.2 and
we consider normalized model (0(x) = (o(x)/Z(0) with partition function (=(x)/Z with learnable normalization (0) Σnr (x for MLE, a model 20.2 0o(x)/2 with fixed normalization constant Z for parameter for NCE, and model 9x.2(z)
NEG. We show the results both for general Z and noise distribution and for the default value Z = / and uniform noise distribution {(x) 1/|X/.
Thus, the losses are
MLE (0) = EEE log (g+(x)),
(18)
90 (x) mm(x) ) -mEwn log
40.2 (x)
1 (0,2(2)
NCE (0, Z) = - EENP log
(19)
98. 2 (z) + m
40 (x)
(0.z(2)
NBG (0, 2) E Enp log
M.EEE log
1
(20)
(0,2 mx(x))
4o (x) mm(x))
(1)))) +1 - MBBBB log (1 (1-
Φ1(x))
(x(2)
CNEG (0) - E Enap log
(21)
(x))) +
For MLE, we find
d.M.F.(()
d
(- Bzup log (go(2)))
(22)
d0
d0
d
Σ (p(x) log (dbo(z)) log Σ (2r)
(23)
d0
p(x)
deb(a))
(x)(())
Σ
(24)
(x(
dB
Σx Φ0(z)
d8
Σ
p(z)
)
1
d
(25)
(x(
Z(0)
d8
16

---

Published as a conference paper at ICLR 2023
For the NCE loss will use the templates
dloog
[(z)
d dlog [+c/f(x)
[())=c)
(26)
dz
dz
dlog(1 1 + f2))
(27)
dz
1
0 df(z)
(28)
1+c/f(22
f(2) dz
c
df(z)
(29)
f(z) + f(z)
dz
dlogg
dlog (f(2)/c+1)
(30)
dz
dz
1
1 (2(2)
(31)
f(=)/c+1
+1 -1
dz
(f(
(32)
f(z) +
dz
with some differentiable function f() and iindependent of z. For the NCE loss we get d.C.CE(O, (0, 2) d6 dB
d
q0
-m EuEu log (1 (1-
-0
Exap log
90.2 (z) + mm(x))
20, (x) + mg (a))
(33)
d EEup log
2 (x)
mf(x)
-mExxz log
d0
(0,2(x)) + mE(x))
(0,2((x) + mx(x))
(34)
(x(x)
dqo.2 (x))
p(x)
(35)
10 (x) + mE(x) 90.2
d0 dgo (x)
-1
+m)(
(36)
20,2 + +mE(1)
d8
Σ
20.z(x) -1)
p(z)
mE(x)
dd)(x)
(37)
(0,2(x) + + (x)
d0
We used our templates at the third equality sign with f(z) = q 2 (x) and c = mE(x). The derivation
of the gradients for the NEG loss is entirely analogous to that for NCE with q0,z (x)) replaced by le 2..2 (r).
Together, the gradients of the three losses
dC)
p(x))
deo(x)
Σ
-1
(38)
d8
(x(x)
Z(0)
d9
ZEX
d.C NCE (0,2) Σ
p(x)
-1)
mx(x)
1
dip (x)
(39)
d8 ZEX
(0.2
20,2(3) (x) + mE(x)
Z
d0
NCNNE (0,2) Σ
p(x)
mx(x)
1
dΦo(x)
(40)
d0 ZEX
(0.2(2)
(x)
40 (1) + m=(
7
d0
NE (0)
Σ
p(x)
m
(41)
d8
(x)
X
20 (x)
d0
ZEX
The fractions involving m²( in the gradients of CNC and NEG tend to one as m - 00 high- lighting that higher number of noise samples improves NCE's approximation of MI_E (Gutmann
17

---

Published as a conference paper at ICLR 2023
Artemenkov & Panov 2020 All four gradients are the same up this factor and the different choice of normalization. In all them, the models qo. 98.2, or 9g.2 try to match the data distribution p according the first factor in each gradient. This similarity of the gradients holds independent of the assumptions of Thm. | and Cor, 2 We optimize all losses with stochastic gradient descent and can therefore expect our analysis to hold even if the assumptions violated.
& Hyvärinen 2010: 2012
B.2 GRADIENTS FOR NEIGHBOR EMBEDDINGS
Here, we rewrite the above gradients for the case of neighbor embeddings. This means that MLE, NCE, and NEG become t-SNE, NC-t-SNE, and Neg-t-SNE, respectively. We include two variants of Neg-t-SNE: for a general value of Z and for the default value Z (?) //m used by UMAP. In addition, we also show the gradient of UMAP. Recall that for neighbor embedding, we have X {ijll < i < j < n). 0 (ei,....ex) ). and Φ(ij) = 1/(1 + lle: eg1l²). The noise
distributions are close to uniform, see Supp. D so that {(t)) = (2)
dL
b(tj)
p((5)
((1))(e) ea) (42)
de;
Ense ((kt)
144
d.L.CAASSE
m (ig)
olii)
p((5)
((1)((e) e.) (43)
deg
d(t))
+ mE(jj)
7
N.N.----SNN dec
o(i))
p(1))
((i))ee, ..) (44)
a(t))
+ mmE(i))
2
Nog-
o(1))
RS >
p(1))
s(i)((s) ei) (45)
de:
((1)) +1
(2) /m
E[0.5,1]
d.MIMAPP
Σ
p(i))
x(i))
o(it)(e, - e.) (46)
de:
(*) //m
((j)
374
mamerically unstable For i.
As above, we see that NC-t-SNE and Neg-t-SNE have terms that go to one for m - oc. For Neg-I-SNE with default Z, we used the approximation E(ij) x (?) Here, the corresponding term is restricted to the interval [0.5, 1]. More generally, we see that the repulsive force in Neg-t-SNE scales as 1/2. Its default value of n(n - ()m(2m) is much larger than the typical values of the partition function Eeye ((kl) in t-SNE or the learned Z of NC-I-SNE, which are typically in the range [50m, 100m] (Böhm et al. 2022), leading much smaller repulsion in default Neg-t-SNE and in UMAP than NC-1-SNE or t-EE. Finally, the repulsive part of the UMAP gradient contains a term that diverges for e ej. leading d(ij) 1, reflecting the discussion of UMAP's numerical instability in Sec.
C UMAP'S LOSS FUNCTION
In the original UMAP paper, McInnes et al. 2018) define weights μutz) E [0, 1] the skNN graph and state that these shall be reproduced by the low-dimensional similarities ((1)) by means of a sum of binary cross-entropy loss functions, one for each edge
Σ p(is) log (d(i)) + ((())) log (1 (ii))
(47)
Indeed, this loss has its minimum at uu(t)) o(ir) for all ij. However, it is of course not possible to achieve zero loss for any real-world data using the Cauchy kernel two dimensions. Experiments show that using this loss function in practice leads to excess of repulsion and consequently to very
18

---

Published as a conference paper at ICLR 2023
poor embeddings (Böhm et al. 2022). The actual UMAP implementation has much less repulsion due to the sampling of repulsive edges, see below.
As the weights plūj) only supported the sparse skNN graph, most of the 1 pllj) terms are equal to one. To simplify the loss function, the UMAP paper replaces all 1 - -m(ii) terms by 1, leading to the loss function
Σ 17
p(ii) log (o(i)) + log (1 (-(((i))
(48)
In the implementation, UMAP samples the repulsive edges, which drastically changes the loss (Böhm et al. 2022) to the effective loss (Damrich & Hamprecht) 2021)
Σ (((t)) log (o(1)) + m(d; + ddj) log (1 -0(()
(49)
2n
where d; = Σj m(ūs) denotes the degree of node i and the number of negative samples m is hyperparameter. By default, = 5. Since d, s log(k:), the effective loss only has about log(k)/v of the repulsion in the originally stated loss function. As a result, the ((tj) are not reproduced in the embedding space by this loss function.
We rewrite this effective loss function further to fit into our framework. The attractive prefactors u(ij) sum to Eig ((i)), while the repulsive prefactors add up to m times this factor. Dividing the entire loss function by this term does not change its properties. But then, we can write the prefactors as probability distributions p(ij) p(ij)/ Eij p(ij) and {(is) (p(i) + p()) /2m
using p(t) = E, p(tj). With this, we can write the effective loss function as
Σ p(ij) log (o(i))
Σ E(ij) log (1 -(i)),
(50)
or in the expectation form as
Eijop log (δ(1j)) - mEEj-e log (1 o(ij)),
(51)
like we do in Eq.
D NOISE DISTRIBUTIONS
Here we discuss the various noise distributions used by UMAP, NCVis, and our framework. The main claim is that all these noise distributions are sufficiently close to uniform, even though their exact shape depends on the implementation details.
Since our actual implementation, as well as the reference implementations UMAP and NCVis, considers edges ij and ji separately, we will do so from now on. Hence, there is now total of E = 2|s edges. We always assume that p(ij) = p(jt) and adding up the probabilities for both directions yields one: Σx p(ij) = 1. For given data distribution
pairs of points ij, define p(i) Σラ= p(ij) so that Σ, p()) = As discussed in Supp. B of Damrich & Hamprecht 2021 J. the p(z) values are approximately constant when p(ij) is uniform on the s&NN graph or proportional to the UMAP similarities.
D.1 NOISE DISTRIBUTIONS OF UMAP AND NCVIS
UMAP's noise distribution is derived in Damrich & Hamprecht (202T) and reads in our notation (Supp.
{(i)) p(i) + p(j).
(52)
2n
Note that UMAP uses a weighted version of the skNN graph. Still, g is close to uniform, see Supp. of Damrich & Hamprecht (2021).
19

---

Published as a conference paper at ICLR 2023
The noise distribution of NCVis is also close being uniform and equals (Artemenkov & Panov 2020
p(i) Y
{(i)
(53)
This is slightly different noise distribution than in UMAP and in particular it is asymmetric. How- ever, we argue that in practice it is equivalent to the same noise distribution as in UMAP. The noise distribution is used in two ways in NCVis: for sampling noise samples and in the posterior class probabilities
40.z (ig)
P ij)
(54)
20,z + mE(
Both in the reference NCVis implementation and in ours, for the second role, the noise distribution explicitly approximated by the uniform one and we use the posterior probabilities
(0,z P(datalij)= 48, (ij) + 2|ANNN
(55)
Together with the symmetry of the Cauchy kernel this implies that the repulsion on the embedding vectors ey and ej from noise sample ij and ji is the same, As a result, the expectation
Eijug log (1-
qo (ij)
(56)
90.2 (ij) + TRANN
is the same for E(tj) = p(i)/n h and for UMAP's noise distribution
{(ij) p(i) + p())
(57)
2n
D.2 EFFECT OF BATCHED TRAINING ON THE NOISE DISTRIBUTION
In our framework, the noise distribution is influenced by the batched training procedure (Alg. SI because the negative samples can come only from the current training batch.
In every epoch, we first shuffle the set of directed edges of the skNN graph and then chunk into batches. To emphasize, the batches consist of directed edges and not of the original data points. For each edge in a batch, we take its head and sample m indices from the heads and tails of all edges in the batch (excluding the already selected head) and use them as tails form negative sample pairs.
To obtain a negative sample pair ij, the batch must contain some directed edge ik, providing the head of the negative sample, and some pair lj jl. providing the tail. We want to derive the expected number of times that a directed edge ij is considered as negative sample in batch. For simplicity, let us assume that the number of batches divides the number of directed edges E. As the set of s&NN edges is shuffled every epoch, the expected number of pairs ij as negative samples is the same for all batches.
Let us consider batch B of size b. We denote by Yrs the random variable that holds the num- ber of times edge r's appears B. We also introduce random variables Y-rs Eitrr YLs and
Y = -. Yr.. Let p(r-s) = p(-sr) == p(r) p(rs). For each occurrence of an as head of an edge B, we sample m tails to create negative samples uniformly from all head and tails in B with replacement, but we prevent sampling the identical head i negative sample tail. If, however, the same node i is part of the other edges in the batch, then may be sampled and would create futile negative sample ii. There are m chances for creating negative sample edge ij for every head i and any occurrence of j in the batch. The number of heads i in the batch is YıJ + Y and the number of occurrences of j is Yij + YjJ Y-ij + Yj Since we sample the tail of a negative sample pair uniformly with replacement, any of the occurrences of j has probability 1/(2b- 1) to be selected. Hence, the expected number Ni; of times that the ordered pair ij with A j considered as a negative sample in batch B is
Y4 + YN
+ Y-oj + Y
NJ mm1;; + Yr-s)
(58)
2h
1
20

---

Published as a conference paper at ICLR 2023
Since a head i may not choose itself to form negative sample, the expected number of times that éi appears as negative sample in the batch is
Na = m Σ Vij Y1
1 Y Yjs
Y-ja
(59)
2b --1
Since the batches are sampled without replacement, the random variables Yrs are distributed accord- ing to multivariate hypergeometric distribution, so that
B( = bp(rs),
(60)
E((Yrs)) = bp(-ra);
(61)
Var(Yrs) b E - b
F. 1 -(((ss) 11-111pp11 p(rs)),
(62)
Kou -1 E-b - p ((rr))((-u))
(63)
We use these expressions and analogous ones together with the symmetries p(rs) p(sr) com- pute (leaving out intermediate algebra steps) the expectation of Ni over the shuffles:
mb
E - p(is) E 1 p(is) +2
+2(0- E
( p(j)p(i)
E 1ー-
B(N,)
(64)
26
Since we sample m negative samples for each positive sample and since each batch contains positive samples, we need to divide ((Ni)) by mà to obtain {(t)):
F. b
p(is) + 2 b E 1
((()p(()))) p(()p(5))
E(i)) = 2b 1 E 1
(65)
Similarly,
mb b (-b-Tp() +2
E- b) E F-1 p(i)2)
B(N.) 2b - 1
(66)
and hence the noise distribution value for the pair vi is
1 (- b-1 E(ii) = 2b -- (-E-T p(i) +2
6 E- E- 1 p(i)2)
(67)
We see that the noise distribution depends on the batch size b. This is not surprising: For example, the batch size is equal to one, the ordered pair ij can only be sampled as a negative sample in the single batch that consists of that pair. Indeed, for b our formula yields
{(t) - p(i)),
(68)
meaning that the data and the noise distributions coincide. Conversely, if b and there only one batch, we obtain
2F
E(i))
2E p()(())
(69)
and the noise distribution close to uniform. For batch sizes between I and the noise distribution is in between these two extremes. For MNIST, E 1.5 105, and in our experiments we used
b = 1024. This means that the prefactor of the share of the data distribution is about 0.0005 while that of the near-uniform distribution p(i) (()((j) is about 0.9995, the resulting noise distribution is close to uniform. Note that Thm. and Cor, Jonly require the noise distribution to have full support which is the case for any batch size greater than one.
21

---

Published as a conference paper at ICLR 2023
10
(a) Ç = 10-3, no anncaling
(b) 10 10 no anncaling
(c) Ç no annealing
10
10
10
(d) Ç 10-3 with annealing
(c) 10 with annealing
(f) 0, with annealing
Figure S1: UMAP embeddings of the MNIST dataset, ablating numerical optimization tricks of UMAP's reference implementation. The learning rate annealing is crucial (bottom row) but safe- guarding against divisions by zero in UMAP's repulsive term Fq. (71) by adding to the denomi- nator has little effect. These experiments were run using the reference implementation, modified to change the { value and to optionally switch off the learning rate annealing.
E OPTIMIZATION TRICKS IN UMAP'S REFERENCE IMPLEMENTATION
UMAP's repulsive term
1+ di
log(1 o(i))) log
(70)
can lead to numerical problems the two points of the negative sample pair are very close. In addition to the learning rate decay, discussed in Sec. 6 UMAP's implementation uses further tricks
prevent unstable or even crashing training.
In non parammeett UMAP's reference implementation, the gradient on embedding position e, exerted by a single sampled repulsive pair ij actually
1
2
+11 de (e, ei)
(71)
with Ç = 0.001 instead of ( = This corresponds to the full loss function
- -iis loo((o(()))))) - m [++ mm(+ { log (1 - ( o(i))
(1+
(72)
However, we found that { does not have much influence on the appearance of a UMAP embedding. Fig. shows MNIST embeddings obtained using the original UMAP implementation modified to use different values of Ç. Neither a much smaller positive value such as Ç 10 10-10 nor setting substantially changed the appearance of the embedding (even though some runs with ( did crash). The learning rate annealing played a much bigger role in how the embedding looked like (Fig. S1] bottom row).
The reference implementation of parametric UMAP uses automatic differentiation instead of im- plementing the gradients manually. To avoid terms such log(0) in the repulsive loss, it clips the argument of the logarithm from below at the value = 10-4, effectively using the loss function
- Eijop log max {e,
1 1+ d.
1 mEEija log
max {e, 1 1 1 1)
(73)
22

---

Published as a conference paper at ICLR 2023
(a) UMAP, 10 no
(b) UMAP, 10 10 ann.
10
10
(c) UMAP, with ann.
(d) UMAP,
with ann.
10
10
10
(e) Neg-I-SNE, E 10 no ann.
(f) Neg-t-SNE, 10 no ann.
(g) Neg-t-SNE,
10
10
10
(h) Neg-t-SNE, 10-4, with (in. Neg-t-SNE, 10-10, 10 with (j) Neg-t-SNE, 0, with ann.
Figure S2: UMAP and Neg-t-SNE embeddings of the MNIST dataset using different values at which we clip arguments to logarithm functions. These experiments were done using our imple- mentation. Varying did not strongly influence the appearance of the embedding. But setting E led to crashing UMAP runs. Annealing the learning rate is important for UMAP, yet not for Neg-I-SNE.
We employ a similar clipping in our code whenever we apply the logarithm function. Again, we found that the exact value of is not important for our UMAP reimplementation, while using the learning rate annealing is (Fig. SS2 top two rows). In the extreme case of setting O, our UMAP runs crashed. We believe that the reason is that we allow negative sample pairs to be of the form ii, which would not send any gradient, but would lead to a zero argument to the logarithm. The reference implementation of UMAP excludes such negative sample pairs ii.
Our Neg-I-SNE approach does not have any of these problems, as the repulsive term upper bounded
I+d
2 + dz
-log
1
log
< log(2)
(74)
+
1
I+d
23

---

Published as a conference paper at ICLR 2023
and does not diverge for d; - 0. For this reason, Neg-t-SNE is not very sensitive to the value at which we clip arguments to the logarithm and works even with = 0, both with and without learning rate annealing (Fig. S2 bottom two rows).
The attractive terms in the loss functions do not pose numerical problems in practice due to the heavy tail of the Cauchy kernel. That said, in order to keep different experiments and losses comparable, we used clipping in both the attractive and the repulsive loss terms with с = 10-10 10 for all neighbor embedding plots computed with our framework unless otherwise stated.
A recent pull request (#856) to the parametric part of UMAP's reference implementation proposed another way ameliorate the numerical instabilities. The clipping of the arguments the loga- rithm was replaced with sigmoid of the logarithm of the Cauchy kernel, so that the attractive and repulsive terms become
- log max (e, ((i)) 7 --log (o(108 (o(())))
(75)
1 o (og (o((t)))
-log max (c, 1 o(i))) + - log
11
(76)
where (1)) = 1/(1 + exp(-x)) is the sigmoid function. This change can seem drastic as, e.g., for p(i)) = we have max (E, {(i)) = 1, but of log (é(tj)) 1/2. But unravelling the definitions
shows that this turns the loss function precisely into our Neg-I-SNE loss function since
of (og (d(ii) =
1 1+ ((0))
((i)) o(i)) +1
(77)
+ exp
lolo (d(ij))
So, in order to overcome the numerical problems incurred by UMAP's implicit choice of 1/df, as similarity kernel, the pull request suggested a fix that turns out to be equivalent to negative sampling using the Cauchy kernel. We encourage this change to UMAP as it makes its loss function equivalent to our Neg-t-SNE and thus also conceptually more related to t-SNE. We also suggest to implement it in the non- parameraetricc case.
F TRIMAP AND INFONC-I-SNE
The neighbor embedding method TriMap (Amid & Warmuth 2019) also employs contrastive technique to compute the layout. TriMap considers triplets (7, K), where and are data points that are more similar than i and k. It moves the embeddings e; and e, closer together and pushes e, and eg further apart. While a full investigation of TriMap is beyond the scope of our work, here we argue that it bears some similarity to InfoNC-I-SNE with m 1.
First, we describe TriMap in more detail. Most of the triplets (i.j. k) consist of nearest neighbors i and j and random point k. By default, 12 nearest neighbors j are chosen for each i, using modified Euclidean distance. For each such pair (i,j) additional distinct points k (by default 4) chosen randomly from the set of all points excluding i and all the chosen j. This leads to 48 triplets (i, k) for each point i. Additionally, several (by default 3) triplets are formed for each i with random j and only ensuring that the similarity between i and
larger than between and k. Thus. for each point there are in total 51 triplets (i. k) leading to a grand total of 5in triplets. These triplets are formed ahead of the layout optimization phase and kept fixed throughout. TriMap also assigns& a weight Wiyk to each triplet. This weight is larger for triplets in which i and j are much more similar to each other than i and k.
In our notation, TriMap's 's loss function can be written
dikk)
d(ij) Wijk Φ(i)) + (ik))
Wijk
const
Σ
(78)
(ii) + d(ik)
This loss is very similar to the loss of InfoNC-t-SNE with m 1:
d(ij) Φ ((ik)
E log
(79)
1j-p
k-lld
24

---

Published as a conference paper at ICLR 2023
I6
16
(a) TriMap default
(b) TriMap Eucl. KNN
(c) TriMap no random
(d) MriMap no weights
(e) InfoNC-L-SNE
M
Figure S3: Ablating design choices of TriMap on the MNIST dataset. Simplifying TriMap leads to an embedding similar to that of InfoNC-t-SNE with m = 1. The biggest difference results from the omission of random triplets in panele
Table S1: Quality of TriMap and InfoNC-t-SNE, Means and standard deviations over three runs.
kNN recall
Spearman correlation
TriMap (default)
0.098 + 0
0.245 + 0.005
TriMap (ANN)
0.099 +
0.232 + 0.003
TriMap (no random)
0.101 +
0.355 + 0.004
TriMap (no weights)
0.099 + 0
0.381 4: 0.001
InfoNC-I-SNE (m = 1)
0.085 + 0.001
0.381 +: 0.006
InfoNC-I-SNE (m 5)
0.104 +
0.365 + 0.005
The differences are: the absence of log: the presence of weights; the presence of random triplets; nearest neighbors being based not exactly on Euclidean metric: and fixed triplets during optimiza- tion. In the following we modify the reference TriMap implementation and ablate these differences in order to see which ones are more or less important (Figure (3)). We measure the quality of all embeddings using two metrics (Tab. ST]: as global metric we use the Spearman correlation be- tween high- and low-dimensional pairwise distances between 5000 randomly chosen points (Kobak) & Berens 2019) and local metric we use ANN recall with k = 15 (Kobak & Berens 2019).
First, we modified TriMap to use the 15 nearest neighbors in Euclidean metric. This did not change the visual appearance of the MNIST embedding (Figs. S3a b). Next, additionally omitted the random triplets. The resulting embedding became visually closer to the InfoNC-t-SNE embedding Finally, additionally setting all the weights Wiyk one had only small visual effect Together, these simplifications noticeably improved the global metric compared to the default TriMap, while leaving the local metric almost unchanged (Tab. SII.
(Fig. S3c
(Fig. S3d
Similar to the experiments of Wang et al. (2021). our ablations made TriMap look very similar to InfoNC-I-SNE with
(Fig. [See), suggesting that the remaining differences between them do not play major role. This refers to the details of the optimization (c.g. fixed triplets vs. randomly sampled triplets in each epoch, full-batch vs. stochastic gradient descent, momentum and adaptive learning rates, etc.), as well as to the presence/absence of the logarithm in the loss function. Since
d (lo
d(s)) ((0))+(())))))) d0
<(ij) ((ik) d( o(f))
+(()))((a))
(80)
((i))
d0
the gradients of TriMap and InfoNC-I-SNE point in the same direction, but are differently scaled. InfoNC-I-SNE prioritizes triplets with high (ø(i)) + ((lk)))((())) i.e. triplets in which the em- bedding similarity does not respect the triplet well. Note that this is conceptually different from TriMap's weights Wiyk which are based on the nigh-dimensional similarities. However, at least on MNIST, this difference in gradients did not have major effect (Figs. S3d
Note that our default for InfoNC---SNE is m = 5 instead of m = 1. On MNIST, this setting yields better local score and a similar global score compared to 1, and much better scores than the default TriMap (Tab, [T).. The work of & Collins (2018) theoretically underpins our observation in Fig. S19 that the higher gets, the better InfoNC- -ONNC--SNEE.. approximates (-SNE.
25

---

Published as a conference paper at ICLR 2023
G RELATION TO OTHER VISUALIZATION METHODS
G.1 ESNE APPROXIMATIONS
A vanilla implementation of I-SNE has to compute the partition function 20) and hence scales quadratically with the sample size n. Therefore, nearly all modern t-SNE packages implement approximations. Common are Barnes-Hutt--NN (BH-I-SNE) (Yang et al. 2013; van der Maaten 2014) and FFT-accelerated interpolation-based t-SNE (FU-SNE) (Linderman et al. 2019). Both methods approximate the repulsive interaction between all pairs of points and the computation of the partition function, achieving complexities Okn (n)))) and (kn22)) respectively. In fact, all our t-SNE plots are done with the FIt-SNE implementation of openTSNE (Policar al. 2019).
The focus of our work is not primarily accelerating i-SNE, but on understanding its relation to contrastive neighbor embeddings. Different from the 1-SNE approximations above, these do not approximately compute the partition function, but either learn it (NC-1-SNE), use a fixed normal- ization parameter (Neg-t-SNE and UMAP), or do not require at all (InfoNC-I-SNE), They only sample nmn repulsive interactions per epoch. This cuts their complexity down to Okknndd) In particular, they scale linearly with the embedding dimension d and can therefore be used for more general representation learning with > 2, unlike BH-+-SNE and FIt-SNE.
G.2 OTHER CONTRASTIVE t-SNE APPROXIMATIONS
In addition to NC-1-SNE and InfoNC-t-SNE, there are two other, recent campling-bbseed strategies to approximate (-SNE, GDR-I-SNE (Draganov al. 2022) and SCE (Yang al.) (023). Both sample m repulsive interactions per each attractive interaction. In order to scale these repulsive interactions properly, an estimate of the partition function is computed.
In GDR-E-SNE, the sum of the Cauchy kernels of the mkn repulsive interactions over each epoch are added up to obtain an estimate of SNE (0). mkn/ (n(n 1)). Since both the number of repulsive interactions and the estimate of the partition function are decreased by factor of mkk(n 1) compared to the vanilla L-SNE, the overall repulsion strength is correct. In contrast, SCE Yang et al.) 2023) initializes its estimate of the partition function with the maximum value nnn 1) and then updates it using a moving average after each sampled repulsive pair. Both Draganov et al. (2022)
and Yang al. (2023) use m 1. Their approaches are similar to NCE in that they approximately estimate 2 using the sampled noise points, while NCE treats Z as learnable parameter and performs
gradient descent on it. Note, however, that the second factor of the NCE gradient in Eq. (39) is not present in the approaches of Draganov et al. (2022) and Yang et al. 2023
G.3 LARGEVIS
Large Vis (Tang et al.) 2016) was, to the best of our knowledge, the first contrastive neighbor embed- ding method. It uses NEG. Since it quickly overshadowed by very similar UMAP, we focused the exposition in the main paper on UMAP. Damrich & Hamprecht (202I) computed Large effective loss function in closed form. In notation it reads
CLargeVis (8) = =- -ojj-plog(((1)) (()() -ymlEsj- log(1 ((1)))
(81)
The are some implementation differences between Large and UMAP, but in terms of the loss function, the main difference is the > factor in front of the repulsive term, which defaults 7. Therefore, our analysis of UMAP carries over to Large Vis: Its loss is essentially an instance of NEG with inverse square kernel. The additional factor 7 moves it along the attraction-repulsion spectrum towards more repulsion, that is, towards (-SNE.
G.4 PACMAP
Pairwise Controlled Manifold Approximation Projection (PaCMAP) (Wang et al. 2021) is a recent visualization method also based on sampling repulsive forces per attractive force (with m = 2 by default). It employs a large number of additional design choices, such as weak attraction between 'mid-near' points in addition to attraction between nearest neighbors (which are based modified Euclidean distance, as in TriMap), several optimization regimes with dynamically changing loss weights, etc. Nevertheless, the core parts of its loss can be related to (generalized) Neg-I-SNE.
26

---

Published as a conference paper at ICLR 2023
The attractive loss in PaCMAP is
de + d +
c.
(82)
+++
with 10 for nearest neighbors (and switched off during the final stage of the optimization). The attractive loss for Neg-f-SNE with uniform noise distribution and Z = c|xl//m
000 for mid-near points but that part of the loss
((d) o(d) + -oo
(dlvo)2+1+++ (
1
log
(83)
Thus, the differences are the logarithm and some rescaling of the distances. Note that Neg-t-SNE with e 10 typically produces very similar result compared to the default = 1 (cf. Fig I)
The repulsive loss in PaCMAP is
1+ d?
(84)
2+ d2
2+ d2
Again it is similar the repulsive loss of Neg-t-SNE, but now for Z ||/m, the default negative sampling value also used by UMAP:
((d) (dd) + +1 11) log ((d) (1d)+1)
(0(0)1))= log
1+d 2 + d2
- log 1
(85)
Here, the difference is just in the logarithm, similar to the connection between TriMap and InfoNC-t-SNE in Supp. [F]
Empirically, PaCMAP embeddings of high-dimensional data like MNIST look similar to UMAP embeddings, and hence to Neg-I-SNE embeddings, in agreement with our analysis.
H QUANTITATIVE EVALUATION
This section provides quantitative evaluation of the Neg-t-SNE spectrum. For each embedding on the spectrum, we compute two metrics. The first metric, &NN recall with = 15 (Kobak & Berens 2019). measures the fraction of nearest neighbors in the embedding that are also nearest is therefore a measure of local quality. The second
neighbors in the reference configuration. metric is the Spearman correlation between the pairwise distances in the embedding and in the reference configuration (Kobak & Berens 2019). To speed up the computation, we consider all pairwise distances between sample of 5000 points. Since most random pairs of points are not close to each other, this is a measure of global quality.
As reference configuration, use three different layouts for each dataset. We compare against the original high-dimensional data to measure how faithful Neg-I-SNE embeddings are. Additionally, compare the corresponding (-SNE and UMAP embeddings investigate for which Z value Neg-t-SNE matches t-SNE and UMAP the best.
We found that compared the high-dimensional data, the &NN recall followed an inverse U-shape across the spectrum (Fig. (Sa). ANN recall was low for very large and for very small values of Z. It peaked when Z was close to t-SNE's partition function ZISSNE and NC-I-SNE's learned nor- malization parameter NNC-I-SNE At UMAP's normalization constant ZUMAP the kNN recall was usually lower. This confirms our observation that the local quality of the embedding improves when decreasing Z from ZUMAP to SNE in agreement with Böhm et al. (2022). The ANN recall for the Kuzushiji-49 dataset at = Z SNE was very low, compared to other datasets. We suspect that this was due to incomplete convergence (Fig. S17 Tab. S4).
Conversely, the Spearman correlation mostly increased with Z (Fig. S4b), which aligns with our finding that higher attraction improves the global layout of the embedding.
We also computed the :NN recall and the Spearman correlation for the proper t-SNE and UMAP embeddings (not depicted in Figs. S4a b). The &NN recall was higher for t-SNE embeddings than for Neg-t-SNE at 2 = SNE (see, e.g., Fig. (181). likely because proper t-SNE considers the repulsive interaction between all points. The metries for the UMAP embeddings and the Spearman
27

---

Published as a conference paper at ICLR 2023
correlation for t-SNE were close to the corresponding values for Neg-t-SNE the respective Z values.
When comparing Neg-t-SNE embeddings to the proper t-SNE embedding. the best fit in terms of KNN recall (Fig. S4ch and terms of Spearman correlation (Fig. S4d) was usually achieved when Z was close to 7 in accordance with our theory. Again, the Kuzushiji-49 dataset was an outlier, likely due to convergence issues.
Finally, when comparing Neg-t-SNE embeddings to the UMAP embedding, the highest Spearman correlation was achieved by Z x ZUMAP (Fig. S4f). in agreement with our theoretical predictions. The highest &NN recall was typically achieved slightly lower Z (Fig. S4e
Overall, these experiments provide empirical support for our interpretation of the Neg-I-SNE spec- trum as implementing trade-off between global and local structure preservation, and they confirm the predicted locations of t-SNE- and UMAP-like embeddings on the spectrum.
We computed the ANN recall and the Spearman correlation also for the embeddings in Figs. S18 and [S19, where we varied the number of noise samples m and the initialization method for NC-t-SNE and InfoNC-t-SNE. As expected, we found that higher m improves the KNN recall, but t-SNE proper achieved higher kNN recall still. The Spearman correlation decreased with m when we initialized randomly and did not change much for other initialization methods. Random initialization hurt the Spearman correlation significantly.
I
TOY DATASET
Cor. 2 predicts that the partition function of a Neg-t-SNE embedding should equal the Z value. In our real-world examples (panels [ in Figs. [ between them, but not perfect agreement. As discussed in Sec. [ this is due to the shape of the Cauchy kernel and the fact that the data distribution is zero for many pairs of points. Here, consider toy example for which observe a perfect match between Neg-t-SNE's partition function and the value, confirming our Cor. 2
we observed monotone relationship
As operate with the binary skNN graph, the only possible high- -iah-diimnnional similarities are zero and one. Due to the heavy tail of the Cauchy kernel, we would like our toy example to have no pairs of points for which the data distribution is zero. Thus, all pairs of points need to have equal high-dimensional similarity. In two dimensions, only up to three points can be placed equidistantly from each other. Therefore, we consider the simple case of placing three points according to the Neg-I-SNE loss function with p = ī (there are six directed edges) for various values of Z. We keep the Cauchy kernel as similarity function, which has maximum 1/(1 + 0?) = 1. Thus. it is not possible to match values above 7 6. and the three points end up having the same position in the embedding. But for smaller values of Z, the resulting partition function is indeed exactly equal to Z (Fig. (5).
For this experiment we decreased the batch size to 6 and the learning rate to 0.01, but kept all other hyperparameters at their default values.
J DATASETS
We used the well-known MNIST (LeCun et al. 1998) dataset for most of our experiments. We
downloaded it via the torchvision API from http://yamn lecun, wttp///n..o//e//////cceeoe st/ This website does not give a license. But httpp::/
/o/api dataaaaae daddaaatttssmmmmmem mn iss and html name Yann LeCun and Corinna Cortes
http::/wwwy wwwppp.......................... or.. wtto///aaaaaaaaaaoeeea ado as copyright holders and claim MNIST to be licensed under CC BY-SA 3.0, which permits use and adaptation. The MNIST dataset consists of 70000 grayscale images, 28 x 28 pixels each, that show handwritten digits.
The Kuzushiji-49 dataset (Tarin et al. 2018) was downloaded from rois- cools-coo/// ceoodh/kmnisse kmnist where it is licensed under CC-BY-4.0. It contains 270 grayscale im- ages, 28 x 28 pixels each, that show 49 different cursive Japanese characters.
com/
28

---

Published as a conference paper at ICLR 2023
0.25
MNIST
0.8
Imbalanccd MNIST
Imbalanced
0.20
Zehrafish
0.7
Zebrofish
Brain organoid
0.6
Brain organoid
C-clegans
0.5
C-elegans
INN
0.10
Kuzashiji-4
0.4
Kuzushiji-H 49
Z
0.3
2
0.05
NCNSs
0.2
NCN
ZUMAr
0.1
20MAP
10
10
10
10"
10"
10
10
10
10
2
(a) Relative to the high-dimensional data
(b) Relative to the high-dimensional data
Imbrllanced
0.9
Imbulanced
Zehrafish
correlation
Zebmoiis
Brain organoid
0.8
Brain organoid
C-elegans
C-elegans
2NN
0.2
Kuzushiji-ii 49
Kuzushiji 49
0.1
-
0.6
Z
NNV
NCN
2UMAP
0.5
20MAP
0.0
10'
10
10
10"
10
10"
10
10
10"
10
(c) Relative to L-SNE embeddings
(d) Relative to i-SNE embeddings
0.6
Imbslancced
Imbulanced
0.5
Zehrafish
Spermmn correlation
0.9
Zobmfiis
Brain organoid C-elegans
Brain organoid
0.4
0.8
C-elegans
RNN
0.3
Kuzushiji 49
Kuzushijji 49
0.2
-
0.7
-
0.1
NCN
2UMAP
20MAP
0.0
10
10
10
10"
10"
10"
10
10
10"
10"
(e) Relative to UMAP embeddings
(I) Relative to UMAP embeddings
Figure S4: Quantitative evaluation of embeddings on the Neg-t-SNE spectrum with respect dif- ferent reference configurations. Means and standard deviations over three random seeds are plotted. Left column: 6NN recall, measure of local agreement. Right column: Spearman correlation, measure of global agreement. First row: Comparison of Neg-t-SNE embeddings to the high- dimensional input data. Second row: Comparison of Neg-t-SNE embeddings to the correspond- ing t-SNE embedding. Third row: Comparison of Neg-t-SNE embeddings to the corresponding UMAP embedding.
The SimCLR experiments were performed on the CIFAR-10 Krizzevsky 2009 dataset, another standard machine learning resource. We downloaded sklearn. datasstt. wtw.ttssfehhhhpc.ooecc ce API from ltttt::// /tetts::/www.opptt www.ml..ww....mmmmmmmmmmmmmmm... appenml.org/searcc.. Unfortunately, we were able to find license for this dataset. CIFAR- 10 consists of 60000 images, 32 x 32 RGB pixels each, depicting objects from five animal and five vehicle classes.
the
The transcriptomic dataset of Kanton et al. (201)) was downloaded from https:// www.ebi.cd www.kk/arraeerresaa..... weweeeeperrrreee i experiments/eee..... mww.mm//--ta----55-5
which permits free use. We only used the 20272 cells in the human brain organoid cell line '409b2'. The transcriptomic dataset of Wagner et al.] (0118) was downloaded hww.hhhw...hhh.aa..amma. harvard. wdw/paaaeeeeee http:/paapppbbbibbeeee websites/wagnee
its scanpy
version hoopppsss///leetttolosss... hms zebrafish ott.e//iniiicccrroo/////aaaaaaee nebi. nih. wwt. hct.:.............o.g/eeeeer.... html, The full dataset at hhtps::/ //www.
free to download and
produce. The dataset contains gene expressions for 63 530 cells from a developing zebrafish em-
bryo. The downloaded UMIs of both datasets preprocessed in (Böhm al. 2022
Kobak
29

---

Published as a conference paper at ICLR 2023
7
6
Partition function
5
4-
3
2
1
Z
2
3
4
5
6
7
Figure S5: Partition function of Neg-t-SNE embeddings three equidistant points. There is a perfect fit between Z and the partition function until = 6, which is the largest partition function set of three points with six directed edges can have under the Cauchy kernel. Beyond this value, all three points overlap in the embedding. Mean with standard deviation over three random seeds is plotted.
function of Z for toy dataset with
After selecting the 1000 most variable genes, we normalized the library sizes to the median library size in the dataset, log- transformeed the normalized values with log2(2 1), and finally reduced the dimensionality to 50 via PCA.
& Berens 2019).
The transcriptomic dataset of the elegans flatworm (Packer al.. 2019 Narayan al. 2021
was obtained from /ttp::/cbb. csail 1. ,mit. edu/ clo densvis. / dat aastss with consent of the authors who license it under CC BY-NC 2.0. It is already preprocessed 100 principal components.
K IMPLEMENTATION
K. PACKAGES
All contrastive embeddings were computed with our PyTorch (Paszke et al. 2019) implementa- tion of Neg-t-SNE, NC-t-SNE, UMAP, and InfoNC-t-SNE. Exceptions are Fig. and analogous
There, for panel g we used the reference implementation of NCVis (Artemenkov (with fixed number of noise samples m, and not the default schedule), and for panel h we used U.5 The t-SNE plots were created with the openTSNE (Poličar et al. 2019) (version 0.6.1) package. Similarly, used the reference UMAP implementation in Fig. S] and oSen'SSNE in Figs. and The TriMap plots in Supp. F were computed with version 1.1.4 of the TriMap package by Amid Warmuth (2019).
Figs. STT
S16
& Panoy 2020
We extended these implementations of NCVis. UMAP, and t-SNE to make them accept custom embedding initializations and unweighted s&NN graphs and to log various quantities of interest. We always used the standard Cauchy kernel for better comparability.
K.2 INITIALIZATION, EXAGGERATION AND S&NN GRAPH
All PCAs were computed with sklearn (Pedregosa al. 2011). We used PyKeOps (Charlier et al.) 2021) to compute the exact skNN graph and to handle the quadratic complexity computing the partition functions
GPU. The same PCA initialization and sÀNN graph with & = 15 were used for all embeddings. The s&NN graph for MNIST and Kuzushiji-49 was computed on a 50- dimensional PCA of the dataset.
We initialized all embeddings with a scaled version of PCA (save for Figs. S18 and S19 For
t-SNE embeddings rescaled the initialization so that the first dimension has standard deviation of 0.0001 (as is default in OSEN) for all other embeddings to a standard deviation of 1. For TriMap, stuck to its default of scaling the PCA down by factor of 0.01.
30

---

Published as a conference paper at ICLR 2023
We employed some version of "early exaggeration' (yan der Maaten & Hinton 2008 for the first 250 epochs in most non parametric plots. For t-SNE it is the default early exaggeration of openTSNE. When varying 2 in non- non-parametre, parametric Neg-t-SNE, early exaggeration meant using 2 = [X]] [X|/m for the first 250 epochs (save for Fig. [STT). When varying the number of noise samples in Figs. S88 ST8
and [ST9] we still used m = for the first 250 epochs. In Figs. 2 ST and [S2] as well in all reference NCVis or UMAP plots, we did not use early exaggeration as neither small 2 nor high m made it necessary. When we used some form of early exaggeration and learning rate annealing, the annealing to zero took place over the first 250 epochs, was then reset, and annealed again to zero for the remaining. typically 500, epochs.
K.3 OTHER DETAILS FOR NEIGHBOR EMBEDDING EXPERIMENTS
When computing logarithms during the optimization of neighbor embeddings. we clip the arguments to the range [10 10 1], save for Fig. S2 where we varied this lower bound. The lower bound is smaller than in the reference implementation of parametric UMAP, where it is set 10-4.
Our defaults were a batch size of 1024, linear learning rate annealing from 1 (non-parametricc or 0.001 (parametric)
(save for Figs. ST and [S2) 750 epochs (save for Figs. [S10 and (T7) and
m = 5 noise samples (save for Figs. S8 S10
S18 and S19).
Non- von-paramettic runs were optimized with SGD without momentum and parametric runs with the Adam optimizer (Kingma & Ba 2015). Parametric runs used the same feed-forward neural net architecture as the reference parametric UMAP implementation. That is, four layers with dimensions imput dimension - 100 100 - 100 - 2 with ReLU activations in all but the last one. We used the vectorized, 786-dimensional version of MNIST as input to the parametric neighbor embedding methods (and not the 50-dimensional PCA; but the skNN graph was computed in the PCA space for consistency with non-parametric embeddings).
Like the reference NCVis implementation, we used the fractions qe, g0,z(z) (x))/(g (x) + m) instead of (xx) (go,z (xx + mf(x)). This is mild approximation as the noise distribution is close to uniform. But it means that the model learns scaled data distribution (ef. Cor 2 so that we need to multiply the learned normalization parameter Z by n(n 1) when comparing to t-SNE or checking normalization of the NC-t-SNE model. Similarly, we also approximate the true noise distribution by the uniform distribution for the fractions qo (x))(g((x) + lm/ instead of go (x)) (go(x) + Zm{(x)) in our Neg-t-SNE implementation.
We mentioned in Sec. [ and showed in Fig. S8 that one can move along the attraction-repulsion spectrum also by changing the number of noise samples m, instead of the fixed normalization con- stant 2. In UMAP's reference implementation, there is a scalar prefactor y for the repulsive forces. Theoretically, adjusting 7 should also move along the attraction-repulsion spectrum, but setting higher than 1 led to convergence problems in (Böhm et al. 2022), Fig. All. When varying our Z, did not have such issues.
For panels in Figs. 1 S11 S16 the Neg-t-SNE spectra were computed for Ž equal to ((B--SN)), &NC-E-SNE and [xn .z, where E 15-10-5, 1-10- 1.2-,,,111111 2-10-4, 10-4,5-10- 4,--10-44 ..... 1-102, 2- 102, 5- 102)..
K.4 SIMCLR EXPERIMENTS
For the SimCLR experiments, we trained the model for 1000 epochs, of which we used 5 epochs for warmup. The learning rate during warmup was linearly interpolated from the initial lean- ing rate. After the warmup epochs, we annealed the learning rate with cosine schedule (without restarts) to 0 (Loshchilov & Hutter, 2017 We optimized the model parameters with SGD and mo- mentum 0.9. We used the same data augmentations as in Chen et al. (2020) and their recommended batch size of 1024. We used a ResNet18 (H et al. 2016) as the backbone and a projection head consisting of two linear layers (512- 1024 128) with ReLU activation in-between. The loss was applied to the L2 normalized output of the projection head, but like Chen et al. (2020) we used the output of the ResNet the representation for the linear evaluation. As similarity function used the exponential of the normalized scalar product (cosine similarity) and always kept the temperature at 0.5, suggested in Chen et al. (2020).
31

---

Published as a conference paper at ICLR 2023
Table S2: Run time overview for the most compute-heavy experiments
Number of runs
Time per run [min] (mean-tSDD)
Neg-t-SNE for Figs. S11
S13
$14
S15
360
39 +
Neg-t-SNE for Fig. ST6
24
121 + 44
Neg-t-SNE for Fig. ST7
3592 44
NC-I-SNE (our implementation) for Fig. S10b
3
786 2
SimCLR runs for Tab.
721 +
Table S3: Learned normalization parameter for NC-t-SNE and partition function of t-SNE in our experiments. Mean and standard deviation is computed over three random seeds. In our setup t-SNE deterministic.
NC [10%]
Z(0t SNE) [10%]
MNIST Fig. 1
+
8.13
MNIST without EE Fig.
$11
3.1
6.25
MNIST imbalanced Fig. ST2
6.15
3.12
Human brain organoid Fig. 513
3.07
1.30
Zebrafish Fig. S14
3.1
7.98
C. elegans Fig. S15
36.9
11.7
Kuzushiji-49 Fig. S16
395 +
89.6
The ResNet was trained on the combined CIFAR-10 train and test sets. When evaluating the aceu- racy, we froze the backbone, trained the classifier on the train set, and evaluated its accuracy on the test set. We used sklearn's 's WNeighborsCC ass fier with cosine metric and 15 neighbors and sklearn's Logi st settiiieeessssss on classifier with the SAGA solver (Defazio et al. 2014), regularization penalty, a tolerance of 0.0001, and max ster=1000. Other parameters were left at the default values.
When sampling negative samples for a given head, we excluded that head from the candidates for negative samples. We sampled negative samples with replacement. If the desired number of negative samples m equals twice the batch size minus 2 (n 2b 2, 'full-batch repulsion'), we took the entire batch without the current head and its tail negative samples for that head.
K.S CODE AVAILABILITY
Our code is publicly available. The PyTorch implementation of contrastive neighbor embeddings can be found at https:::////. //tithub..b/////// com wrenssab/eae wataaa/oottsstiiiiaaaaaaaa ne Details for repro- ducing the experiments and figures, alongside scripts and notebooks are at chttps://gii com/ wwwphhhiiuiinhhahaaeeeeeiieaiiih ceteed/cllsseeeeeee clt.:ce-mttseepppppp umap
K.6 STABILITY
Whenever we reported a metric or show graph, we ran the experiments for 3 different random seeds reported the mean the standard deviation. When the standard deviation was very small, omitted it from the main text and report it in Tab, SS Save for the usually approximate s&NN graph computation, t-SNE does not depend on a random seed. As we computed the s&NN exactly with PyKeOps (Charlier et al. 202T), t-SNE is deterministic in framework.
$16 show the standard deviation as shaded area. Again, the standard never larger than 0.006 in panels [ of Figs. SIT [16 Similarly, the standard deviation in Figs. S9
Panels in Figs. I S11
deviations very small and barely visible. The ratio of standard deviation to
and S10 shown shaded area, is mostly smaller than the line width.
32

---

Published as a conference paper at ICLR 2023
10
10'
time
I-SNE
UMAP
10
non-param GPU non non-param CPU
param GPU
param CPU
211
2/2
2/3
2/4
215
26
batch size
Figure S6: Run times of the embedding optimization phase for the MNIST dataset using different batch sizes, training modes, and hardware. Running on GPU is much faster than CPU; non- parametric runs are faster than parametric runs. As the batch size increases, the run time decreases strongly in all settings.
K.7 COMPUTE
We ran our neighbor embedding experiments on a machine with 56 Intel(R) Xeon(R) Gold 6132 CPU @ 2.60GHz, 502 GB RAM and 10 NVIDIA TITAN Xp GPUs. The SimCLR experiments were conducted on SLURM cluster node with 8 cores of an Intel(R) Xeon(R) Gold 5220 CPU @ 2.20GHz and Nvidia V100 GPU with RAM limit of 54 GB. Each experiment used one GPU at most.
Our total compute is dominated by the neighbor embedding runs for Figs. S S13 S16 and S1Ob and by the SimCLR experiments. Tab. [S2 lists the number of runs and the average run time. We thus estimate the total compute time to be about 646 hours.
Our implementation relies on pure PyTorch and our experiments were conducted on GPUs. We originally kept the batch size for all our experiments the default of 1024, motivated by Chen et al. (200)) and Sainburg et al. (202T), but eventually noticed that the run time of the visualization experiments depends crucially the batch size (Fig. S6). Increasing the batch size to 2 decreased the run time of the embedding optimization on MNIST data (without the s&NN graph computation) from about 40 min just above 20 For batch size of at least 216 our implementation was faster than the reference implementations of UMAP and (-SNE (via openTSNNE). The latter run only on CPU, while our experiments ran on GPU. Nevertheless. we observed substantial improvement in run time for higher batch sizes also when running our Py PyTorch implementation on CPU and also when training parametric embedding. Note that the parametric setting with full batch gradient descent (batch size 1,500,006 for MNIST's skNN graph) exceeded our GPU's memory. On CPU, our implementation is just shy of the performance UMAP when using 219 attractive pairs per batch. Dedicated CUDA implementations (Chan al. 2018 Eisenmann. 2019 Nolet et al.) 2021) outperform our implementation on GPU. Compared to the Sumba-acceleree tion of UMAP and the CUDA-acceleruue GPU implementations, arguably strikes a good speed / complexity trade-off, is easier to study and adapt by the machine
CPU implementa- pure PyTorch implementation
learning community, and seamlessly integrates non-parametric and parametric settings well as all four contrastive loss functions.
Note that the change from NC-t-SNE to Neg-t-SNE is as simple fixing the learnable normalization parameter to a constant, so the original NCVis code written in C++ can easily be adapted to compute Neg-I-SNE. We have not used this for any of the experiments our paper.
33

---

Published as a conference paper at ICLR 2023
Algorithm S1: Batched contrastive neighbor embedding algorithm
input list directed skNN graph edges E [i1j....., Aaataa
parameters 0
// embeddings (non muon-param.)/ network weights (param.)
number of epochs T
learning rate
number noise samples m Cauchy kernel
// of embeddings (non-param.) / network output (param.)
batch size b loss mode mode normalization constant 7
// default (2) required for mode = -Neg-t-SNE
output:
final embeddings ,n,...,
mode = NC-t-SNE then
Z ==
for / = 0 to do
// Learning rate annealing
Nt 17- (1 4)
0
while < | do ==
for 3 = =,...,,,bbl
// Treat attractive edge la+sJa+s and noise edges lat8j7
// Sample noise edge tails but omit head of considered edge Jm. ~ (irtmmm((
// Aggregate loss based mode
10
mode = Neg-t-SNE then
L L log
golio=ajote)
Ex= log 1
do (..
90(nn=No==1) (m/
go(in+a5p 2m
else if mode
NC-t-SNE then
9olla+8do+s)/2
Ex=1 log (1
gotta ( o1i)
f L log
4o(6o44))=a)/22 /2mm
(6( )/Z+m
else if mode
InfoNC-I-SNE then
C = L - log
go ((in==)o==)+20 (o(Ho055
else mode
UMAP then
(o (oata3aat))) Em log (1 go ((++4977))
L = L log
// Update parameters with SGD (non-param.) Adam (param.)
18
= 0 - ?i VoL.
19
if mode NC-t-SNE then
Z = Z n1 22
21
a a b
Shuffle E
return 0
34

---

Published as a conference paper at ICLR 2023
L
ADDITIONAL FIGURES
4,0
Attr. UMAP
3.5
Attr. Nog-I-SNE
Rep. UMAP
2.5
Rep. Neg-s-NNE
2.0
1.5
0.5
0.0
Emhodding distance
Figure S7: Attractive and repulsive loss terms of UMAP and Neg-I-SNE. The main difference is that UMAP's repulsive loss diverges at zero challenging its numerical optimization. The attractive terms are log(1 dit)) and log(2 + dly) for UMAP and Neg-t-SNE, respectively, and the repulsive ones are log ((1 + d and log ((2 + dt + d.y)). respectively.
To
(a)
(b) = 50
(c) 500
(d) 2b 2 = 2046
Figure S8: Neg-t-SNE embeddings of the MNIST dataset for varying number noise samples and using batch size b 1024. While for NC-I-SNE and InfoNC-I-SNE more noise samples improve the approximation to i-SNE, see Figs. STS and ST9 changing m Neg-I-SNE moves the result along the attraction- attraction-repulsion repulsion spectrum (Fig. with more repulsion for larger m. However, the computational complexity of Neg-t-SNE scales with m, so that moving along the spectrum via changing / is much more efficient. For the first 250 epochs, m set to achieve effect similar to early exaggeration (Supp.[K)
35

---

Published as a conference paper at ICLR 2023
puramctric noG paramotiic
paranctrie
1x10
con-pomaaettiic
Normalizatioo
1.0
purametric
Loss
10
son-parametric
0.5
10"
$x-10
0.0
200
400
600
750
200
.400
600
750
200
400
600
750
Eppcciss
Eppocss
Epoclas
(a) InfoNC-L-SNE loss
(b) NC-I-SNE loss
(c) NC-1-SNE normalization
Figure $9: (a, b) Loss curves for the parametric and non non-parametric InfoNC-I-SNE and NC-L-SNE optimizations leading Figs. 3b and While the embedding scale differs drastically between the non- parameertetic and the parametric run, the loss values are close. (c) Normalization the model Ei (ij)/Z for the parametric and non-parametric NC-t-SNE optimizations. The difference in the embedding scale is compensated by three orders of magnitude change in Z, so that both versions learn approximately normalized models. These experiments used our NC-t- t-SNE reimplementation.
NCVis, m=
PF
NCVis, m=5.
PF
NOVis, m=
NCVIS, m=5,
10
NCVis, m=50,
PF
NCVis, 500, PF
Partition function
NCVis, 5=
Partition fumetion
NCVis, m=500, Z
NCVis, 5000
A-NE
NCVis, 5=500, Z
10
10"
ISNE
10"
10'
250
500
750
5000
10000
Epochs
Epochs
(a)
(b)
Figure S10: NC-t-SNE learns to have the same partition function (PF) as t-SNE on the MNIST dataset. The higher the number of noise samples (a) or the longer the optimization (b), the better the match. Both methods used early exaggeration, which for NC-1-SNE meant to start with m noise samples for the first 250 epochs. The learned normalization parameter Z converged to but did not exactly equal NC-t-SNE's partition function E,, qo (iz). Nevertheless, it was the same order magnitude. Again, the match was better for more noise samples. Since we reinitialized the leamable Z for NC-1-SNE after the early exaggeration phase, there were brief jumps in the partition function and Z at the beginning of the non non-exaggerated phase.
36

---

Published as a conference paper at ICLR 2023
T6
(a) 2 -
(b) 2 -SNE
2 Z
NCV
(d) ă |X/mm
(c) 2 |X|/m
10"
10"
10²
10
10
10
10a
(c)
(c)
10
2
10
10
(f) t-SNE
(g) NCVis
(h) UMAP
(i) Partition function
Figure S11: (a-e) Neg-t-SNE embeddings of the MNIST dataset for various values of the fixed normalization constant Z. As Z increases, the scale of the embedding decreases, clusters become more compact and separated before eventually starting to merge. The Neg-I-SNE spectrum produces embeddings very similar those of (f) t-SNE, (g) NCVis, and (h) UMAP, when Z equals the partition function of t-SNE, the learned normalization parameter Z of NCVis, or [ //m = (²)/m used by UMAP, as predicted in Sec. 4
(i) The partition function En, (1 + d. - tries to match did not use early exaggeration here, but initialized the Neg-t-SNE and t-SNE with PCA rescaled so that the first dimension has standard deviation 1 and 0.0001, respectively. This makes the embeddings with small Z values show cluster fragmentation, similar to the t-SNE embedding in (f) without early exaggeration. For very low Z, the Neg-t-SNE embedding in (a) shows very little structure.
Z and grows with In contrast Fig.
37

---

Published as a conference paper at ICLR 2023
100
To
10
(a) 7 < 7-SNE
(b) 7 = 7 -SNE
(c) 7 = 2 NCVs
(d) 7 X mm
(c) 7
10*
10
10
10'
10
10
10
10a
10
(a)
(b)
т6
10
10
10
10"
(f) S-NNE
(g) NCVis
(h) UMAP
(i) Partition function
Figure S12: (a-e) Neg-t-SNE embeddings of an imbalanced version of the MNIST dataset for various values of the fixed normalization constant Z. As Z increases, the scale of the embedding decreases, clusters become more compact and separated before eventually starting merge. The Neg-I-SNE spectrum produces embeddings very similar to those of (f) I-SNE, (g) NCVis, and (h) UMAP, when Z equals the partition function of t-SNE, the learned normalization parameter of NCVis, or | (²)m /m used by UMAP, as predicted in Sec. 4 (i) The partition function (1 dey ) tries to match Z and grows with it. Similar to early exaggeration in t-SNE we started all Neg-t-SNE runs using Z |X]/m and only switched the desired Z for the last two thirds of the optimization. The dataset was created by randomly removing 10 c% of the class of digit e, so that the class sizes linearly decrease from digit digit 9.
38

---

Published as a conference paper at ICLR 2023
106
15
T6
(a) Z < Z.-NNE
(b) 7 = ZASNE
(c) 7 z NCVs
(d) Z
|X|/m
(c)
XX Xl/m /m
10
10²
10
10
10y
10
Z
days
days
10 days
10"
15 days
10
month
(b)
mouths
10
10
10
10"
mouths
10
(f) t-SNE
(g) NCVis
(h) UMAP
(i) Partition function
Figure S13: (a e) S-NE spectrum on the developmental single-cell RNA sequencing dataset from Kanton al. (2019) for various parameters Z. As Z increases, the scale of the embedding decreases and the continuous structure (corresponding to the developmental stage) becomes more apparent, making higher Z more suitable for visualizing continuous datasets (Böhm et al. 2022). The spectrum produces embeddings very similar to those of (f) t-SNE and (g) NCVis when Z equals the partition function of t-SNE the learned normalization parameter of NCVis. The UMAP embedding in (h) closely resembles the Neg-I-SNE embedding at Z = |X|m = (²)/m. (i) The partition function Ei + d of the Neg-I-SNE embeddings increased with Z. Similar to early started all Neg-I-SNE runs using Z | and only switched the
exaggeration in i-SNE desired Z for the last two thirds of the optimization. The dataset contains 20 272 cells and is colored by the duration of the development. There are times fewer cells collected after 10 days than after one month.
39

---

Published as a conference paper at ICLR 2023
100
T6
16
70
10
(a) Z < Z.SNE
(b) Z = Z SNE
(c) Z = NCYs
(d) 2 |X//m /m
(e) 2 >
|
10
10
10'
10a
10
10
z
hpf
hpf
hpf
hpf
10
14 hpf
(d)
10
2
18 hpf
10"
10"
10
10
To
24 hpf
(1) 1-SNE
(g) NCVis
(h) UMAP
(i) Partition function
Figure $14: ea Neg-I-SNE spectrum on the single-cell RNA sequencing dataset of developing
zebrafish embryo (Wagner et al. 2018) for various parameters Z. As Z increases, the scale of the embedding decreases and the continuous structure (corresponding to the developmental stage) becomes more apparent, making higher Z more suitable for visualizing continuous datasets (Bhhm et al. 2022). The spectrum produces embeddings very similar to those of (f) t-SNE and (g) NCVis when Z equals the partition function of t-SNE or the learned normalization parameter of NCVis. The UMAP embedding in (h) closely resembles the Neg-I-SNE embedding at = |X//m = (²)mm.
(i) The partition function E;, (1 d -1 of the Neg-t-SNE embeddings increased with Z. Similar to early exaggeration in t-SNE started all Neg-t-SNE runs using Ž |X|/m and only switched to the desired Z for the last two thirds of the optimization. The dataset contains 63 530 cells and colored by the hours post fertilization (hpf). There are ten times fewer cells collected after hours than after 24.
40

---

Published as a conference paper at ICLR 2023
T0b
100
To
10
(a) 2 < ZeSSNE
(b) 7 Z SNE
(c) 2 = 2 NCVs
(d) 2
|X| /m
(c)
XX|
Xl/m
10
10
10
10
10
10
Z
10
(d)
10
(1)
2
16
10"
10
10
10"
(f) t-SNE
(g) NCVis
(h) UMAP
(i) Partition function
Figure S15: (a-e) Neg-t-SND spectrum of the single-cell RNA sequencing dataset of the C. elegans flatworm (Packer et al. 2019, Narayan et al.) 2021) for various values of the fixed normalization constant Z. As Z increases, the scale of the embedding decreases, the scale of the embedding decreases, and more continuous structure becomes apparent. The Neg-t-SNE spectrum produces embeddings very similar those of (f) t-SNE, (g) NCVis, and (h) UMAP, when Z equals the partition function of (-SNE, the learned normalization parameter Z of NCVis, or XX] X|/m (?) /m used by UMAP, as predicted in Sec. 4 (i) The partition function Ei (1 + df,) ) tries to match Z and grows with it. Similar to early exaggeration in t-SNE started all Neg-t-SNE runs using = X X and only switched to the desired for the last two thirds of the optimization. The dataset contains information on 86 0224 cells of 37 types indicated by the colors. It is imbalanced with only 25 cells of the least abundant type but 31 375 cells of unknown type (grey).
41

---

Published as a conference paper at ICLR 2023
10
100
To
(a) Z < Z
(b) Z Z
(c) Z NCVs
(d) 2 |
(e) 2 >
|
10
10'
10"
10
10 1
10" 11
10
Z
10
(c)
(c)
(d)
10
(a)
10"
To
10"
10
10
10"
(1) I-SNE
(g) NCVis
(h) UMAP
(i) Partition function
Figure S16: (a- (a-e) Neg-t-SNE embeddings of the Kuzushiji-4y -49 dataset (Tarnn al. 2018) for var- ious values of the fixed normalization constant Z. As Z increases, the scale of the embedding decreases, clusters become more compact and separated before eventually starting merge. The Neg-I-SNE spectrum produces embeddings similar to those of (f) 1-SNE, (g) NCVis, and (h) UMAP, when Z equals the partition function of t-SNE, the learned normalization parameter Z of NCVis, or | = (2) /mm used by UMAP, as predicted in Sec. 6 (i) The partition function (1
tries to match Z and grows with it. Similar early exaggeration in I-SNE started all Neg-I-SNE runs using = | and only switched to the desired for the last two thirds the opti- mization. The dataset contains 270912 images of 49 different Japanese characters. The classes are imbalanced with 456 to 7 000 samples per class. We see that a higher level of repulsion than UMAP's Z |X//m helps visualize the discrete structure of the dataset. The sampling based Neg-t-SNE embedding at Z ZtSSNE has less structure than the t-SNE embedding. Fig. S17 and Tab. S4 show that the Neg-t-SNE result improves for longer optimization.
(a) 500 epochs
(b) 1000 epochs
(c) 5000 epochs
(d) 10000 epochs
Figure $17: Neg-I-SNE embeddings of the Kuzushiji-49 dataset (Tarin al. 2018 Z 2ISNE show more structure when optimized longer. Similar to early exaggeration in t-SNE started all Neg-t-SNE runs using Z = |X|/m for 250 epochs and only switched to the desired for the remaining number of epochs indicated in the subcaptions.
42

---

Published as a conference paper at ICLR 2023
Table S4: Longer run times improve the Neg-t-SNE optimization on the Kuzushiji-49 dataset (Tainn et al. 2018) for Z = S The KL divergence is computed with respect to the normalized model
40 (25 (o()))
Epochs
500
1000
5000
10000
Partition function [10%]
18.96 + 0.02
13.27 + 0.01
6.93 + 0.01
5.75 + 0.01
Neg-I-SNE loss
1021 + 2
832 2
630 =1
599 +
KL divergence
5.52 + 0.01
5.18 + 0.01
4.76 + 0.01
4.65 0.00
INN: 0.11 Spear:
KNN: 0.17 Speae: 0.11
KNN: 0.30 Spear: 0.07
INN: 0.36
Spear: 0.13
10
To
100
(a)
(b) 50 random init
(c) 500
(d) t-SNE random init
random init
random init
KNN: 0.6 Spear 0.34
INN: 0.30 Spect: 0.35
ANN: 0.36
KNN: ILII Spear: 0.35
Spear: 0.38
TO
(e)
(1) m = 50 PCA init
(g) = 500
(h) ENE PCA init
PCA init
PCA init
VNN: ILII Spear: 0.35
INN: 0 Spear: 0.54
INN: 0.29
Speat: 0.33
To
(i)
(i 50
(k) = 500 EE
()) L-SNE EE
EE
EE
Figure S18: NC-I-SNE (our implementation) on the MNIST dataset for varying number of noise samples m and different starting conditions. Higher number of noise samples m improves the ap- proximation quality to t-SN (last column). The first row is initialized with isotropic Gaussian noise and the second and the third rows with PCA (both normalized to have standard deviation of one or 0.0001 in the first dimension for NC-+-SNE or t-SNE, respectively). In the third row, the first 250 epochs used m = 5 and the latter used the given m value for NC-I-SNE. This is similar to I-SNE's early exaggeration that we used in panel || NC-I-SNE seems to be less dependent on early exag- geration than t-SNE, especially for low m values. Insets show the &NN recall and the Spearman correlation between distances of pairs of points. Higher increases the ANN recall, while mostly leaving the Spearman correlation unchanged. Random initialization hurts the Spearman correlation, but not the &NN recall.
43

---

Published as a conference paper at ICLR 2023
KNN: 0.16
ENNN 0.28 Spear: 0.10
KNN: 0.36
KNN: 0.10 Spear U22
Spear
100
(a)
(b) 50 random init
(c) 500
(d) t-SNE random init
random init
random init
Spear: 0.35
INN 0,14
INN: 0.28 Spear 0.35
KNN: Spear 0.36
(e)
(f) 50 PCA init
(g) 500 PCA init
(h) t-SNE PCA init
PCA init
UNN: LLOO Spear: 0.36
KNN: 0.14 Sperr 0.35
Spear 0.34
INN: 0.23
INN: 0.35
Spert 0.35
TO
TO
( m
(i) m 50 EE
(k) 500
()) t-SNE
EE
Figure S19: InfoNC-I-SNE the MNIST dataset for varying number of noise samples and different starting conditions. Higher number of noise samples m improves the approximation quality t-SNE (last column). The first row is initialized with isotropic Gaussian noise and the second and the third rows with PCA (both normalized to have standard deviation of one or 0.0001 in the first dimension for InfoNC-I-SNE
t-SNE, respectively). In the third row, the first 250 epochs used m = 5 and the latter used the given m value for infoNC-t-SNE This is similar to t-SNE's early exaggeration that we used in panel []] InfoNC-t-SNE seems be less dependent on early exaggeration than I-SNE, especially for low values. Insets show the ANN recall and the Spearman correlation between distances of pairs of points. Higher m increases the iNN recall, while mostly leaving the Spearman correlation unchanged. Random initialization hurts the Spearman correlation, but not the &NN recall.
44


Reviews:
[{"review_id": "qffqBAhjvKS", "reviewer": "Reviewer_gEqf", "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": "The authors discuss noise contrastive estimation (NCE) and negative sampling (NEG) in the context of dimensionality reduction and their connection to t-SNE and UMAP. They propose a variant of t-SNE, called NEG-t-SNE, which relies on NEG to reduce the complexity and produce more compact clusters.", "summary_of_the_review": "The authors need to expand the connection to contrastive learning and, especially TriMap and provide comparisons. They also need to highlight their main contributions and distinguish the new results from previous approaches such as LargeVis. Also, I recommend providing further evidence that tuning other hyperparameters in t-SNE and UMAP (such as perplexity) fails to provide a similar effect as the one proposed in NEG-t-SNE.\n", "strength_and_weaknesses": "### Strength:\n* The authors do a reasonably well job motivating the problem and discussing NCE and NEG in the context of word embedding and dimensionality reduction.\n\n### Weaknesses:\n* The current version of the paper fails to distinguish itself from previous work, especially different variants of t-SNE (e.g., Barnes-Hut t-SNE) or its relation to UMAP, discussed in Böhm et al. (2022). It is hard to pinpoint the main contribution of the paper ito using negative samples (already done in UMAP and LargeVis).\n* The main shortcoming is the lack of comparison to TriMap, which is the only DR method that truly relies on contrastive learning! Unlike what the authors discuss in Section 2, TriMap is not a variant of UMAP (TriMap stands for Triplet **Mapping**, IIUC, not Manifold Approximation and Projection) and uses NEG sampling (i.e., triplets) to form an embedding. It is well known that TriMap provides a distinct view of the data ito the global structure. I find the lack of comparison and discussion to TriMap as the main shortcoming of the paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "q8VWKgCZFwb", "reviewer": "Reviewer_fZKZ", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The authors propose to unify two popular neighborhood embedding method, t-SNE and UMAP, from the perspective of contrastive learning. It is shown that a single normalization constant $\\bar Z$ is controlling the visualization quality, and the same constant interpolates between t-SNE and UMAP. By making the connections, the author argue that the instability of UMAP can be remedied. ", "summary_of_the_review": "The authors make connections between t-SNE and UMAP from the contrastive learning perspective, notably using a normalization constant $\\bar Z$. I find that many statements are quite vague and informal, which unfortunately makes the contribution unclear and obscure. I would not recommend acceptance of this paper. ", "strength_and_weaknesses": "**Strengths**: it is quite useful to compare and analyze the two popular data visualization techniques, namely t-SNE and UMAP. I find it plausible that the normalization constant $\\bar Z$ is playing a crucial role in controlling the compactness of embedded clusters.\n\n**Weaknesses**: In my opinion, most arguments made in this paper are quite casual and handwaving. Other than the role of $\\bar Z$, I do not see a clear argument being made, so I didn't find myself more informed after reading this paper. \n\nThere are also crucial parts of t-SNE and UMAP that are not carefully discussed. For example, it is known that using random initialization or spectral initialization has a great impact on the visualization quality. Also, there are parameters in UMAP that determine how fat the tail is in the loss function, which presumably controls the compactness of embedded clusters. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6lHH08wc7Uy", "reviewer": "Reviewer_ZbpN", "summary": "", "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": "", "summary_of_the_paper": "The paper \"From t-SNE to UMAP with contrastive learning\" presents a new insight into the connection of two contrastive learning methods: noise contrastive estimation (NCE) and negative sampling (NEG). This insight allows to connect t-SNE and UMAP, and span a spectrum of methods along their connection. Finally, connection to other self-supervised methods (such as SimCLR) are established. Figures of the method show dimensionality reductions on MNIST. The method is accompanied by a package in PyTorch.", "summary_of_the_review": "The paper is well written and offers novel insights into the relation of NCE & NEG. This paves the way to interpolate between UMAP and t-SNE, two highly used dimensionality reduction techniques.", "strength_and_weaknesses": "Strenghts.\n- good presentation of a novel insight connecting NCE and NEG\n- well and clearly written paper\n- new insight about a connection of t-SNE and UMAP, which spans a range of methods\n\nWeaknesses.\n- the relation of NCE and NEG could benefit from more empirical support. In particular, Corollary 2 states that the resulting function q is proportional to the density with \\hat Z. Fig1(i) shows a monotonic trend, but not a precise relation (as argued on the text). For a simpler model I'd expect that one could be able to establish this relationship, which would empirically harden the statement.\n- Equation 10 shows that a Cauchy Kernel in UMAP corresponds to a inverse-square kernel in NEG. However, as far as I understood, you're using a Cauchy kernel in NEG. It'd be illustrative to see the comparison of NEG and explicit inverse-square kernel - which should show a closer resemblance to UMAP. Also, I think this difference in kernels when interpolating between the methods should be emphasized when talking about the interpolation ability.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5rK0GgM8fk", "reviewer": "Reviewer_d2PD", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper relates tSNE and UMAP, starting from linking noise contrastive estimation and negative sampling. The authors also provided analysis on linking neighbor embedding and self-supervised learning, and it leads to optimizing tSNE with InfoNCE loss. The provided experimental results demonstrates the authors' arguments.", "summary_of_the_review": "While I’m positive on this paper, I’m not very familiar with experiment parts of dimensionality reduction algorithms. Hence, I’m willing to see other reviewer’s comments.\n", "strength_and_weaknesses": "The paper extensively covers from neighbor embedding to self-supervised learning, and the authors linked those two concepts, which has the originality. Also, the paper is easy to follow, and the experimental results are promising. \n\nHowever, at the same time, the quantitative result seems to be lacking. Are there any other quantitative result that can be shown in the experiment of dimensionality reduction algorithms?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0-2v1i2zrAg", "reviewer": "Reviewer_xsMD", "summary": "", "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": "", "summary_of_the_paper": "The paper reveals the connection between t-SNE and UMAP via a new connection between the contrastive methods NCE and NEG. The paper also builds the connection between contrastive neighborhood embedding and self-supervised contrastive learning. ", "summary_of_the_review": "Overall, I am very excited about this work. As an ML practitioner, I use t-SNE and UMAP almost everyday. I always wonder what is the connection between them. This paper answers my question. I think this paper's findings are useful to the majority of the ML community. ", "strength_and_weaknesses": "Pros:\n\n1. The paper provides very novel findings. Its theory (Corollary 2) explains the NEG’s behavior in the minibatch setting. The theory seems to predict the fact that Neg-t-SNE produced more compact clusters than t-SNE. Based on its theory, the paper reveals that UMAP is NEG applied to the t-SNE framework. It explains the empirical phenomenon that UMAP pulls embedding points closer together than t-SNE. \n\n2. The paper is well-written and well-structured. I am not an expert in the field. I am not able to verify the correctness of the theory. However, following the explanation of the paper. I can grasp the high-level idea and understand the relationship between UMAP and t-SNE. \n\nSuggestions:\n\n1. It would be better if the author can give further instructions to the practitioner about how to better use UMAP and t-SNE in real practice according to the findings of this paper. As the author says, \"Our conceptual relation between UMAP and t-SNE is therefore of practical impact – as is the fact that both are just instances on a spectrum highlighting more continuous or more discrete structures.\" How should this fact affect our daily usage of UMAP and t-SNE. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster