UMAP for dimensionality reduction: Visual walkthrough

Before anything else, let us agree on the words.

We use the ordinary straight-line distance (Euclidean) as our default, the same $d_{ij}$ you would get with a ruler. When we say "high-D" we mean the original $d$ -dimensional space; "low-D" means the flat 2-D map we are trying to draw.

Prerequisites worth a glance: Nearest Neighbors Algorithms (Step 1), Cross-Entropy Loss (Step 5), and cousins PCA, Isomap, Spectral Clustering, Autoencoders, Random Projection, Topological Data Analysis.

Step 1 — Find each point's neighbours

WHAT. Pick one point $x_{i}$ . Look outward and grab its $k$ closest points. That number $k$ is the hyperparameter n_neighbors. Do this for every point.

WHY. UMAP never trusts global straight-line distances (a straight line through a crumpled sheet cuts through empty air). It only trusts who is next to whom locally. So the raw material is not "all distances" but "each point's little circle of friends." This is exactly the nearest-neighbours query.

PICTURE. Below, the blue point is $x_{i}$ . The $k = 5$ orange points are its nearest neighbours; the gray points are ignored for now. The nearest of all — its very closest friend — is circled in green; its distance is called $ρ_{i}$ (Greek letter "rho", just a name for "distance to closest friend").

Figure — UMAP for dimensionality reduction

$x_{i}$ ::: the point we are currently focused on (blue).
$k$ ::: how many neighbours we keep — small $k$ = very local view, large $k$ = broader view.
$ρ_{i}$ ::: the distance from $x_{i}$ to its single closest neighbour (green circle).
$N (i)$ ::: the set of those $k$ nearest neighbours of $x_{i}$ — the only points $j$ we will ever attach a weight to.

Step 2 — Turn distances into "friendship strengths"

WHAT. A raw distance is awkward: it grows without limit. We want instead a weight $w_{ij}$ between $0$ and $1$ — think "how strongly are $i$ and $j$ connected?" — where $1$ means glued together and $0$ means strangers. For every neighbour $j \in N (i)$ we compute:

w_{ij} = exp (- \frac{max ( 0 , d _{ij} - ρ _{i} )}{σ _{i}})

Let us read every piece right where it sits:

$d_{ij}$ ::: raw distance from $x_{i}$ to neighbour $x_{j}$ — the ruler number.
$d_{ij} - ρ_{i}$ ::: distance beyond the closest friend. We measure from the nearest neighbour, not from $x_{i}$ itself.
$max (0, \cdot)$ ::: a floor at zero — anything closer than $ρ_{i}$ can't give a negative gap, so it stays at $0$ .
$σ_{i}$ ::: the "softness" or bandwidth (Greek "sigma") — big $σ_{i}$ makes distant friends still count, small $σ_{i}$ makes the friendship die off fast.
$exp (- \cdot)$ ::: the exponential decay — turns "gap" into a number that starts at $1$ and slides smoothly toward $0$ .

For any $j$ not in $N (i)$ we simply set $w_{ij} = 0$ — those pairs never enter any sum.

WHY the $exp$ and not, say, $1/ d$ ? We want three things at once: (1) the value must sit in $[0, 1]$ , (2) it must be exactly $1$ at zero gap, (3) it must fade smoothly with no sudden cliff. The falling exponential $e^{- t}$ is the unique simple function that does all three: $e^{0} = 1$ and it decays gently. That is why this tool and not a reciprocal (which blows up at $d = 0$ ) or a hard cutoff (which has a cliff).

WHY $ρ_{i}$ (the $max (0, \cdot)$ subtraction)? Without it, a lonely point in a sparse region would have all weights tiny and float off alone. Subtracting $ρ_{i}$ guarantees the nearest friend gets $w = exp (0) = 1$ — everyone is fully connected to at least one neighbour. No islands.

PICTURE. The curve below is $w$ as the gap $d_{ij} - ρ_{i}$ grows. It starts at $1$ (the green dot, the nearest friend) and decays. The vertical dashed line marks where the friendship has faded to about a third — that spot is controlled by $σ_{i}$ .

Step 3 — Tune $σ_{i}$ so every point has the same "amount of neighbourhood"

WHAT. We don't pick $σ_{i}$ by hand. We choose it so the weights of point $i$ add up to a fixed budget, where the sum runs over exactly the $k$ nearest neighbours $N (i)$ from Step 1 (the only $j$ with nonzero $w_{ij}$ ):

j \in N (i) \sum w_{ij} = lo g_{2} (k)

$\sum_{j \in N (i)}$ ::: sum over the $k$ nearest neighbours of $x_{i}$ — not over all $n$ points, only over $i$ 's own circle of friends.
$w_{ij}$ ::: the friendship weight from Step 2.
$lo g_{2} (k)$ ::: the target budget — the "effective number of neighbours" measured in information-theory units. For $k = 15$ this is $lo g_{2} 15 \approx 3.906$ .

