Fuzzy Simplicial Sets in UMAP

From Neighbor Distances to Fuzzy Memberships

A nearest-neighbor graph records which cells are near one another, but a binary edge does not distinguish a barely included neighbor from a very close one. UMAP instead assigns graded strengths to directed neighbor relationships, adapts the distance scale to each cell, and then combines the two directions of each pair. The result is a fuzzy representation of local relationships, not a set of statistically estimated probabilities.

The construction begins with a directed \(k\)-nearest-neighbor list. For cell \(i\), let \(N_k(i)\) be the cells in its list and let \(d_{ij}\) be the chosen input-space distance from \(i\) to neighbor \(j\). The distance is generally not symmetric in the neighbor lists: \(j\) can be among \(i\)'s nearest neighbors without \(i\) being among \(j\)'s. Each cell receives its own offset \(\rho_i\) and scale \(\sigma_i\), so the same distance can yield different directed strengths from different cells.

The maximum in the formula makes every neighbor at distance no greater than \(\rho_i\) have membership 1. Beyond that offset, membership decreases exponentially with distance, with the rate of decrease determined by \(\sigma_i\). A larger \(\sigma_i\) makes weights decline more gradually; a smaller one makes them decline more sharply.

The offset \(\rho_i\) represents a local distance floor: it ensures that the closest neighbor or neighbors receive full membership despite differences in local density. In a common setting with local connectivity equal to 1, \(\rho_i\) is based on the distance to the nearest nonzero-distance neighbor. More general local-connectivity settings can place the offset farther into the ordered neighbor distances, with interpolation when needed. Implementations also need conventions for duplicate points and zero distances. Thus, \(\rho_i\) is not simply a universal distance threshold shared by all cells.

After choosing the offset, UMAP selects \(\sigma_i\) by a numerical smoothing procedure. In the standard formulation, the target is to make the sum of directed memberships over the \(k\) neighbors approximately \(\log_2(k)\):

This target gives each local neighborhood a comparable aggregate membership while allowing its distance scale to adapt. It is a construction rule, not a claim that every cell has exactly \(\log_2(k)\) neighbors in a probabilistic sense. Numerical implementations solve to a tolerance and may use bounds or special handling for ties. If several neighbors lie at or inside \(\rho_i\), they each contribute 1, which can make exact matching to the target impossible; practical handling of such cases matters.

Combining the Two Directions

For a pair of cells \(i\) and \(j\), write \(a=w_{i\to j}\) and \(b=w_{j\to i}\). UMAP combines them using the fuzzy union:

This is the probabilistic-sum fuzzy union, also called the algebraic sum. The complement form shows its logic: the combined membership is one minus the product of the two non-memberships. This is an algebraic rule for fuzzy memberships; it does not assert that the two directions are independent random events. The resulting weight is symmetric in \(i\) and \(j\), even when the directed values differ.

The union rule has useful bounds and monotonicity properties. For \(a,b\in[0,1]\), its membership is at least each input because \(w_{ij}-a=b(1-a)\geq0\) and \(w_{ij}-b=a(1-b)\geq0\). It is at most 1 because \(w_{ij}=1-(1-a)(1-b)\leq1\), and it is nonnegative because both inputs are nonnegative. Thus \(w_{ij}\in[0,1]\).

It is also nondecreasing in each directed strength. Holding \(b\) fixed and increasing \(a\) to \(a'\geq a\), the change in the union is \(w(a',b)-w(a,b)=(a'-a)(1-b)\geq0\). Holding \(a\) fixed and increasing \(b\) to \(b'\geq b\), the change is \(w(a,b')-w(a,b)=(b'-b)(1-a)\geq0\). If both inputs are positive and both are less than 1, then \(w_{ij}-a=b(1-a)>0\) and \(w_{ij}-b=a(1-b)>0\), so the union is strictly greater than either input. If either input is 1, the union is 1.

Why This Construction Matters—and Where It Can Fail

Local offsets and scales let the graph represent neighborhood relationships across regions with different distance densities. Without a local offset, the nearest relationship might receive a small membership in a sparse region simply because all distances there are large. Without a cell-specific scale, a single exponential decay could make dense neighborhoods overly connected or sparse neighborhoods too weak. Fuzzy union then preserves one-sided neighbor evidence while strengthening a pair supported in both directions.

A useful diagnostic is to inspect the directed memberships, \(\rho_i\), and \(\sigma_i\) for a sample of cells, especially when the resulting graph looks unexpectedly dense, weak, or uneven. Extremely small scales can make most memberships beyond \(\rho_i\) nearly zero; very large scales can leave many neighbors with substantial weights. Many tied distances or duplicate cells can yield multiple memberships of 1 and complicate the scale target. These patterns may reflect the data, but can also point to a distance choice, preprocessing issue, or numerical edge case that deserves checking.

The fuzzy union is one of several possible symmetrizations. Keeping only directed edges retains asymmetry but does not produce the undirected fuzzy graph used in the standard construction. Adding reciprocal weights can exceed 1, and clipping the sum at 1 behaves differently from fuzzy union. Taking the arithmetic mean keeps weights bounded but can reduce a strong one-sided relationship. A fuzzy intersection, often represented by the product \(ab\), emphasizes reciprocal support; for \(a,b\in[0,1]\), it is no greater than either input and is strictly smaller than both when \(a,b\in(0,1)\). These alternatives encode different choices; they are not interchangeable versions of the same rule.

The edge weights summarize the constructed neighborhood structure. They are not p-values, probabilities that two cells belong to the same biological population, or direct measures of gene-expression difference. The graph also depends on the input representation, distance metric, neighbor count, local-connectivity setting, and numerical implementation. A fuzzy edge can retain local evidence without guaranteeing that the chosen neighbors are biologically meaningful. The construction defines the input relationships to a later embedding stage; it does not by itself explain or validate the resulting coordinates.