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

In plain words

Plotting data with hundreds of features means squashing it onto a flat map. Common squashing tools make pretty pictures, but they often lie: clusters appear that are not in the data, or points that are far apart look close. The tools tend to be good either at keeping small neighbourhoods intact or at keeping the overall shape, rarely both.

PaCMAP tries to get both. Like other tools, it pulls each point toward its closest neighbours and pushes apart points that are far away. The new ingredient is a small set of "mid-near" pairs: points that are moderately far away, picked at random and pulled gently together. At the start, these pairs are weighted heavily, which pins down the big picture. Later, their weight drops to zero and the neighbour pulls take over, which tidies up the local detail.

The authors argue that this schedule is why PaCMAP keeps the overall layout without needing a clever starting position for the points.

TL;DR

PaCMAP is a dimension reduction method for 2-D visualisation. It builds three kinds of pairs (near neighbours, mid-near points and random far points) and minimises a loss on them with Adam in three phases. The phases first set the global layout through mid-near pairs and then refine neighbourhoods. The authors report good local and global scores across many datasets and lower runtime than the compared methods. All numbers are author-reported.

Problem

Tools such as t-SNE and UMAP preserve local neighbourhoods well but struggle with global structure; TriMap does better globally but is weaker locally §1 fig. 1 fig. 2. t-SNE is sensitive to its perplexity parameter and can create spurious clusters §1. Changing a single parameter does not move these methods smoothly from local to global behaviour §1. The paper's analysis finds that global structure in TriMap comes largely from its PCA initialisation rather than from its triplets §6 §3.

Method

Overview. PaCMAP is a pairwise method. Every point has three groups of partners: neighbours, mid-near points and further points. The loss has one term per group, with weights that change across three optimisation phases §7 alg. 1. The loss design follows principles the authors derive from the attractive and repulsive forces of t-SNE, UMAP and TriMap §4 §5.1.

Steps (as in alg. 1 and §7):

1. Neighbour pairs. Take the min(n_NB + 50, N) Euclidean nearest candidates of each point. Rank them by the scaled squared distance d^{2,\text{select}}_{ij} = \|x_i - x_j\|^2 / (\sigma_i \sigma_j), where \sigma_i is the mean distance to the 4th to 6th nearest neighbours §7 eq. 2. Keep the n_NB best. The scaled distance is used only for selection, not in the loss §7.
2. Mid-near pairs. For each point, draw 6 random other points and keep the second closest one §7 alg. 1. There are n_MN = floor(n_NB × MN_ratio) such pairs per point alg. 1.
3. Further pairs. For each point, draw n_FP = n_NB × FP_ratio random non-neighbours §7 alg. 1.
4. Initialise the 2-D positions Y with PCA alg. 1.
5. Run Adam for 450 iterations on the three-term loss, with the weights of each phase alg. 1.

# PaCMAP  [alg. 1]
# Input:  X (N, D); n_neighbors = 10; MN_ratio = 0.5; FP_ratio = 2
# Output: Y (N, 2)

def pacmap(X, n_neighbors, MN_ratio, FP_ratio, n_iterations=450):
    # Scaled-distance neighbours; sigma_i uses the 4th to 6th
    # nearest neighbours  [§7] [eq. 2]
    neighbor_pairs = nearest_neighbor_pairs(X, n_neighbors)
    # floor(n_neighbors * MN_ratio) mid-near partners per point  [§7]
    mid_near_pairs = sample_mid_near_pairs(X, floor(n_neighbors * MN_ratio))
    # n_neighbors * FP_ratio random non-neighbours per point  [§7]
    further_pairs = sample_further_pairs(
        X,
        n_neighbors * FP_ratio,
    )
    # Starting layout from PCA  [alg. 1]
    Y = pca_initialization(X)
    for step in range(1, n_iterations + 1):
        # Phase-dependent weights for this step  [alg. 1]
        w_neighbor, w_mid_near, w_further = weights(step)
        # Gradient of the three-term loss, then one Adam update  [alg. 1]
        grad = loss_gradient(
            Y,
            neighbor_pairs,
            mid_near_pairs,
            further_pairs,
            w_neighbor,
            w_mid_near,
            w_further,
        )
        Y = adam_update(Y, grad)
    return Y


