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

• t-SNE is sensitive to perplexity and can create spurious clusters, while t-SNE and UMAP preserve local structure well but struggle with global structure.TriMap generally handles global structure well but can struggle with local structure, and none of these methods smoothly controls the local-global trade-off through obvious parameter adjustments.Source: §1 · p. 2
• The paper shows that loss functions govern pairwise attractive and repulsive forces, and introduces a simple PaCMAP loss whose mechanisms are revealed by a “rainbow figure.”The authors report that deviating from their proposed loss-function principles empirically damages dimension-reduction performance.Source: §1 · p. 2
• Graph-component choices determine which pairs attract or repel; non-neighbor forces and “mid-near” attractive pairs provide a mechanism for preserving global structure.PaCMAP uses mid-near pairs to contrast with repulsion from more distant points.Source: §1 · pp. 2–3
• Initialization and scaling can materially affect performance, with TriMap’s global-structure preservation attributed unexpectedly to initialization.The paper also reports that qualitative visual judgments often correlate directly with quantitative local-and-global structure-preservation metrics.Source: §1 · p. 3
• PaCMAP preserves both local and global structure through a dynamic choice of graph components during optimization.The method builds on principles for loss functions and guidelines for neighbors, mid-near pairs, and further points.Source: §1 · p. 3
• Figure 1 shows PaCMAP preserving the Mammoth dataset’s local and global structure, while t-SNE and LargeVis form spurious clusters, UMAP struggles globally, and TriMap struggles locally.The figure evaluates local features such as mammoth toes and global shape; the accompanying discussion characterizes each method’s typical behavior.Source: §1 · p. 3, Figure 1 · p. 4

Local and global methods

• Local methods preserve neighborhoods and neighbor rankings, whereas global methods emphasize relative distances between farther-apart points, and neither is universally sufficient.Global methods better preserve overall layouts, while local methods better reveal cluster composition.Source: §2 · pp. 4–5

Prior dimension-reduction methods

• PCA and MDS exemplify global methods, while LLE, Isomap, Laplacian Eigenmaps, t-SNE, LargeVis (Tang et al., 2016), and UMAP (McInnes et al., 2018) emphasize local structure.Global methods cannot capture complex nonlinear structure, motivating local approaches.Source: §2 · p. 5

Local structure preservation methods before t-SNE

• Preserving raw local distances often failed because high-dimensional distances concentrate, prompting a shift toward preserving neighborhood graph structure.This limitation affected Isomap, LLE, Hessian LLE, and Laplacian Eigenmaps.Source: §2 · p. 6

t-SNE and its variants

• SNE, t-SNE, and later implementations improved neighborhood visualization and scalability, but t-SNE-derived methods still suffer global-structure loss and false clusters.t-SNE addressed crowding with a long-tailed low-dimensional t-distribution, while BH-SNE, viSNE, FIt-SNE (Linderman et al., 2017; Linderman et al., 2019), and opt-SNE improved speed and scale.Source: §2 · pp. 6–7

Triplet constraint methods

• Triplet methods encode relative similarity comparisons, and TriMap (Amid and Warmuth, 2019) randomly samples neighbor-containing triplets to keep neighbors close and farther points distant.The paper presents triplets as appealing for preserving global structure but argues that both structures can be preserved without modifying TriMap or using triplets.Source: §2 · p. 7

Other related work

• The paper addresses major gaps in understanding DR principles by arguing that which points receive attraction or repulsion matters more for global structure than force magnitude, motivating weighted mid-near pairs in PaCMAP.This contrasts with B¨ohm et al. (2020), who emphasize stronger attraction for continuous manifolds and stronger repulsion for discrete clusters; their analysis associates UMAP with increased attraction relative to t-SNE.Source: §2 · pp. 7–8

3.1 t-SNE

• t-SNE matches high-dimensional relative distances with low-dimensional probabilities by minimizing Kullback–Leibler divergence, with Perplexity controlling probability concentration.Smaller Perplexity concentrates probabilities on nearest points, whereas larger Perplexity makes them more uniform.Source: §3.1 · pp. 8–9

