t-SNE Exaggerates Clusters, Provably

This paper proves that t-SNE visualizations cannot reliably reflect the strength of input clustering or the extremity of outliers, thereby challenging the common belief that t-SNE outputs accurately preserve the structure of the original data.

The Gist

The Big Picture: The "Magic Map" That Lies to You

Imagine you have a giant, messy room filled with thousands of different objects (data points). Some are clearly grouped together (like all the red balls in one corner, all the blue books in another), and some are just random junk scattered everywhere.

You want to take a photo of this room and shrink it down to a flat, 2D poster so you can see the patterns. t-SNE is the most popular "magic camera" used by scientists to do this. It's famous because it usually does a great job: it pulls similar things together and pushes different things apart, making beautiful, colorful clusters on a screen.

The Problem: This paper argues that t-SNE is a bit of a magician who pulls rabbits out of hats that aren't there. It is so good at making things look organized that it can trick you into seeing structure where none exists, or hide structure that is actually there.

The authors prove two main things:

1. It exaggerates clusters: It can make a messy pile of sand look like distinct islands, even if the sand was just one big, uniform pile.
2. It hides outliers: If you have a single, weird object that doesn't fit anywhere (an outlier), t-SNE will often force it to fit in with the crowd, hiding its weirdness.

---

1. The "Imposter" Clusters (Making the Messy Look Organized)

The Analogy: Imagine you have a group of people standing in a room.

• Scenario A: They are standing in two tight, distinct groups (Team Red and Team Blue), far apart from each other.
• Scenario B: They are all standing in one giant, jumbled circle, barely touching each other.

If you ask t-SNE to take a picture of both scenarios, it will produce the exact same picture for both.

What the paper proves:
The authors show that you can take a dataset that is perfectly un-clustered (like Scenario B) and tweak the distances between the points just a tiny bit. Even though the data is now "messy," t-SNE will still spit out a beautiful, clean picture with two distinct islands (Scenario A).

The Takeaway:
If you see a pretty, clustered t-SNE plot, you cannot be sure that your data actually has those clusters. The map might be lying. It's like looking at a weather map that shows a sunny day, but you're actually standing in a thunderstorm. The map is just "optimizing" to look nice, not to be accurate.

2. The "House of Cards" Instability (One Tiny Change, Total Chaos)

The Analogy: Imagine a house of cards. If you have a perfectly balanced structure, it looks great. But if you blow a tiny breath of air (a tiny change in the data), the whole thing collapses into a pile.

What the paper proves:
t-SNE is incredibly unstable. If you have a dataset that looks like a "regular simplex" (a geometric shape where every point is roughly the same distance from every other point, like a perfect pyramid), t-SNE can turn it into any shape you want just by changing the distances between points by a microscopic amount (like 1%).

The Takeaway:
Because high-dimensional data (like gene sequences or text) often behaves like this "perfect pyramid" where distances are all similar, t-SNE is essentially playing with a house of cards. A tiny, invisible change in the data can make the clusters appear, disappear, or merge completely. You can't trust the stability of the picture.

3. The "Poison Point" Attack (One Bad Apple Spoils the Bunch)

The Analogy: Imagine a classroom where the students are sitting in two distinct groups: Math kids and Art kids.
Now, imagine you sneak one single student into the room who sits exactly in the middle of the room, equidistant from everyone.

What the paper proves:
If you add just one "poison point" (a single data point placed strategically in the center), t-SNE's entire worldview collapses.

• Before: The Math and Art kids are clearly separated.
• After: t-SNE gets confused. Because the poison point is the "nearest neighbor" to almost everyone, t-SNE drags all the Math and Art kids toward the poison point. The two distinct groups merge into one big, messy blob.

The Takeaway:
t-SNE is incredibly fragile. An attacker (or just a random glitch) only needs to add one weird data point to completely destroy the ability to see the real clusters in your data.