WHY a fixed budget? Some points sit in crowded regions, some in empty ones. If we used one global $σ$ , crowded points would be over-connected and lonely points under-connected. Forcing every point's weights to sum to the same number makes UMAP treat dense and sparse regions fairly — this is the "uniform" in Uniform Manifold Approximation. It is the same idea as perplexity in t-SNE.

HOW. The sum shrinks when $σ_{i}$ is small (weights decay fast) and grows when $σ_{i}$ is big. Since it moves monotonically, a binary search nails the right $σ_{i}$ in about 20 halving steps.

PICTURE. Left: a dense point needs a small $σ_{i}$ (tight decay) to keep its sum at the budget. Right: a sparse point needs a large $σ_{i}$ . Same budget, different softness — that's the equalisation.

Step 4 — Make the graph symmetric (fuzzy union)

WHAT. So far friendship can be one-sided: $x_{i}$ might list $x_{j}$ as a neighbour but not vice-versa, so $w_{ij} \neq = w_{j i}$ . We merge the two views into one undirected weight:

w_{ij}^{sym} = w_{ij} + w_{j i} - w_{ij} w_{j i}

$w_{ij}$ ::: how strongly $i$ reaches out to $j$ .
$w_{j i}$ ::: how strongly $j$ reaches out to $i$ .
$w_{ij} + w_{j i} - w_{ij} w_{j i}$ ::: the fuzzy OR — "at least one of them thinks they're friends."

WHY this exact formula? Read it as probability. If $w_{ij}$ is the chance $i$ -sees- $j$ and $w_{j i}$ the chance $j$ -sees- $i$ , then the chance at least one is true is $P (A) + P (B) - P (A \cap B)$ . That is precisely $w_{ij} + w_{j i} - w_{ij} w_{j i}$ . It keeps the result in $[0, 1]$ and is generous: one strong direction is enough to bind the edge.

EDGE CASES.

If both directions are $1$ : $1 + 1 - 1 = 1$ (stays capped, never overflows past $1$ ).
If both are $0$ : $0$ (true strangers stay strangers).
If one is $1$ , other $0$ : $1 + 0 - 0 = 1$ (one-sided strong friendship is honoured).
Self-edges ( $i = j$ ): we never form them. Nearest-neighbour search excludes a point from its own neighbour list, so $i \in / N (i)$ , $w_{ii}$ is never defined, and the loss in Step 6 sums only over pairs with $i \neq = j$ .

PICTURE. Left: two directed arrows with unequal strengths. Right: one fused undirected edge whose thickness is the fuzzy-OR result.

The result is a single fuzzy graph — this is the fuzzy topological structure of your data, the object Topological Data Analysis also studies.

Step 5 — Give the flat map its own connection kernel

WHAT. Now flip to the 2-D world. Scatter the points anywhere as $y_{1}, \dots, y_{n}$ (2-D positions we get to move). Define their connection strength with a different formula:

v_{ij} = \frac{1}{1 + a ∥ y _{i} - y _{j} ∥ _{2}^{2 b}}

$∥ y_{i} - y_{j} ∥_{2}$ ::: the flat-map distance between the two 2-D dots.
$2 b$ ::: the exponent controlling how sharply nearness turns into strong connection.
$a$ ::: a scale knob for how quickly $v$ falls off.
$\frac{1}{1 + ( \cdot )}$ ::: gives $v = 1$ at zero distance and a heavy tail — it never crashes to $0$ too abruptly.

Where do $a$ and $b$ come from? Enter min_dist. First the definition, then the picture, then the solve.

PICTURE (target shape). We first draw the shape we WANT the low-D kernel to have. It should equal $1$ for any distance up to $m$ , then fall off exponentially:

