Diffusion Kernels as Cell-to-Cell Transitions

From Cell Distances to Local Transition Probabilities

A cell-to-cell distance says how far apart two cells are in a chosen representation; it does not yet say how much probability should be assigned to moving between them. A diffusion kernel supplies a rule for converting distances into nonnegative similarity weights. Row normalization then turns the weights leaving each cell into a probability distribution over possible next cells.

The result is a mathematical random walk on a cell-neighborhood graph. Its one-step probabilities describe local connectivity under the selected distance, graph, and kernel scale. They are not observed cell movements, and they do not establish that one cell biologically turns into another.

Definition: Let $x_i$ denote the representation of cell $i$, and let $d_{ij}$ be the chosen distance between cells $i$ and $j$. Let $A_{ij}$ equal 1 when the graph includes the directed edge from $i$ to $j$, and 0 otherwise. For bandwidth $h>0$, a Gaussian neighborhood kernel with self-loops is $$ K_{ij}=A_{ij}\exp\left(-\frac{d_{ij}^{2}}{2h^{2}}\right), $$ where $A_{ii}=1$ and $d_{ii}=0$, so $K_{ii}=1$. The row sum $q_i=\sum_j K_{ij}$ is the total weight leaving cell $i$. If $q_i>0$, the row-normalized transition probability is $P_{ij}=K_{ij}/q_i$.

The distance may be Euclidean distance in a selected low-dimensional representation or another scientifically justified metric. The bandwidth $h$ must be in the same units as that distance. Multiplying all distances and $h$ by the same positive constant leaves the kernel weights unchanged, but changing $h$ alone changes how rapidly weights decline with distance. A neighborhood restriction is often used: weights outside a $k$-nearest-neighbor or radius-based graph are set to zero. Thus the graph determines which moves are allowed, while the kernel determines their relative weights among allowed moves.

This tutorial uses self-loops, so each cell has positive diagonal weight and can remain at its current node in one step. Other implementations may omit self-loops; then a row must still have at least one positive outgoing weight for row normalization to be defined. When an undirected neighborhood is wanted, the graph can be constructed to include reciprocal edges, for example by using a union or mutual-neighbor rule. A directed neighborhood is also possible, but its row-normalized probabilities describe outgoing moves and need not be reciprocal.

Why Row Normalization Gives Probabilities

The kernel entries are nonnegative weights, not probabilities: their row sums generally differ from 1. For any cell $i$ with $q_i>0$, division by $q_i$ gives nonnegative entries whose sum is one:

P_{ij}\geq 0,\qquad \sum_j P_{ij} =\sum_j\frac{K_{ij}}{q_i} =\frac{q_i}{q_i} =1.

Consequently, row $i$ can be read as a conditional distribution: $P_{ij}$ is the probability of the next graph node being cell $j$, given that the current node is cell $i$, under this chosen random-walk rule. This is a definition of a graph-based stochastic process, not an estimate of a biological transition rate.

If the current cell is random with row-vector distribution $\boldsymbol{\pi}$, where $\pi_i\geq0$ and $\sum_i\pi_i=1$, then the distribution after one step is $\boldsymbol{\pi}'=\boldsymbol{\pi}P$. In components, $\pi'_j=\sum_i\pi_iP_{ij}$: probability arriving at $j$ is the sum of the probabilities of starting at each $i$ and moving from $i$ to $j$.

Worked Example: Building a Gaussian Kernel and Taking One Step

Consider three hypothetical cells, A, B, and C, with pairwise distances $d_{\mathrm{AB}}=1$, $d_{\mathrm{AC}}=2$, and $d_{\mathrm{BC}}=1.5$, in arbitrary distance units. Use a complete graph, include self-loops, and set $h=1$ distance unit. The graph is undirected, and the distances are finite and nonnegative, so the stated Gaussian kernel applies. The weight for a distance $d$ is $\exp(-d^2/2)$.

The diagonal weights are 1. The off-diagonal weights are $K_{\mathrm{AB}}=\exp(-0.5)\approx0.6065$, $K_{\mathrm{AC}}=\exp(-2)\approx0.1353$, and $K_{\mathrm{BC}}=\exp(-1.125)\approx0.3247$. Symmetry gives the corresponding reverse-edge weights. The kernel matrix, with rows and columns ordered A, B, C, is therefore

K\approx \begin{pmatrix} 1 & 0.6065 & 0.1353\\ 0.6065 & 1 & 0.3247\\ 0.1353 & 0.3247 & 1 \end{pmatrix}.

