SpaceMAP: Visualizing High-Dimensional Data by Space Expansion

Xinrui Zu, Qian TaoICML 2022

Visualizing high-dimensional data is a bit like trying to gift-wrap a soccer ball using only a single, flat sheet of paper without any wrinkles. In data science, this is known as the "crowding problem": when you try to squash complex, high-dimensional relationships into a 2D or 3D plot, points that were distinct in the original space end up on top of each other, obscuring the true structure of the data.

A new paper from researchers at the Delft University of Technology introduces SpaceMAP, a dimensionality reduction (DR) framework that moves beyond the heuristic "hacks" of the past to provide a principled, analytical way to expand space and keep our data visualizations clean.

TL;DR

SpaceMAP is a novel visualization method that addresses the "crowding problem" by analytically matching the "capacity" of high- and low-dimensional spaces. By introducing a transformation called Equivalent Extended Distance (EED), it provably preserves the intrinsic geometry of data, outperforming state-of-the-art methods like t-SNE and UMAP in maintaining both local details and global structures.

What Problem Does This Paper Address?

High-dimensional space is weird. Our 3D intuition fails us because of a phenomenon called "concentration on the crust." In high dimensions, almost all the volume of a ball is located in a thin shell near its surface.

Illustration of the 'concentration on the crust' phenomenon

When we use traditional methods to project this data into 2D, we run into the crowding problem: because there is "more room" in high-dimensional space, a faithful preservation of distances forces all points to become neighbors in 2D. To fix this, popular tools like t-SNE and UMAP use "heavy-tailed" distributions (like the t-distribution) to push points apart. However, these methods are largely empirical—they work, but we haven't had a rigorous analytical explanation for why or a way to tune them based on the actual intrinsic dimensionality of the data.

Methods

The authors propose two major innovations:

  1. Space Expansion via EED: They define "Space Capacity" as the volume of a ball in $D$-dimensional space. To move data from $D$ dimensions to $d$ dimensions (where $d=2$ or $3$), they introduce Equivalent Extended Distance (EED). This is a mathematical transformation that scales distances so that the "capacity" of the high-D neighborhood matches the "capacity" of the low-D neighborhood.
  2. Hierarchical Manifold Approximation: Real-world data isn't just one big blob; it often has "sub-manifolds" (clusters within clusters). SpaceMAP models similarity differently for the near-field (immediate neighbors) and the middle-field (the broader neighborhood). This allows the algorithm to be "data-specific," adapting its math to whether the data is a continuous sheet (like a Swiss roll) or disjoint clusters (like digits in MNIST).

The optimization itself follows a contrastive learning framework similar to UMAP, using a cross-entropy loss function to pull similar points together and push dissimilar ones away.

Datasets

The researchers evaluated SpaceMAP on a diverse battery of tests:

  • Synthetic Benchmarks: 2D concentric rings, 3D Gaussian clouds, and various "Swiss rolls" (including one with a hole and one made of parallel lines) to test if the algorithm can "unfold" geometry without breaking it.
  • Real-World Data: Standard machine learning sets like MNIST (handwritten digits), Fashion-MNIST, COIL-20 (object images), and RNA-seq (genetic expressions).
  • Large-Scale Data: The GoogleNews Word2Vec dataset (3 million words in 300 dimensions) and a Prime Number Divisibility dataset (1 million integers) to test scalability and fractal structure preservation.

Key Insights and Ideas

  • The "Aha!" Moment on Heavy Tails: The paper proves that the "heavy-tailed" distributions used by t-SNE and UMAP are actually implicit forms of space expansion. SpaceMAP simply makes this explicit and mathematically grounded.
  • Intrinsic Dimension (ID) Matters: SpaceMAP uses Maximum Likelihood Estimation (MLE) to calculate the intrinsic dimensionality of the data. They prove that applying EED effectively transforms the data's ID to match the target dimension (e.g., 2), which is why the visualizations look so much cleaner.
  • Preserving the "Hole": One of the most striking insights is that while t-SNE and UMAP often "break" continuous manifolds (like tearing a hole in a sheet), SpaceMAP’s hierarchical approach preserves these structures, maintaining the global continuity of the data.

Key Results

  • Quantitative Superiority: SpaceMAP consistently outperformed or matched PCA, t-SNE, and UMAP across metrics like Trustworthiness, Continuity, and Shepard Goodness.
  • Better Sub-clustering: In the MNIST and Fashion-MNIST datasets, SpaceMAP revealed subtle sub-clusters (e.g., different ways of writing the same digit) that were blurred or merged in other methods.
Comparison of dimensionality reduction methods on synthetic datasets
  • Scalability: The algorithm successfully mapped 3 million word vectors, revealing a deep hierarchical structure based on geography and culture (e.g., grouping South American countries with Spain and Portugal due to linguistic/cultural ties).
  • Robustness: The "Swiss roll with a hole" test showed that SpaceMAP was the only method that correctly unfolded the shape without collapsing the hole or tearing the edges.

Limitations and Future Work

While SpaceMAP offers a more principled approach, the authors note a few areas for consideration:

  • Hyper-parameters: Although the results are stable, the choice of $k_{near}$ and $k_{middle}$ (neighborhood sizes) is still somewhat empirical, though the authors provide stable defaults (20 and 50).
  • Computational Cost: While faster than t-SNE on large datasets, it is slightly slower than UMAP (e.g., 85s vs 34s for MNIST).
  • Integration of Priors: The authors suggest that because SpaceMAP's parameters are "explainable" (linked to intrinsic dimension), future work could involve more deeply integrating prior knowledge about a dataset's dimensionality to guide the visualization.

Summary updated

BibTeX
@inproceedings{zu2022spacemap,
  author = {Xinrui Zu and Qian Tao},
  title = {{SpaceMAP: Visualizing High-Dimensional Data by Space Expansion}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
}
Figure