t-SNE Exaggerates Clusters, Provably

AI summary

Overview

Research area: Machine learning theory, specifically the theoretical analysis of dimensionality reduction and data visualization methods (t-distributed stochastic neighbor embedding, t-SNE).

Technical level: Advanced. The paper is a theory paper built on formal definitions, theorems, and proofs about the stationary points of the t-SNE objective, supplemented with experiments. The writing is aimed at readers comfortable with optimization and metric geometry, though the headline messages are stated in plain terms.

Scope: The paper proves that t-SNE visualizations can misrepresent both the strength of cluster separation in the input data and the extremity of outliers in the input data, and it demonstrates both failure modes on synthetic and real datasets.

What This Paper Is About

t-SNE is widely trusted because practitioners believe its plots roughly reflect the structure of the input data. Prior theory had shown that well-separated, spherically clustered inputs do produce clustered t-SNE plots (true positives), but nobody had analyzed whether t-SNE can also produce clusters where there are none (false positives) or hide clusters that exist (false negatives). This paper proves, via formal theorems, that the degree of clustering and the severity of outliers in the input cannot always be inferred from the t-SNE output, and it shows that these failure modes occur in practice.

Key Contributions

1. Misrepresentation of cluster salience. The authors prove that any well-clustered t-SNE visualization can be produced identically by a strongly separated input and by an arbitrarily weakly separated input (Theorem 3 and Corollary 4), and that tiny distance perturbations of the input can lead to vastly different visualizations (Theorem 5).
2. An adversarial attack on cluster structure. Understanding the mechanism behind these results, the authors design an attack that disrupts the cluster structure of the output by moving as little as one point (Figures 4, 10, 15).
3. Misrepresentation of outliers. The authors prove that no stationary t-SNE output — regardless of its input — can depict an extreme outlier, formalized as a bound on the "outlier number" of the embedding (Theorem 9).
4. Empirical demonstration on real data. They show the predicted phenomena on a single-cell genomics dataset (PBMC3k, 2638 points, 50 dimensions), a financial fraud dataset, and BBC news article embeddings (n=2225, D=1024), and report preliminary comparisons with UMAP.

The authors state that, to the best of their knowledge, this is the first work to theoretically analyze some of the key limitations of t-SNE.

Main Findings

