Flow-Ordered Storage for Streaming RNA Velocity Graphs

RNA velocity estimates which way each cell is heading. It does this by comparing a cell's unspliced (newly made) and spliced (mature) messenger RNA for each gene: an excess of unspliced RNA means a gene is switching on, a deficit means it is switching off. Downstream, most analyses turn these per-cell directions into a random walk over a graph of similar cells. That walk yields fate probabilities, mean hitting times to terminal states, and a latent-time ordering. Every current pipeline builds this graph once, on a fixed set of cells. When a new sequencing batch or tissue slice arrives, the neighbor graph, the transition matrix and every walk-based quantity are recomputed from scratch.

This note proposes storing the cell transition graph in memory in the order of the velocity field's own latent time, then keeping that order as new cells arrive. The bet is that one ordering does three jobs. Random walks mostly step "forward" in latent time, so the next cell's data usually sits in nearby memory. Iterative solvers for hitting times, swept in that order, behave almost like exact back-substitution. And a new cell's position in the order can be predicted from its own splicing state, so it can be inserted locally without re-sorting the whole graph. If this holds, velocity analysis over growing atlases becomes an incremental operation instead of a batch rebuild. The graph-layout literature has not had access to a direction of flow; this proposal uses the one that velocity supplies.

Core Claim

Hardware-aware graph reordering speeds up traversals by putting co-accessed nodes in the same cache line or disk page. It does so using undirected structure, such as neighbor overlap, triplet cache-miss bounds, or query traffic profiles. Graph Reordering for Cache-Efficient Near Neighbor Search studies these orderings (Gorder, Corder, Porder) for vector-search graphs and finds that local structure, not degree, determines cache behavior. It explicitly leaves dynamic maintenance of the layout to future work. Velocity transition graphs differ from vector-search graphs in one way that matters: they are directed and nearly acyclic along latent time.

Let $P$ be the row-stochastic transition matrix over cells and $h$ the vector of mean hitting times to a target set $T$. Hitting times satisfy

$$h_i = 1 + \sum_{j \notin T} P_{ij} h_j \quad \text{for } i \notin T, \qquad h_i = 0 \text{ for } i \in T.$$

Order cells by latent time and define the backward mass $\delta = \frac{1}{n}\sum_i \sum_{j:\,\tau_j<\tau_i} P_{ij}$, where $n$ is the number of cells and $\tau$ is latent time. $\delta$ is the average probability that a step goes to an earlier cell. When $\delta = 0$ the system is triangular and one reverse sweep of Gauss–Seidel solves it exactly. Gauss–Seidel is an iterative solver that updates each unknown in place using the newest values of the others. For small $\delta$, we expect the number of sweeps to grow slowly with $\delta$. This is a heuristic drawn from the triangular limit, and we will measure it rather than assume it.

The same order also places $P_{ij}$'s nonzeros close to the diagonal, which gives the memory locality. Generic bandwidth-reducing or community orderings can match the locality, but they have no reason to match the sweep direction. That is the separable, testable part of the claim.

Relation to Prior Work

Three velocity papers supply the objects we operate on, and all three treat the cell graph as static. On the Mathematics of RNA Velocity II: Algorithmic Aspects defines the Markov transition kernel over cell neighbors, fixes a gene-shared latent time via a Perron–Frobenius argument, and computes hitting times with "taboo sets" (states the walk may not enter) to avoid distortion from competing branches. We reuse its kernel, its latent time and its hitting-time definitions as the ground-truth computation our incremental system must reproduce. It also proves that kernel error grows with gene dimension. That constrains us to build graphs in a low-dimensional embedding, which fortunately also keeps per-node records small enough to pack several per cache line. This matters because the "large node" regime is where Coleman et al. saw reordering gains shrink.

spVelo builds a graph that combines tissue adjacency with cross-batch mutual nearest neighbors and trains a graph-attention autoencoder over it. Its "spatial" means tissue coordinates, not memory, and it has no path for adding a slice without retraining. Its multi-batch spatial datasets motivate our streaming setting.

Cell2fate fits linearized kinetics offline. It also supplies the pancreas, dentate gyrus, erythroid and bone marrow benchmarks.

On the systems side, DiskGNN packs co-accessed features contiguously on disk and orders a disk cache with MinHash. Its authors state that the design assumes static graphs, and packing inflates storage up to tenfold, which rules out re-packing on every update. Locality-Aware Cache Replacement Policy for Graph Traversals shows that on-disk serialization order becomes cache reuse if replacement is distance-aware, but it covers read-only traversals only. Flash co-locates compact neighbor codes with neighbor IDs for construction speed, again statically. We borrow the idea of co-locating neighbor IDs with compact neighbor data, and we avoid designs that require full re-packing.

For maintenance, the DiskANN library buffers inserts and consolidates lazily. Dynamic coarsening offers two strategies: DIGC, which freezes old assignments and places only new nodes, and ACNR, which allows old nodes to be reassigned. It reports that incremental updates can regularize against single-snapshot noise. That result motivates testing whether incremental velocity graphs are more stable across batches than rebuilt ones, not only faster. None of these methods maintains physical layout, and none has a flow direction to exploit.

Research Program

We would build a streaming velocity-graph store with four components.

Cells are kept in a gapped array sorted by latent time, with empty slots left for future insertions (the packed-memory-array idea). Each cell's record co-locates its neighbor IDs, transition weights and a low-dimensional state, in the spirit of Flash.

When a batch arrives, each new cell gets a predicted latent time. The prediction comes from its phase-portrait position under the kinetic parameters already fitted, refined by its nearest existing neighbors. The cell is then inserted into the nearest gap. The array is rebalanced locally when a region fills.

