PaperlayerView exact revision on arXiv

Source-linked AI summary

Understanding How Dimension Reduction Tools Work: An Empirical Approach to Deciphering t-SNE, UMAP, TriMAP, and PaCMAP for Data Visualization

Yingfan Wang, Haiyang Huang, Cynthia Rudin, Yaron Shaposhnik

arXiv:2012.04456v2cs.LGstat.ML

TL;DR

Dimension-reduction methods face a tension between preserving local neighborhoods and global structure, while their design choices remain difficult to interpret. This paper empirically deciphers loss functions, graph components, and initialization, then uses those insights to develop PaCMAP. PaCMAP is reported to preserve both local and global structure, with qualitative findings leading to high-quality quantitative results across 12 datasets.

  • Problem

    Dimension-reduction visualizations can misrepresent geometric and neighborhood structure, motivating a clearer understanding of trustworthy representations.

  • Method

    The paper empirically analyzes loss functions, graph components, and initialization, then designs PaCMAP using a simple loss and dynamic graph-component selection.

  • Results

    PaCMAP is reported to preserve both local and global structure, and qualitative performance results led to high-quality quantitative results on 12 datasets.

  • Takeaways & Limitations

    The study identifies empirical principles for attractive and repulsive forces and shows that seemingly important modeling choices may obscure what drives performance.

  • Takeaways & Limitations

    The paper reports that all methods have difficulty displaying hierarchical structure at every level and identifies very large, high-dimensional datasets as future work.

Abstract

from arXiv · show

Dimension reduction (DR) techniques such as t-SNE, UMAP, and TriMAP have demonstrated impressive visualization performance on many real world datasets. One tension that has always faced these methods is the trade-off between preservation of global structure and preservation of local structure: these methods can either handle one or the other, but not both. In this work, our main goal is to understand what aspects of DR methods are important for preserving both local and global structure: it is difficult to design a better method without a true understanding of the choices we make in our algorithms and their empirical impact on the lower-dimensional embeddings they produce. Towards the goal of local structure preservation, we provide several useful design principles for DR loss functions based on our new understanding of the mechanisms behind successful DR methods. Towards the goal of global structure preservation, our analysis illuminates that the choice of which components to preserve is important. We leverage these insights to design a new algorithm for DR, called Pairwise Controlled Manifold Approximation Projection (PaCMAP), which preserves both local and global structure. Our work provides several unexpected insights into what design choices both to make and avoid when constructing DR algorithms.

1. Introduction

The paper examines why dimension-reduction visualizations can misrepresent geometric and neighborhood structure, then uses empirical analysis to derive principles for preserving local and global structure. These insights motivate PaCMAP, which dynamically selects graph components to preserve both types of structure.

  • Dimension-reduction results may display clusters absent from the original data or separate observations that are close in the original space.
  • t-SNE and UMAP preserve local structure well but struggle with global structure, while TriMap handles global structure yet sometimes struggles locally.
  • The paper studies how loss functions and graph components control attractive and repulsive forces between data points.
  • Initialization and scaling affect dimension-reduction behavior, and TriMap’s global-structure preservation comes unexpectedly from its initialization.
  • Qualitative visual assessments often correlate directly with quantitative local-and-global structure-preservation metrics.
  • PaCMAP preserves both local and global structure through a dynamic choice of graph components during optimization.

2. Related Work

Related work distinguishes local and global dimension-reduction goals and reviews methods that emphasize either neighborhood structure, broader distances, or triplet relations. It also identifies persistent weaknesses and the paper’s empirical focus on explaining their causes.

  • Local methods mainly preserve high-dimensional neighbors, whereas global methods aim to preserve relative distances or rank information between points farther apart.
  • PCA and MDS are prominent global methods, while t-SNE, LargeVis, and UMAP are modern methods focused on local structure.
  • t-SNE variants improved efficiency and scalability while retaining the same basic conceptual ideas.
  • t-SNE and UMAP remain vulnerable to global-structure loss and false clusters despite improvements in efficiency, neighborhood accuracy, and qualitative global preservation.
  • Triplet methods encode relations such as “a is more similar to b than to c,” with TriMap being the notable triplet method approaching UMAP and t-SNE performance.
  • The paper addresses gaps in understanding the basic principles behind the successes and failures of dimension-reduction methods.
  • Its proposed principles concern attractive and repulsive forces on neighbors and further points, linking these choices to local-structure preservation.

3. t-SNE, UMAP, TriMap, and PaCMAP