• Cluster strength cannot be read off the plot. For any n-point dataset X with a partition into k > 1 clusters (each of size > 1), and for every 0 < ε ≤ 1, there exists an "impostor" dataset X_ε with average silhouette score ε times that of X such that t-SNE_ρ(X) and t-SNE_ρ(X_ε) have exactly the same set of stationary points, for any perplexity ρ ∈ [1, n−1]. So a strongly clustered input and a minimally separated one are indistinguishable from the visualization alone.
• A perfectly clustered embedding can be a stationary point for arbitrarily unclustered inputs. For even n ≥ 4 with a balanced two-way partition, there is a sequence of datasets {X_ε} with average silhouette score ε, and a visualization Y with silhouette score 1 that is a stationary point (local and, per the appendix proof, global) for every member of the sequence.
• Small input perturbations cause large output changes. For any ε > 0 and any two outputs in the image of the t-SNE map, there exist two datasets whose pairwise squared distances agree within a factor of 1 ± ε, yet whose t-SNE stationary points are those two chosen outputs.
• Near-simplex data generate every possible output. The set Δ_ε of datasets whose pairwise squared distances all lie in [1−ε, 1+ε] satisfies t-SNE_ρ(Δ_ε) equal to the entire image of t-SNE, for every ε > 0. Experiments perturb a 200-point unit regular simplex with ε ≤ 0.01 and produce strikingly different plots. The authors connect this to the concentration of measure phenomenon, since many high-dimensional datasets fall into this regime.
• The underlying mechanism is additive invariance. t-SNE is invariant not only to multiplicative scaling of input distances but also to additive shifts of squared interpoint distances: if ||x′_i − x′_j||² = ||x_i − x_j||² + C ≥ 0, then the stationary point sets coincide (Lemma 17). This is also discussed by Lee and Verleysen (2011, 2014).
• A single poison point can destroy a clustered visualization. In a dataset of 400 points sampled from a mixture of two Gaussians in R^2000, placing one point at the mean of the data (giving 401 points) collapses the two-cluster picture in t-SNE while PCA still shows the clusters. The effect persists for 1000-point and 5000-point variants.
• Formal version of the poison-point result. For even n ≥ 4, there exist datasets X_0 (silhouette score 0 with respect to all partitions) and X_1 (silhouette score (√3−1)/√3 ≥ 0.42 with respect to some partition) and a point x_0 such that, at ρ = 1, t-SNE_ρ(X_0 ∪ {x_0}) equals t-SNE_ρ(X_1 ∪ {x_0}). The authors note this makes a clustered and an unclustered input indistinguishable from their t-SNE loss landscapes, and that experiments show similar degradation at typical perplexity settings.
• Outliers are provably capped in the output. Defining the "outlier number" α(X) via a separating hyperplane of margin at least α · max{1, diam(X \ {x_0})}, the authors prove that for any stationary t-SNE embedding Y in the image of the t-SNE map, α(Y) ≤ 3.266 + o_n(1). Even an extreme outlier input cannot be depicted past roughly α ≈ 3.6.
• In practice, outliers get absorbed. On both synthetic and real data, t-SNE seldom depicts outliers past α > 0.2, and sometimes places them inside the convex hull of the other points (yielding α = 0). In the fraud dataset, t-SNE mixes fraudulent users into the bulk of points while PCA separates them; on a mixture of two Gaussians plus 1, 10, and 100 outliers, t-SNE treats the outliers as essentially part of the cluster structure, whereas PCA's outliers overtake the embedding.
• Asymmetry between input and output affinities explains the outlier result. The input affinity behaves like a normalized, symmetrized nearest-neighbor graph with a lower bound of 1/(2n) on the aggregate affinity of the outlier, while the output affinity behaves more like a radius-neighbors graph and is optimized to place the outlier near at least some points even if it was far from them in the input.
• Poison points versus outliers are distinct failure modes. On BBC news article RoBERTa embeddings (n=2225, D=1024) clustering into five topics, injecting 220 poison points (roughly 10%) can halve the silhouette score of the t-SNE embedding with respect to the ground-truth labels, whereas injecting 1100 points (roughly 50%) as α-outliers with α ∈ (0.8, 1) does not degrade the cluster structure.
• PCA pre-processing does not eliminate the problem. With 1000 points sampled from a mixture of two Gaussians in 100 dimensions, applying PCA pre-processing at various strengths still yields a sequence of datasets with similar visualizations but widely different input cluster strengths (measured by silhouette score and aspect ratio). Exact additive invariance holds without PCA pre-processing but not with it.
• Preliminary UMAP comparisons. UMAP's output is qualitatively unchanged between a single-cell dataset and its near-simplex impostor, but UMAP does not display exact additive invariance. UMAP also shows extreme instability near the unit simplex; its response to a single poison point is less pronounced than t-SNE's, though injecting multiple poison points can still substantially change cluster shapes.

Methodology in Plain English

The authors work with the standard t-SNE formulation: input affinities P built from Gaussian kernels with per-point bandwidths chosen so that the entropy of each conditional distribution matches log₂ρ (ρ is the perplexity), symmetrized as P_ij = (1/2n)(P_{i|j} + P_{j|i}); output affinities Q built from a t-distribution; and the objective being the KL divergence between P and Q, minimized over the embedding coordinates.

Rather than studying only the output of a particular optimization run, the authors analyze the set of all stationary points of the objective for a given input. They then ask which inputs share the same stationary point set, constructing explicit "impostor" datasets that are deliberately unclustered or near-simplex but produce identical sets of stationary points, and proving that such constructions always exist.

