The Spectral Formula for Diffusion Distance

Comparing Cells by Their Multi-Step Transitions

Two cells can be close in an expression-space representation yet differ in how their local neighborhoods connect to the rest of a cell graph. Diffusion distance compares them through the transition distributions they generate: after a specified number of steps, how similarly are their probabilities spread across the graph? This gives a graph-based notion of similarity that incorporates indirect paths, not only a direct edge or immediate neighborhood.

The introductory material on Diffusion Maps from Eigenvectors motivates representing cells with eigenvectors of a transition operator. Here we derive the corresponding distance formula and connect it directly to the transition distributions it summarizes.

The stationary weights matter: a discrepancy in a cell with small \(\pi_k\) contributes more than an equally sized discrepancy in a common cell. This weighting is part of the definition, not an optional rescaling. The distance is dimensionless because its inputs are probabilities.

Assumptions and the Spectral Formula

For the standard spectral formula, assume the cell graph defines a finite, connected, reversible Markov chain. Reversibility means detailed balance holds: \(\pi_iP_{ik}=\pi_kP_{ki}\) for every pair \(i,k\). The probabilities \(\pi_k\) sum to one and are stationary, meaning \(\sum_i\pi_iP_{ik}=\pi_k\). Connectedness ensures that the eigenvalue \(1\) is simple. Reversibility makes \(P\) self-adjoint under the \(\pi\)-weighted inner product, so it has real eigenvalues and a complete set of eigenfunctions orthonormal under that inner product.

Write the eigenvalues as \(1=\lambda_0,\lambda_1,\ldots,\lambda_{m-1}\), where \(m\) is the number of cells, and let \(\psi_\ell\) satisfy \(P\psi_\ell=\lambda_\ell\psi_\ell\). Choose the eigenfunctions so that \(\sum_k\pi_k\psi_\ell(k)\psi_r(k)=1\) when \(\ell=r\) and \(0\) otherwise. The stationary eigenfunction is \(\psi_0(k)=1\). Under these conditions, the spectral formula is:

To justify the formula, reversibility and the stated orthonormal normalization give the transition-probability expansion \(P^t_{ik}=\pi_k\sum_{\ell=0}^{m-1}\lambda_\ell^t\psi_\ell(i)\psi_\ell(k)\). Subtract the corresponding expansion for cell \(j\), then substitute into the definition of \(D_t^2\):

The second equality uses orthonormality: the inner sum is zero for \(\ell\ne r\) and one for \(\ell=r\). The final equality drops \(\ell=0\), since \(\psi_0(i)-\psi_0(j)=1-1=0\). The square on \(\lambda_\ell^t\) is important, including when an eigenvalue is negative.

Reading the Formula and Its Time Dependence

Each nonstationary eigenfunction measures a pattern of variation across cells. The term \(\{\psi_\ell(i)-\psi_\ell(j)\}^2\) records how differently that pattern scores the two cells; \(\lambda_\ell^{2t}\) determines how much that pattern contributes at time \(t\). When \(|\lambda_\ell|<1\), its contribution decays as \(t\) grows. The distance thus compares distributions after a chosen number of transitions, rather than asserting that cells are close in every possible sense.

In diffusion coordinates, cell \(i\) has coordinates \(\lambda_\ell^t\psi_\ell(i)\) for the nonstationary eigenfunctions. The squared Euclidean distance between these coordinates is exactly the spectral formula, provided all nonstationary components are included. Keeping only a subset gives an approximation, not generally the exact diffusion distance.

Diagnostics, Alternatives, and Limitations

Before interpreting a calculated diffusion distance, check that the transition matrix is row-stochastic, the stationary probabilities are positive on the cells being compared, and detailed balance holds for the claimed reversible formulation. For a matrix derived from a symmetric affinity graph, the chosen normalization determines the transition matrix and its stationary distribution; these should be checked rather than assumed. A disconnected graph has multiple closed components, so the stationary eigenvalue need not be simple and cells in separate components may not communicate. A single connected-chain spectral interpretation then requires care.

A truncated spectral calculation can be checked by examining the omitted contribution:

where \(D_{t,L}^2\) retains only the first \(L\) nonstationary terms. Thus truncation underestimates the exact squared distance; it is adequate only when the omitted terms are negligible for the cell pairs and time of interest. Very small stationary probabilities can also magnify modest probability differences and make the distance sensitive to rare cells or graph irregularities.

Diffusion distance differs from ordinary Euclidean distance in a chosen expression or embedding space: it compares transition distributions and therefore reflects graph connectivity and multi-step routes. It also differs from shortest-path distance, which focuses on a least-cost route rather than the full distribution of possible walks. These alternatives answer different questions; none is a universal replacement. Diffusion distance depends on the graph, its normalization, and the chosen \(t\), and it is not by itself a measure of biological causation or a guarantee that the inferred graph represents true cell-state connectivity.

Common Mistakes

• Dropping the stationary denominator. This changes the defined metric; use \(\pi_k\) for each destination cell \(k\).
• Using \(\lambda_\ell^t\) rather than \(\lambda_\ell^{2t}\) in the squared distance. The eigenvalue factor is squared when the coordinate difference is squared.
• Keeping the stationary eigenfunction as a nonzero contribution. It is constant across cells, so its difference is zero.
• Calling a low-dimensional spectral approximation exact. Omitted components are nonnegative contributions to squared distance and may matter.
• Interpreting the result as a direct expression difference. It measures differences in multi-step transition distributions under the specified graph and time.