The paper reviews t-SNE, UMAP, and TriMap as algorithms that construct high-dimensional relationships and optimize a two-dimensional layout. Their differing graph, force, triplet, initialization, and optimization choices expose the design space that PaCMAP builds upon.

  • The paper represents the original dataset X ∈ R^N×P and seeks a two-dimensional embedding Y ∈ R^N×2.
  • t-SNE: t-SNE matches low-dimensional relative distances to high-dimensional similarities, with Perplexity controlling how concentrated those similarities are.
  • UMAP: UMAP constructs a weighted nearest-neighbor graph, then optimizes its low-dimensional layout using attractive forces on graph edges and repulsive forces on sampled non-neighbors.
  • UMAP: UMAP’s graph construction uses nearest-neighbor distances, local scales, and a normalization parameter σ_i to preserve relative high-dimensional proximities.
  • TriMap: TriMap forms triplets satisfying Distance_i,j < Distance_i,k and optimizes a loss that favors placing j closer to i than k.
  • TriMap: TriMap initializes with PCA and uses full-batch gradient descent with momentum, while its triplet set contains 55 · N triplets.
  • The reviewed algorithms contain many empirical design choices whose essential contributions to visualization quality are not immediately evident.

4. Principles of a Good Objective Function for Dimension Reduction, Part I: The Loss Function

The paper evaluates dimension-reduction objectives by separating local neighborhood preservation from global relative-position preservation, then uses loss-function analysis to identify principles associated with good local structure. Its examples show that violations of specific gradient or force-tradeoff principles degrade visualization quality, while PaCMAP combines neighbor, mid-near, and further-point interactions.

  • Evaluation criteria: Local structure preserves each observation’s neighborhood, whereas global structure preserves the relative positions of neighborhoods in the embedding.The paper evaluates these criteria separately using labeled MNIST and COIL-20 for local structure, and 3D S-curve and Mammoth data for global structure.
  • Rainbow analysis: Rainbow figures compare attractive and repulsive forces across losses and reveal patterns associated with successful local-structure preservation.The authors formalize shared properties of good losses as principles and contrast them with bad-loss failures.
  • Loss-function principles: The principles require asymmetric treatment of near and far edges because neighbors and further points have different preservation requirements.The paper emphasizes that gradient behavior should prioritize appropriate neighbor compactness while maintaining separation and structure among farther points.
  • Algorithm-specific qualification: TriMap appears to violate the large-horizontal-gradient principle, but its initialization may prevent problematic triplets from receiving harmful forces.The authors identify initialization as a possible reason TriMap can preserve global structure despite this apparent loss-function violation.
  • Loss-function principles: Monotonicity alone is insufficient: good losses require appropriate tradeoffs between attracting neighbors and repulsing distant points.The bad-loss examples link cluster overlap, crowding, and poor fine-grained structure to violations of particular principles governing gradients and force allocation.
  • PaCMAP objective: PaCMAP uses neighbor, mid-near, and further-point edges, with attractive forces on the first two and repulsion on the last.Mid-near pairs provide a contrast to further-point repulsion and are used to improve global-structure optimization early in training.

5. Principles of a Good Objective Function for Dimension Reduction, Part II: Graph Construction and Attractive and Repulsive Forces

Preserving global structure depends critically on which graph components receive attractive or repulsive forces, because local-only objectives can achieve low loss while distorting relationships among distant points. The analysis motivates non-neighbor forces and PaCMAP’s mid-near pairs, while showing that initialization can also strongly affect global structure.

  • Graph component selection: Choosing which points to attract and repulse determines the balance between local and global structure preservation.Attracting only neighbors and repulsing far points only when they become too close can lose global structure.
  • Graph component selection: Local-only triplet objectives can reach zero loss while failing to preserve even simple global shapes.The UMAP-like curve in Figure 8 respects local structure but not the original line’s global organization.
  • Graph component selection: For global structure preservation, forces must act on non-neighbors; otherwise relative distances among further points do not affect the loss.This requirement follows from examples where neighbors remain close and further points remain separated without preserving their global arrangement.
  • Existing methods: t-SNE and UMAP are near-sighted because their attractive and repulsive forces decay rapidly and are minimal for sufficiently distant points.Most point pairs therefore exert little force, limiting the influence of distant relationships on the embedding.
  • Existing methods: TriMap’s global-structure preservation appears to come primarily from PCA initialization rather than its random triplets.Approximately 90% of its triplets use a neighbor, while removing PCA initialization substantially affects the outcome.
  • PaCMAP: PaCMAP uses mid-near pairs and dynamically chooses graph elements, applying strong early attraction to mid-near pairs to create global structure.On a simple curve, adding more mid-near points progressively recovers more global structure, while t-SNE and UMAP struggle regardless of initialization.

6. Initialization Can Really Matter

