Selecting Neighborhood and Kernel Scales

Why Scale Choices Matter

A diffusion-based trajectory depends on which cells are allowed to exchange information and how strongly each connected pair is linked. These are related but distinct choices: the neighborhood size determines which cell pairs can have edges, while the kernel bandwidth controls how quickly edge weights decrease with distance. A graph can include the right local edges but weight them so unevenly that diffusion rarely crosses some of them. Conversely, a large neighborhood can introduce shortcuts between cells that are far apart along the biological trajectory.

This tutorial focuses on the effect of these scale choices on connectivity and smoothing. Earlier material on diffusion kernels and diffusion pseudotime establishes how cell-to-cell transitions are used downstream. Here, the practical question is whether the chosen graph and weights represent local transitions plausibly enough for those downstream calculations to be informative.

Two Scale Parameters, Two Different Effects

In a \(k\)-nearest-neighbor graph, each cell selects its \(k\) closest other cells. Because these selections can be asymmetric, a graph must specify how to turn them into undirected edges. The union rule retains an edge if either cell selects the other; the mutual rule retains it only if both cells select one another. The union rule tends to include more edges, while the mutual rule is more restrictive. Thus, the same \(k\) can produce different connectivity under the two rules.

A radius-based neighborhood instead connects pairs whose distance is no greater than a chosen radius. It applies the same distance threshold everywhere, so the number of neighbors can vary substantially across the representation. A \(k\)-nearest-neighbor rule fixes the number of selections per cell, but the distances to those neighbors can vary.

A common Gaussian kernel for a selected edge is

where \(h>0\) is the bandwidth. Smaller \(h\) makes affinities fall sharply with distance; larger \(h\) makes them more similar. A global bandwidth uses the same \(h\) for all pairs. An adaptive or locally scaled kernel uses cell-specific scales, for example \(W_{ij}=\exp(-d_{ij}^{2}/(\sigma_i\sigma_j))\), where \(\sigma_i\) and \(\sigma_j\) are positive local distance scales. The precise local-scaling rule varies, so it should be reported rather than assumed.

If the graph is sparse, affinities for unselected pairs are set to zero. Increasing \(k\) can then change the graph’s topology by adding edges. Changing \(h\) on a fixed graph does not add edges, but it can make some existing edges carry so little transition probability that they are effectively weak links. These distinctions are important: a zero weight caused by graph construction is not the same as a very small positive weight caused by the kernel.

Bandwidth Changes the Strength of Smoothing

For a fixed edge set, a larger bandwidth makes distances matter less in the weights. This generally spreads transition probability more evenly among a cell’s neighbors, so one diffusion step mixes information across more of the local neighborhood. A smaller bandwidth concentrates probability on the closest neighbors. This can preserve fine local distinctions, but it can also make a graph behave as if it were nearly disconnected if some bridging edges receive negligible weight.

The limiting cases clarify the mechanism. On a fixed graph with positive edge distances, as \(h\) becomes very small, the longest edges’ weights approach zero faster than the shortest edges’ weights. As \(h\) becomes very large, every selected edge weight approaches 1. The latter does not create new graph edges, but it makes all existing neighbors nearly equally likely at a given cell, regardless of distance. These statements concern the Gaussian weights; the exact resulting transition probabilities also depend on each cell’s selected neighbors.

Choosing and Diagnosing Scales

There is no scale value that is automatically correct for every cell population or representation. The working assumption behind a local neighborhood is that the chosen distance measure gives a meaningful ordering of local similarity, and that nearby cells are plausible candidates for local transitions. The kernel further assumes that distance should reduce affinity according to its specified rule. These assumptions can fail if the representation is dominated by irrelevant variation, if distances do not reflect state similarity, or if a single scale is unsuitable across the dataset.

A practical assessment compares a small, defensible range of neighborhood sizes and bandwidths rather than selecting a value from a single visual impression. Examine the graph and the transition weights together. Useful checks include:

• Neighbor distances and degree patterns. Inspect the distances to selected neighbors and the resulting numbers of undirected edges. Very long selected edges may indicate that a cell has no convincing local neighbors under the chosen representation.
• Weak links. Compare edge weights or normalized transition probabilities. A graph may be technically connected while a few bridge edges carry almost no probability. Repeating the calculation at a moderately larger bandwidth can show whether this is a weighting issue rather than a missing edge.
• Shortcuts. Check whether increasing \(k\) adds edges between regions that appear separated in the representation or that would bypass an expected local sequence. Such edges can make diffusion mix across a trajectory too quickly.
• Sensitivity. Compare neighborhoods and downstream pseudotime patterns across nearby parameter choices. Large changes indicate that the inferred structure is scale-dependent and should be reported as such, not hidden by choosing one setting.

These checks are diagnostics, not a proof that the graph is biologically correct. Apparent branches or gaps in a visualization do not by themselves establish that edges across them are invalid, and a stable result can still reflect a poor distance representation. Where available, known cell-state information can help assess plausibility, but it does not turn an association in the representation into evidence of a causal transition.

Alternatives and Limitations

A fixed-\(k\) graph is useful when a roughly comparable number of local candidates per cell is desired. A radius graph instead enforces a common distance cutoff, which can avoid connecting cells beyond a chosen scale but may leave some cells with few or no neighbors. A global-bandwidth kernel is simple to interpret and compare across pairs, but may not adapt well when relevant local distances vary. Local bandwidths can accommodate different distance scales, though they make an edge’s weight depend on scales at both endpoints and add another modeling choice. Union and mutual \(k\)-nearest-neighbor symmetrizations offer a separate trade-off: union retains more candidate edges, while mutual selection removes edges not supported in both directions.

None of these choices eliminates the need to inspect the representation and the resulting graph. Increasing \(k\) can connect regions that should remain locally distinct; decreasing it can remove useful links. Increasing bandwidth can blur local distinctions; decreasing it can make some edges practically irrelevant. A graph is also only as meaningful as the distance measure used to construct it. Report the neighborhood rule, symmetrization, kernel form, bandwidth or local-scaling rule, and any sensitivity checks so the scale-dependent nature of the result is clear.

Common Pitfall