TL;DR
Popular data visualization tools like t-SNE and UMAP compress high-dimensional datasets into 2D or 3D plots under the assumption that they faithfully preserve local neighborhood structures. This paper proves mathematically that for most datasets—even those with clear cluster structures or sparse connectivity—constant-dimensional embeddings cannot faithfully preserve these neighborhoods. Instead, the required dimension must scale with the number of data points, challenging the foundational aspirations of low-dimensional data visualization.
What Problem Does This Paper Address?
When data scientists project a 1,000-dimensional dataset down to a 2D scatter plot, they know they are losing information. Thanks to classical mathematical theorems, we know it is impossible to preserve all pairwise distances (near-isometry) in low dimensions. However, practitioners justify using methods like t-SNE and UMAP by arguing that these algorithms don't need to preserve all distances—they just need to keep local neighborhoods intact (i.e., keeping close points close and far points far).
This paper tackles a fundamental question: Is it actually mathematically possible to preserve neighborhood structures in a constant number of dimensions (like 2D or 3D)?
The authors formalize this by framing the data's neighborhood structure as an unweighted graph and analyzing the minimum dimension required to embed this graph into a target metric space. They define a property called $\alpha$-preservation, where all graph neighbors are mapped within a threshold distance $r$, and all non-neighbors are separated by at least $\alpha \cdot r$.
Methods
The authors use a rigorous graph-theoretic and metric geometry framework to establish lower and upper bounds on the embedding dimension:
- $\alpha$-Preservation Dimension: They define the dimensionality of the target space using the doubling dimension—a highly general metric concept that counts how many small balls are needed to cover a larger ball. This ensures their impossibility results apply to any valid metric space, not just Euclidean space.
- Clique and Neighborhood Partitions: To find the limits of compressibility, the authors connect embedding difficulty to graph invariants. They show that graphs with large "clique partitions" (groups of fully connected nodes) or distinct "neighborhood partitions" force the embedding dimension to scale upwards because you cannot pack too many distinct structures into a tight low-dimensional space.
- Probabilistic Analysis: The authors analyze how these geometric constraints behave on average by evaluating them against random graph models.
- Volume and Polynomial Arguments: For normed and Euclidean spaces, they employ volume bounding techniques and Warren’s theorem on the sign assignments of polynomials to prove strict lower bounds.
Datasets
Because this is a purely theoretical paper, no real-world empirical datasets were used. Instead, the authors evaluate their theorems against three mathematical graph models that simulate common data structures:
- Erdős–Rényi Random Graphs ($G_{n, 1/2}$): Used to represent "typical" or general graph structures.
- Random $k$-Regular Graphs: Used to model sparse datasets where every point has a fixed, limited number of neighbors.
- Planted Partition Model (Stochastic Block Model): Used to simulate datasets with distinct, intrinsic cluster structures.
Key Insights and Ideas
- Locality Doesn't Save You: Even though $\alpha$-preservation is a drastically weaker constraint than full distance preservation, it is still fundamentally bottlenecked by the number of points $n$. For the vast majority of graphs, a dimension of $\Omega(\log n)$ is strictly necessary.
- The Normed Space Penalty: When forcing embeddings into normed spaces (like Euclidean space $\ell_2$), the problem becomes exponentially harder. For general graphs, the required dimension jumps from logarithmic ($\Omega(\log n)$) to linear ($\Omega(n)$).
- Clusters Don't Bypass the Barrier: You might hope that if your data has clean, well-separated clusters, a 2D plot could easily capture it. The paper proves this wrong: even with highly salient cluster structures, preserving local neighborhoods within those clusters still requires $\Omega(\log n)$ dimensions.
- A Phase Transition in Euclidean Space: For Euclidean embeddings, the authors discovered a sharp threshold. Below a certain value of $\alpha$, low-dimensional embedding is possible and depends on the graph's eigenvalues; above this threshold, faithful neighborhood preservation becomes mathematically impossible.
Key Results
- General Metrics: An overwhelming fraction of graphs require a dimension of $\dim_\alpha(G) = \Omega\left(\frac{\log n}{\log(8/\alpha)}\right)$. Even sparse, regular graphs typically require $\Omega(\log n / \log \log n)$ dimensions.
- Normed Spaces: If you want to be able to reconstruct the graph from the embedding ($\alpha > 1$), general graphs require a crushing linear dimension of $\Omega\left(\frac{n}{\log(\frac{16}{\alpha-1})}\right)$. For Euclidean space at $\alpha=1$, the bound is strictly $\Omega(n)$.
- Clustered Data: In a planted partition model with $k$ clusters, the required dimension is lower-bounded by $\Omega\left(\frac{(1-\xi)\log n + \xi \log(k/2c)}{\log(8/\alpha)}\right)$, where $\xi$ represents cluster salience. If $\alpha > 1$, it requires $\Omega(\log n)$ dimensions regardless of how distinct the clusters are.
Limitations and Future Work
The primary limitation of this work is its focus on worst-case and average-case random graphs. Real-world datasets are rarely completely random; they often lie on smooth, low-dimensional manifolds. The authors acknowledge that exploring how manifold structures interact with $\alpha$-preservation is a vital next step.
Additionally, the paper deals with strict neighborhood preservation. Future work could relax these definitions to explore approximate $\alpha$-preservation—for instance, determining the minimum dimension required if an algorithm is allowed to misrepresent a small, acceptable percentage of neighborhoods.
Summary updated