Building UMAP’s Nearest-Neighbor Graph

From Cell Distances to Directed Edges

UMAP’s graph construction begins with cells represented as points in a space where a distance has been chosen. The representation might be a set of selected principal-component scores rather than the original gene counts. The first graph-building task is local: for each cell, identify a specified number of nearby cells. The second is to convert those distances into edge weights that adapt to how tightly or loosely the neighborhood is spaced.

These weights are directed because the neighborhood and the distance scale are calculated separately for each cell. Cell \(j\) can be among cell \(i\)’s nearest neighbors without cell \(i\) being among cell \(j\)’s nearest neighbors. Even when each cell selects the other, the two directed weights can differ. This tutorial stops at those directed weights; combining them into a fuzzy graph is a distinct subsequent step.

The calculation assumes that the chosen representation and distance are meaningful for the neighborhoods of interest, that distances are nonnegative, and that each cell has at least \(k\) other cells available. It does not require normally distributed cell coordinates. However, the resulting graph depends on the representation, distance metric, value of \(k\), and handling of ties. It is a description of local geometry in the chosen space, not evidence by itself of biological interaction or causation.

Nearest Neighbors, Local Offsets, and Local Scales

For each cell \(i\), UMAP identifies its \(k\) nearest other cells and their distances. The cell itself is excluded. Write the ordered neighbor distances as \(d_{i(1)}\le d_{i(2)}\le\cdots\le d_{i(k)}\). In the simplest setting, the local offset \(\rho_i\) is the distance to the nearest neighbor, \(d_{i(1)}\). More generally, implementations can set \(\rho_i\) using a local-connectivity choice that interpolates among the nearest-neighbor distances. That adjustment controls how many very close neighbors receive full weight; it does not change the basic weighting formula.

The local scale \(\sigma_i>0\) controls how quickly weights fall as a neighbor’s distance exceeds \(\rho_i\). Given \(\rho_i\) and \(\sigma_i\), the directed edge weight is

Distances at or below \(\rho_i\) therefore receive weight 1. Beyond that offset, weight decreases exponentially. A small \(\sigma_i\) makes it decrease quickly; a large \(\sigma_i\) makes it decrease more gradually. The scale is local: cells in crowded and sparse regions can have different values of \(\sigma_i\), even though the same weighting rule applies to both.

UMAP selects \(\sigma_i\) by approximately matching a target sum of the weights over cell \(i\)’s nearest neighbors:

where \(N_k(i)\) is the set of \(k\) nearest neighbors of \(i\). The target \(\log_2(k)\) is not a claim that exactly \(\log_2(k)\) neighbors have nonzero weights: all selected neighbors generally have positive weights. Rather, it sets the approximate total membership weight and helps calibrate neighborhoods locally. Implementations find a suitable scale by a bounded numerical search, typically binary search, and may apply small-scale safeguards for numerical stability.

Worked Calculations

Why the Scale Search Works

For fixed \(\rho_i\), define the target-sum function as the sum of the \(k\) edge weights at a proposed scale \(\sigma_i\). For any neighbor with \(d_{ij}\le\rho_i\), its contribution is constantly 1. For a neighbor with \(d_{ij}>\rho_i\), its contribution is \(\exp(-(d_{ij}-\rho_i)/\sigma_i)\). Its derivative with respect to \(\sigma_i\) is

Consequently, the target sum is nondecreasing in the scale and strictly increasing whenever at least one selected neighbor lies beyond the offset. This gives the search a reliable direction: if a trial sum is too small, increase the scale; if it is too large, decrease it. As the scale approaches zero, weights beyond the offset approach zero, while as the scale grows, those weights approach 1. In ordinary cases these limits bracket the intended target. Tied distances, a large number of distances at or below the offset, and numerical bounds can complicate exact matching, which is one reason implementations use approximate searches and safeguards.

The basic derivation also explains the role of the offset. Subtracting \(\rho_i\) makes the closest neighborhood distances a reference point, so weights are driven by distance beyond that local reference rather than by the absolute distance from the cell. The scale then adapts the rate of decay to the local spacing.

Diagnostics, Alternatives, and Limitations

Before interpreting a constructed graph, check the inputs and the resulting neighborhoods. Confirm which cell representation and distance metric were used; inspect whether nearest-neighbor distances look plausible; and check for duplicate points, ties, missing or non-finite distances, and cells whose neighbors are unexpectedly dominated by technical or batch structure. A scale search that repeatedly reaches a numerical bound, or a cell with many tied distances, deserves attention. These checks do not establish that a chosen representation is biologically appropriate, but they can reveal when the graph is not behaving as intended.

The local weighting has a practical advantage over a hard \(k\)-nearest-neighbor graph: a hard graph gives every selected edge the same weight and every unselected edge weight zero, whereas UMAP’s directed weights distinguish closer from farther selected neighbors. It also differs from a single fixed-bandwidth Gaussian weighting of all distances. A fixed bandwidth applies a common decay scale; UMAP estimates a separate scale for each cell, adapting to local density. This adaptation is useful when neighborhood spacing varies, but it also means edge weights are relative to local scales and are not direct, globally comparable measurements of physical distance.

The directed weights are also distinct from the conditional similarities used in t-SNE. Both methods encode local relationships, but UMAP’s construction uses a local offset and a scale chosen to match a target sum, rather than t-SNE’s perplexity-calibrated probability distribution. These are different constructions, so one method’s parameters or edge weights should not be interpreted as though they were the other’s.

Several limitations remain. Nearest-neighbor search can be approximate in large data sets, so different search settings may change neighbor identities. Results are sensitive to the input representation and metric; an unsuitable distance can make even a correctly computed graph scientifically unhelpful. Ties and duplicate cells may yield several equal distances, and local scale safeguards can mean the target sum is not matched exactly. Finally, directed weights alone do not establish the final graph used by UMAP’s embedding procedure. Their later combination is a separate operation.