Why Diffusion Operators Are Symmetrically Normalized

Why normalize a cell-transition operator?

A diffusion kernel represents local connections among cells by nonnegative affinities. Turning those affinities into row probabilities gives a transition operator: from a cell, one step selects a neighboring cell with probabilities summing to one. But unequal numbers of sampled cells in different regions can influence those probabilities, and the resulting transition matrix is generally not symmetric. Symmetric normalization addresses the spectral problem; a separate degree-based correction can reduce the effect of sampling density.

The distinction matters. A transition matrix can be nonsymmetric and still describe a reversible process, in which case a diagonal change of coordinates makes it symmetric. That fact guarantees real eigenvalues and allows symmetric-matrix spectral results to apply. It does not, by itself, remove sampling-density effects. The correction for density is controlled by a normalization parameter.

The case \(\alpha=0\) leaves the original affinities unchanged before row normalization. The case \(\alpha=1\) divides each affinity by the raw degrees at both ends. Intermediate values make intermediate corrections. Throughout, the affinities are assumed symmetric, and the transition matrix is formed by row-normalizing the adjusted affinities.

Reversibility and symmetric conjugation

For clarity, write \(A=W^{(\alpha)}\) and \(D=\operatorname{diag}(d_1^{(\alpha)},\ldots,d_n^{(\alpha)})\). Then \(A\) and \(D\) are symmetric, \(D\) has positive diagonal entries, and \(P=D^{-1}A\). Define \(\pi_i=d_i^{(\alpha)}/\sum_k d_k^{(\alpha)}\). This is a stationary distribution: \(\sum_i\pi_iP_{ij}=\pi_j\). More strongly, it satisfies detailed balance, \(\pi_iP_{ij}=\pi_jP_{ji}\). This equality is the definition of reversibility for this finite-state transition matrix.

Detailed balance says that, at stationarity, the probability flow from cell \(i\) to cell \(j\) equals the flow in the reverse direction. It follows here directly from the shared symmetric affinity: \(\pi_iP_{ij}=A_{ij}/\sum_k d_k^{(\alpha)}=\pi_jP_{ji}\). Thus row-stochasticity alone is not the reason the operator has a symmetric representation; the symmetry of its underlying affinities is essential.

The similarity and its consequence can be checked directly:

Because \(S\) is real and symmetric, the spectral theorem gives real eigenvalues and a basis of orthogonal eigenvectors for \(S\). Similar matrices have the same characteristic polynomial, since \(\det(\lambda I-D^{1/2}PD^{-1/2})=\det(D^{1/2}(\lambda I-P)D^{-1/2})=\det(\lambda I-P)\). Therefore \(P\) has those same real eigenvalues. The eigenvectors of \(P\) need not be orthogonal in the ordinary Euclidean inner product; the symmetric representation is what supplies the orthogonal basis in transformed coordinates.

Since \(P\) is row-stochastic, \(P\mathbf{1}=\mathbf{1}\), so 1 is an eigenvalue. Also, every eigenvalue has absolute value at most 1: for an eigenvector \(v\), choose an entry with largest absolute value. The corresponding entry of \(Pv\) is a weighted average of entries of \(v\), so \(|\lambda|\max_i|v_i|\leq\max_i|v_i|\). Reversibility makes the eigenvalues real, and this bound then places them in \([-1,1]\). They need not all be nonnegative; for example, a transition graph that alternates between two groups can have eigenvalue \(-1\).

Density correction is a separate normalization choice

The raw degree \(q_i\) estimates local sampling mass when the affinity kernel has a fixed local scale: a cell in a densely sampled region tends to have more nearby cells and hence a larger degree. In \(w_{ij}^{(\alpha)}=w_{ij}/(q_i^\alpha q_j^\alpha)\), dividing by these degrees at both endpoints changes the influence of that local mass before the rows are converted to probabilities. This is distinct from the later symmetric conjugation \(D^{-1/2}AD^{-1/2}\), which changes coordinates for spectral analysis but does not choose the density correction.

