Clustering with t-SNE, provably

By George C. Linderman, Stefan Steinerberger. 2017

280 citations recorded by the source corpus.

t-distributed Stochastic Neighborhood Embedding (t-SNE), a clustering and visualization method proposed by van der Maaten & Hinton in 2008, has rapidly become a standard tool in a number of natural sciences. Despite its overwhelming success, there is a distinct lack of mathematical foundations and the inner workings of the algorithm are not well understood. The purpose of this paper is to prove that t-SNE is able to recover well-separated clusters; more precisely, we prove that t-SNE in the ‘early exaggeration’ phase, an optimization technique proposed by van der Maaten & Hinton (2008) and van der Maaten (2014), can be rigorously analyzed. As a byproduct, the proof suggests novel ways for setting the exaggeration parameter α and step size h. Numerical examples illustrate the effectiveness of these rules: in particular, the quality of embedding of topological structures (e.g. the swiss roll) improves. We also discuss a connection to spectral clustering methods.

Subfields: Computational Theory and Mathematics, Molecular Biology, Statistical and Nonlinear Physics, Representation & Self-Supervised Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Molecular Biology

In Statistical and Nonlinear Physics

In Representation & Self-Supervised Learning

Citations in the corpus

UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction (2018, background): “In theoretical analyses of t-SNE such as [38] results are obtained only under an early exaggeration regimen with either large constant (of order of the number of samples), or in the limit of innite exaggeration.”
Understanding How Dimension Reduction Tools Work: An Empirical Approach to Deciphering t-SNE, UMAP, TriMAP, and PaCMAP for Data Visualization (2020, neutral): “We briefly note that some research (see, e.g., Linderman and Steinerberger, 2019) looked into the dynamics of the optimization process applied by t-SNE and showed that finding a good loss function for the graph layout is similar to finding a good loss function for a discrete dynamical system.”
Automated optimized parameters for T-distributed stochastic neighbor embedding improve visualization and analysis of large datasets (2019, background): “In a recent publication, Linderman and Steinerberger 23 prove that in general t-SNE embedding will not converge if a product of EE factor α and of ﬁ xed learning rate step size η is larger than the number of datapoints n (i.e., if αη > n ).”
Unmasking Clever Hans predictors and assessing what machines really learn (2019, methodology): “The connection between SC and t-SNE described in [150] can also be observed in all following results, making t-SNE a suitable tool for visually supporting the analysis via SC.”
A Unifying Perspective on Neighbor Embeddings along the Attraction-Repulsion Spectrum (2020, methodology): “Carreira-Perpiñán (2010) and Linderman and Steinerberger (2019) noticed that the attractive term in the t-SNE loss function reduces to the loss function of Laplacian eigenmaps.”
Stochastic Neighbor Embedding under f-divergences (2018, background): “Only recently researchers showed that if the high-dimensional input data does contain prominent clusters then the 2D t-SNE visualization will be able to successfully capture the cluster structure [12, 3].”
Dissecting stellar chemical abundance space with t-SNE (2018, background): “Recently, Linderman & Steinerberger (2017) demonstrated that two other hyper-parameters of t-SNE can be chosen optimally: the learning rate should be set to ∼ 1, and the early-exaggeration parameter should be set to ∼ 0 .”
An Analysis of the t-SNE Algorithm for Data Visualization (2018, methodology): “While it was not made rigorous, similarity with the power method was discussed in the work of Linderman and Steinerberger (2017).”
Efficient Algorithms for t-distributed Stochastic Neighborhood Embedding (2017, background): “Linderman and Steinerberger (2017) showed that this early exaggeration phase is essential for convergence of the algorithm and that when the exaggeration coefficient α is set optimally, t-SNE is guaranteed to recover well-separated clusters.”
Randomized Near Neighbor Graphs, Giant Components, and Applications in Data Science (2017, methodology): “There are a great many other methods of dimensionality reduction that start by constructing a graph that roughly approximates the data, for example t-distributed Stochastic Neighborhood Embedding (t-SNE) [16, 31], diﬀusion maps [7] or Laplacian Eigenmaps [2].”
Automated Optimal Parameters for T-Distributed Stochastic Neighbor Embedding Improve Visualization and Allow Analysis of Large Datasets (2018, background): “In a recent publication, Linderman and Steinerberger 24 prove that in general t-SNE embedding will not converge if a product of EE factor a and of fixed learning rate step size h is larger than the number of datapoints n (i.e. if a h > n ).”
Mapping Scientific Knowledge in Systematic Literature Reviews Through Embeddings and Bibliometric Techniques (2026, unknown): “Recent studies confirm that, through a two-stage process similar to spectral clustering, the method preserves local structure while reducing dimensionality from 768 to 2D [44], [45].”