UMAP for dimensionality reduction: Question bank

Before we start, a few plain-word reminders so no symbol below is a surprise.

Definition The two distances — keep them apart

Two totally different "distances" appear on this page, and reusing one letter for both is the single most common source of confusion. So we give them different names:

$d_{ij}^{hi}$ = distance between points $i$ and $j$ in the original high-D space. By default this is the ordinary Euclidean ( $ℓ_{2}$ ) distance, but UMAP happily accepts any metric you pass in (metric="cosine", Manhattan, etc.) — the fuzzy-graph machinery only needs some number saying "how far apart"; it never assumes $ℓ_{2}$ .
$d_{ij}^{lo} = ∥ y_{i} - y_{j} ∥_{2}$ = straight-line distance between the two points in the low-D picture (positions $y_{i}$ ). This one is always Euclidean, because it's a 2-D or 3-D plot.

Rule: if you see $ρ_{i}$ or $σ_{i}$ nearby, the distance is $d^{hi}$ . If you see $a$ or $b$ nearby, it's $d^{lo}$ .

Formula The full cross-entropy loss (attraction + repulsion)

Writing $w$ for $w_{ij}^{sym}$ and $v$ for $v_{ij}$ , the layout $Y$ is found by minimising $L = \sum_{i \neq = j} [attraction w lo g \frac{w}{v} + repulsion (1 - w) lo g \frac{1 - w}{1 - v}]$ The attraction term is large when high-D says "connected" ( $w$ high) but low-D put them apart ( $v$ low) — so it pulls neighbours together. The repulsion term is large when high-D says "unconnected" ( $w$ low) but low-D put them close ( $v$ high) — so it pushes strangers apart. Because the sum runs over all pairs, computing the repulsion exactly costs $O (n^{2})$ ; negative sampling fixes this by, per attractive edge, drawing only a handful of random $j$ and applying repulsion to those. Random pairs are almost always far apart in high-D ( $w \approx 0$ ), so a few samples give an unbiased, cheap estimate of the full repulsive gradient.

Recall What

$k$ is (the number of neighbours) $k$ is just a nickname for the hyperparameter n_neighbors — the number of nearest neighbours each point is allowed to look at when we build the graph. So "sum to $lo g_{2} (k)$ " means "sum to $lo g_{2} (n_neighbors)$ ". Small $k$ = very local view; large $k$ = broader, more global view.

Recall What

$ρ_{i}$ and $σ_{i}$ mean $ρ_{i}$ = distance ( $d^{hi}$ ) from point $i$ to its closest neighbour (a floor we subtract off). $σ_{i}$ = a per-point "stretch" tuned so the point's outgoing edge weights sum to $lo g_{2} (k)$ — this makes dense and sparse regions get treated fairly.

Recall What

$a$ , $b$ , and $d^{lo}$ are in the low-D kernel In $v_{ij} = \frac{1}{1 + a ( d _{ij}^{lo} ) ^{2 b}}$ , the distance $d_{ij}^{lo} = ∥ y_{i} - y_{j} ∥_{2}$ is the straight-line distance between the two points in the 2-D picture. The two constants $a$ and $b$ are shape knobs fitted once (numerically, giving roughly $a \approx 1.93, b \approx 0.79$ for the default min_dist) so the kernel's flat-then-falling curve matches the min_dist you asked for. You never tune $a, b$ by hand — UMAP solves for them from min_dist.

Recall What

min_dist is and its valid range min_dist sets how tightly points are allowed to pack in the picture: it is the effective minimum gap the low-D kernel encourages. Valid range is $[0, 1)$ (typically $0.0$ – $0.99$ ; default $\approx 0.1$ ). At $0$ points may sit right on top of each other (tight, dense clusters); near $1$ they are pushed apart into an airy, spread-out layout. It only reshapes $a, b$ — it never touches the high-D graph.

The figure below shows both kernels together so you can see how a distance becomes a weight before you tackle the traps.

Figure — UMAP for dimensionality reduction

Figure s01. Horizontal axis = distance between two points; vertical axis = the resulting edge weight (0 to 1). The pale-yellow curve is the high-D map $w_{ij} = exp (- max (0, d^{hi} - ρ) / σ)$ : flat at 1 until the nearest-neighbour floor $ρ$ (pink dashed line), then exponential decay set by $σ$ . The blue curve is the low-D kernel $v_{ij} = 1/ (1 + a (d^{lo})^{2 b})$ : notice its heavy tail — far-apart points in the picture still feel a faint pull, which is what prevents the "crowding problem".

