UMAP (Uniform Manifold Approximation & Projection)

C sits at the elbow of the path. Even though A and E are only two hops away along the bend, C's actual nearest neighbors are always B and D — never A or E — no matter whether you ask for its 1 or 2 closest points. The neighbor graph tracks the path, not a straight ruler laid across the page.

UMAP builds a fuzzy neighbor graph: instead of a hard yes/no "is this a neighbor," every pair of points gets a membership strength between 0 and 1.

• $\rho_i$ — point $i$'s local radius: the distance to its single closest neighbor.
• $d(x_i, x_j)$ — the distance between points $i$ and $j$.
• $\sigma$ — a bandwidth controlling how fast membership decays with distance (fixed here for exact arithmetic; real UMAP solves for it per point).
• $v_{j \mid i}$ — the directed membership of $j$ in $i$'s neighborhood: $1$ at the local radius, decaying beyond it, and exactly $0$ once $j$ isn't among $i$'s $k$ nearest neighbors at all.

1. Every point gets a full-strength connection to its nearest neighbor

   Subtracting $\rho_i$ shifts the exponential so that $j$'s membership is exactly $1$ right at $i$'s local radius — regardless of whether $i$ lives in a dense or sparse region. That's what makes this "uniform": density doesn't change how strongly a point connects to its own closest neighbor.

2. Membership is directed, and can disagree in each direction

   $v_{j\mid i}$ answers "how much does $i$ consider $j$ a neighbor" — which need not match $v_{i \mid j}$, the reverse question. C might see B as an obvious neighbor while B has closer points of its own to worry about.

3. Symmetrize with a fuzzy-set union, not an average

   $v_{ij} = v_{j\mid i} + v_{i\mid j} - v_{j\mid i}\, v_{i\mid j}$ An edge counts as long as either direction sees it — the same logic as a union of probabilities of independent events. A plain average would let one side's "no" cancel out the other side's "yes."

Starting from a random-looking jumble, the same attract-along-edges, repel-everywhere-else rule that drives the real optimizer pulls A and B — connected at full strength — together almost immediately, while A and D — never neighbors — drift apart. Step forward and watch the gap between "A to B" and "A to D" open up.

Point A's true nearest neighbor is B, one unit away; C sits two units from A, and A doesn't make C's own shortlist:

1. A's local radius

   $\rho_A = d(A, B) = 1$ — A's nearest neighbor is exactly one unit away, so full-strength membership starts there.

2. A's view of C

   $d(A, C) = 2$, so $v_{C \mid A} = \exp(-(2 - 1)/1) = \exp(-1) \approx 0.368$. A genuinely considers C a neighbor — just a weaker one than B.

3. C's view of A — nothing at all

   C's two nearest neighbors are B and D, not A — so $v_{A \mid C} = 0$. From C's side, A isn't close enough to register.

4. The symmetrized edge survives on A's vote alone

   $v_{AC} = 0.368 + 0 - (0.368)(0) = 0.368$. The fuzzy union means A's "yes" is enough to create a real, if partial, edge — even though C's own answer was "no."