Neighbor lists and kernel weights are repaired only within a radius of the inserted cells, and we count the per-insert "recourse", meaning the number of rewired entries. Kinetic parameters are refit on a slower schedule, with the confidence intervals from the Mathematics II paper deciding when drift warrants a global latent-time re-fix.

Hitting times and fate probabilities are warm-started from the previous solution and solved by Gauss–Seidel sweeps in stored order, restricted to the affected region wherever the taboo-set structure allows.

Analysis accompanies the build. We will measure $\delta$ on each real dataset to check whether velocity graphs really are nearly triangular in latent time. Graphs with strong cycles, such as cell-cycle programs, are the expected failure case and will be reported as such. We will also measure how prediction error in inserted latent times translates into extra backward mass and into layout fragmentation over many batches.

Baselines

The naive reference is full recomputation. On each batch arrival we rebuild the neighbor graph and transition kernel, re-fix latent time, and re-solve hitting times and fate probabilities with the same solver, storing cells in arrival order. This is exactly what practitioners do today. It defines both the accuracy target (our incremental answers should match it) and the time to beat.

The strongest layout competitor is Gorder, the best-performing ordering in Graph Reordering for Cache-Efficient Near Neighbor Search. On SIFT100M that paper reports up to 40% lower mean query latency, 20% lower P99 latency, and a cut in L3 cache misses from 6.5% to 4.0%. Those figures come from vector search rather than cell graphs, and no reported result was found on Lacuna for any reordering applied to velocity graphs. We will run Gorder, a reverse Cuthill–McKee bandwidth ordering and a random ordering on the same transition matrices. Each will be used both statically (reorder once, append new cells) and with full reorder after every batch. All runs use the same machine, thread count, solver tolerance and convergence criterion. Beating Gorder means lower end-to-end time for maintaining hitting times and fate probabilities at equal accuracy, not merely fewer cache misses.

The strongest maintenance competitor is lazy consolidation as in the DiskANN library. New cells go into an auxiliary buffer whose neighbor edges are merged periodically, and the downstream solves run cold on the merged graph. No reported result was found on Lacuna for DiskANN-style maintenance on cell graphs.

We also include ACNR from dynamic coarsening applied to a metacell graph. In this baseline the walk runs over supernodes and results are mapped back to cells.

Two ablations isolate the key ingredient. The first keeps our gapped array, local repair and warm start, but orders cells by Gorder or reverse Cuthill–McKee instead of latent time. This separates the value of flow direction from the value of locality. The second inserts new cells next to their nearest neighbor instead of at their predicted latent time, which tests whether velocity-based placement matters.

Why not just…?

Why not just recompute everything from scratch? At the scale of classic benchmarks like the developing pancreas, recomputation is likely fast enough, and this is a real threat to the proposal's relevance. We will not argue around it. We will report the crossover: the number of cells and the batch frequency at which incremental maintenance becomes faster, using the synthetic kinetic generator from the Mathematics II paper to scale beyond the real datasets. If the crossover lies beyond plausible atlas sizes, the systems half of the proposal fails, and only the stability question (below) remains.

Why not just apply Gorder or bandwidth reordering once and append new cells? This is the cheapest serious alternative. It may capture most of the memory benefit, since Coleman et al. found reordering overhead negligible and its gains robust. The first ablation settles the question. If static generic orderings match our time-to-solution, then flow direction adds nothing and the claim reduces to "any locality ordering works". The distinguishing prediction is that generic orderings need several times more Gauss–Seidel sweeps than latent-time ordering whenever measured $\delta$ is small.

Why not just use a dynamic nearest-neighbor index and ignore layout? A DiskANN-style index keeps neighbor lists fresh, but it maintains neither the directed transition kernel nor the hitting-time and fate solutions, which are the expensive downstream objects. The lazy-consolidation baseline measures exactly how much is lost by solving cold on an arrival-ordered graph.

Why not just coarsen cells into metacells so the graph is small enough that memory layout stops mattering? This is also a genuine threat, because coarsening shrinks the problem and may denoise velocity in the way the coarsening paper suggests. The cost is resolution. Rare or transient transitions can be merged away, and taboo-set hitting times depend on fine branch structure. We will compare ACNR against cell-level maintenance on hitting-time fidelity and on recovery of known branch points. Coarsening wins if its fidelity loss is small.

Proposed Experiments

Fidelity is anchored on the synthetic kinetic datasets from On the Mathematics of RNA Velocity II. Built from scratch, their latent time correlates about 0.989 with physical time, and mean hitting time fits physical time with $R^2 = 0.971$. We will stream the same cells in random and time-skewed batches and require the incrementally maintained quantities to stay within the from-scratch values. Time-skewed batches are the hard case for latent-time prediction.

Streaming realism comes from treating each batch of the OSCC and Stereo-seq mouse brain data used by spVelo as an arrival event. Direction checks come from the pancreas, dentate gyrus, erythroid and bone marrow datasets used by Cell2fate. Neither paper quotes numeric velocity scores in the file, so our reference points are our own from-scratch runs. Metrics are rank correlation of hitting times and fate probabilities against from-scratch values, per-batch wall-clock and sweep counts, cache-miss rates from hardware counters, recourse per insert, and layout fragmentation over many batches. We also measure stability: how much fate probabilities of unchanged cells move when a batch is added, compared between incremental and rebuilt pipelines.

Two outcomes are decisive. The first is whether measured backward mass $\delta$ is small on real developmental datasets and whether sweep count tracks it. The second is whether latent-time ordering beats Gorder and reverse Cuthill–McKee inside the identical incremental system. If $\delta$ is not small, or if the ablation shows no gap, the flow-ordering idea is wrong. What would remain is a plain engineering result about incremental velocity graphs.