UMAP

Build a fuzzy k-nearest-neighbour graph and lay it out in low dimensions — faster than t-SNE, with more global structure kept.

18 min read1892 wordscore2 viewsupdated 2026-10-07

Definition

UMAP (Uniform Manifold Approximation and Projection) is a nonlinear dimensionality-reduction method. It describes the data as a weighted graph in which each point is joined to its nearest neighbours with a membership strength wij∈[0,1]w_{ij}\in[0,1], then finds low-dimensional coordinates yiy_i whose own graph of similarities qijq_{ij} matches wijw_{ij} as closely as possible under a fuzzy cross-entropy loss.

At a glance

Task
Unsupervised dimensionality reduction — mostly 2-D/3-D visualisation, also 5–50-D features for clustering
Input → output
nn points in RD\mathbb{R}^D (any metric) → nn points yi∈Rdy_i\in\mathbb{R}^d, usually d=2d=2
Learns
a coordinate yiy_i per training point (non-parametric); new points are placed by a short extra optimisation
Training
approximate kNN by NN-descent (empirically about O(n1.14)O(n^{1.14})) + SGD over the graph edges, O(E⋅nk)O(E\cdot n k) for EE epochs
Prediction
transform: find the new point's kk neighbours, start at their weighted mean, refine for a few epochs
Hyperparameters
n_neighbors (local vs global), min_dist (how tightly points pack), n_components, metric, n_epochs
Assumes
the data lie near a low-dimensional manifold, and are roughly uniformly spread over it (each point gets its own distance scale to make this true)

The problem

PCA finds the best linear projection. When data lie on a curved surface — a rolled-up sheet, images of a rotating object, cell types along a developmental trajectory — a linear projection folds distant parts of the surface on top of each other. Linear latent-factor models (ICA, NMF, factor analysis) share that limit.

t-SNE fixed the folding by keeping only neighbourhoods: it matches neighbour probabilities in the input and the embedding. But it is slow (O(nlog⁡n)O(n\log n) per iteration with Barnes–Hut, and hard to scale past a few hundred thousand points), it cannot embed new points, it only works well in 2–3 output dimensions, and the distances between its clusters carry almost no information. UMAP keeps t-SNE's local view but builds it on a sparse graph that is cheap to optimise, so it is much faster, it can map new points, it works in any output dimension, and it usually keeps more of the large-scale arrangement.

The idea

Think of each point as looking around at its kk nearest neighbours with its own ruler. In a dense region the ruler is short; in a sparse region it is long. Measured with that local ruler, every point has neighbours at "unit" distance, as if the data were spread uniformly over the manifold. Each point then says how strongly it belongs with each neighbour — a fuzzy edge between 0 and 1. Two points' opinions about the same edge are merged with a fuzzy OR.

The result is one weighted graph — a skeleton of the data. UMAP then drops the points into 2-D at random and runs a spring simulation: edges with high weight pull their endpoints together, and every pair that is not strongly connected pushes apart. When the forces balance, points that were neighbours in the input are neighbours in the picture.

Vocabulary

k (n_neighbors)
size of each point's neighbourhood. In umap-learn the count includes the point itself, so n_neighbors=4 keeps 3 other points
ρᵢ (rho)
distance from point ii to its nearest neighbour. Subtracting it guarantees every point is fully connected (w=1w=1) to at least one neighbour — the local connectivity assumption
σᵢ (sigma)
point ii's local length scale, found by binary search so its memberships add up to log⁡2k\log_2 k
Membership vⱼ|ᵢ
how strongly ii thinks jj is its neighbour: 11 for the nearest, decaying exponentially beyond it, 00 for non-neighbours
Fuzzy union
symmetrisation by probabilistic OR, wij=vj∣i+vi∣j−vj∣ivi∣jw_{ij}=v_{j|i}+v_{i|j}-v_{j|i}v_{i|j}: the edge exists if either endpoint thinks so
Fuzzy simplicial set
the topological name for this weighted graph (UMAP only uses its edges, the 1-simplices)
min_dist
the smallest distance two points are allowed to have in the embedding before the similarity curve stops rewarding closeness
a, b
the two constants of the low-dimensional similarity curve q(d)=1/(1+ad2b)q(d)=1/(1+a d^{2b}), fitted from min_dist
Negative sample
a randomly chosen point that is pushed away from an edge endpoint; this is how repulsion stays cheap

