Why a Gap in a Trajectory Graph Needs Interpretation
A cell-neighborhood graph is a model of which cells can exchange information through local connections. If the graph separates into components, no sequence of retained edges connects cells in different components. That fact has a precise mathematical consequence for diffusion: a random walk started in one component cannot reach another. It does not, by itself, establish that the corresponding cell states are biologically unrelated or that a developmental process contains a true discontinuity.
The gap may reflect the neighborhood rule, its scale, the representation used to calculate cell distances, or sparse sampling of an otherwise continuous state path. The first task is therefore to determine what the constructed graph implies, and the second is to assess whether the disconnection is stable and scientifically interpretable. This is especially important for diffusion pseudotime, which uses diffusion on a graph to describe relationships to a root cell.
What Disconnection Implies for Diffusion
Let \(W=(w_{ij})\) be the symmetric weight matrix, with \(w_{ii}=0\) unless self-edges are deliberately included. The degree of cell \(i\) is \(d_i=\sum_j w_{ij}\). When every cell has positive degree, the ordinary random-walk transition matrix is defined by \(P_{ij}=w_{ij}/d_i\). Each row then gives a probability distribution over the next cell visited by the walk. If any cell has degree zero, this formula does not define its transition row.
For a graph with at least two components and positive degree for every cell, reorder the cells so that cells in the same component are adjacent in the ordering. Then \(W\), the diagonal degree matrix, and \(P\) have block-diagonal form. This condition matters: positive weights on retained edges alone do not ensure that every cell has positive degree, because a graph may contain isolated cells.
The justification is direct. At one step, \(P_{ij}=0\) across components because there is no edge between them. If \(P^t_{ij}=0\) across components, then \(P^{t+1}_{ij}=\sum_k P^t_{ik}P_{kj}=0\): any \(k\) reachable from \(i\) is in \(i\)'s component, and from there \(P_{kj}=0\) for \(j\) in another component. Thus the claim holds for every finite \(t\). Equivalently, powers of a block-diagonal transition matrix remain block diagonal.
A root-based trajectory interpretation is consequently confined to the root's component if it relies on walks or paths in this graph. The introductory material on Diffusion Pseudotime from a Root Cell establishes the root-referenced diffusion perspective; here the key edge case is that a disconnected graph has no graph-based route from the root to cells outside its component.
Worked Example: Two Components and Unreachable Cells
Suppose five hypothetical cells have unit-weight edges \(A\!-\!B\), \(B\!-\!C\), and \(D\!-\!E\), with no other edges. Every cell has positive degree: \(d_A=d_C=d_D=d_E=1\), and \(d_B=2\). The components are \(\{A,B,C\}\) and \(\{D,E\}\), so the ordinary random-walk transition matrix is defined for all five cells.
From cell \(A\), the first step goes to \(B\) with probability 1. From \(B\), the walk goes to \(A\) or \(C\), each with probability \(1/2\). After two steps, the distribution starting at \(A\) therefore assigns probability \(1/2\) to \(A\), \(1/2\) to \(C\), and zero to \(B,D,E\). In particular, \(P^2_{AD}=0\). The block argument shows that \(P^t_{AD}=0\) at every later finite step as well.
If \(A\) is the root, there is no graph path by which a root-based diffusion trajectory can reach \(D\) or \(E\). The graph supports a within-component ordering, subject to the usual modeling assumptions, but does not support a cross-component ordering. It would be incorrect to read the absence of such an ordering as evidence that these cells cannot lie on the same biological process.
Disconnected Is Not the Same as a Very Long Gap
A disconnection is a topological property of the retained graph: there is no path. A weakly connected pair of regions is different. If a few low-weight edges link them, a walk can cross, but may do so rarely. Diffusion across a weak link can therefore be slow, and a finite-time analysis may make the regions appear far apart. Conversely, a single retained edge can technically connect two dense regions even when that edge is unstable or biologically implausible.
Some diffusion distances compare transition-probability distributions at a chosen time. Such a distance can be finite between cells in separate components: their distributions have disjoint support, so the distance measures how different those distributions are. But a finite pairwise distance is not a path or a progression time. In a disconnected graph, diffusion pseudotime implementations may leave cells outside the root component unassigned, return an undefined value, or assign a finite value according to a spectral or normalization convention. That finite number does not supply the missing graph route.
There is a further spectral warning. A disconnected transition operator has more than one closed component, and typically has multiple eigenvectors associated with eigenvalue 1. Within a component, a random walk can have its own stationary distribution; without a rule for allocating stationary mass across components, a global stationary distribution is not unique. As a result, spectral coordinates or distances that depend on a global ordering of these modes can be ambiguous across components. A software output should not be treated as a uniquely determined biological pseudotime merely because it is numeric.
Worked Example: An Isolated Cell and an Undefined Transition
Consider a hypothetical graph with cells \(U,V,W\), a unit-weight edge between \(U\) and \(V\), and no retained edge incident to \(W\). Then \(d_U=d_V=1\) and \(d_W=0\). For \(U\) and \(V\), the random walk alternates deterministically: \(P_{UV}=P_{VU}=1\). But the formula for \(P_{Wj}\) requires division by \(d_W=0\), so the ordinary transition matrix for all three cells is not defined.
One possible explicit convention is to add a self-transition for the isolated cell, setting \(P_{WW}=1\) and \(P_{WU}=P_{WV}=0\). This makes a row-stochastic matrix, but \(W\) is then an absorbing singleton component by construction. It remains unreachable from \(U\) and \(V\); adding the self-transition does not create evidence of biological isolation. Another valid analysis choice is to flag \(W\) as an isolated vertex and exclude it from walk-based calculations, while reporting that choice.
The important check is not to assert that \(P^t_{ij}=0\) for all cells before handling zero-degree rows. First establish that the transition matrix exists, either because all degrees are positive or because an explicit isolated-cell convention has been adopted.
Diagnosing a False Trajectory Gap
A graph component is determined jointly by the observed cells, the distance representation, and the neighborhood rule. For example, a radius graph retains edges only below a distance threshold; a small radius can split a continuous but sparsely sampled path. A \(k\)-nearest-neighbor graph can also be disconnected, particularly when groups are far apart or when ties and mutual-neighbor rules remove candidate connections. Changes to kernel scales and edge-pruning rules can alter connectivity without any change to the underlying biology.
Use a diagnostic sequence rather than interpreting the graph from a plot alone:
Count connected components and identify zero-degree cells. Confirm that the transition rule is defined for every cell included in diffusion calculations.
List component sizes and inspect cells near the apparent gap in the representation used to build the graph. Check whether a small number of boundary cells or low-density regions explain the split.
Rebuild the graph over a justified range of neighborhood sizes or kernel scales. Record whether the same cells remain separated and whether a proposed connecting edge is stable.
Ask whether it is supported by local neighbors and consistent with relevant cell annotations, or whether it is a single long bridge that merely forces connectivity.
State which component contains the root and whether cells outside it have undefined, excluded, or convention-dependent pseudotime.
Stability is informative, not conclusive. A separation that persists across reasonable graph choices is more robust as a property of the sampled representation, but it still does not prove distinct biological processes. A connection that appears only after a large neighborhood expansion is also not automatically valid: increasing neighborhood size can add shortcuts across a curved path or between unrelated states. Cell density, batch structure, and measurement noise can all affect the observed graph, so component membership should be interpreted alongside the scientific design and data quality.
Worked Example: A Radius Choice Creates a Gap
Suppose five hypothetical cells lie at positions \(0.0,0.1,0.2,1.0,1.1\) on a one-dimensional representation, with Euclidean distance as the graph-building distance. A radius graph with threshold \(r=0.25\) connects the first three cells to one another and connects the last two, but it does not connect \(0.2\) to \(1.0\), whose separation is \(0.8\). The graph has two components, \(\{0.0,0.1,0.2\}\) and \(\{1.0,1.1\}\), and all cells have positive degree.
If the threshold is increased to \(r=0.85\), the two boundary cells become connected. If edge weights are Gaussian with scale \(\sigma=0.2\), that boundary edge has weight \(w=\exp[-0.8^2/(2(0.2)^2)]=\exp(-8)\approx0.0003355\). It is positive, so the graph is now connected, but it is much weaker than an edge of weight 1 between cells separated by \(0.1\), for which the weight is \(\exp(-0.125)\approx0.8825\).
This calculation shows why “connected” and “well-supported continuous trajectory” are not equivalent. The larger radius removes the formal gap, but the proposed bridge has very low weight relative to local edges. One should examine its stability and local support rather than infer that the two groups form a confidently traversable progression.
Common Mistake and Practical Limits
Wrong reasoning: “The diffusion pseudotime output gives every cell a number, so cells in different graph components must have an inferred order.” Correction: a numeric output can result from a software convention, spectral embedding, or a calculation that does not encode a connecting path. Verify component membership and root reachability before interpreting the number. If the root cannot reach a cell under the stated transition model, a root-to-cell diffusion trajectory is not identified by that model.
A minimum spanning tree can be used to connect a set of cells, but enforcing a single connected tree may introduce a long edge between otherwise separate groups. That edge is a modeling choice, not evidence that the missing local neighborhood was observed. At the other extreme, a sparse neighborhood graph may omit plausible links and create artificial components. These approaches answer different graph-construction needs; neither removes the need to justify connectivity. The later comparison of principal curves, MSTs, and diffusion maps considers broader method differences, while the present issue is the interpretation of a gap under a given graph.
Finally, connectivity diagnostics address only the graph-based part of trajectory inference. They cannot determine whether observed differences are caused by developmental progression, cell type, technical effects, or undersampling. Pseudotime is an inferred coordinate, not measured elapsed time, and disconnection alone cannot identify the biological explanation for a gap.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions.
- A weighted graph has two components, and every cell has positive degree. What is \(P^t_{ij}\) for cells \(i\) and \(j\) in different components, for finite integer \(t\)? Why?
- Why is the usual random-walk transition row undefined for an isolated cell? Name one explicit way to handle the cell.
- A diffusion distance between cells in separate components is finite. Does that establish a root-to-cell trajectory? Explain.
- A graph becomes connected after increasing the neighborhood threshold, but the joining edge is far weaker than local edges. What should be checked before interpreting the resulting pseudotime?
Solutions. (1) \(P^t_{ij}=0\): the one-step transition matrix is block diagonal, and its powers remain block diagonal. (2) Its degree is zero, so \(P_{ij}=w_{ij}/d_i\) divides by zero. One may explicitly add an absorbing self-transition or flag and exclude the isolated cell. (3) No. A finite distance can quantify difference between diffusion distributions, but it does not create a path or establish progression from the root. (4) Check stability across reasonable neighborhood choices, local support for the bridge, and whether the edge is a plausible connection rather than an artifact; report the root component and any cells not reachable under the graph.