For row A, the total weight is $q_{\mathrm A}=1+0.6065+0.1353=1.7418$. Thus $P_{\mathrm{AA}}=1/1.7418\approx0.5741$, $P_{\mathrm{AB}}=0.6065/1.7418\approx0.3482$, and $P_{\mathrm{AC}}=0.1353/1.7418\approx0.0777$. For row B, $q_{\mathrm B}=1+0.6065+0.3247=1.9312$, giving probabilities approximately $0.3141$, $0.5178$, and $0.1681$ for A, B, and C. For row C, $q_{\mathrm C}=1+0.1353+0.3247=1.4600$, giving probabilities approximately $0.0927$, $0.2224$, and $0.6849$ for A, B, and C.

The resulting transition matrix is

P\approx \begin{pmatrix} 0.5741 & 0.3482 & 0.0777\\ 0.3141 & 0.5178 & 0.1681\\ 0.0927 & 0.2224 & 0.6849 \end{pmatrix}.

Each row sums to approximately 1, allowing for rounding. Suppose the initial distribution puts probability $0.5$ on A and $0.5$ on B, and none on C: $\boldsymbol{\pi}=(0.5,0.5,0)$. Multiplication gives $\pi'_{\mathrm A}=(0.5741+0.3141)/2=0.4441$, $\pi'_{\mathrm B}=(0.3482+0.5178)/2=0.4330$, and $\pi'_{\mathrm C}=(0.0777+0.1681)/2=0.1229$. These are the probabilities of occupying A, B, and C after one step under the graph rule. The relatively large probability of remaining at C reflects its row’s self-weight relative to its two other weights; it is not evidence that C is biologically stable.

Neighborhood Choice Changes the Meaning of a Move

A complete graph assigns a positive Gaussian weight to every pair of cells, including distant pairs. In a large data set, that can create many weak edges and allow moves that are not intended to be local. Restricting the graph before normalization makes excluded moves have probability zero. Because normalization is performed separately for each row, removing even one edge changes the probabilities of the remaining edges in that row.

Worked Example: Removing a Long-Range Edge

Use the same three hypothetical distances and bandwidth as above, but retain only pairs whose distance is less than 2 units, along with all self-loops. This is an undirected radius graph: A–B and B–C remain, while A–C is excluded. The distances are finite, each cell has a positive self-weight, and each cell has at least one allowed edge, so every row can be normalized.

For A, the retained weights are $1$ to itself and $0.6065$ to B, so the row sum is $1.6065$. The probabilities are $P_{\mathrm{AA}}=1/1.6065\approx0.6225$ and $P_{\mathrm{AB}}=0.6065/1.6065\approx0.3775$; $P_{\mathrm{AC}}=0$. For B, the retained weights are unchanged from the first example, so its row is approximately $(0.3141,0.5178,0.1681)$. For C, the row sum is $1+0.3247=1.3247$, giving $P_{\mathrm{CB}}=0.3247/1.3247\approx0.2451$, $P_{\mathrm{CC}}=1/1.3247\approx0.7549$, and $P_{\mathrm{CA}}=0$.

The probability of moving directly between A and C is now zero, although their distance and kernel value have not changed. That is a consequence of the graph restriction, not a claim that the cells are unrelated in every biological sense. Under this rule, a path from A to C must pass through B.

Directed Neighborhoods and Row-Specific Interpretation

Distance-based weights are symmetric when $d_{ij}=d_{ji}$, but the final kernel need not be symmetric if the neighborhood mask is directed. For example, a $k$-nearest-neighbor rule can include $j$ among the neighbors of $i$ without including $i$ among the neighbors of $j$. Row normalization remains valid as long as each row has a positive sum; it does not make such a graph reciprocal.

Worked Example: Normalizing a Directed Two-Cell Neighborhood

Suppose a hypothetical directed graph has two cells, U and V. Self-loops have weight 1, the allowed U-to-V edge has weight 0.8, and the allowed V-to-U edge has weight 0.4. These weights could arise from a distance kernel followed by a directed neighborhood mask. Both row sums are positive, so normalization is defined.

The row sums are $q_{\mathrm U}=1+0.8=1.8$ and $q_{\mathrm V}=1+0.4=1.4$. Therefore $P_{\mathrm{UU}}=1/1.8\approx0.5556$, $P_{\mathrm{UV}}=0.8/1.8\approx0.4444$, $P_{\mathrm{VU}}=0.4/1.4\approx0.2857$, and $P_{\mathrm{VV}}=1/1.4\approx0.7143$. Each row sums to 1, but $P_{\mathrm{UV}}\ne P_{\mathrm{VU}}$. The probabilities answer different conditional questions: the first concerns the next node given U as the current node; the second concerns the next node given V. They are not required to match.

