# UMAP

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

Source: https://www.mlfoundry.in/learn/umap  
Section: ML Algorithms › Unsupervised · Dimensionality Reduction  
Level: core · 18 min read · updated 2026-10-07

**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* $w_{ij}\in[0,1]$, then finds low-dimensional coordinates $y_i$ whose own graph of similarities $q_{ij}$ matches $w_{ij}$ as closely as possible under a **fuzzy cross-entropy** loss.

- **Task:** Unsupervised dimensionality reduction — mostly 2-D/3-D visualisation, also 5–50-D features for clustering
- **Input → output:** $n$ points in $\mathbb{R}^D$ (any metric) → $n$ points $y_i\in\mathbb{R}^d$, usually $d=2$
- **Learns:** a coordinate $y_i$ per training point (non-parametric); new points are placed by a short extra optimisation
- **Training:** approximate kNN by NN-descent (empirically about $O(n^{1.14})$) + SGD over the graph edges, $O(E\cdot n k)$ for $E$ epochs
- **Prediction:** `transform`: find the new point's $k$ 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(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 $k$ 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 $i$ to its nearest neighbour. Subtracting it guarantees every point is fully connected ($w=1$) to at least one neighbour — the *local connectivity* assumption
- **σᵢ (sigma):** point $i$'s local length scale, found by binary search so its memberships add up to $\log_2 k$
- **Membership vⱼ|ᵢ:** how strongly $i$ thinks $j$ is its neighbour: $1$ for the nearest, decaying exponentially beyond it, $0$ for non-neighbours
- **Fuzzy union:** symmetrisation by probabilistic OR, $w_{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+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 $i$ take its $k-1$ nearest neighbours $j_1,\dots,j_{k-1}$ at distances $d(x_i,x_j)$. Set $\rho_i$ to the smallest of them and choose $\sigma_i$ so that

$$
\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(x_i,x_j)$: input-space distance (Euclidean here; any metric works)
- $\rho_i$: distance from $i$ to its nearest neighbour
- $\sigma_i$: local length scale of point i, solved by binary search (the left side increases with σ)
- $\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_2 k$ instead of $\log_2(\text{perplexity})$ bits. Because the nearest neighbour always contributes $e^0=1$, the remaining $k-2$ neighbours share the remaining $\log_2 k-1$.

$$
v_{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}
$$

- $v_{j|i}$: directed membership of $j$ in $i$'s neighbourhood (0 if $j$ is not among $i$'s neighbours)
- $w_{ij}$: symmetric edge weight of the input graph: the fuzzy union (probabilistic OR) of the two directions

The union is $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 $d_{ij}=\lVert y_i-y_j\rVert$:

$$
q_{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}
$$

- $q_{ij}$: similarity of points i and j in the embedding, in (0, 1]
- $a,\,b$: found once by least-squares fitting $q$ to the target curve $\Psi$ (with \texttt{spread} = 1)
- $\text{min\_dist}$: distance below which points count as fully similar

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

The fitted constants (umap-learn find_ab_params, spread = 1) and the resulting similarity q at four embedding distances.

| min_dist | a | b | q(0.1) | q(0.5) | q(1) | q(2) |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | 1.9328 | 0.7905 | 0.952 | 0.608 | 0.341 | 0.147 |
| **0.1** (default) | **1.5769** | **0.8951** | 0.975 | 0.687 | 0.388 | 0.155 |
| 0.5 | 0.5830 | 1.3342 | 0.999 | 0.916 | 0.632 | 0.212 |
| 1.0 | 0.1150 | 1.9292 | 1.000 | 0.992 | 0.897 | 0.375 |

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

$$
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]
$$

- $Y$: the embedding coordinates $y_1,\dots,y_n$ (the only variables)
- $w_{ij}\log\tfrac{w}{q}$: large when an input edge is strong but the embedded points are far apart
- $(1-w)\log\tfrac{1-w}{1-q}$: large when two unconnected points sit close together in the embedding

The $w\log w$ terms do not depend on $Y$, so only $-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 $n^2$ pairs.

**Deriving the gradient.** Write $s=d_{ij}^2$, so $q=(1+a s^b)^{-1}$. Then $-\log q=\log(1+a s^b)$ has derivative $\dfrac{ab\,s^{b-1}}{1+a s^b}$ with respect to $s$, and $-\log(1-q)=\log(1+a s^b)-\log a-b\log s$ has derivative $\dfrac{ab\,s^{b-1}}{1+a s^b}-\dfrac{b}{s}=-\dfrac{b}{s(1+a s^b)}$. Multiplying by $\partial s/\partial y_i=2(y_i-y_j)$:

$$
\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)
$$

- $(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 $y_i\leftarrow y_i-\alpha\,\partial C/\partial y_i$, with every per-pair term clipped to $[-4,4]$ and the step size $\alpha$ decaying linearly to 0.

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

> **Why UMAP keeps more global structure than t-SNE:** Two reasons, neither of them magic. (1) The default **spectral initialisation** places points using the eigenvectors of the graph Laplacian, which already encode how components connect; t-SNE traditionally started from random noise (with PCA initialisation t-SNE also improves a lot). (2) Edge weights are **not normalised per point**, so a bridge of weak edges between two groups still pulls them toward each other. If the graph has *no* edges between two groups, nothing ties them together, and their distance in the picture is arbitrary.

## 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=4$, so each point keeps 3 neighbours and its memberships must sum to $\log_2 4=2$.

The dataset. Highlighted: point 0, whose neighbourhood we compute by hand.

| Point | Group | x₁ | x₂ | x₃ |
| --- | --- | --- | --- | --- |
| 0 | A | 0.0 | 0.0 | 0.0 |
| 1 | A | 0.6 | 0.2 | 0.1 |
| 2 | A | 0.1 | 0.7 | 0.3 |
| 3 | A | 0.5 | 0.6 | −0.2 |
| 4 | B | 3.0 | 0.4 | 0.5 |
| 5 | B | 3.5 | 0.1 | 0.9 |
| 6 | B | 3.2 | 0.9 | 1.1 |
| 7 | B | 3.8 | 0.7 | 0.4 |
| 8 | C | 1.5 | 4.5 | 3.5 |
| 9 | C | 2.1 | 4.9 | 3.8 |
| 10 | C | 1.4 | 5.2 | 4.1 |
| 11 | C | 2.0 | 4.4 | 4.4 |

**Point 0's fuzzy neighbourhood**

1. **Neighbours.** Distances from point 0: to 1 is $\sqrt{0.41}=0.640$, to 2 is $\sqrt{0.59}=0.768$, to 3 is $\sqrt{0.65}=0.806$; every B or C point is at least 3.07 away. The three nearest are 1, 2, 3.
2. **ρ.** $\rho_0=0.640$, so the shifted distances are $0,\;0.128,\;0.166$.
3. **σ.** Solve $1+e^{-0.128/\sigma}+e^{-0.166/\sigma}=2$. Binary search gives $\sigma_0=0.2106$.
4. **Memberships.** $v_{1|0}=1$, $v_{2|0}=e^{-0.128/0.2106}=0.545$, $v_{3|0}=e^{-0.166/0.2106}=0.455$. They sum to $2.000=\log_2 4$, as required.
5. **Union with the other direction.** Point 2 computes its own view, $v_{0|2}=0.444$, so $w_{02}=0.545+0.444-0.545\cdot0.444=0.747$. Likewise $w_{03}=0.455+0.371-0.455\cdot0.371=0.657$, and $w_{01}=1$ because $v_{1|0}=1$.

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.

| Point | Neighbours | Distances | ρ | σ | Memberships v |
| --- | --- | --- | --- | --- | --- |
| 0 | 1, 2, 3 | 0.640, 0.768, 0.806 | 0.640 | 0.2106 | 1, 0.545, 0.455 |
| 1 | 3, 0, 2 | 0.510, 0.640, 0.735 | 0.510 | 0.2499 | 1, 0.593, 0.407 |
| 2 | 3, 1, 0 | 0.648, 0.735, 0.768 | 0.648 | 0.1478 | 1, 0.556, 0.444 |
| 3 | 1, 2, 0 | 0.510, 0.648, 0.806 | 0.510 | 0.2985 | 1, 0.629, 0.371 |
| 4 | 5, 6, 7 | 0.707, 0.806, 0.860 | 0.707 | 0.1790 | 1, 0.575, 0.425 |
| 5 | 4, 7, 6 | 0.707, 0.837, 0.877 | 0.707 | 0.2150 | 1, 0.547, 0.453 |
| 6 | 4, 5, 7 | 0.806, 0.877, 0.943 | 0.806 | 0.1450 | 1, 0.612, 0.388 |
| 7 | 5, 4, 6 | 0.837, 0.860, 0.943 | 0.837 | 0.0789 | 1, 0.742, 0.258 |
| 8 | 9, 10, 11 | 0.781, 0.927, 1.034 | 0.781 | 0.2810 | 1, 0.594, 0.406 |
| 9 | 8, 11, 10 | 0.781, 0.787, 0.819 | 0.781 | 0.0251 | 1, 0.776, 0.224 |
| 10 | 9, 8, 11 | 0.819, 0.927, 1.044 | 0.819 | 0.2306 | 1, 0.624, 0.376 |
| 11 | 9, 8, 10 | 0.787, 1.034, 1.044 | 0.787 | 0.3633 | 1, 0.507, 0.493 |

Notice point 9: its three neighbours are almost equidistant (0.781, 0.787, 0.819), so a tiny $\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 $\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. **Initialise.** Place the 12 points uniformly at random in $[-5,5]^2$ (seeded). Points 0 and 2 start at $(-4.883,-4.380)$ and $(0.214,-0.945)$, a distance $d=6.147$ apart, so $q_{02}=1/(1+1.5769\cdot6.147^{1.790})=0.024$ — far below $w_{02}=0.747$.
2. **One force.** For pair (0, 2) the attractive coefficient is $\tfrac{2ab\,w\,d^{2(b-1)}}{1+a d^{2b}}=0.0345$ and the repulsive one is $\tfrac{2b(1-w)}{(\varepsilon+d^2)(1+a d^{2b})}=0.0003$. The net $0.0343$ times $y_0-y_2=(-5.097,-3.435)$ gives the gradient $(-0.175,-0.118)$: the step moves point 0 *toward* point 2.
3. **A force with no edge.** Points 0 and 8 have $w=0$ and start $5.50$ apart. They only feel the repulsive coefficient, $0.0017$, which pushes them apart.
4. **Iterate.** Sum these forces over all 66 pairs, step with $\alpha=1-e/200$, and repeat for 200 epochs. The loss falls from 53.27 to 6.38.
5. **Result.** The groups collapse into three tight clumps with centroids A $(5.10,-3.38)$, B $(-3.07,-2.80)$ and C $(-5.09,5.46)$. Points 0 and 2 end up 0.448 apart, so $q_{02}=0.727\approx w_{02}=0.747$.
6. **A new point** $x^*=(3.3,\,0.5,\,0.7)$. Its neighbours are 4, 5 and 6 (distances 0.374, 0.490, 0.574), giving $\rho=0.374$, $\sigma=0.2222$ and memberships $1,\,0.594,\,0.406$. Its starting position is the membership-weighted mean of $y_4,y_5,y_6$, which is $(-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=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.

> Figure: 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. **Neighbours.** Find each point's $k-1$ approximate nearest neighbours with NN-descent: start from random-projection-tree candidates, then repeatedly ask "are my neighbours' neighbours closer?".
2. **Calibrate.** For each point set $\rho_i$ to its nearest-neighbour distance and binary-search $\sigma_i$ so that $\sum_j e^{-(d_{ij}-\rho_i)/\sigma_i}=\log_2 k$.
3. **Graph.** Directed memberships $v_{j|i}$, then fuzzy union $w_{ij}=v+v^\top-v\circ v^\top$, a sparse symmetric matrix with about $nk$ nonzeros.
4. **Curve.** Fit $a,b$ so that $1/(1+a d^{2b})$ matches the `min_dist` target curve.
5. **Initialise** $Y$ with the leading eigenvectors of the graph's normalised Laplacian (spectral embedding), rescaled, plus a little noise; random init is the fallback.
6. **Optimise.** For $E$ epochs ($E=500$ for small data, 200 for large): for each edge, with frequency $\propto w_{ij}$, pull $y_i$ and $y_j$ together; for each pull, push $y_i$ away from 5 random points. Clip each update to $\pm4$ and decay the learning rate linearly.
7. **Transform 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(n^{1.14})$ distance evaluations in practice; exact search would be $O(n^2 D)$
- **Calibration:** $O(nk)$ times about 64 binary-search iterations
- **Spectral init:** a sparse eigen-solve on the $n\times n$ graph Laplacian, roughly linear in $nk$
- **Optimisation:** $O(E\cdot nk\cdot(1+\text{negative\_sample\_rate}))$, linear in $n$; t-SNE with Barnes–Hut is $O(n\log n)$ per iteration
- **Memory:** $O(nk)$ for the sparse graph, plus $O(nd)$ for the embedding

## Hyperparameters and tuning

**What each knob does**

- **n_neighbors (15):** Sets the target $\log_2 k$ and *which* edges exist. Small $k$ (5–10) builds a graph of tight local patches that may fall into disconnected pieces. Large $k$ (50–200) adds weak long-range bridges that pull the global layout into shape but blur fine structure.
- **min_dist (0.1):** Changes $a,b$. Near 0, $q$ keeps rising as points get closer, so neighbours pile up into dense clumps, which helps clustering. At 0.5–1, $q\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^\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.

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.

| n_neighbors | Edges | Edges between groups | Gap A–B | Gap B–C | Gap A–C | Final loss |
| --- | --- | --- | --- | --- | --- | --- |
| 3 | 15 | 0 | 7.67 | 7.66 | 15.00 | 8.00 |
| 4 | 18 | 0 | 8.19 | 8.51 | 13.49 | 6.38 |
| 5 | 29 | 11 | 8.74 | 8.93 | 12.97 | 4.30 |
| 6 | 38 | 20 | 6.10 | 7.80 | 13.90 | 3.92 |
| **8** | **50** | **32** | **2.30** | **5.47** | **7.74** | 10.36 |

At $k=5$ the 11 bridge edges are almost weightless (the largest is 0.015), so the layout barely changes. At $k=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 $k$: a graph with more weak edges simply has more terms. On the same example with $k=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.

> **A practical recipe:** Standardise or otherwise make features comparable (or pick a suitable metric). For big, high-dimensional data, reduce to 50 dimensions with PCA first. Then try `n_neighbors` ∈ {5, 15, 50} × `min_dist` ∈ {0, 0.1, 0.5}. Fix `random_state` only when you need reproducibility (it disables parallelism), and check that any structure you see holds up across a few seeds.

## In code

```python
import numpy as np

X = 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
            [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
            [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

def fuzzy_graph(X, k):
  """k counts the point itself (umap-learn convention): keep k-1 neighbours."""
  n = len(X)
  D = np.sqrt(((X[:, None] - X[None]) ** 2).sum(-1))
  V = np.zeros((n, n)); rho = np.zeros(n); sigma = np.zeros(n)
  for i in range(n):
      nb = [j for j in np.argsort(D[i], kind="stable") if j != i][: k - 1]
      d = D[i, nb]
      rho[i] = d.min()                          # distance to the nearest neighbour
      lo, hi, s = 0.0, np.inf, 1.0              # binary search: sum of memberships = log2 k
      for _ in range(64):
          total = np.exp(-np.maximum(0, d - rho[i]) / s).sum()
          if abs(total - np.log2(k)) < 1e-5:
              break
          if total > np.log2(k):
              hi = s; s = (lo + hi) / 2
          else:
              lo = s; s = s * 2 if hi == np.inf else (lo + hi) / 2
      sigma[i] = max(s, 1e-3 * D[i][D[i] > 0].mean())
      V[i, nb] = np.exp(-np.maximum(0, d - rho[i]) / sigma[i])
  W = V + V.T - V * V.T                         # fuzzy union (probabilistic OR)
  return W, rho, sigma, V

def mulberry32(seed):                             # same seeded generator as the figure
  s = seed
  def r():
      nonlocal s
      s = (s + 0x6D2B79F5) & 0xFFFFFFFF
      t = ((s ^ (s >> 15)) * (1 | s)) & 0xFFFFFFFF
      t = (t + (((t ^ (t >> 7)) * (61 | t)) & 0xFFFFFFFF)) & 0xFFFFFFFF ^ t
      return ((t ^ (t >> 14)) & 0xFFFFFFFF) / 2**32
  return r

def layout(W, a, b, epochs=200, seed=7):
  n = len(W); r = mulberry32(seed)
  Y = np.array([[r() * 10 - 5, r() * 10 - 5] for _ in range(n)])
  iu, ju = np.triu_indices(n, 1)
  w = W[iu, ju]
  for e in range(epochs):
      diff = Y[iu] - Y[ju]
      s = (diff ** 2).sum(1)                    # squared low-dim distances
      att = 2 * a * b * w * s ** (b - 1) / (1 + a * s ** b)
      rep = 2 * b * (1 - w) / ((0.001 + s) * (1 + a * s ** b))
      g = np.clip((att - rep)[:, None] * diff, -4, 4)
      G = np.zeros_like(Y)
      np.add.at(G, iu, g); np.add.at(G, ju, -g)
      q = np.clip(1 / (1 + a * s ** b), 1e-12, 1 - 1e-12)
      loss = -(w * np.log(q) + (1 - w) * np.log(1 - q)).sum()
      Y = np.round(Y - (1 - e / epochs) * G, 4)  # linearly decaying step; rounding = bit-reproducible
  return Y, loss

W, rho, sigma, V = fuzzy_graph(X, k=4)
print("rho_0 = %.3f  sigma_0 = %.4f" % (rho[0], sigma[0]))
print("v(.|0) =", V[0, 1:4].round(3), " w_02 = %.3f" % W[0, 2])
print("edges:", int((W > 0).sum() // 2))
Y, loss = layout(W, a=1.5769, b=0.8951)          # min_dist = 0.1
print("final loss %.2f" % loss)
for g in range(3):
  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
import numpy as np, umap
from umap.umap_ import fuzzy_simplicial_set, find_ab_params
from sklearn.manifold import trustworthiness

# X: the 12 x 3 array from the table above
W, sigma, rho = fuzzy_simplicial_set(X, n_neighbors=4, random_state=0, metric="euclidean")
W = W.toarray()
print(rho[:4].round(3), sigma[0].round(4))       # [0.64 0.51 0.648 0.51] 0.2106
print(W[0, 1:4].round(3), int((W > 0).sum() // 2)) # [1. 0.747 0.657] 18
print(np.round(find_ab_params(1.0, 0.1), 4))      # [1.5769 0.8951]

reducer = umap.UMAP(n_neighbors=4, min_dist=0.1, random_state=42)
Y = reducer.fit_transform(X)
print(trustworthiness(X, Y, n_neighbors=3))       # 1.0
for g in range(3):
  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]
print(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.

> **Where the from-scratch version cuts corners:** It computes exact neighbours and the exact gradient over all pairs ($O(n^2)$ per epoch), and starts from a random layout. umap-learn instead uses NN-descent, edge sampling, 5 negative samples per edge and a spectral start. Those changes are what make UMAP fast, but they also mean its repulsion is a stochastic approximation of the $(1-w)$ term, not the exact one.

**Strengths**

- 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.

**Limitations**

- 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.

- **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.

> **Gaps and sizes between clusters are not distances:** In the worked example with `n_neighbors=4` the graph had no edges between groups, and the layout put A–B and B–C at almost the same distance (8.19 vs 8.51) even though B–C is 1.8× farther in the input. Cluster areas are also equalised, because every point gets the same total membership. Don't read density or between-cluster distance off a UMAP plot. Check them in the original space.

> **Small n_neighbors invents clusters:** With a tiny neighbourhood the graph breaks into many small pieces, and repulsion spreads them apart as if they were separate groups, even for a single Gaussian blob. Before believing a cluster, check that it survives larger `n_neighbors`, a few seeds and a different `min_dist`, and confirm it with a clustering algorithm run in the original space or a 10–50-D UMAP.

> **Feature scale decides the neighbours:** The kNN graph uses raw distances, so a feature measured in thousands dominates one measured in fractions. Standardise, or choose a metric that suits the data, before UMAP — exactly as for k-NN.

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

- A. 0
- B. 0.5
- C. 1
- D. It depends on σ

**Answer:** C. 1 — Distances are shifted by $\rho_i$ (the nearest-neighbour distance), so the nearest neighbour gets $e^{-0/\sigma}=1$ whatever $\sigma$ is. This is the local-connectivity guarantee: no point is left isolated.

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

- A. 1, 0.5, 0.25
- B. 1, 0.618, 0.382
- C. 0.333, 0.333, 0.333
- D. 1, 0.75, 0.5

**Answer:** B. 1, 0.618, 0.382 — $\rho=1$, so the shifted distances are 0, 0.5 and 1. With $x=e^{-0.5/\sigma}$ the constraint is $1+x+x^2=2$, so $x=0.618$ and $x^2=0.382$ (σ = 1.039). The memberships sum to $\log_2 4=2$.

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

- A. 0.2
- B. 0.45
- C. 0.7
- D. 0.9

**Answer:** C. 0.7 — Fuzzy union: $0.5+0.4-0.5\cdot0.4=0.7$, i.e. $1-(1-0.5)(1-0.4)$, the probability that at least one direction says "edge".

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

- A. min_dist from 0.1 to 1.0
- B. n_neighbors from 4 to 8
- C. More epochs
- D. n_components = 3

**Answer:** B. n_neighbors from 4 to 8 — With k = 4 there are no edges between groups, so nothing but random placement and repulsion sets their distances. With k = 8 there are 32 bridge edges, and the centroid gaps become 2.30 / 5.47 / 7.74, the same order as the input's 3.15 / 5.56 / 6.04.

**Key points**

- UMAP builds a fuzzy kNN graph: $v_{j|i}=e^{-(d_{ij}-\rho_i)/\sigma_i}$ with $\sigma_i$ set so memberships sum to $\log_2 k$, then symmetrises by fuzzy union $v+v'-vv'$.
- The embedding uses $q=1/(1+a d^{2b})$, where $a,b$ come from `min_dist`. The layout minimises the cross-entropy between $w$ and $q$: 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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
