Uniform manifold approximation and projection (UMAP) is a nonlinear dimensionality reduction algorithm that constructs a weighted graph of local similarities and computes low-dimensional coordinates for its vertices (McInnes et al. 2020). Its two stages are construction of local affinity weights and optimization of a layout. The weights are interpreted as membership strengths in a fuzzy set of graph edges.
For a nondegenerate formulation, let 
be distinct points in
a metric space with distance 
,
and let 
contain the indices of the 
closest other points to 
, where 
. Assume that each 
has a unique closest neighbor, and put 
. For 
, define the directed affinity
 |
(1)
|
where the local scale 
is chosen so that
 |
(2)
|
Set 
for 
, including 
. Under the stated assumptions, the sum increases continuously
from 1 to 
as 
increases from zero to infinity, so the scale is uniquely
determined. Tied or repeated data require additional conventions for the local scales.
The two directed affinities are combined into the symmetric weight
 |
(3)
|
This is the probabilistic union rule for two fuzzy set membership strengths. It produces a weighted graph
with 
and at most 
graph edges. A large weight
denotes strong local similarity rather than a large distance.
For low-dimensional coordinates 
, define
 |
(4)
|
where 
control the similarity curve, 
denotes the real numbers, and
is the l2-norm.
The ideal layout objective is the sum of pairwise Bernoulli cross entropies,
![C(Y)=-sum_(1<=i<j<=n)[w_(ij)lnq_(ij)+(1-w_(ij))ln(1-q_(ij))],](/images/equations/UniformManifoldApproximationandProjection/NumberedEquation5.svg) |
(5)
|
with limiting conventions at zero. This differs from the original fuzzy-set objective only by terms independent of the coordinates 
.
It favors proximity for pairs with large 
and separation for pairs with small 
.
The practical algorithm samples attractive interactions along graph edges. It approximates repulsion by sampling pairs of vertices, a procedure called negative sampling. Damrich and Hamprecht (2021) showed that negative sampling changes the relative weighting of attraction and repulsion. These updates therefore are not unbiased stochastic gradients of the full pairwise cross entropy above.
The layout stage can also start from an existing weighted graph with affinity weights, without constructing it from a collection of points. For 
, these coordinates can be
used for graph drawing. Such a layout need not be
a crossing-free graph embedding and does not guarantee
preservation of all graph distances.