3.2 UMAP

• UMAP constructs a weighted nearest-neighbor graph, then optimizes its layout using attractive forces for neighbors and repulsive forces for sampled non-neighbors.The method can be viewed as stochastic gradient descent or force-directed graph layout.Source: §3.2 · pp. 9–10

3.3 TriMap

• TriMap preserves distance ordering within triplets that usually pair a nearest neighbor with a farther observation, supplemented by randomized non-neighbor triplets.Its triplet weights increase when the tuple’s distances are more significant, emphasizing relations judged important to preserve.Source: §3.3 · pp. 10–11

3.4 PaCMAP

• PaCMAP selects near, mid-near, and further pairs using scaled distances, then minimizes a three-stage loss whose weights shift from mid-near emphasis toward near and further pairs.The short description precedes PaCMAP’s full algorithm and derivation in Section 7.Source: §3.4 · pp. 11–12

4.1 A unified DR objective

• DR methods can be represented as graph-based objectives that optimize low-dimensional positions using weighted high-dimensional graph components and attraction–repulsion forces.The loss balances attraction and repulsion while preserving high-dimensional graph structure and mitigating crowding.Source: §4.1 · pp. 13–14

4.2 The rainbow figure for loss functions

• Rainbow figures compare triplet losses and gradients across algorithms, revealing tradeoffs between attracting neighbors and repulsing further points; TriMap alone explicitly uses triplet-based losses.The figures support local-structure analysis, while t-SNE dynamically determines attracted and repulsed points and the other methods choose them in advance.Source: §4.2 · pp. 14–16

4.3 Principles of good loss functions

• The six principles require monotonic attraction and repulsion, prioritizing separation when far points are too close, limiting gains from already-separated points, and moderating neighbor penalties.They also require strong repulsion for overly close far points, small gradients for sufficiently close neighbors, and unimodal dependence on neighbor distance; these tradeoffs reflect limited low-dimensional capacity.Source: §4.3 · pp. 17–18
• Violating the principles produces distinct failures: cluster overlap, weak local structure, severe crowding, or non-compact clusters, showing that monotonicity alone is insufficient.BadLoss 1 ignores useful triplets, BadLoss 2 favors global over local structure, BadLoss 3 lacks repulsion when far points are close, and BadLoss 4 overemphasizes distant neighbors.Source: §4.3 · p. 20

4.4 Sufficient conditions for obeying the principles

• For additive losses f(dij) − g(dik), nonnegative unimodal f and g that vanish at both distance limits are sufficient to satisfy all six principles.The proof derives each principle from unimodality, nonnegativity, and the limiting behavior of the attractive and repulsive terms.Source: §4.4 · p. 21
• UMAP with b > 0.5 satisfies the sufficient conditions, while t-SNE and TriMap do not; PaCMAP satisfies them by construction.UMAP’s min dist range [0,1] yields b values from 0.79 to 1.92, all meeting the condition.Source: §4.4 · pp. 21–22

4.5 Applying the principles of a good loss function and introducing PaCMAP’s loss

• PaCMAP combines neighbor, mid-near, and further-point repulsion edges in a weighted pairwise loss, with mid-near attraction improving global-structure optimization early in training.Neighbor and mid-near terms attract, whereas further-point terms repel; the three weights are important design parameters.Source: §4.5 · pp. 22–23
• The specific simple-fraction formulas are replaceable, provided alternative functions remain tractable, satisfy the six force principles, and retain a separate mid-near attractive force.The authors identify graph-component construction as another key ingredient beyond the loss-function principles.Source: §4.5 · p. 23
• PaCMAP’s loss obeys the six principles because neighbor forces act across a broader distance range, while further-point repulsion is strong only at very small distances.Neighbor losses are monotone, saturate at large distances, and have strong moderate-distance gradients; further-point forces rapidly approach zero as distance increases.Source: §4.5 · p. 23

5.1 Graph component selection and loss terms in most methods mainly favors preservation of local structure