The math

Step 1 — local scales. For each point ii take its k−1k-1 nearest neighbours j1,…,jk−1j_1,\dots,j_{k-1} at distances d(xi,xj)d(x_i,x_j). Set ρi\rho_i to the smallest of them and choose σi\sigma_i so that

∑m=1k−1exp⁡ ⁣(−max⁡ ⁣(0,  d(xi,xjm)−ρi)σi)=log⁡2k\sum_{m=1}^{k-1}\exp\!\left(-\frac{\max\!\big(0,\;d(x_i,x_{j_m})-\rho_i\big)}{\sigma_i}\right)=\log_2 k
d(xi,xj)d(x_i,x_j)
input-space distance (Euclidean here; any metric works)
ρi\rho_i
distance from ii to its nearest neighbour
σi\sigma_i
local length scale of point i, solved by binary search (the left side increases with σ)
log⁡2k\log_2 k
target total membership — a fixed 'effective number of neighbours'

This is the analogue of t-SNE's perplexity calibration, but without normalising to a probability distribution and with a target of log⁡2k\log_2 k instead of log⁡2(perplexity)\log_2(\text{perplexity}) bits. Because the nearest neighbour always contributes e0=1e^0=1, the remaining k−2k-2 neighbours share the remaining log⁡2k−1\log_2 k-1.

vj∣i=exp⁡ ⁣(−d(xi,xj)−ρiσi),wij=vj∣i+vi∣j−vj∣i vi∣jv_{j|i}=\exp\!\left(-\frac{d(x_i,x_j)-\rho_i}{\sigma_i}\right),\qquad w_{ij}=v_{j|i}+v_{i|j}-v_{j|i}\,v_{i|j}
vj∣iv_{j|i}
directed membership of jj in ii's neighbourhood (0 if jj is not among ii's neighbours)
wijw_{ij}
symmetric edge weight of the input graph: the fuzzy union (probabilistic OR) of the two directions

The union is 1−(1−vj∣i)(1−vi∣j)1-(1-v_{j|i})(1-v_{i|j}): the probability that at least one of two independent events happens. It is ≥\ge either direction, so edges are only ever strengthened by symmetrisation.

Step 2 — the low-dimensional similarity. In the embedding UMAP uses a smooth, heavy-tailed curve of the distance dij=∥yi−yj∥d_{ij}=\lVert y_i-y_j\rVert:

