Shared Nearest-Neighbor Graphs

Why Compare Neighborhoods?

A distance between two cells is measured on the scale of the chosen representation and metric. In a dense region of a cell space, nearby cells may be separated by small distances; in a sparse region, cells with similar local relationships may be farther apart. This makes a single raw-distance threshold difficult to interpret uniformly. Shared-nearest-neighbor (SNN) similarity instead asks whether two cells have similar local neighborhoods.

The idea is to compare the sets of cells surrounding a pair, rather than relying only on the distance between the pair. If two cells have many neighbors in common, their local neighborhoods overlap strongly. This can make their relationship less dependent on the absolute scale of distances in a particular region. It does not remove the need to choose a representation, distance metric, or neighborhood size carefully.

This tutorial uses the Jaccard definition above. Implementations can use other overlap conventions, so the precise definition should be checked before comparing reported values. With fixed \(k\), each neighborhood has \(k\) members. The cell \(i\) itself can still appear in \(N_k(j)\), and \(j\) in \(N_k(i)\), if the cells are mutual neighbors: only a cell’s own neighborhood excludes itself.

Calculating Neighborhood Overlap

The calculation has three parts: list each cell’s neighbors, find the intersection, and count the union. The intersection contains members present in both sets; the union contains members present in at least one. The denominator matters: a count of shared neighbors alone does not show what fraction of the combined neighborhoods is shared.

For fixed neighborhood size \(k\), if \(c\) members are shared, then the union contains \(2k-c\) members. Thus the Jaccard similarity can also be calculated as \(c/(2k-c)\). This relation is useful for checking arithmetic, but the intersection-over-union definition is the one to apply directly, especially if neighborhood sizes vary.

Why Local Neighborhoods Can Help with Uneven Density

A k-nearest-neighbor set is defined by rank: it contains the \(k\) closest eligible cells to a given cell. The distance to the \(k\)th neighbor can therefore differ across the data. In a dense region, that distance may be small; in a sparse region, it may be much larger. SNN compares the resulting sets, so two cells can have similar scores when their local neighborhoods overlap to a similar extent, even if their absolute distances are on different scales.

This is a relative, local comparison—not a claim that density is irrelevant. The cells still need to have meaningful neighbors under the selected representation and metric. Neighborhood overlap may also reflect a broad transition between populations, a shared boundary, or noise rather than a coherent biological group.

Symmetry, Candidate Pairs, and a Short Justification

The underlying kNN relation is directed: \(j\) can be among \(i\)’s nearest neighbors without \(i\) being among \(j\)’s. However, the Jaccard similarity is symmetric because set intersection and union do not depend on the order of their arguments:

so \(S(i,j)=S(j,i)\), whenever the denominator is nonzero. With \(k\geq 1\), the union of two fixed-size neighborhoods is nonempty. Symmetry of the score does not by itself specify which cell pairs an implementation evaluates. One may calculate similarities for all pairs or restrict calculations to candidate pairs selected from a kNN graph. That candidate-pair choice is separate from the similarity formula.

A further useful property follows when both sets have size \(k\). If \(c=\lvert N_k(i)\cap N_k(j)\rvert\), then their union has size \(2k-c\): add the two set sizes, then subtract the \(c\) members counted twice. Therefore,

For \(0\leq c\leq k\), the denominator is positive, and the expression increases with \(c\). For example, its derivative with respect to \(c\), treating \(c\) as continuous for this monotonicity check, is \(2k/(2k-c)^2>0\). Thus, for a fixed \(k\), pairs with more shared neighbors always have larger Jaccard similarity. The normalization expresses overlap relative to the union; it does not make the score a calibrated measure of biological similarity.

Assumptions, Diagnostics, and Limitations

SNN is a descriptive construction, not a hypothesis test. It does not require independent observations or a sampling model to compute. Its interpretation nevertheless depends on substantive choices and conditions:

• Meaningful representation and distance: the cell profiles or transformed coordinates and the distance metric should represent the relationships of interest. A misleading distance can produce misleading neighbor sets.
• A specified \(k\): all sets should use a stated neighborhood size and a consistent rule for ties. If ties at the \(k\)th distance are broken differently, the resulting sets and similarities can change.
• Consistent cell handling: the comparison should use the same eligible cell universe, with self-neighbors treated consistently. Missing or excluded cells can alter both intersections and unions.
• Local rankings that remain informative: rank-based neighborhoods help accommodate different local distance scales, but they still force every cell to have \(k\) neighbors. They do not establish that a sparse region is as well supported as a dense one.

Useful diagnostics include checking whether the \(k\)th-neighbor distance varies substantially across cells, whether small changes in \(k\) alter important overlaps, and whether many pairs have no shared neighbors. Inspecting ties and the underlying distance structure can reveal unstable neighborhoods. If a result changes sharply under reasonable alternative choices, that sensitivity should be reported rather than hidden.

The main alternative is to compare cells using raw distances. Raw distances preserve absolute scale, which can be important when that scale is meaningful, but a fixed distance can have different local significance in dense and sparse regions. SNN instead compares neighbor-set overlap, gaining some tolerance to local scale differences while discarding information about exact distances. Neither comparison is universally superior: the choice depends on whether absolute separation or local neighborhood agreement is the target.

Common failure modes include choosing \(k\) so small that neighbor sets are unstable, or so large that neighborhoods span distinct local structures; interpreting a high score as proof of a shared cell type; and treating zero overlap as proof that two cells are unrelated. A score of zero means only that the chosen sets have no members in common. It can result from a genuine local separation, a boundary, a small \(k\), or unstable neighborhoods.