• Attracting only neighbors and repulsing only nearby or sufficiently close points can yield zero loss while sacrificing global structure, because non-neighbor distances are not distinguished.This failure appears in triplet losses and attractive/repulsive objectives; t-SNE and UMAP forces decay rapidly for distant pairs, while TriMap’s global structure depends heavily on PCA initialization.Source: §5.1 · pp. 24, 25, 27, 28

5.2 PaCMAP’s graph structure using mid-near edges and dynamic choice of graph elements

• PaCMAP robustly recovers global aspects of a curve that t-SNE and UMAP miss, while TriMap depends heavily on initialization; adding more mid-near points progressively improves global structure.On the curve dataset, PaCMAP remains robust, and its global recovery increases from zero to eight mid-near points per point.Source: §5.2 · p. 31, Figure 14 · p. 32
• PaCMAP samples six points and selects the second nearest as a weakly attracted mid-near point, then gradually removes its attraction so global structure precedes local refinement.Early iterations attract neighbors and mid-near pairs while repulsing further points; later iterations reduce mid-near attraction and refine local structure.Source: §5.2 · p. 31

5.3 Assigning weights for graph components is not always helpful

• TriMap’s complicated graph-component weights have little apparent effect across several datasets, whereas initialization and component selection matter more; PaCMAP therefore uses uniform component weights with simple iteration-dependent changes.Removing TriMap’s weights produces performance very similar to the weighted version, while PaCMAP assigns equal weights to neighbors, mid-near points, and further points.Source: §5.3 · p. 33, Figure 15 · p. 33

6.1 Some algorithms are not robust to random initialization

• Random initialization substantially worsened UMAP and TriMap results across runs, and hyperparameter tuning did not recover performance achieved with careful initialization.The initialization method influenced success rate more than merely accelerating convergence or improving stability.Source: §6.1 · pp. 33–34, Figure 16 · p. 34, Figure 17 · p. 35
• UMAP and TriMap are initialization-sensitive because their limited attractive and repulsive force working zones can prevent displaced neighbors from reconnecting, producing false clusters.This reflects the near-sightedness of their loss functions.Source: §6.1 · pp. 34–35
• PaCMAP is fairly, though not completely, robust to initialization choice because it uses mid-near points and a dynamic graph structure.Source: §6.1 · p. 35

6.2 DR algorithms are often sensitive to the scale of initialization

• Scaling initialization distances by a constant substantially changed results, showing that DR algorithms are not scale invariant even when original and embedded spaces are both 2D.Even using the correct 2D embedding as the starting point could allow attractive and repulsive forces to disintegrate global structure.Source: §6.2 · pp. 35–36, Figure 18 · p. 36
• Poor outcomes can arise when initialization scale lies outside the distance range where attractive and repulsive forces are effective; initialization should avoid making all forces zero.Scaling all dimensions by 1000 made repulsion fade and could cause algorithms to stop at the first iteration, although it produced perfect results in the illustrated case.Source: §6.2 · p. 36

Graph construction and loss

• PaCMAP constructs neighbor, mid-near, and further pairs, then optimizes their distinct weighted losses with Adam while dynamically adjusting the weights.Neighbor pairs use locally scaled distances for selection; mid-near and further pairs are randomly sampled, reducing computational burden.Source: §7 · p. 38

Initialization of PaCMAP

• PCA initialization can improve running time, but PaCMAP outcomes are fairly insensitive to initialization and random initialization can still capture global structure.The figures use random initialization to demonstrate the algorithm’s behavior, while PCA can make global structure more stable.Source: §7 · pp. 38–39

Dynamic Optimization

• Three optimization phases first emphasize mid-near pairs for global structure, then preserve that structure while improving local structure, and finally suppress mid-near forces while emphasizing repulsion.This schedule avoids neglecting non-neighbor forces and prevents early neighbor separation from causing derivative saturation and false clusters.Source: §7 · pp. 38–39

Algorithm characteristics

