UMAP’s Cross-Entropy Embedding Objective

Matching Neighborhood Structure With an Embedding Objective

UMAP represents local relationships between cells as weighted edges, then places the cells in a low-dimensional space. The embedding objective gives a precise meaning to “matching”: for each cell pair, it compares the pair’s high-dimensional edge membership with the membership implied by the cells’ embedded positions. A mismatch creates a loss, and optimization changes the positions to reduce the total loss.

This is not a test of a biological hypothesis. It is an optimization criterion for constructing a representation of a fixed graph. The introductory material on fuzzy simplicial sets describes how to interpret the graph memberships; here we derive how those memberships enter the objective and how they exert attractive and repulsive effects on cell positions.

For a fixed, symmetric graph, it is convenient to sum over unordered pairs \(i<j\), so each pair contributes once. The binary cross-entropy for one pair is

This expression treats membership as a probability-like quantity: the first term penalizes a low embedded membership when the graph membership is high, while the second penalizes a high embedded membership when the graph membership is low. The total cross-entropy is \(C=\sum_{i<j}\ell_{ij}\). In practice, implementations use sparse graph edges and stochastic optimization rather than explicitly evaluating every pair at every step.

Why Cross-Entropy Is the Matching Criterion

A direct way to compare two membership values is the Bernoulli Kullback–Leibler divergence, which compares a Bernoulli distribution with success probability \(p_{ij}\) to one with success probability \(q_{ij}\):

Expanding the logarithms separates terms involving \(q_{ij}\) from terms involving only the fixed graph membership \(p_{ij}\):

Therefore \(D_{\mathrm{Ber}}(p_{ij}\,\|\,q_{ij})=\ell_{ij}-H(p_{ij})\), where \(H(p_{ij})=-p_{ij}\log(p_{ij})-(1-p_{ij})\log(1-p_{ij})\) is fixed while the graph is fixed. Summing over pairs adds only constants to the objective. Thus minimizing cross-entropy over embedded positions is equivalent to minimizing the summed Bernoulli divergence. The cross-entropy form is useful because it displays the two error types directly: missing a strong edge and inventing a strong edge.

How Embedded Distance Determines Membership

A common low-dimensional membership curve has the form

where \(y_i\) and \(y_j\) are the embedded coordinates, \(a>0\) and \(b>0\) determine the curve, and \(\lVert y_i-y_j\rVert\) is their Euclidean distance. This curve assigns higher membership to nearby cells and lower membership to distant cells. For the derivation below, take \(r=\lVert y_i-y_j\rVert>0\), so \(0<q_{ij}<1\), and treat \(a,b,p_{ij}\) as fixed.

Differentiating the membership curve gives \(dq_{ij}/dr=-2ab r^{2b-1}q_{ij}^{2}\). Differentiating the cross-entropy with respect to \(q_{ij}\) gives \((q_{ij}-p_{ij})/[q_{ij}(1-q_{ij})]\). Since \(q_{ij}(1-q_{ij})=a r^{2b}q_{ij}^{2}\), the chain rule yields

This derivative gives the basic geometric interpretation. If \(p_{ij}>q_{ij}\), the embedded pair has less membership than the graph target, and \(d\ell_{ij}/dr>0\): increasing the distance raises the loss, so gradient descent tends to bring the cells closer. This is the attractive effect. If \(p_{ij}<q_{ij}\), the embedded pair has too much membership, and \(d\ell_{ij}/dr<0\): increasing the distance lowers the loss. This is the repulsive effect. The same pairwise loss can therefore either pull cells together or push them apart, depending on the mismatch.

The derivative is with respect to distance; the coordinate gradient points along the line joining the embedded points. In particular, for \(r>0\),

Gradient descent moves against this gradient. A full embedding update combines contributions from many pairs, so a cell’s net movement depends on the surrounding graph and the other embedded cells, not on one edge in isolation.

Optimization, Diagnostics, and Limitations

The ideal objective sums losses over pairs, including both graph connections and pairs with little or no connection. A direct all-pairs calculation can be expensive for a large cell dataset. UMAP implementations commonly exploit the sparse graph for attractive contributions and use sampled non-neighbor pairs to approximate repulsive contributions. This stochastic computation is an approximation to the full objective; a sampled update is not the exact gradient of every pair at every iteration.

Useful checks follow directly from the objective. For selected pairs, verify that larger \(p_{ij}\) than \(q_{ij}\) gives an attractive direction, and that smaller \(p_{ij}\) than \(q_{ij}\) gives a repulsive direction. Monitor whether the optimization proceeds without numerical warnings or non-finite losses. If sampled or plotted pair memberships consistently move in the wrong direction, check the sign convention, whether pairs are counted consistently, and whether the repulsive contribution is being included. A decrease in the objective is evidence of progress on this optimization target, not proof that every aspect of cell geometry has been preserved.

The formula also has boundary cases. At \(p_{ij}=0\), the first term is interpreted by its limit as zero; at \(p_{ij}=1\), the second term is interpreted by its limit as zero. But if \(q_{ij}=0\) while \(p_{ij}>0\), or \(q_{ij}=1\) while \(p_{ij}<1\), the corresponding loss diverges. Implementations need numerical safeguards around such extremes. The distance derivative above assumes \(r>0\); at exactly coincident coordinates, its radial expression is not directly defined and implementations must handle that case safely.

The objective balances preserving graph connections against discouraging unsupported memberships. It does not guarantee a unique embedding: different coordinate configurations can produce similar losses, and optimization can depend on initialization and stochastic updates. Nor does a low loss establish that distances between distant groups have a literal biological interpretation, or that visually separated cells are distinct cell types. Such claims require evidence beyond the objective itself.

How This Objective Differs From Other Approaches

These objectives are not interchangeable merely because each can produce a two-dimensional plot. The UMAP objective is tied to fuzzy edge memberships and the chosen low-dimensional membership curve. Its advantage is a direct local graph-matching interpretation; its limitation is that the resulting coordinates remain an optimized representation, not a general-purpose metric map or an inferential model.