Initialization and scale substantially influence dimension-reduction outcomes: random or poorly scaled starts can degrade UMAP, TriMap, and other methods, while PaCMAP is comparatively robust.

  • Random initialization: Initialization has a much larger influence on algorithm success than merely accelerating convergence.t-SNE uses random values, UMAP spectral embedding, and TriMap PCA initialization.
  • Random initialization: UMAP and TriMap produced substantially worse results with random initialization, even after convergence and hyperparameter tuning.The poor results were consistent across runs.
  • Mechanism: Limited working zones of attractive and repulsive forces can prevent separated neighbors from recovering, producing false clusters.Once points move outside effective attractive forces, little force remains to reunite them.
  • PaCMAP: PaCMAP is fairly robust, though not completely robust, to initialization because of its mid-near points and dynamic graph structure.Its outcomes are less sensitive to initialization than those of other methods.
  • Initialization scale: DR methods are not generally scale-invariant, so initialization scales outside the effective force range can produce poor outcomes.Scaling the original distances by a constant substantially changed results, including when the original embedding was used as a start.

7. The PaCMAP Algorithm

PaCMAP combines graph construction, a pair-specific loss, and three-phase dynamic optimization to balance global and local structure while reducing sensitivity to initialization.

  • Graph construction: PaCMAP constructs neighbor, mid-near, and further graph-component pairs from the high-dimensional data.Neighbor pairs use scaled distances; mid-near and further pairs are sampled separately.
  • Graph construction: Scaled distances select neighbors while accounting for differing neighborhood magnitudes across the feature space.The scaling uses σ_i, the average distance to each point’s fourth through sixth nearest neighbors, and is not used during optimization.
  • Loss function: PaCMAP uses three distinct pair-type loss functions with dynamically updated weights.The transformed distance and weights define contributions from neighbor, mid-near, and further pairs.
  • Initialization and outcome: PaCMAP is fairly insensitive to initialization, although PCA initialization can improve running time.Its design uses graph construction, initialization, and iterative optimization with AdamOptimizer.
  • Dynamic optimization: The first optimization phase heavily weights mid-near pairs to establish a placement emphasizing global structure.Mid-near weights are gradually decreased so optimization can refocus toward local structure.
  • Dynamic optimization: The second phase improves local structure while maintaining the captured global structure through a small, nonzero mid-near weight.The first two phases are designed to avoid local optima.
  • Dynamic optimization: The third phase sets mid-near weight to zero and reduces neighbor weight, emphasizing repulsion to separate clusters and clarify boundaries.This phase has a larger effect on primarily local datasets such as MNIST than on globally structured Mammoth.

8. Numerical experiments

Experiments across datasets show that PaCMAP balances local and global structure, remains comparatively robust, and runs faster than competing methods.

  • Main results: PaCMAP performs as well as local-structure methods on locally structured datasets and comparably with global-structure methods on globally structured datasets.The reported balance holds across a wide range of datasets.
  • Evaluation: PaCMAP’s qualitative visual assessments correlate directly with quantitative local- and global-structure metrics in many cases.The paper uses KNN and SVM accuracies for local structure and random or centroid triplet accuracy for global structure.
  • Local structure: UMAP and t-SNE tend to perform better on local-preservation metrics, while PaCMAP also preserves local structure and performs well.SVM accuracy favored PaCMAP on more datasets than the other methods.
  • Global structure: PaCMAP and TriMap preserve more global structure than other compared methods, particularly on the S-curve dataset.The comparison includes t-SNE, UMAP, LargeVis, TriMap, and PaCMAP.
  • Main results: PaCMAP preserves global structure without sacrificing local structure or depending on initialization.This summarizes the paper’s main experimental conclusion.
  • Local-global trade-off: t-SNE performed well on F-MNIST local metrics but had one of the worst global-structure results there.This illustrates the tension between local and global preservation.
  • Runtime: PaCMAP was significantly faster than other algorithms, with speedups exceeding 1.5 times on most datasets.Several competing methods failed to converge or ran out of memory on large datasets.
  • Robustness: PaCMAP is qualitatively consistent across random and PCA initialization, unlike UMAP, particularly on the S-curve dataset.UMAP reliably fails to capture the S-curve’s global structure regardless of initialization.

9. Discussion and Conclusion