Assumptions, Diagnostics, and Alternatives

The construction is mathematically well-defined under modest conditions, but its usefulness depends on scientific and computational choices. Check that the cell representation and distance metric are meaningful for the intended notion of neighborhood, that $h$ is positive and expressed on the distance scale, and that the graph mask and kernel weights have been applied in the intended order. After construction, verify nonnegative finite weights, positive row sums, and row sums of $P$ equal to 1 within numerical tolerance. Inspect the number of allowed neighbors per cell and the distribution of nonzero transition probabilities; a valid stochastic matrix can still encode a poor neighborhood.

Zero rows: If self-loops are omitted and a cell has no outgoing edge, then $q_i=0$, so its row cannot be normalized. Add or revise edges, or explicitly define how such a cell is handled; do not divide by zero.
Unexpectedly concentrated rows: If nearly all probability lies on the diagonal, off-diagonal weights may be tiny relative to the self-loop, perhaps because $h$ is too small for the distance scale. If rows are nearly uniform across many cells, the scale may be too broad or the graph too dense.
Disconnected components: A graph can have valid rows yet split into components with no edges between them. A random walk cannot cross between components. Inspect graph connectivity rather than interpreting absent transitions as strong evidence of biological separation.
Feature scaling and artifacts: Distances can be dominated by feature scales or technical variation. A kernel faithfully transforms the supplied distances; it cannot repair an unsuitable representation or metric.
Numerical underflow: Very large $d_{ij}/h$ can make exponentials numerically zero. A sparse neighborhood can avoid retaining negligible long-range weights, but the resulting graph should be checked for unintended isolated nodes.

Common alternatives make different choices. A binary neighborhood assigns equal positive weight to every retained edge and zero elsewhere, ignoring distance differences among neighbors. A radius graph makes inclusion depend on a distance cutoff, whereas a $k$-nearest-neighbor graph fixes a neighbor count but can have varying edge lengths. A Gaussian kernel preserves graded distance information, but its probabilities depend on the bandwidth as well as the graph. These approaches are not interchangeable without consequences for the resulting transitions.

Row normalization is also distinct from leaving the kernel weights unnormalized: raw weights measure relative affinity but are not conditional probabilities. It is distinct as well from symmetric normalization, which uses a different operator; that construction is not needed to interpret the one-step row probabilities developed here. None of these normalizations establishes direction in biological time. In particular, $P_{ij}$ is not a measured rate of cell $i$ becoming cell $j$, and a high value can reflect graph design, local density, the self-loop, or distance scaling.

Key takeaway: A diffusion transition matrix is obtained by assigning nonnegative kernel weights to allowed cell pairs and dividing each row by its own positive sum. Its rows describe one-step conditional probabilities under a chosen graph-based random walk, not observed biological transitions.

Check Your Understanding

Answer each question, then compare with the solutions below.

If a cell has outgoing kernel weights 1 to itself, 0.5 to cell B, and 0 to cell C, what are its transition probabilities?
Why can a Gaussian kernel assign a zero transition probability to a pair of cells with finite distance?
A directed two-cell graph has self-weights 1 and cross-weights 0.2 from U to V and 0.8 from V to U. Calculate both cross-transition probabilities.
What does it mean if every row of $P$ sums to 1 but the graph has two disconnected components?
Give one reason that a large $P_{ii}$ should not automatically be interpreted as biological persistence.

Solutions. (1) The row sum is $1+0.5=1.5$, so the probabilities are $P_{i i}=1/1.5\approx0.6667$, $P_{i\mathrm B}=0.5/1.5\approx0.3333$, and $P_{i\mathrm C}=0$. (2) The graph mask can exclude the pair; setting $A_{ij}=0$ makes $K_{ij}=0$ regardless of finite distance. (3) The U row sum is $1.2$, so $P_{\mathrm{UV}}=0.2/1.2\approx0.1667$. The V row sum is $1.8$, so $P_{\mathrm{VU}}=0.8/1.8\approx0.4444$. (4) Each cell has a valid probability distribution over its outgoing neighbors, but a walk starting in one component cannot reach the other component. (5) The diagonal probability depends on the self-loop relative to the other row weights, which are affected by the bandwidth, graph, and distance scale; it is a property of the constructed random walk, not direct biological evidence.