qij=11+a dij 2b  ≈  Ψ(d)={1d≤min_diste−(d−min_dist)d>min_distq_{ij}=\frac{1}{1+a\,d_{ij}^{\,2b}}\;\approx\;\Psi(d)=\begin{cases}1 & d\le \text{min\_dist}\\ e^{-(d-\text{min\_dist})} & d>\text{min\_dist}\end{cases}
qijq_{ij}
similarity of points i and j in the embedding, in (0, 1]
a, ba,\,b
found once by least-squares fitting qq to the target curve Ψ\Psi (with \texttt{spread} = 1)
min_dist\text{min\_dist}
distance below which points count as fully similar

With a=b=1a=b=1 this is exactly t-SNE's Student-t kernel. min_dist changes aa and bb: a larger value makes qq stay near 1 for longer, so neighbours no longer gain anything by sitting on top of each other and the clusters loosen.

min_distabq(0.1)q(0.5)q(1)q(2)
01.93280.79050.9520.6080.3410.147
0.1 (default)1.57690.89510.9750.6870.3880.155
0.50.58301.33420.9990.9160.6320.212
1.00.11501.92921.0000.9920.8970.375
The fitted constants (umap-learn find_ab_params, spread = 1) and the resulting similarity q at four embedding distances.

Step 3 — the loss. Treat each pair as a Bernoulli "edge present" variable: wijw_{ij} in the input, qijq_{ij} in the embedding. UMAP minimises the cross-entropy between the two fuzzy sets:

C(Y)=∑i<j[wijlog⁡wijqij⏟attraction+(1−wij)log⁡1−wij1−qij⏟repulsion]C(Y)=\sum_{i<j}\Big[\underbrace{w_{ij}\log\frac{w_{ij}}{q_{ij}}}_{\text{attraction}}+\underbrace{(1-w_{ij})\log\frac{1-w_{ij}}{1-q_{ij}}}_{\text{repulsion}}\Big]
YY
the embedding coordinates y1,…,yny_1,\dots,y_n (the only variables)
wijlog⁡wqw_{ij}\log\tfrac{w}{q}
large when an input edge is strong but the embedded points are far apart
(1−w)log⁡1−w1−q(1-w)\log\tfrac{1-w}{1-q}
large when two unconnected points sit close together in the embedding

The wlog⁡ww\log w terms do not depend on YY, so only −wlog⁡q−(1−w)log⁡(1−q)-w\log q-(1-w)\log(1-q) matters. t-SNE's KL divergence has only the first term; the explicit repulsion term is what lets UMAP keep gaps between clusters without normalising over all n2n^2 pairs.

Deriving the gradient. Write s=dij2s=d_{ij}^2, so q=(1+asb)−1q=(1+a s^b)^{-1}. Then −log⁡q=log⁡(1+asb)-\log q=\log(1+a s^b) has derivative ab sb−11+asb\dfrac{ab\,s^{b-1}}{1+a s^b} with respect to ss, and −log⁡(1−q)=log⁡(1+asb)−log⁡a−blog⁡s-\log(1-q)=\log(1+a s^b)-\log a-b\log s has derivative ab sb−11+asb−bs=−bs(1+asb)\dfrac{ab\,s^{b-1}}{1+a s^b}-\dfrac{b}{s}=-\dfrac{b}{s(1+a s^b)}. Multiplying by ∂s/∂yi=2(yi−yj)\partial s/\partial y_i=2(y_i-y_j):

∂C∂yi=∑j[2ab wij dij2(b−1)1+a dij2b⏟attractive coefficient  −  2b (1−wij)(ε+dij2)(1+a dij2b)⏟repulsive coefficient](yi−yj)\frac{\partial C}{\partial y_i}=\sum_{j}\left[\underbrace{\frac{2ab\,w_{ij}\,d_{ij}^{2(b-1)}}{1+a\,d_{ij}^{2b}}}_{\text{attractive coefficient}}\;-\;\underbrace{\frac{2b\,(1-w_{ij})}{(\varepsilon+d_{ij}^2)(1+a\,d_{ij}^{2b})}}_{\text{repulsive coefficient}}\right](y_i-y_j)
(yi−yj)(y_i-y_j)
direction of the force; a positive coefficient pulls i toward j when we step against the gradient
ε\varepsilon
a small constant (0.001) that stops the repulsion blowing up at zero distance

Each term is a spring along the line between two points. Gradient descent moves yi←yi−α ∂C/∂yiy_i\leftarrow y_i-\alpha\,\partial C/\partial y_i, with every per-pair term clipped to [−4,4][-4,4] and the step size α\alpha decaying linearly to 0.

Step 4 — making it fast. The attractive sum has only about nknk nonzero terms (the graph edges), but the repulsive sum runs over all n2n^2 pairs. umap-learn uses SGD with two sampling tricks. It visits each edge (i,j)(i,j) with frequency proportional to wijw_{ij} and applies the attractive term with weight 1. For each such visit it draws a few random points ll (negative_sample_rate = 5) and applies the repulsive term to (i,l)(i,l) as if wil=0w_{il}=0. Each epoch therefore costs O(nk)O(nk) instead of O(n2)O(n^2).

Worked example: twelve points in 3-D

Three groups of four points. In the input, group B is the nearest to A (centroid gap 3.15), C is farther from B (5.56) and farthest from A (6.04). We use n_neighbors k=4k=4, so each point keeps 3 neighbours and its memberships must sum to log⁡24=2\log_2 4=2.

PointGroupx₁x₂x₃
0A0.00.00.0
1A0.60.20.1
2A0.10.70.3
3A0.50.6−0.2
4B3.00.40.5
5B3.50.10.9
6B3.20.91.1
7B3.80.70.4
8C1.54.53.5
9C2.14.93.8
10C1.45.24.1
11C2.04.44.4
The dataset. Highlighted: point 0, whose neighbourhood we compute by hand.

Point 0's fuzzy neighbourhood

  1. 1Neighbours. Distances from point 0: to 1 is 0.41=0.640\sqrt{0.41}=0.640, to 2 is 0.59=0.768\sqrt{0.59}=0.768, to 3 is 0.65=0.806\sqrt{0.65}=0.806; every B or C point is at least 3.07 away. The three nearest are 1, 2, 3.
  2. 2ρ. ρ0=0.640\rho_0=0.640, so the shifted distances are 0,  0.128,  0.1660,\;0.128,\;0.166.
  3. 3σ. Solve 1+e−0.128/σ+e−0.166/σ=21+e^{-0.128/\sigma}+e^{-0.166/\sigma}=2. Binary search gives σ0=0.2106\sigma_0=0.2106.
  4. 4Memberships. v1∣0=1v_{1|0}=1, v2∣0=e−0.128/0.2106=0.545v_{2|0}=e^{-0.128/0.2106}=0.545, v3∣0=e−0.166/0.2106=0.455v_{3|0}=e^{-0.166/0.2106}=0.455. They sum to 2.000=log⁡242.000=\log_2 4, as required.
  5. 5Union with the other direction. Point 2 computes its own view, v0∣2=0.444v_{0|2}=0.444, so w02=0.545+0.444−0.545⋅0.444=0.747w_{02}=0.545+0.444-0.545\cdot0.444=0.747. Likewise w03=0.455+0.371−0.455⋅0.371=0.657w_{03}=0.455+0.371-0.455\cdot0.371=0.657, and w01=1w_{01}=1 because v1∣0=1v_{1|0}=1.
PointNeighboursDistancesρσMemberships v
01, 2, 30.640, 0.768, 0.8060.6400.21061, 0.545, 0.455
13, 0, 20.510, 0.640, 0.7350.5100.24991, 0.593, 0.407
23, 1, 00.648, 0.735, 0.7680.6480.14781, 0.556, 0.444
31, 2, 00.510, 0.648, 0.8060.5100.29851, 0.629, 0.371
45, 6, 70.707, 0.806, 0.8600.7070.17901, 0.575, 0.425
54, 7, 60.707, 0.837, 0.8770.7070.21501, 0.547, 0.453
64, 5, 70.806, 0.877, 0.9430.8060.14501, 0.612, 0.388
75, 4, 60.837, 0.860, 0.9430.8370.07891, 0.742, 0.258
89, 10, 110.781, 0.927, 1.0340.7810.28101, 0.594, 0.406
98, 11, 100.781, 0.787, 0.8190.7810.02511, 0.776, 0.224
109, 8, 110.819, 0.927, 1.0440.8190.23061, 0.624, 0.376
119, 8, 100.787, 1.034, 1.0440.7870.36331, 0.507, 0.493
All twelve neighbourhoods (k = 4). Every neighbour of every point lies in its own group, so the graph has 18 edges and none between groups.

Notice point 9: its three neighbours are almost equidistant (0.781, 0.787, 0.819), so a tiny σ9=0.0251\sigma_9=0.0251 is needed to bring the total down to 2. Point 11's neighbours are spread out, so it gets a large σ11=0.3633\sigma_{11}=0.3633. Each point's ruler adapts to its surroundings.

Laying the graph out in 2-D (min_dist = 0.1, so a = 1.5769, b = 0.8951)

  1. 1Initialise. Place the 12 points uniformly at random in [−5,5]2[-5,5]^2 (seeded). Points 0 and 2 start at (−4.883,−4.380)(-4.883,-4.380) and (0.214,−0.945)(0.214,-0.945), a distance d=6.147d=6.147 apart, so q02=1/(1+1.5769⋅6.1471.790)=0.024q_{02}=1/(1+1.5769\cdot6.147^{1.790})=0.024 — far below w02=0.747w_{02}=0.747.
  2. 2One force. For pair (0, 2) the attractive coefficient is 2ab w d2(b−1)1+ad2b=0.0345\tfrac{2ab\,w\,d^{2(b-1)}}{1+a d^{2b}}=0.0345 and the repulsive one is 2b(1−w)(ε+d2)(1+ad2b)=0.0003\tfrac{2b(1-w)}{(\varepsilon+d^2)(1+a d^{2b})}=0.0003. The net 0.03430.0343 times y0−y2=(−5.097,−3.435)y_0-y_2=(-5.097,-3.435) gives the gradient (−0.175,−0.118)(-0.175,-0.118): the step moves point 0 toward point 2.
  3. 3A force with no edge. Points 0 and 8 have w=0w=0 and start 5.505.50 apart. They only feel the repulsive coefficient, 0.00170.0017, which pushes them apart.
  4. 4Iterate. Sum these forces over all 66 pairs, step with α=1−e/200\alpha=1-e/200, and repeat for 200 epochs. The loss falls from 53.27 to 6.38.
  5. 5Result. The groups collapse into three tight clumps with centroids A (5.10,−3.38)(5.10,-3.38), B (−3.07,−2.80)(-3.07,-2.80) and C (−5.09,5.46)(-5.09,5.46). Points 0 and 2 end up 0.448 apart, so q02=0.727≈w02=0.747q_{02}=0.727\approx w_{02}=0.747.
  6. 6A new point x∗=(3.3, 0.5, 0.7)x^*=(3.3,\,0.5,\,0.7). Its neighbours are 4, 5 and 6 (distances 0.374, 0.490, 0.574), giving ρ=0.374\rho=0.374, σ=0.2222\sigma=0.2222 and memberships 1, 0.594, 0.4061,\,0.594,\,0.406. Its starting position is the membership-weighted mean of y4,y5,y6y_4,y_5,y_6, which is (−3.082,−2.862)(-3.082,-2.862), right inside group B. A few more epochs with the training points held fixed refine it.

The three clumps are cleanly separated (trustworthiness 1.0), but look at the gaps between them. A–B is 8.19 and B–C is 8.51, nearly equal, while in the input B–C is 1.8× A–B. With k=4k=4 the graph has no edges between groups, so only repulsion acts between them. Their placement is fixed by the random start, not by the data.

input (3-D) · fuzzy graph, k = 42-D layout · epoch 200/2001.000.550.45ABCcross-entropy over epochs · now 6.3853.27
n_neighborsmin_dist
point 0 (A) · neighbours 1, 2, 3 · ρ = 0.640 · σ = 0.2106 · v = 1.000 + 0.545 + 0.455 = 2.000 = log₂4
graph: 18 edges, 0 between groups · a = 1.5769, b = 0.8951
centroid gaps A–B / B–C / A–C · layout 8.19 / 8.51 / 13.49 · input 3.15 / 5.56 / 6.04
click a point to see its neighbours, ρ, σ and memberships · changing a setting replays the optimisation
fig.UMAP from scratch on the 12-point example. Left: the 3-D input and its fuzzy graph (line width = w; dashed red = edges between groups). Click a point to see its neighbours, ρ, σ and memberships v (point 0: ρ = 0.640, σ = 0.2106, v = 1 + 0.545 + 0.455 = log₂4). Right: the 2-D layout; press play or scrub through the 200 epochs and watch the loss curve. With n_neighbors = 4 there are 0 edges between groups, and the final centroid gaps are 8.19 / 8.51 / 13.49 against 3.15 / 5.56 / 6.04 in the input. Switch to n_neighbors = 8: 32 bridge edges appear and the gaps become 2.30 / 5.47 / 7.74, the input's ordering. Raise min_dist to see each clump loosen.

The algorithm, step by step

UMAP(X, k, min_dist, d)

  1. 1Neighbours. Find each point's k−1k-1 approximate nearest neighbours with NN-descent: start from random-projection-tree candidates, then repeatedly ask "are my neighbours' neighbours closer?".
  2. 2Calibrate. For each point set ρi\rho_i to its nearest-neighbour distance and binary-search σi\sigma_i so that ∑je−(dij−ρi)/σi=log⁡2k\sum_j e^{-(d_{ij}-\rho_i)/\sigma_i}=\log_2 k.
  3. 3Graph. Directed memberships vj∣iv_{j|i}, then fuzzy union wij=v+v⊤−v∘v⊤w_{ij}=v+v^\top-v\circ v^\top, a sparse symmetric matrix with about nknk nonzeros.
  4. 4Curve. Fit a,ba,b so that 1/(1+ad2b)1/(1+a d^{2b}) matches the min_dist target curve.
  5. 5Initialise YY with the leading eigenvectors of the graph's normalised Laplacian (spectral embedding), rescaled, plus a little noise; random init is the fallback.
  6. 6Optimise. For EE epochs (E=500E=500 for small data, 200 for large): for each edge, with frequency ∝wij\propto w_{ij}, pull yiy_i and yjy_j together; for each pull, push yiy_i away from 5 random points. Clip each update to ±4\pm4 and decay the learning rate linearly.
  7. 7Transform new data (optional): neighbours in the training set → memberships → weighted-mean start → a few epochs with the training embedding frozen.

Complexity

kNN graph
NN-descent is about O(n1.14)O(n^{1.14}) distance evaluations in practice; exact search would be O(n2D)O(n^2 D)
Calibration
O(nk)O(nk) times about 64 binary-search iterations
Spectral init
a sparse eigen-solve on the n×nn\times n graph Laplacian, roughly linear in nknk
Optimisation
O(E⋅nk⋅(1+negative_sample_rate))O(E\cdot nk\cdot(1+\text{negative\_sample\_rate})), linear in nn; t-SNE with Barnes–Hut is O(nlog⁡n)O(n\log n) per iteration
Memory
O(nk)O(nk) for the sparse graph, plus O(nd)O(nd) for the embedding

Hyperparameters and tuning

What each knob does

n_neighbors (15)
Sets the target log⁡2k\log_2 k and which edges exist. Small kk (5–10) builds a graph of tight local patches that may fall into disconnected pieces. Large kk (50–200) adds weak long-range bridges that pull the global layout into shape but blur fine structure.
min_dist (0.1)
Changes a,ba,b. Near 0, qq keeps rising as points get closer, so neighbours pile up into dense clumps, which helps clustering. At 0.5–1, q≈1q\approx1 already at moderate distances, so points spread out evenly, which helps when you want to see the structure inside a cluster.
spread (1.0)
Scale of the target curve; min_dist must be ≤ spread. Rarely changed.
n_components (2)
Output dimension. Unlike t-SNE, UMAP stays cheap at 10–50 dimensions, which is useful as preprocessing for HDBSCAN.
metric
Any distance: euclidean, cosine (text and embeddings), manhattan, hamming/jaccard (binary data), or a custom numba function.
n_epochs, learning_rate
More epochs give a more converged layout. The default learning rate of 1.0 is rarely changed.
negative_sample_rate (5)
Number of repulsive samples per attractive one. Higher values give more separation and slower runs.
init
'spectral' (default), 'pca', or 'random'. Spectral init is the main source of UMAP's global structure.
set_op_mix_ratio (1.0)
Interpolates between fuzzy union (1) and fuzzy intersection v v⊤v\,v^\top (0). Intersection keeps only edges that both endpoints agree on.
densmap
Adds a term that preserves local density, so sparse clusters look sparse instead of being equalised.
n_neighborsEdgesEdges between groupsGap A–BGap B–CGap A–CFinal loss
31507.677.6615.008.00
41808.198.5113.496.38
529118.748.9312.974.30
638206.107.8013.903.92
850322.305.477.7410.36
Effect of n_neighbors on the worked example (min_dist = 0.1, same seeded start, from-scratch code). Gaps are distances between group centroids; input: A–B 3.15, B–C 5.56, A–C 6.04.

At k=5k=5 the 11 bridge edges are almost weightless (the largest is 0.015), so the layout barely changes. At k=8k=8 every A point has edges to every B point (weights up to 0.22), and the embedding finally reproduces the input's ordering A–B < B–C < A–C. The loss is not comparable across kk: a graph with more weak edges simply has more terms. On the same example with k=4k=4, raising min_dist from 0 to 0.1, 0.5 and 1.0 grows the mean within-group distance from 0.198 to 0.265, 0.565 and 0.980.

In code

python
1import numpy as np
2
3X = np.array([[0.0, 0.0, 0.0], [0.6, 0.2, 0.1], [0.1, 0.7, 0.3], [0.5, 0.6, -0.2], # A
4 [3.0, 0.4, 0.5], [3.5, 0.1, 0.9], [3.2, 0.9, 1.1], [3.8, 0.7, 0.4], # B
5 [1.5, 4.5, 3.5], [2.1, 4.9, 3.8], [1.4, 5.2, 4.1], [2.0, 4.4, 4.4]]) # C
6
7def fuzzy_graph(X, k):
8 """k counts the point itself (umap-learn convention): keep k-1 neighbours."""
9 n = len(X)
10 D = np.sqrt(((X[:, None] - X[None]) ** 2).sum(-1))
11 V = np.zeros((n, n)); rho = np.zeros(n); sigma = np.zeros(n)
12 for i in range(n):
13 nb = [j for j in np.argsort(D[i], kind="stable") if j != i][: k - 1]
14 d = D[i, nb]
15 rho[i] = d.min() # distance to the nearest neighbour
16 lo, hi, s = 0.0, np.inf, 1.0 # binary search: sum of memberships = log2 k
17 for _ in range(64):
18 total = np.exp(-np.maximum(0, d - rho[i]) / s).sum()
19 if abs(total - np.log2(k)) < 1e-5:
20 break
21 if total > np.log2(k):
22 hi = s; s = (lo + hi) / 2
23 else:
24 lo = s; s = s * 2 if hi == np.inf else (lo + hi) / 2
25 sigma[i] = max(s, 1e-3 * D[i][D[i] > 0].mean())
26 V[i, nb] = np.exp(-np.maximum(0, d - rho[i]) / sigma[i])
27 W = V + V.T - V * V.T # fuzzy union (probabilistic OR)
28 return W, rho, sigma, V
29
30def mulberry32(seed): # same seeded generator as the figure
31 s = seed
32 def r():
33 nonlocal s
34 s = (s + 0x6D2B79F5) & 0xFFFFFFFF
35 t = ((s ^ (s >> 15)) * (1 | s)) & 0xFFFFFFFF
36 t = (t + (((t ^ (t >> 7)) * (61 | t)) & 0xFFFFFFFF)) & 0xFFFFFFFF ^ t
37 return ((t ^ (t >> 14)) & 0xFFFFFFFF) / 2**32
38 return r
39
40def layout(W, a, b, epochs=200, seed=7):
41 n = len(W); r = mulberry32(seed)
42 Y = np.array([[r() * 10 - 5, r() * 10 - 5] for _ in range(n)])
43 iu, ju = np.triu_indices(n, 1)
44 w = W[iu, ju]
45 for e in range(epochs):
46 diff = Y[iu] - Y[ju]
47 s = (diff ** 2).sum(1) # squared low-dim distances
48 att = 2 * a * b * w * s ** (b - 1) / (1 + a * s ** b)
49 rep = 2 * b * (1 - w) / ((0.001 + s) * (1 + a * s ** b))
50 g = np.clip((att - rep)[:, None] * diff, -4, 4)
51 G = np.zeros_like(Y)
52 np.add.at(G, iu, g); np.add.at(G, ju, -g)
53 q = np.clip(1 / (1 + a * s ** b), 1e-12, 1 - 1e-12)
54 loss = -(w * np.log(q) + (1 - w) * np.log(1 - q)).sum()
55 Y = np.round(Y - (1 - e / epochs) * G, 4) # linearly decaying step; rounding = bit-reproducible
56 return Y, loss
57
58W, rho, sigma, V = fuzzy_graph(X, k=4)
59print("rho_0 = %.3f sigma_0 = %.4f" % (rho[0], sigma[0]))
60print("v(.|0) =", V[0, 1:4].round(3), " w_02 = %.3f" % W[0, 2])
61print("edges:", int((W > 0).sum() // 2))
62Y, loss = layout(W, a=1.5769, b=0.8951) # min_dist = 0.1
63print("final loss %.2f" % loss)
64for g in range(3):
65 print("group", "ABC"[g], "centroid", Y[4 * g: 4 * g + 4].mean(0).round(2))
From scratch: fuzzy graph + full-batch gradient descent on the exact cross-entropy (no negative sampling, so it is only for small n). Prints ρ₀ = 0.640, σ₀ = 0.2106, v = [1, 0.545, 0.455], w₀₂ = 0.747, 18 edges, final loss 6.38 and centroids A (5.10, −3.38), B (−3.07, −2.80), C (−5.09, 5.46), the same numbers as the figure.
python
1import numpy as np, umap
2from umap.umap_ import fuzzy_simplicial_set, find_ab_params
3from sklearn.manifold import trustworthiness
4
5# X: the 12 x 3 array from the table above
6W, sigma, rho = fuzzy_simplicial_set(X, n_neighbors=4, random_state=0, metric="euclidean")
7W = W.toarray()
8print(rho[:4].round(3), sigma[0].round(4)) # [0.64 0.51 0.648 0.51] 0.2106
9print(W[0, 1:4].round(3), int((W > 0).sum() // 2)) # [1. 0.747 0.657] 18
10print(np.round(find_ab_params(1.0, 0.1), 4)) # [1.5769 0.8951]
11
12reducer = umap.UMAP(n_neighbors=4, min_dist=0.1, random_state=42)
13Y = reducer.fit_transform(X)
14print(trustworthiness(X, Y, n_neighbors=3)) # 1.0
15for g in range(3):
16 print("ABC"[g], Y[4*g:4*g+4].mean(0).round(2)) # A [-9.34 -15.08] B [-14.77 5.14] C [17.54 9.39]
17print(reducer.transform([[3.3, 0.5, 0.7]]).round(2)) # [[-15.82 5.54]] -> next to B
umap-learn 0.5 on the same data. Its graph is identical to the hand computation; its layout uses spectral init and negative-sampling SGD, so the coordinates differ, but it gives the same three clumps, and the new point lands in group B.

Use when

  • +You want a 2-D/3-D map of large data (10⁵–10⁷ points): UMAP is typically several times faster than t-SNE.
  • +You need to embed new points later (transform) or reuse the embedding as features.
  • +You want 10–50 output dimensions as preprocessing for density-based clustering (HDBSCAN).
  • +You have non-Euclidean data: cosine for text embeddings, Jaccard for sets, a custom metric.

Avoid when

  • −You need distances, densities or cluster sizes in the picture to mean something quantitatively.
  • −The data are small or roughly linear: PCA is exact, deterministic and interpretable.
  • −You need a reproducible, invertible or explainable mapping (axes have no meaning; inverse_transform is approximate).
  • −You might over-interpret: UMAP can show clusters in pure noise when n_neighbors is small.

Where it's used

Single-cell genomics

Standard 2-D maps of cell types in Scanpy and Seurat, built from the PCA of gene expression and the same kNN graph used for Leiden clustering.

Embedding inspection

Visualising sentence, image or LLM embeddings with the cosine metric to spot topics, duplicates and label noise.

Clustering pipelines

UMAP to about 10 dimensions followed by HDBSCAN, e.g. BERTopic's topic model.

Data and model debugging

Colouring a UMAP of a network's penultimate-layer features by label or error to find confused classes and outliers.

Check yourself

A point's nearest neighbour is 2.5 away. Before symmetrisation, what membership v does it assign to that neighbour?

Check yourself

With n_neighbors = 4, a point's three neighbours are at distances 1.0, 1.5 and 2.0. Its memberships are…

Check yourself

Point i says v₍j|i₎ = 0.5 and point j says v₍i|j₎ = 0.4. The symmetric edge weight w_ij is…

Check yourself

In the worked example, which change makes the embedding reproduce the input's ordering of group distances (A–B < B–C < A–C)?

Remember

  • ✓UMAP builds a fuzzy kNN graph: vj∣i=e−(dij−ρi)/σiv_{j|i}=e^{-(d_{ij}-\rho_i)/\sigma_i} with σi\sigma_i set so memberships sum to log⁡2k\log_2 k, then symmetrises by fuzzy union v+v′−vv′v+v'-vv'.
  • ✓The embedding uses q=1/(1+ad2b)q=1/(1+a d^{2b}), where a,ba,b come from min_dist. The layout minimises the cross-entropy between ww and qq: attraction along edges, repulsion between everything else.
  • ✓SGD with edge sampling and negative sampling makes each epoch linear in n, which is why UMAP scales further than t-SNE and supports transform and any output dimension.
  • ✓n_neighbors trades local detail for global structure (it decides which bridges exist); min_dist controls how tightly points pack.
  • ✓Read neighbourhoods off a UMAP plot, not distances, densities or cluster sizes, and check any cluster you find across settings and seeds.
← back to ML Algorithms roadmap