Store-and-Forward Transport for Gapped Spatial Time Series

Spatial transcriptomics measures gene expression at known positions in a tissue slice, but it destroys the tissue. A "time series" is therefore a sequence of different specimens, often different animals or biopsies, each cut through a different plane. Methods that reconstruct how cells at one time give rise to cells at the next match consecutive slices with optimal transport, a method that pairs up two distributions at minimum total "moving cost." These methods assume that whatever is present at time $t$ is either visible at time $t+1$ or has died. In tumors that assumption breaks all the time. A small serial biopsy can simply miss a macrophage-rich niche or a resistant clone that is still there. Pairwise matching then destroys that population at the gap and recreates it from nothing later, which cuts exactly the lineage a therapy study cares about.

Satellite networks face the same structure. Links between fast-moving nodes exist only in short windows, so a message often has no path at the moment it is sent. The networking fix is a time-expanded graph with storage links: a node holds its data across time slots until a usable link appears, instead of dropping it. We propose to import that construction into lineage inference across tissue slices. All timepoints are solved jointly on one time-expanded graph. Cell mass can pass through a hidden, state-preserving holding arc when it is absent from an intermediate slice. The claim is that this recovers lineages across sampling gaps that chained pairwise transport breaks. As a by-product, the amount of mass routed through storage estimates how much of the tissue each slice failed to capture.

Core Claim and Relation to Prior Work

The method comes from Service Function Chain Dynamic Scheduling in Space-Air-Ground Integrated Networks. That paper cuts continuously moving drone and satellite topologies into quasi-static time slots and adds self-loop storage links, so tasks are buffered rather than discarded when outgoing links break. It then schedules over this graph with a deep Q-network. We keep only the graph construction and replace the learned scheduler with a convex flow problem. Lineage inference is an estimation problem, not a control problem, and a reinforcement-learning policy would add variance with nothing to show for it.

The direct competitor is SOCS. SOCS matches consecutive spatial slices with unbalanced Gromov-Wasserstein transport and penalizes maps that scatter a contiguous anatomical structure at $t_1$ across unrelated structures at $t_2$. Its authors acknowledge that transport remains vulnerable to cell-type imbalance between timepoints and depends on dense temporal sampling. We build on SOCS rather than replace it. SOCS's structure-aware transition cost is kept on the arcs between consecutive slices, and the new ingredient is the storage arcs. The contrast is therefore clean: SOCS reasons over pairs of slices and can only create or destroy mass at a gap, while our method reasons over all slices at once and can also carry mass through a gap.

Two other lines of work motivate the problem without solving it. Static spatial communication methods such as HoloNet and COMMOT infer who signals to whom within one slice and have no time axis. GraphCompass compares tissue graphs across conditions but does not link cells between them. On the dynamics side, Graph Neural ODEs with Stability and Conservation Guarantees models tumor cell states with message passing over time-varying neighborhoods. It is validated only on a synthetic agent-based simulator with diffusion, and it notes serious identifiability problems. Integration of Graph Neural Network and Neural-ODEs for Tumor Dynamic Prediction forecasts scalar tumor volume and ignores spatial structure. Both papers need the spatially resolved lineage estimates our method produces as training targets, and neither provides them.

We deliberately do not adopt several items from the research file. Neural link sparsification and bandit routing are not used because nothing in the lineage problem resembles signaling contention. The idea that immune-contact "dwelling time" explains therapy response is also dropped, because no live-imaging data in the file could test it.

Formulation

Let slices $t = 1, \dots, T$ each carry observed cells or metacells $i$ with mass $a_{t,i}$. A metacell is a small group of similar neighboring cells, used to keep the problem tractable. Let $S_{t}(i,j)$ be the SOCS transition cost from cell $i$ at $t$ to cell $j$ at $t+1$, including its structure penalty.

We add a hidden reservoir node $r_{t,k}$ for each discrete cell state $k$ at each time. The states are, for example, EcoTyper-style cell states of the kind defined in the colorectal cancer immunophenotyping study. Flow can take four kinds of arcs:

  • Transition arcs. Observed cells at $t$ flow to observed cells at $t+1$ with cost $S_t$.
  • Deposit arcs. Cells deposit into the reservoir matching their own state at cost $\lambda_s$ per step.
  • Storage arcs. Reservoirs carry mass forward to the next time, $r_{t,k} \to r_{t+1,k}$, at cost $\lambda_s$ per step.
  • Release arcs. Reservoirs release mass to observed cells of the same state at a later slice.

Birth and death arcs cost $\lambda_b$ and $\lambda_d$. The joint problem is

$$ \min_{f \ge 0} \sum_{e} c_e f_e - \varepsilon H(f) \quad \text{subject to flow conservation at every node and } \textstyle\sum_{\text{out}} f = a_{t,i} \text{ at each observed cell}, $$

where $f_e$ is the flow on arc $e$, $c_e$ is that arc's cost, and $H$ is an entropy term with weight $\varepsilon$ that makes the solution smooth and solvable by Sinkhorn-style scaling.

The single design rule is $\lambda_s(\Delta t) < \lambda_b + \lambda_d$, where $\Delta t$ is the number of slice gaps crossed. Under this rule, holding a population is cheaper than destroying and recreating it, but only when mass of the same state reappears later. Storage cost grows with $\Delta t$, so long unexplained absences are still resolved as death.