True or false — justify

TF — "UMAP preserves the actual distances between clusters, so a gap twice as wide means twice as different."

False. UMAP preserves ordering and connectivity of structure, not metric distances; inter-cluster gaps are qualitatively meaningful but not quantitatively to scale.

TF — "Because UMAP keeps some global structure, cluster sizes in the plot reflect how spread-out those groups are in high-D."

False. Cluster size in the embedding is mostly an artefact of min_dist and the repulsion dynamics, not high-D variance — a tiny plotted blob can be a huge manifold region.

TF — "By default (parallel threads, no fixed seed) UMAP gives an identical layout every run."

False. Default runs are non-deterministic — parallelism and random negative sampling make each layout differ (often just a rotation/reflection); you must fix the random seed and run single-threaded to reproduce a layout exactly.

TF — "The high-D weight

w_{ij}

is symmetric before we symmetrize it."

False.

w_{ij}

(how much

i

sees

j

) differs from

w_{j i}

because

ρ

and

σ

are per-point; that is exactly why the fuzzy-union step

w_{ij} + w_{j i} - w_{ij} w_{j i}

exists.

TF — "The fuzzy-union weight

w_{ij}^{sym}

can exceed 1 if both directions are strong."

False. The

- w_{ij} w_{j i}

correction term caps it: even with

w_{ij} = w_{j i} = 1

you get

1 + 1 - 1 = 1

, so it stays a valid membership in

[0, 1]

TF — "Increasing n_neighbors always improves the embedding."

False. Large

k

buys global structure but blurs fine local clusters and costs more; the 'best'

k

depends on whether you care about micro-clusters or the macro-layout.

TF — "min_dist changes what UMAP thinks the data is."

False. min_dist only shapes the low-D kernel (how tightly points may pack); it never touches the high-D graph

w_{ij}

, so it is purely a cosmetic/visualisation knob.

TF — "UMAP only works if you feed it Euclidean distances."

False. Euclidean is the default for

d^{hi}

, but the fuzzy-graph construction accepts any metric (cosine, Manhattan, etc.); only the low-D distance

d^{lo}

is fixed to Euclidean because it's a plot.

TF — "UMAP can embed a brand-new point without re-running the whole optimisation."

True. Once trained, UMAP can transform new points into the existing embedding — something t-SNE fundamentally cannot do without refitting.

TF — "Setting min_dist=0.0 guarantees clusters that touch will merge visually."

False. min_dist=0 only allows points to pack tightly; the attractive/repulsive forces from

w_{ij}

still keep genuinely different clusters apart.

Spot the error

Error — "We compute

σ_{i}

so that

\sum_{j} w_{ij} = k

(the number of neighbours)."

The target is

lo g_{2} (k)

, not

k

. Summing to

k

would ignore the information-theoretic perplexity idea and over-connect every point.

Error — "

ρ_{i}

is subtracted so that even a point's farthest neighbour gets weight 1."

No —

ρ_{i}

is the nearest-neighbour distance, so only the closest neighbour (

d_{ij}^{hi} = ρ_{i}

) gets weight

exp (0) = 1

; farther ones still decay.

Error — "Cross-entropy here only rewards putting connected points close together."

It has two halves. The second term

(1 - w) lo g \frac{1 - w}{1 - v}

punishes putting unconnected points close — that repulsion is what stops everything collapsing to one dot.

Error — "Negative sampling picks the closest non-neighbours to push apart."

Negative sampling picks random pairs (mostly far ones, so

w \approx 0

) to cheaply and unbiasedly approximate the repulsive term; picking closest non-neighbours would be the wrong statistic and slow.

Error — "The low-D kernel

v_{ij} = \frac{1}{1 + a ( d ^{lo} ) ^{2 b}}

uses the same exponential form as the high-D weight."

No — high-D uses an exponential decay in

d^{hi}

; low-D uses a rational, heavy-tailed (Student-t-like) kernel in

d^{lo}

to avoid the crowding problem.

Error — "The constants

a

and

b

in the low-D kernel are hyperparameters you set by hand."

No — they are derived from min_dist by a one-time curve fit, so the knob you actually turn is min_dist;

a, b

follow from it automatically.