# Mid-near partner of point i: draw 6 random points, keep the second
# closest to i  [§7] [alg. 1]
def mid_near_partner(X, i):
    candidates = random_sample(6, exclude=i)
    ordered = sort_by_distance(candidates, X[i])
    return ordered[1]


# Weights at 1-based step t  [alg. 1]
def weights(t):
    # Phase 1 (t = 1..100): mid-near weight falls linearly from 1000 to 3
    if t < 101:
        w_mid_near = 1000 * (1 - (t - 1) / 100) + 3 * (t - 1) / 100
        return 2, w_mid_near, 1
    # Phase 2 (t = 101..200): small, constant mid-near weight  [alg. 1]
    if t < 201:
        return 3, 3, 1
    # Phase 3 (t = 201..450): no mid-near term  [alg. 1]
    return 1, 0, 1

Loss. With the transformed squared distance \tilde d_{ab} = \|y_a - y_b\|^2 + 1 §7, the loss is

L = w_{NB} \sum_{(i,j)\in NB} \frac{\tilde d_{ij}}{10 + \tilde d_{ij}} + w_{MN} \sum_{(i,k)\in MN} \frac{\tilde d_{ik}}{10000 + \tilde d_{ik}} + w_{FP} \sum_{(i,l)\in FP} \frac{1}{1 + \tilde d_{il}} alg. 1 §7

The neighbour and mid-near terms are attractive; the further-point term is repulsive. The authors motivate the choice of \tilde d by the Student-t kernel used in t-SNE and TriMap §7. The paper's own discussion of the loss principles is in §4.5.

Why mid-near pairs. Early in the run, PaCMAP exerts strong attraction on mid-near pairs, which builds global structure. Later it relies on neighbours for local detail §5.2. The authors add mid-near points one at a time, from 0 to 8 per point, and report that more of the global structure is recovered as they are added §5.2 fig. 14. PaCMAP is not robust to omitting mid-near points altogether §8.3.

Dynamic phases. Phase 1 (steps 1 to 100) heavily weights mid-near pairs and gradually lowers their weight, which moves the layout from global to local. Phase 2 (steps 101 to 200) keeps a small mid-near weight to hold the global layout. Phase 3 (steps 201 to 450) removes mid-near pairs and repels points more strongly, which separates clusters §7 fig. 19 fig. 20.

Key equations. Scaled distance §7 eq. 2. Loss and weight schedule alg. 1.

Hyperparameters

Results

Author-reported. Setup: 12 datasets, 2-D embeddings, each method run with three hyperparameter settings and the best reported per metric §8.1. Hardware: one Dell R730 server with 2 Intel Xeon E5-2640 v4 CPUs, 64 GB memory limit, 24 h time limit §8.1. The "best other" column is the strongest competitor on that row, as read from the tables. The paper's high-dimensional baseline column is not repeated here.

Summary the authors draw: PaCMAP matches local-structure methods on local datasets and matches TriMap on global-structure datasets §8.2 fig. 21 fig. 22. The authors state that PaCMAP gets its global structure from its graph choice and does not depend on initialisation §8.2. Robustness to initialisation is shown qualitatively §8.3.

Paper vs code

Code: source/pacmap/pacmap.py at commit 2e7237aa1d702ed8ab104e5af1347ff2e709266c in the repository linked in the paper's experimental section §8.1. The repository is under the first author's GitHub account, and its README cites the paper. The README points to the JMLR version of the paper, which may differ in detail from the arXiv v2 source used here.

Confirmed matches (no discrepancy found):