• PaCMAP tends to favor global structure when present, preserve local structure when present, run efficiently, and remain less sensitive to initialization than other methods.These characteristics are attributed to its loss function and are identified as advantages in the experiments.Source: §7 · p. 39

8.1 Experimental design

• Experiments compare PaCMAP with t-SNE, UMAP, TriMap, and LargeVis across diverse labeled and unlabeled datasets using tuned local-structure and global-structure metrics.Local structure is assessed with KNN and SVM accuracy, while global structure is assessed with random and centroid triplet accuracy.Source: §8.1 · pp. 40–42

8.2 Main Results

• PaCMAP balances local and global structure, behaving like UMAP on locally structured datasets and like TriMap on globally structured datasets.It preserves global structure without sacrificing local structure or depending on initialization.Source: Figure 21 · p. 43, §8.2 · pp. 43, 46, Figure 22 · p. 44
• PaCMAP is significantly faster than other methods, exceeding 1.5× speedup on most datasets and completing large-scale tasks where others timed out or exhausted memory.Its speed is attributed to a loss function that reduces the number of pairs considered per iteration, lowering computing and memory requirements.Source: §8 · p. 40, §8.2 · p. 46

8.3 PaCMAP-specific considerations and sensitivity analysis

• PaCMAP’s qualitative performance is consistent across random and PCA initialization, unlike UMAP on the globally structured S-curve dataset.The S-curve results show that UMAP reliably fails to capture global structure regardless of initialization.Source: §8.3 · p. 47
• PaCMAP is robust across a wide range of graph-component ratios, but omitting mid-near pairs harms structure and extreme mid-near counts overwhelm other forces.The authors suggest setting the mid-near ratio to 0.5 because larger values are computationally expensive and can damage local and global structure.Source: §8.3 · p. 47

Design principles

• The empirical analysis showed that probabilistic and simplex-based derivations are modeling choices rather than requirements, making purely loss-based approaches such as TriMap and PaCMAP equally feasible.Rainbow figures and force plots exposed principles for effective loss functions; combining three fractional losses with these insights yielded PaCMAP.Source: §9 · p. 48

Empirical findings

• The study found that t-SNE and UMAP’s weighting and graph-component choices omit forces on further points, making them near-sighted, while TriMap’s global performance depends strongly on initialization.These findings identify design choices that fail to preserve global structure and can hurt performance.Source: §9 · p. 48

PaCMAP design

• PaCMAP preserves local and global structure through non-zero forces on further points and dynamic graph selection that emphasizes global structure early and local structure later.It performs like UMAP on mainly local datasets and like TriMap on globally structured datasets, while remaining effective under random initialization.Source: §9 · pp. 48–49

PaCMAP results

• PaCMAP’s qualitative results led to high-quality quantitative results measured on 12 datasets, while its performance remained relatively robust across reasonable parameter choices.Its loss function also supports faster computation and convergence by avoiding triplets and unnecessary graph components.Source: §9 · p. 49

Future work

• Future work includes handling multi-scale structure, scaling to very large high-dimensional datasets, combining distance-metric learning with DR, developing domain-specific evaluation metrics, and designing new methods from the study’s principles.On a hierarchical synthetic dataset, all methods struggled across every level, although PaCMAP slightly outperformed the others.Source: §9 · p. 49

• Figures A.3–A.7 provide additional DR outcomes for Olivetti Faces, Flow Cytometry, and KDD Cup99, including PaCMAP and TriMap visualizations.Source: Appendix A · p. 50, Figure A.3 · p. 51, Figure A.4 · p. 52
• Figures A.8–A.12 examine performance consistency across runs and PaCMAP’s robustness to initialization, neighbor counts, and point-pair ratios.Source: Appendix A · p. 50, Figure A.8 · p. 54, Figure A.9 · p. 55
• Figures A.13–A.17 visualize ILSVRC 2012 ResNet-50 penultimate-layer activations using t-SNE, LargeVis, UMAP, TriMap, and PaCMAP, with samples colored by labels.Source: Appendix A · p. 50, Figure A.13 · p. 59, Figure A.14 · p. 60
• Figures A.1 and A.2 show DR algorithms’ results with MDS and spectral embedding initialization, respectively.Source: Figure A.1 · p. 50, Appendix A · p. 50, Figure A.2 · p. 51