The technical engine is additive invariance: t-SNE depends on squared interpoint distances only through their differences, so adding a constant to every squared distance leaves the stationary points unchanged. By inflating or deflating distances according to this invariance, the authors can make a clustered input look like a near-simplex input, or vice versa, without changing what t-SNE can output. To quantify clustering they use the average silhouette score, and prove the same statements with respect to the Calinski-Harabasz index and the Dunn index in the appendices. To analyze outliers, they define a hyperplane-margin-based outlier number and analyze the t-SNE gradient at a stationary point, comparing the aggregate outlier affinity in the input (lower-bounded at 1/(2n) by normalization) against the output, showing that a sufficiently far outlier would have nonzero gradient.

Empirically, they run t-SNE on synthetic Gaussian mixtures, an adversarially perturbed unit simplex, a single-cell genomics dataset (PBMC3k), a credit-card fraud dataset, and BBC news article embeddings, comparing against PCA and, in the appendices, UMAP. Code is available at the project's GitHub repository.

Why This Matters

Impact on research. The paper shifts attention from t-SNE's true-positive guarantees to its false positives and false negatives, showing that existing performance guarantees for well-clustered inputs do not license the reverse inference practitioners commonly make. It identifies additive invariance and input/output affinity asymmetry as the structural causes, and it follows a recent line of work (including Snoeck et al., 2026) arguing that misrepresentation in constant-dimensional embeddings is geometrically inevitable, with this paper pinning down how it manifests in t-SNE specifically.

Real-world applications.

• Single-cell genomics: A t-SNE plot of PBMC3k data can look essentially identical whether the underlying clusters are strongly or barely separated, which matters for how cell types and states are interpreted.
• Fraud and anomaly detection: In a credit-card fraud dataset where 0.172% of points (492 out of 284,807) are fraudulent, t-SNE mixes the fraudulent users into the bulk while PCA keeps them largely separated — so t-SNE is the wrong tool for that task.
• Text and topic analysis: On BBC news article embeddings clustering into five topics, roughly 10% poison points can halve the silhouette score of the embedding with respect to true labels, while roughly 50% injected α-outliers with α ∈ (0.8, 1) leave the cluster structure intact — an asymmetry that could badly mislead exploratory analysis.
• General exploratory data analysis: Because t-SNE is used across fields from genomics to language model interpretability, downstream hypothesis generation, experimental design, and scientific conclusions can inherit these distortions.

Industry relevance. t-SNE is embedded in standard analysis pipelines in bioinformatics, NLP, and general analytics dashboards. The paper's findings imply that products built on t-SNE visualizations should either add corroborating metrics (such as PCA plots, distance matrices, or dendrograms) or warn users that cluster salience and outlier severity in a plot are not reliable evidence about the input.

Future Directions

• Characterizing exactly what can be deduced. The authors frame the essential open question as: what can be provably inferred from a visualization? Their results rule out some inferences but leave the positive direction open.
• Extending the theory beyond t-SNE. Preliminary experiments in the appendices suggest the failure modes may extend to other force-based dimension reduction methods such as UMAP, but no theorem is given for those methods.
• Reconciling additive invariance's costs and benefits. The paper notes it cannot rule out the utility of additive invariance, since prior work indicates it may help filter high-dimensional noise, and asks whether that benefit can be retained while avoiding exaggerated clusters.
• Understanding practical parameters. The formal poison-point theorem is proved at perplexity ρ = 1, and the authors rely on experiments to argue that similar degradation persists at typical settings; pinning down the behavior across the full perplexity range is left open.

Target Audience

This paper is most valuable to machine learning theorists working on dimensionality reduction and embedding methods, and to methodologists and statisticians who need to know what claims about data are and are not supported by an embedding plot. It also directly serves applied researchers and data scientists in genomics, fraud detection, and NLP who use t-SNE as an exploratory tool and need a precise accounting of its failure modes, plus tool builders who decide which embedding methods and diagnostics to ship in analysis software.

Authors’ abstract

Central to the widespread use of t-distributed stochastic neighbor embedding (t-SNE) is the conviction that it produces visualizations whose structure roughly matches that of the input. To the contrary, we prove that (1) the strength of the input clustering, and (2) the extremity of outlier points, cannot be reliably inferred from the t-SNE output. We demonstrate the prevalence of these failure modes in practice as well.