• Phase weights and boundaries: the code's find_weight uses the same schedule and the same 1-based boundaries after shifting by one pacmap.py alg. 1.
• Iteration count: default (100, 100, 250) sums to 450 pacmap.py alg. 1.
• Loss terms and the transformed distance \tilde d pacmap.py alg. 1.
• Mid-near pair rule: 6 draws, the closest is dropped and the next closest is kept pacmap.py alg. 1.
• Sigma from the 4th to 6th neighbours pacmap.py §7.

Differences:

• Learning rate and Adam constants: the paper does not state them alg. 1. The code uses lr 1.0 pacmap.py with beta1 0.9, beta2 0.999 pacmap.py.
• PCA start: the paper says only "initialize Y using PCA" alg. 1. The code multiplies the PCA coordinates by 0.01 pacmap.py pacmap.py.
• Random start: the paper writes N(0, 10^-4 I) alg. 1, which reads as variance 10^-4 under covariance notation. The code draws with standard deviation 1e-4 pacmap.py, which is variance 10^-8.
• Nearest-neighbour backend: the paper's timing setup says Annoy §8.1. The code's default is FAISS HNSW, an approximate method pacmap.py pacmap.py. The repository README notes that Annoy was the original default [README, "Note" under the parameter list].
• Neighbour count: the paper uses 10 §7. The code also has a size-dependent default for n above 10 000 if n_neighbors=None is passed pacmap.py. The class default is 10 pacmap.py.
• Input normalisation: not stated in the paper. The code applies it pacmap.py.
• Speedup claim: §8.2 says "more than 1.5 times faster ... for most datasets" §8.2. In Table 5, three speedups fall below 1.5 (USPS 1.40, MNIST 1.33, F-MNIST 1.26) tab. 5. The base of the speedup ratio is not stated.
• Dataset size: USPS is listed as 9K in tab. 2–tab. 4 and as 9.5K in tab. 5.

Pitfalls

• Missing optimiser settings. The learning rate and Adam constants are not in the paper. An implementation that follows alg. 1 alone will not reproduce the paper's behaviour. Use the code defaults above and say so.
• Scale-dependent constants. The 10 and 10 000 in the loss, and the 0.01 PCA scale in the code, set the scale of the embedding. Changing the initial scale or learning rate changes how strongly the mid-near term acts pacmap.py pacmap.py.
• Mid-near partners are not filtered. Both the paper and the code sample 6 random points, with no check against the neighbour set §7 pacmap.py. A mid-near partner can therefore also be a neighbour. The paper does not discuss this.
• Hidden cost in phase 3. The mid-near weight is 0 after step 200, but the code still loops over all mid-near pairs every step pacmap.py. The mid-near sampling is paid for even though it no longer contributes.
• Approximate neighbours. The code's default kNN is approximate pacmap.py. Neighbour sets, and so the sigma values, can differ from exact kNN. The paper does not discuss this.
• Mid-near ratio sensitivity. Removing mid-near pairs loses the global shape. Too many overwhelm the neighbour and repulsion terms and hurt local structure too §8.3 fig. 14.
• Best-of-three reporting. Each method is reported at the best of three settings per metric, and PaCMAP's own range is also one of three values §8.1. Expect results for a single fixed setting to be lower.
• Random-triplet metric variance. Triplet accuracy is sampled and averaged over five runs §8.1. The reported standard deviations are over those runs, not over datasets.
• Speedup is not a fixed factor. The runtime advantage is reported on one server with one CPU model §8.1. Relative speedups vary from 1.26 to 2.23 in the table tab. 5.
• Initialisation claims are partly qualitative. The robustness to initialisation is shown with figures §8.3 fig. 19 fig. 20, not with a table. Do not treat it as a measured guarantee.

Lineage

• Builds on: t-SNE, UMAP and TriMap, whose attraction and repulsion forces are analysed in §3 and §4. No cards for these yet, so nothing from their content is used here.
• Compared against: t-SNE, LargeVis, UMAP and TriMap §8.1.
• Superseded by: none in the wiki.