4. The "Outlier" Eraser (Hiding the Weirdos)

The Analogy: Imagine a party where 99 people are dancing in a circle, and one person is standing 100 feet away in the corner, screaming.

• A normal camera (like PCA): Would show the crowd in the center and the screaming person far away.
• t-SNE: Would drag the screaming person right into the middle of the dance circle and make them look like they are part of the group.

What the paper proves:
t-SNE is mathematically incapable of showing extreme outliers. Its goal is to keep points close to their neighbors. If a point is too far away, t-SNE gets confused and forces it to be close to someone, even if that someone is far away in reality.

The Takeaway:
If you are using t-SNE to find fraud (like a credit card thief who looks very different from normal users), t-SNE will likely hide the thief. It will tuck the thief into the crowd of normal users, making them invisible. If you need to find the "weirdos," do not use t-SNE.

---

Summary: What Should You Do?

The authors aren't saying "Stop using t-SNE." They are saying: "Don't trust it blindly."

• Don't assume: Just because you see a cluster, it doesn't mean the data is actually clustered.
• Don't ignore: Just because you don't see an outlier, it doesn't mean one isn't there.
• Be skeptical: t-SNE is a tool for exploration, not for proof. It's great for getting a "vibe" of the data, but if you need to make scientific conclusions based on the shapes you see, you need to double-check with other methods (like PCA) or mathematical proofs.

In short: t-SNE is a talented artist who loves to paint pretty pictures, but sometimes it paints things that aren't really there, or erases the things that are. Always check the canvas against the reality.

Technical Summary

1. Problem Statement

t-Distributed Stochastic Neighbor Embedding (t-SNE) is a ubiquitous tool for visualizing high-dimensional data, widely trusted by practitioners to reveal underlying cluster structures. While existing theoretical work has proven that t-SNE can successfully preserve true cluster structures (generating "true positives" for well-separated inputs), there has been a lack of rigorous analysis regarding its potential to generate false positives (creating clusters from unclustered data) and false negatives (hiding existing clusters).

The authors address the critical gap: Can one reliably infer the strength of input clustering or the existence of extreme outliers from a t-SNE visualization? The paper argues that the answer is no, demonstrating that t-SNE can fundamentally misrepresent both cluster salience and outlier severity.

2. Methodology

The authors employ a combination of theoretical analysis and empirical validation:

• Theoretical Framework:

  • They analyze t-SNE as an optimization problem minimizing the Kullback-Leibler (KL) divergence between input affinity matrices ($P$) and output affinity matrices ($Q$).
  • They define stationary points (local minima) of the t-SNE objective function.
  • They utilize specific metrics to quantify input quality: Silhouette Score, Calinski-Harabasz Index, and Dunn Index for clustering strength, and a geometric definition of $\alpha$-outliers for outlier extremity.
  • Key theoretical tools include the properties of additive invariance (shifting squared distances by a constant) and the asymmetry between input and output affinity calculations.

• Experimental Design:

  • Adversarial Attacks: Constructing "impostor" datasets that are mathematically distinct from the original but produce identical t-SNE outputs.
  • Poison Point Injection: Adding single or multiple adversarial points to disrupt cluster structures.
  • Comparative Analysis: Benchmarking t-SNE against Principal Component Analysis (PCA) and UMAP on synthetic data (Gaussian mixtures, regular simplices) and real-world datasets (PBMC single-cell genomics, BBC news articles, financial fraud data).

3. Key Contributions & Theoretical Results

A. Misrepresentation of Cluster Salience

The paper proves that the visual "tightness" of clusters in a t-SNE plot does not correlate with the actual separation of clusters in the input data.