Dataset construction

• The synthetic hierarchical dataset contained 125 clusters of 500 observations, organized as 25 mesoclusters across five macroclusters and 125 microclusters in 50 dimensions.Meso- and microcluster centers used covariance scales 1000 and 100, respectively, and observations used covariance scale 10.Source: Appendix B · p. 64

Evaluation

• Figure B.1 visualized each embedding using macro-, meso-, and microcluster color schemes, while Table 6 summarized local- and global-structure metrics.The color schemes used 5, 25, and 125 colors, with lower-level cluster colors matching their higher-level groups.Source: Appendix B · p. 64, Table 6 · p. 65

Results

• All evaluated dimensionality-reduction methods preserve local structure, with visualization indicating that 125 microclusters are identified.The evaluated methods are t-SNE, UMAP, LargeVis, TriMap, and PaCMAP.Source: Appendix B · p. 64
• PaCMAP preserved global hierarchical structure, whereas t-SNE, LargeVis, UMAP, and TriMap did not consistently keep related macro- and mesoclusters nearby.The global-structure metrics in Table 6 support this distinction, although no method visibly separated macro- and mesoclusters without colored labels.Source: Appendix B · p. 64, Table 6 · p. 65

Background

• ForceAtlas2 maps graphs into two dimensions using attractive and repulsive forces, but often performs poorly, potentially because of identifiable loss-function problems.It is the default graph-layout algorithm for Gephi and was analyzed using the rainbow figure.Source: Appendix C · p. 65

Related work

• Researchers apply ForceAtlas2 to k-nearest-neighbor graphs in single-cell transcriptomics because it can sometimes reveal developmental patterns over time (B¨ohm et al., 2020).Source: Appendix C · p. 65

Method

• The analysis considers ForceAtlas2 on a symmetric k-nearest-neighbor graph, with edge weight 1 when either point is the other’s neighbor and 0 otherwise.This setup reflects the most common implementation in single-cell transcriptomic data.Source: Appendix C · p. 65

C.1 The attractive and repulsive force of ForceAtlas2

• ForceAtlas2 directly defines attractive and repulsive forces, effectively specifying loss derivatives without explicitly defining the loss.The algorithm uses two simple force functions to update the layout.Source: §C.1 · p. 65
• Attractive force acts only between connected points and increases linearly with their Euclidean distance in the low-dimensional space.Source: §C.1 · p. 65
• Repulsive force acts between every pair of points, regardless of edges, decreases inversely with distance, and scales with both points’ degrees.Source: §C.1 · pp. 65–66
• The repulsive-force numerator uses (deg(i) + 1)(deg(j) + 1), with kr capped at 10; on symmetric k-nearest-neighbor graphs, it can be approximated by (k + 1)^2.Here, deg(i) denotes the number of edges connected to point i.Source: §C.1 · p. 66

Loss derivation

• Integrating the forces yields the loss associated with each pair type, including a logarithmic repulsive loss term.The supplied derivation gives Loss_repulsive = k_r(k + 1)^2 log(d_ij).Source: §C.2 · p. 66

ForceAtlas2 visualization

• ForceAtlas2 violates Principle 6 but satisfies Principles 3 and 5, producing a rainbow pattern like BadLoss 4 with stronger repulsion.Its repulsive force is applied to every low-dimensional point pair, including neighbors.Source: §C.2 · p. 66
• Applying repulsion to neighbors better preserves local structure, although clusters still overlap and strong attraction links clusters through outliers.The attraction can help assess whether a continuous manifold exists, but makes clusters harder to separate.Source: §C.2 · p. 66

ForceAtlas2 limitations

• ForceAtlas2 is not robust to hyperparameter choices and, in the S-curve-with-a-hole experiment, fails to discover the manifold’s hole.Achieving optimal results therefore requires careful hyperparameter tuning.Source: §C.2 · p. 66