Because storage arcs are restricted to a single state, they cannot silently turn one cell type into another. That restriction is what separates this from simply loosening unbalanced-transport penalties. The total flow through the reservoirs at time $t$ is our estimate of the mass slice $t$ failed to sample.

Research Program

We will build the time-expanded solver on top of SOCS's transition cost. The Gromov-Wasserstein part is non-convex, so we handle it with the same alternating linearization used for pairwise problems, and the storage extension leaves each linearized subproblem a convex flow problem. We will then evaluate the method under controlled sampling gaps where ground truth is known.

The work has three stages. The first is semi-synthetic gaps on real developmental data. The second is a tumor-growth simulator with true lineages under therapy, whose initial conditions are drawn from real tumor sections. The third is a sensitivity study of $\lambda_s$ against $\lambda_b + \lambda_d$, to show the results are not an artifact of tuning.

The research file contains no longitudinal spatial tumor dataset with cell tracking. We state this as a limitation: the decisive real-tumor test requires serial-biopsy spatial data that this project can motivate but not supply.

Baselines

The naive reference is chained pairwise Wasserstein transport (W-OT). This is plain distribution matching between consecutive slices with no structure penalty and no memory. On the MOSTA lung airway task, SOCS reports 79.2% cell-to-descendant mapping accuracy for W-OT. Moscot, a widely used transport toolkit run pairwise, scores 78.8% on the same task in that paper. These two anchor the lower end.

The strongest existing method is SOCS itself, which reports 99.3% mapping accuracy on MOSTA lung airway epithelium with complete slices. It is the right competitor because it already handles structure and imbalance through unbalanced transport. Any gain we show must therefore come from joint reasoning across time, not from a better per-pair cost. We will run SOCS and our method on identical preprocessed slices, the same metacell resolution, and the same transition cost. Each gets the same grid-search budget over its unbalancedness and regularization parameters, tuned on a held-out set of gap configurations.

The method counts as beating SOCS only if two things hold. It must significantly improve mapping accuracy for populations missing from an intermediate slice, across many random gap draws. And it must stay within one percentage point of SOCS on populations present in every slice, since helping the gapped lineages by corrupting the others would be no win.

The key ablation removes the storage arcs, which makes the joint problem split exactly into chained SOCS. A second ablation keeps storage arcs but drops the same-state restriction. It tests whether the benefit comes from carrying state through the gap or merely from extra flexibility in where mass goes.

Why not just…?

Why not just tune the unbalanced-transport penalties in SOCS so disappearing mass is cheaper to destroy and recreate? Destroying and recreating mass cuts the lineage by definition: the population recreated at $t+1$ has no ancestor at $t-1$. Cheaper penalties also let mass disappear spuriously in complete slices. Our penalty sweep reports gapped and non-gapped accuracy together as the penalties vary, so a reader can check whether any setting of SOCS reaches our gapped accuracy without losing accuracy on complete populations.

Why not just map $t_1$ directly to $t_3$ whenever a gap is suspected? This skip heuristic is a real threat when only one slice has a gap and we know which one. It needs to know where the gap is, and it throws away $t_2$ information for every population that was sampled. We will run it with the gap location given to it for free, which is the most favorable setting possible. Our method must match it on gapped lineages while beating it on sampled ones. If the skip heuristic matches on both, the storage construction adds little, and we will report that.

Why not just fill in the missing niche at $t_2$ with a generative model and then run SOCS? Filling in requires deciding what is missing and where, which is the quantity we are trying to estimate. It also produces invented cells that later analyses may treat as observed. We include a filled-in baseline that uses cells sampled from the matching state at the neighboring timepoints. We also compare its implied missing mass with our reservoir estimate against the known dropout.

Why not just use general multi-marginal transport over all slices? Our problem is a structured special case of multi-marginal transport. Unrestricted multi-marginal couplings grow exponentially with the number of slices, while our time-expanded graph grows linearly in the number of arcs. The practical question is whether the same-state restriction costs accuracy. The ablation that drops that restriction answers it directly.

Proposed Experiments and Decisive Checks

MOSTA with controlled gaps. We remove a contiguous structure, such as the lung airway epithelium, from one intermediate slice, and separately from two non-adjacent slices, over many random draws. We report cell-to-descendant mapping accuracy in SOCS's protocol, split into gapped and non-gapped populations, along with the absolute error of the reservoir estimate against the true removed mass. The decisive result is a large accuracy gap over SOCS on gapped lineages with parity on non-gapped ones. We repeat the protocol on the SOCS mouse ovary MERFISH series, for which no reported numerical result was found on Lacuna, so all methods are rerun there.

Simulated tumors under therapy. We use an agent-based simulator coupled to diffusion equations, of the kind used in the Graph Neural ODE study, with drug-sensitive, drug-tolerant, and resistant cells. Initial cell layouts come from cancer sections in HEST-1k, and we reimplement the simulator if it is not released. Destructive sampling is imitated by cutting random small section windows at each time, so that resistant clusters are intermittently missed. The primary metric is the recovered fraction of resistant-lineage ancestry at early times against the simulator's true lineage. We cite the Graph Neural ODE study's resistant-fraction result (0.282 predicted against 0.242 true) only as context, since it addresses forecasting rather than lineage recovery and the numbers are not comparable.

Kill test. If storage arcs improve gapped-lineage accuracy by less than the variation across gap draws, or if the skip heuristic given the gap location matches them everywhere, we conclude that store-and-forward adds nothing beyond careful pairwise transport and report a negative result.