Why can't t-SNE capture a simple parabola structure?

As a toy example, I used t-SNE on a simple parabola to have a representation of it in one dimension.

library(tidyverse)
library(tsne)
theme_set(theme_minimal())

df_parabol <- tibble(x = seq(-5, 5, by = 0.5), y = x^2)
N <- nrow(df_parabol)
colors <- terrain.colors(N)

ggplot(df_parabol) +
aes(x, y) +
geom_point(color = colors) +
geom_text(label = 1:N)


As t-SNE use distances between points to reduce dimensions, I thought I will end up with points on a line with order following the parabola (ie 1 -> 21).

However, points are not ordered at all...

df_tsne <- as.data.frame(tsne(df_parabol, k = 1))

ggplot(df_tsne) +
aes(V1, 0) +
geom_point(color = colors) +
geom_text(label = 1:N)


I also tried several values for perplexity but I got the same results...

df_tsne_cross <-
tibble(p = c(2, 4, 10, 30, 50, 90)) %>%
mutate(lowdim = map(p, ~ tsne(X = df_parabol,
k = 1, perplexity = .)),
lowdim = map(lowdim, as.data.frame),
lowdim = map(lowdim, mutate, N = 1:N, col = colors)) %>%
unnest()

ggplot(df_tsne_cross) +
aes(V1, 0) +
geom_point(aes(color = col)) +
geom_text(aes(label = N)) +
scale_color_identity(guide = FALSE) +
facet_wrap(~ p, scales = "free")


As a comparison, PCA projects the points on the y axis.

Did I need to explore more the space of parameters? Did I expect too much from t-SNE? Do you have an explanation? What is the structure captured by t-SNE here?

Three general remarks:

1. t-SNE is excellent at preserving cluster structure but is not very good at preserving continuous "manifold structure". One famous toy example is the Swiss roll data set, and it is well-known that t-SNE has trouble "unrolling" it. In fact, one can use t-SNE to unroll it, but one has to be really careful with choosing optimisation parameters: https://jlmelville.github.io/smallvis/swisssne.html.

2. Using 1-dimensional t-SNE instead of 2-dimensional is likely to exacerbate this problem, possibly by quite a lot. One-dimensional optimisation is more difficult for t-SNE because points don't have the two-dimensional wiggle space and have to pass right through each other during gradient descent. Given that all pairs of points feel repulsive forces in t-SNE, this can be difficult, and it can get stuck in a bad local minimum.

3. t-SNE is not very good with tiny data sets. It's often easier to get a nice embedding of two million points than of twenty points. Default optimisation parameters might be inappropriate for such a tiny sample size. And by the way, perplexity larger than the sample size does not make mathematical sense (not sure what your R package is doing when you set perplexity larger than $$N$$).

With all these caveats in mind, if you are really careful with optimisation parameters, you can manage to preserve the manifold structure of your data set. But this is really not what t-SNE is for.

%matplotlib notebook

import numpy as np
import pylab as plt
import seaborn as sns; sns.set()
from sklearn.manifold import TSNE

x = np.arange(-5, 5.001, .5)[:,None]
y = x**2
X = np.concatenate((x,y),axis=1)

Z = TSNE(n_components=1, method='exact', perplexity=2,
early_exaggeration=2, learning_rate=1,
random_state=42).fit_transform(X)

plt.figure(figsize=(8,2))
plt.scatter(Z, Z*0, s=400)
for i in range(Z.shape[0]):
plt.text(Z[i], Z[i]*0, str(i), va='center', ha='center', color='w')
plt.tight_layout()


It was easy to make it work with n_components=2, but as I suspected, n_components=1 required some tinkering with optimisation parameters (early_exaggeration and learning_rate).