Error — "Since UMAP models a manifold, it must fail on data with no manifold (pure noise)."

It won't fail to run; it will happily produce a blob or spurious clusters. The trap is trusting structure that the algorithm invented from noise.

Error — "We use spectral embedding as the final answer, then polish with SGD."

Spectral embedding is only the initialisation (a good starting layout); SGD on the cross-entropy loss is what actually produces the result.

Why questions

Why — Why does UMAP subtract

ρ_{i}

inside the exponent at all?

To enforce local connectivity: every point is guaranteed at least one full-strength edge (

w = 1

), preventing isolated points and making the graph a single connected structure.

Why — Why

lo g_{2} (k)

specifically, rather than any constant?

It ties the summed weight to perplexity (effective neighbour count), so dense and sparse regions of the manifold are modelled with matching "local scale" — this is what gives density-aware normalisation.

Why — Why cross-entropy instead of the KL-divergence that t-SNE uses?

Cross-entropy's two-sided form (attraction and repulsion, summed over all pairs) penalises both false-attraction and false-repulsion, which is what lets UMAP preserve global layout; KL in t-SNE mainly rewards local attraction and lets global distances drift.

Why — Why can UMAP afford to sum the repulsion over "all pairs" when that is

O (n^{2})

It doesn't compute them all — negative sampling replaces the exact all-pairs repulsion with a few random draws per edge, giving an unbiased gradient estimate at near-linear cost. See Cross-Entropy Loss.

Why — Why does UMAP need a repulsive term when we already reward keeping neighbours close?

Without repulsion the loss is trivially minimised by piling all points on top of each other; the

(1 - w) lo g \frac{1 - w}{1 - v}

term supplies the spreading force.

Why — Why is UMAP roughly

O (n^{1.14})

rather than

O (n^{2})

like naive t-SNE?

A brute-force pairwise graph is

O (n^{2})

, but UMAP builds the neighbour graph with approximate nearest-neighbour descent (see Nearest Neighbors Algorithms): it starts from a rough graph and iteratively refines "my neighbour's neighbour is probably my neighbour," touching only a near-constant number of candidates per point. That empirically scales like

n^{1.14}

(the exponent is measured, not exact), and negative sampling makes the optimisation cost roughly linear too.

Why — Why does min_dist affect visual density but not which clusters appear?

Cluster membership is decided by the high-D graph

w_{ij}

, which min_dist never touches; min_dist only sets how much the attractive low-D force is capped at short range.

Edge cases

Edge — What happens for a point that is a total outlier, far from everything?

The

ρ_{i}

rule still forces one weight-1 edge to its nearest (though distant) neighbour, so it is tethered in — it won't be dropped, but it may sit at the periphery.

Edge — What if two points are identical (

d_{ij}^{hi} = 0

They become

ρ_{i}

-nearest with weight

1

and are pulled essentially on top of each other; duplicate rows just stack, no division-by-zero because

max (0, d^{hi} - ρ)

handles it.

Edge — What does n_neighbors=1 do, and how does it differ from n_neighbors=2?

With

k = 1

each point connects only to its single nearest neighbour, so the directed graph is essentially a matching — extremely fragmented, with

lo g_{2} (1) = 0

making the

σ

calibration degenerate. With

k = 2

there is finally overlap between neighbourhoods, so small chains/clusters can begin to form;

k = 1

is effectively unusable while

k = 2

is merely very local.

Edge — What if n_neighbors is set larger than the number of points

n

The algorithm clamps to at most

n - 1

neighbours; effectively every point sees every other and you lose all locality, approaching a near-global (almost linear-projection-like) embedding.

Edge — What happens at the extremes of min_dist (0 versus close to 1)?

At min_dist=0 the kernel lets

v \to 1

even as

d^{lo} \to 0

, giving tight, dense clusters that preserve local density; near the upper end (approaching 1) points are strongly repelled at short range, producing an inflated, evenly spread layout that trades density info for readability.

Edge — What if the data is genuinely linear (a flat plane in high-D)?

UMAP will still work, but this is exactly the case where a linear method like PCA or Random Projection is cheaper and gives a faithful, interpretable result.

Edge — What if you feed UMAP a distance metric that violates the triangle inequality?

UMAP tolerates arbitrary metrics for graph construction, but the manifold assumption weakens; interpret the layout cautiously since the "geodesic" reasoning behind Isomap-style methods no longer holds cleanly.