• Theorem 3 (Impostor Datasets): For any well-clustered dataset $X$, there exists an "impostor" dataset $X_\epsilon$ with arbitrarily weak cluster separation (approaching a uniform distribution) such that $t\text{-SNE}(X) = t\text{-SNE}(X_\epsilon)$.
  • Mechanism: This relies on the additive invariance of t-SNE. If one adds a constant $C$ to all squared inter-point distances, the conditional probabilities $P_{j|i}$ remain unchanged because the normalization factor absorbs the shift. This allows the construction of datasets that are nearly unclustered (e.g., near a regular simplex) but produce perfectly clustered visualizations.
• Theorem 5 (Instability): Conversely, arbitrarily small perturbations to the input distances (making them nearly identical) can result in vastly different t-SNE outputs.
  • Implication: t-SNE is highly unstable on high-dimensional data where distances concentrate (near-simplex regime), making it impossible to distinguish between a highly structured input and a random one based solely on the output visualization.

B. Vulnerability to "Poison Points"

The authors demonstrate that t-SNE is extremely sensitive to the insertion of a single adversarial point.

• Theorem 7: A single "poison point" placed at the centroid of a dataset can destroy the cluster structure of a well-separated input, making it visually indistinguishable from an unclustered input.
  • Mechanism: In high dimensions, a point at the mean becomes the nearest neighbor to almost all other points. This hijacks the affinity matrix, forcing all points to cluster around the poison point rather than their true natural clusters.

C. Misrepresentation of Outliers

The paper proves that t-SNE is incapable of depicting extreme outliers.

• Theorem 9: For any stationary t-SNE embedding $Y$, the outlier coefficient $\alpha(Y)$ is bounded by approximately 3.266.
  • Mechanism: The output affinity matrix $Q$ uses a heavy-tailed t-distribution. If an outlier is too far away in the input, the gradient of the loss function with respect to that point remains non-zero, pushing the point closer to the bulk of the data until stationarity is reached.
  • Result: Even if the input contains an extreme outlier (e.g., in fraud detection), t-SNE will compress it into the cluster structure or place it on the periphery, failing to represent its true isolation.

4. Results & Empirical Evidence

• Impostor Datasets: Using the PBMC3k single-cell genomics dataset, the authors constructed an impostor dataset with a silhouette score near zero (unclustered) that produced a 2D t-SNE plot visually identical to the real, well-clustered data.
• Poison Point Attacks: In a mixture of two Gaussians, adding a single point at the mean caused the t-SNE visualization to collapse into a single blob, whereas PCA correctly maintained the two-cluster structure. This effect persisted even with 5,000 points.
• Outlier Suppression: In financial fraud detection (where fraud cases are statistical outliers), t-SNE mixed fraudulent users with legitimate ones, while PCA successfully separated them. Similarly, in synthetic data with 100 extreme outliers, t-SNE absorbed them into the main cluster, whereas PCA preserved their isolation.
• UMAP Comparison: The authors note that UMAP exhibits similar failure modes regarding outlier suppression and instability near the simplex, though it is slightly less sensitive to single poison points than t-SNE.

5. Significance and Implications

• Scientific Caution: The paper fundamentally challenges the "black box" trust in t-SNE. It warns that visual clusters in t-SNE plots cannot be taken as evidence of strong separation in the original high-dimensional space.
• Downstream Impact: Since t-SNE is used for hypothesis generation in fields like genomics and NLP, these findings suggest that conclusions drawn from t-SNE visualizations (e.g., "these cell types are distinct") may be artifacts of the algorithm rather than data properties.
• Algorithmic Limitations: The work identifies specific mathematical properties (additive invariance and affinity asymmetry) that cause these failures. This suggests that fixing t-SNE would require altering its core objective function, potentially sacrificing its ability to filter noise.
• Future Directions: The authors suggest that researchers must develop provable guarantees for visualization methods and exercise extreme caution when interpreting low-dimensional embeddings, particularly regarding cluster strength and outlier detection.

In summary, the paper provides a rigorous mathematical proof that t-SNE is provably unreliable for inferring the strength of clusters or the existence of extreme outliers, urging the data science community to treat t-SNE visualizations with significant skepticism.