Φ (d) = {1 exp (- (d - m)) d \leq m d > m

$Φ (d)$ ::: the ideal connection-vs-distance curve dictated by min_dist.
flat top out to $m$ ::: "points within $m$ are treated as fully together."
exponential drop after $m$ ::: gentle fade, same spirit as Step 2's high-D kernel.

THE SOLVE (fit $a, b$ to $Φ$ ). The smooth rational form $v (d) = \frac{1}{1 + a d ^{2 b}}$ is easy to differentiate (good for gradient descent) but has no flat top. So we least-squares fit $(a, b)$ so that $v (d)$ hugs the target $Φ (d)$ as closely as possible over a grid of distances:

(a, b) = ar g a, b min d \sum (v (d; a, b) - Φ (d))^{2}

$ar g min$ ::: "the $a, b$ that make the mismatch smallest."
inner bracket ::: pointwise gap between the smooth kernel and the ideal target, at each sample distance $d$ .

For the library default $m = 0.1$ this fit returns $a \approx 1.929, b \approx 0.7915$ — the numbers quoted in the parent note are not magic constants but the output of this one-time curve fit. Change $m$ and you re-run the fit, getting new $a, b$ .

WHY a heavy-tailed rational curve at all (instead of another exponential)? In 2-D there isn't enough room; if far points were pulled with full force everything would pile into a blob (the "crowding problem"). The rational form has a heavy tail, so far points stay comfortably far while near points snap together — and it is differentiable everywhere, which the piecewise $Φ$ is not.

Step 6 — Match the two graphs with cross-entropy

WHAT. We now have two fuzzy graphs on the same points: the fixed high-D one ( $w^{sym}$ ) and the movable low-D one ( $v$ ). Slide the 2-D dots until the two graphs agree. We build the disagreement score from scratch.

Step 6a — one edge is a coin flip. Treat "is there an edge between $i$ and $j$ ?" as a yes/no random event (a Bernoulli variable). High-D says the true probability of "yes" is $w_{ij}$ ; low-D currently predicts $v_{ij}$ . The standard cross-entropy between a true probability $p$ and a predicted probability $q$ is:

H (p, q) = - p lo g q - (1 - p) lo g (1 - q)

$- p lo g q$ ::: penalty when the true "yes" chance $p$ is high but predicted $q$ is low.
$- (1 - p) lo g (1 - q)$ ::: penalty when the true "no" chance $1 - p$ is high but predicted "no" chance $1 - q$ is low.

Step 6b — subtract the part we can't change, showing the algebra. Only $v$ (through the dot positions) is adjustable; $w$ is frozen. The entropy of $w$ alone, $H (w) = - w lo g w - (1 - w) lo g (1 - w)$ , is a constant that does not depend on the dots, so minimising $H (w, v)$ is identical to minimising $H (w, v) - H (w)$ . Watch the two constant terms cancel into the variable terms via $lo g a - lo g b = lo g \frac{a}{b}$ :

H (w, v) - H (w) = [- w lo g v - (1 - w) lo g (1 - v)] - [- w lo g w - (1 - w) lo g (1 - w)] = w (lo g w - lo g v) + (1 - w) (lo g (1 - w) - lo g (1 - v)) = w lo g \frac{w}{v} + (1 - w) lo g \frac{1 - w}{1 - v}

line 1 ::: write both cross-entropies out in full.
line 2 ::: group the $w$ -terms and the $(1 - w)$ -terms; signs flip so each $lo g$ pair subtracts.
line 3 ::: fold each subtracted pair into a single ratio with $lo g a - lo g b = lo g \frac{a}{b}$ .

This is the tidy relative form. (Writing $w_{ij}$ for $w_{ij}^{sym}$ from here on.)

Step 6c — sum over pairs, but only the ones that matter. Add this up over pairs:

L = (i, j) \in E \sum attraction w_{ij} lo g \frac{w _{ij}}{v _{ij}} + (i, j) \in S \sum repulsion (1 - w_{ij}) lo g \frac{1 - w _{ij}}{1 - v _{ij}}

$E$ ::: the set of actual graph edges ( $w_{ij} > 0$ , i.e. neighbour pairs, $i \neq = j$ ) — these supply attraction. There are only $O (nk)$ of them, not $n^{2}$ .
$S$ ::: a small set of randomly sampled non-edges ( $w_{ij} \approx 0$ , $i \neq = j$ ) drawn fresh each step — negative sampling. These supply repulsion without ever touching all $n^{2}$ pairs.

How many negatives? For each edge we touch during a step, we draw a fixed number of random strangers — the negative_sample_rate, default 5 non-edges per positive edge. Each stranger $j^{'}$ is picked by sampling an index uniformly at random from all $n$ points (rejecting $j^{'} = i$ ), so $S$ is roughly $5 \times ∣ E ∣$ pairs per epoch, still $O (nk)$ overall. This keeps the two terms balanced: one green pull per edge, five red pushes.

So the innocent-looking $\sum_{i, j}$ in the parent note is, in practice, "sum over the few real edges plus a handful of sampled strangers, all with $i \neq = j$ " — never a full $n^{2}$ sweep, and never a self-edge.

WHY cross-entropy and not t-SNE's KL? t-SNE keeps only the attraction half (a single KL term over normalised probabilities), so it forgets global distances. UMAP's Bernoulli cross-entropy keeps both halves — an explicit attraction on true edges and an explicit repulsion on sampled strangers. That second, repulsive term is exactly what pushes unrelated clusters apart and so preserves the global layout that t-SNE throws away.