The study empirically dissects dimension-reduction design choices and develops PaCMAP to preserve local and global structure. Its conclusions emphasize graph components, dynamic selection, robustness, and remaining challenges for hierarchical and very large datasets.

  • The study empirically examines which dimension-reduction approaches work and which do not across datasets with local- and global-structure preservation needs.
  • PaCMAP’s graph components give further points non-zero forces, addressing a weakness identified in other algorithms and supporting global-structure preservation.
  • PaCMAP dynamically emphasizes global structure early and local structure later, allowing it to preserve both structures and perform well under random initialization.
  • PaCMAP’s loss avoids triplets and unnecessary graph components, leading to faster computation and convergence times.
  • The qualitative observations about PaCMAP’s performance corresponded to high-quality quantitative results on 12 datasets.
  • Hierarchical and very large datasets remain future-work challenges because all methods had difficulty displaying structure at every hierarchy level and scaling issues remain.

Appendix A. Supplemental Figures

Appendix A collects supplemental visualizations and robustness results for the dimension-reduction methods. The figures cover alternative initialization choices, datasets, repeated runs, parameter variations, and ImageNet-derived neural-network activations.

  • Figures A.1 and A.2 show dimension-reduction outputs using MDS and spectral-embedding initialization, respectively.
  • Figures A.3–A.7 provide additional visualizations for Olivetti Faces, Flow Cytometry, and KDD Cup99 datasets.
  • Figures A.8–A.12 assess repeated-run consistency and robustness to initialization, neighbor counts, further-point ratios, and mid-near-point ratios.
  • Figures A.13–A.17 visualize ResNet-50 penultimate-layer activations from all ILSVRC 2012 data, with samples colored by labels.
  • On KDD Cup99, TriMap projects most points together while separating a few outliers, which are shown in a zoomed top-right view.

Appendix B. A Synthetic Hierarchical Dataset

Appendix B evaluates dimension-reduction methods on a synthetic dataset with hierarchical macro, meso, and micro clusters. All methods preserved local micro-cluster structure, but PaCMAP alone preserved the tested global hierarchy effectively, although no method visibly separated macro and meso clusters without labels.

  • The synthetic dataset contains 125 micro clusters with 500 observations each, organized into 25 meso clusters and 5 macro clusters in 50 dimensions.
  • The experiment applies t-SNE, UMAP, LargeVis, TriMap, and PaCMAP, displaying the data with macro-, meso-, and micro-level color schemes.
  • All methods preserved local structure, with the 125 micro clusters identified and local-structure metrics reported as perfect.
  • PaCMAP preserved global hierarchical structure by placing clusters within the same macro and meso groups nearer together.
  • None of the algorithms visibly separated macro and meso clusters without colored labels.

Appendix C. ForceAtlas2

Appendix C examines ForceAtlas2 as a force-directed graph-layout method for dimension reduction. It describes its use on symmetric k-nearest-neighbor graphs and notes potential practical weaknesses in its loss functions.

  • ForceAtlas2 is Gephi’s default graph-layout algorithm and maps graphs into two dimensions using attractive and repulsive forces.
  • ForceAtlas2 did not tend to perform well in practice, potentially because of loss-function problems identified through the rainbow figure.
  • Researchers in single-cell transcriptomics apply force-directed visualization algorithms such as ForceAtlas2 to k-nearest-neighbor graphs for discovering developmental patterns over time.
  • The appendix analyzes ForceAtlas2 on a symmetric k-nearest-neighbor graph whose edge weight is 1 when either point neighbors the other, and 0 otherwise.

C.1 The attractive and repulsive force of ForceAtlas2

ForceAtlas2 defines attractive forces for graph-connected pairs and repulsive forces for all pairs, with repulsion depending on distance and node degrees.

  • ForceAtlas2 directly defines attractive and repulsive forces rather than defining a loss and using its gradient.Its force formulation is analogous to specifying loss derivatives without explicitly specifying the loss.
  • Attractive force acts between graph-connected points and depends linearly on their low-dimensional Euclidean distance.
  • Repulsive force applies to every pair of points, regardless of graph edges, and is inversely proportional to their low-dimensional distance.
  • Repulsion is proportional to the product (deg(i) + 1)(deg(j) + 1) of the two points’ degrees.
  • The repulsive coefficient kr is capped at 10; on a symmetric k-nearest-neighbor graph, the degree numerator can be approximated by (k + 1)^2.

C.2 Visualizing and Analyzing the Loss function

The ForceAtlas2 forces can be integrated into pairwise loss terms, then visualized with a rainbow figure to analyze their structural effects.

  • Integrating the attractive and repulsive forces yields a loss associated with each pair type.
  • The repulsive loss includes a logarithmic distance term, kr(k + 1)^2 log(dij).
  • ForceAtlas2 violates Principle 6 but satisfies Principles 3 and 5, producing a rainbow figure resembling BadLoss 4 with stronger repulsion.
  • Because repulsion is applied even to neighbors, ForceAtlas2’s local structure is better preserved in the reported comparison.
Loading 2012.04456v2…