The population approximation makes the role of \(\alpha\) precise. Suppose cells are sampled from a smooth density \(p(x)>0\) on a smooth \(d\)-dimensional manifold, and affinities come from a small-scale isotropic kernel \(K_\varepsilon(x,y)=\exp(-\|x-y\|^2/(4\varepsilon))\). Assume the data are dense enough for sums to approximate integrals, the points considered are away from boundaries, and the kernel scale is small relative to the scale on which \(p\) changes. Then the raw kernel degree is proportional, to leading order, to \(p(x)\): \(q_\varepsilon(x)\approx c_\varepsilon p(x)\), where \(c_\varepsilon\) does not depend on \(x\) at leading order.

In the row-normalized operator, the factor \(q_\varepsilon(x)^{-\alpha}\) at the starting point cancels between numerator and denominator. The factor at the destination weights the sample density \(p(y)\) by approximately \(p(y)^{-\alpha}\). Thus the effective density in the integral is \(r(y)=p(y)^{1-\alpha}\), not \(p(y)\). For a smooth function \(f\), Taylor expansion of the isotropic Gaussian integrals in the interior gives

To see why the density term has this form, the leading integral expansions are proportional to \(fr+\varepsilon\Delta(fr)\) in the numerator and \(r+\varepsilon\Delta r\) in the denominator. Expanding their ratio to first order gives \(\Delta(fr)/r-f\Delta r/r=\Delta f+2\nabla\log r\cdot\nabla f\), using the product rule. Substituting \(r=p^{1-\alpha}\) yields a drift term \(2(1-\alpha)\nabla\log p\cdot\nabla f\). In particular, \(\alpha=1\) removes this leading sampling-density drift; \(\alpha=0\) retains it. The limiting Laplacian is understood on the manifold.

This is an asymptotic statement, not a promise that a finite data set becomes exactly density-free. Its approximation depends on sampling, kernel scale, smoothness, and boundary conditions. It also concerns the operator's limiting drift; it does not mean that every finite degree becomes equal, or that the data have been resampled to uniform density.

Assumptions, diagnostics, and alternatives

The real-eigenvalue result applies when the adjusted affinity matrix is symmetric and degrees are positive. An isolated cell has zero degree, so its row cannot be normalized; it must be removed, connected using a justified modeling choice, or handled as a separate component. A disconnected graph can still yield a reversible transition matrix on its non-isolated cells, but each connected component has its own stationary distribution, and the eigenvalue 1 is not unique across components.

Check that the affinity matrix is symmetric to numerical tolerance, that its entries are nonnegative when it is intended to represent affinities, and that no analyzed row has zero degree. After row normalization, check that rows sum to one. For a proposed stationary distribution, check detailed balance pairwise or verify that \(\pi^\mathsf{T}P=\pi^\mathsf{T}\). A numerical eigensolver returning appreciably complex eigenvalues for a supposedly reversible operator is a warning: possible causes include asymmetric weights, inconsistent row and column normalization, or numerical error. Small imaginary parts alone may be rounding; they should be judged relative to the scale and precision of the calculation.

A directed transition matrix need not be reversible and need not have real eigenvalues. One alternative is to analyze its nonsymmetric spectrum directly, but then the real-symmetric spectral theorem and its orthogonal-eigenvector guarantees do not apply. Another is to construct a symmetric affinity graph from the outset, when that matches the intended notion of cell similarity. Symmetric conjugation is not a substitute for changing genuinely directed transitions into reversible ones without justification.

A common mistake is to say that \(D^{-1/2}AD^{-1/2}\) removes sampling-density bias because it is symmetric. It does not: it is the conjugate representation that establishes real eigenvalues. The density adjustment is the separate choice of \(\alpha\) in \(A_{ij}=w_{ij}/(q_i^\alpha q_j^\alpha)\), and its effect depends on the sampling and kernel assumptions. Another mistake is to conclude that all eigenvalues must be positive. Reversibility guarantees real eigenvalues; stochasticity bounds their magnitudes by one, but negative eigenvalues remain possible.