$w_{ij} lo g \frac{w _{ij}}{v _{ij}}$ ::: attraction — when high-D says "connected" ( $w$ big) but low-D has them far ( $v$ small), this blows up, so the optimiser pulls them together.
$(1 - w_{ij}) lo g \frac{1 - w _{ij}}{1 - v _{ij}}$ ::: repulsion — when high-D says "strangers" ( $w$ small) but low-D placed them close ( $v$ big), this blows up, so the optimiser pushes them apart.

HOW we actually minimise it. The optimiser is plain stochastic gradient descent (no momentum, no Adam), run for a fixed n_epochs (default ~200 for large data, ~500 for small). The recipe:

Initialise the dot positions with a spectral embedding (eigenvectors of the graph Laplacian) — a smart, deterministic starting layout that is far cheaper than random restarts.
Per epoch, walk over every edge in $E$ . For each edge, apply the attractive gradient to pull $y_{i}, y_{j}$ together, then draw 5 strangers ( $S$ ) and apply the repulsive gradient to push them apart. Gradients are clamped to $[- 4, 4]$ to stop blow-ups.
Learning rate ( $α$ , the step size) starts at $1.0$ and decays linearly to $0$ across the epochs, so early epochs move boldly and late epochs fine-tune.

PICTURE. Two forces on the same dot: a green spring pulling toward a true neighbour (attraction) and a red spring pushing away a sampled non-neighbour (repulsion). Their balance is the final position.

Step 7 — Watch the map settle

WHAT. Repeat the pull/push over the ~200–500 epochs from Step 6. Each epoch walks over the edge set $E$ (one attraction per edge) and, for each edge, samples 5 strangers from $S$ (repulsion), while the learning rate decays from $1.0$ toward $0$ . The tangled initial scatter relaxes into separated, correctly-arranged clusters.

WHY it converges. Every edge in $E$ contributes a pull; every sampled non-edge in $S$ contributes a push. At the layout where pulls balance pushes and the learning rate has shrunk to near zero, the dots stop moving — that's the embedding.

PICTURE. Three snapshots: tangled start → mid-optimisation → settled clusters that keep both local groups and their global arrangement.

The one-picture summary

Every gadget on one canvas: neighbours → weighted graph → fuzzy union → cross-entropy pull/push → flat map.

Recall Feynman retelling — the whole thing in plain words

Imagine everybody in a huge crumpled crowd. First, each person looks around and notes their few closest friends — that little set is $N (i)$ , and it never lists yourself (no self-edges) (Step 1). "Closeness" is turned into a friendship strength between $0$ and $1$ using a gentle falloff, and everyone is guaranteed at least one full friend so nobody floats away (Step 2). We tune each person's "reach" $σ_{i}$ so everyone spends the same friendship budget summed over just their own $k$ friends — crowded folks reach short, lonely folks reach far (Step 3). Friendship is made mutual with a fuzzy-OR: if either says "friend," it counts (Step 4). Now we drop everyone onto a flat floor; we first decide the smallest allowed gap min_dist, draw the ideal closeness curve, and fit the floor's rule $(a, b)$ to it (Step 5). Finally we score the mismatch with Bernoulli cross-entropy (true-probability $w$ vs predicted $v$ , minus the constant part of $w$ ), and let plain SGD — starting at learning-rate $1.0$ , decaying to $0$ over ~200 epochs, one green pull per true edge and five red pushes per sampled stranger — shuffle people until pulls and pushes balance (Steps 6–7). The flat arrangement that results is the UMAP map: neighbours stayed neighbours, and the big-picture layout survived too.

Recall

Why does subtracting $ρ_{i}$ prevent isolated points? ::: The nearest friend gets gap $0$ , so $w = exp (0) = 1$ — every point is fully connected to at least one neighbour. Over which index does $\sum w_{ij} = lo g_{2} (k)$ run? ::: Only over the $k$ nearest neighbours $N (i)$ of point $i$ — the sole pairs with nonzero $w_{ij}$ . Where do $a$ and $b$ come from? ::: A one-time least-squares fit of the smooth kernel $1/ (1 + a d^{2 b})$ to the ideal min_dist target curve $Φ$ . Which half of the cross-entropy creates repulsion, and on which pairs? ::: The second term $(1 - w) lo g \frac{1 - w}{1 - v}$ , evaluated on randomly sampled non-edges $S$ (negative sampling, ~5 per edge). How are self-edges ( $i = j$ ) handled? ::: They never exist — nearest-neighbour search excludes each point from its own neighbour list, so every sum runs over $i \neq = j$ only. What optimiser and schedule does UMAP use? ::: Plain SGD from a spectral initial layout, learning rate starting at $1.0$ and decaying linearly to $0$ over ~200–500 epochs, gradients clamped to $[- 4, 4]$ . Why is UMAP's loss cross-entropy rather than t-SNE's KL? ::: Cross-entropy keeps both an attraction term (true edges) and a repulsion term (strangers); KL keeps only attraction, so it loses global structure.