How Many Neighbors Does a Dissociated Cell Need to Find Its Place?

Single-cell RNA sequencing measures the full set of active genes in thousands of individual cells, but only after the tissue has been digested into a suspension. That step erases where each cell sat and who it touched. Current methods try to put cells back by matching each one, on its own, against a spatial reference map. This proposal asks a different question that graph theory can answer precisely: if each cell is described by its type plus the set of types among its physical neighbors, how many distinguishable types does a tissue need before every position becomes uniquely recoverable? And how does that requirement change as dissociation breaks contacts? Graph theorists have studied exactly this property under the name neighbor-locating coloring: an assignment of colors to vertices in which no two same-colored vertices see the same set of colors around them. They have proven sharp limits on how many vertices such a coloring can tell apart, and they have shown that deleting edges can make identification harder rather than merely less complete.

We propose to turn those results into a recoverability audit for spatial reconstruction. We will measure, on tissues whose cell graphs are known, how far the observed cell-type labeling is from being neighbor-locating. We will track how that distance changes under simulated partial dissociation, meaning progressive loss of contacts until only doublets and triplets survive, as in physical-proximity sequencing. We will then test whether this graph-level identifiability predicts which cells current mapping methods misplace. Extremal constructions, the graphs that sit exactly at the proven limits, serve as adversarial test tissues. They show where any neighbor-informed method must fail.

Core Claim

Spatial recoverability from dissociated cells is limited by a combinatorial capacity, not only by gene count or algorithm choice, and that capacity is computable. Chakraborty et al. prove that a planar graph with a neighbor-locating coloring using $k$ colors has at most

$$n \le k\sum_{i=1}^{6}(7-i)\binom{k-1}{i} - 12$$

vertices. Here $n$ is the number of vertices and $k$ is the number of colors. Evaluating this bound ourselves gives about 353 positions for $k=5$, 810 for $k=6$, 1,731 for $k=7$, and 3,516 for $k=8$. A roughly planar surface graph over the 3,039 bins of the Drosophila stage-6 atlas used in the DREAM challenge therefore cannot be resolved by type-plus-neighbor-types signatures unless at least eight distinguishable classes exist. Tanevski et al. report that 40–60 landmark genes preserve the nine major embryonic clusters and that performance collapses at 20 genes. We do not claim the bound explains that collapse. We claim it yields a testable hypothesis: the collapse happens when the number of classes the reduced gene panel can still separate falls below the neighbor-locating capacity the tissue requires.

The second claim concerns dissociation. The same authors and their CALDAM paper prove that the neighbor-locating number is not monotone under taking subgraphs: removing vertices or edges can increase the number of colors needed. Partial dissociation is an edge-deletion process. So recoverability from neighbor fragments should degrade non-uniformly, with sharp losses at specific fragment sizes and tissue motifs rather than a smooth decline. No prior work measures this.

Relation to Prior Work

Three lines of work motivate the proposal by documenting the gap. The DREAM challenge (Tanevski et al.) benchmarks 34 algorithms that map dissociated cells to atlas bins one cell at a time. It shows that gene properties such as entropy and spatial autocorrelation matter more than architecture, but it never treats the atlas as a graph. Stereoscope deconvolves multi-cell spots as independent mixtures and also ignores spot adjacency. The cell-communication review by Shao et al. describes ProximID, which sequences physically touching doublets and triplets. That is a direct source of neighbor information, but it has no theory of how much such fragments can reveal. Our proposal supplies that theory and its measurement.

Spatial graph methods supply the graph construction but constrain the claims we can make. STELLAR runs a graph convolutional network over distance-threshold cell graphs and gains 11% annotation accuracy from spatial context. Slide Graph uses Delaunay triangulation, which connects nearby points into non-overlapping triangles and always produces a planar graph. Squidpy provides k-nearest-neighbor, radius, and Delaunay graphs together with neighborhood enrichment statistics. All three take the graph as given input and never ask whether neighborhoods identify positions. We reuse their graph builders unchanged. The Delaunay choice matters for us because it is what makes the planar bound applicable.

The extremal results supply the method. Beyond the capacity bound, the sharpness constructions of Chakraborty et al. give explicit graphs that reach the limit. We will adapt these into adversarial tissue layouts. The isolation-number work of Wei et al. characterizes when deleting closed neighborhoods leaves only isolated vertices and edges, which is a formal analogue of dissociation down to singletons and doublets. We use it only as a reference model for the endpoint of dissociation, not as a central tool.

Research Program

The first component is an identifiability audit. For each tissue with known coordinates, we build Delaunay and k-nearest-neighbor graphs and assign cells their reference types. For each cell we compute its signature, defined as its own type plus the set of types among its neighbors, and report the fraction of cells whose signature is unique. We also compute two stronger variants: the multiset version, which keeps neighbor counts, and two-hop refinement, which repeats the signature step once over neighbors' signatures. Together these give a ladder from cell-alone matching to full neighborhood matching. We additionally estimate the minimum number of merged or split classes needed to make the labeling neighbor-locating. Because computing the neighbor-locating number exactly is NP-complete (Chakraborty et al.), we use integer programming on small regions and greedy refinement on large ones, and we report the gap between the two.

The second component is a dissociation simulator. Starting from the intact graph, we delete edges at random, preferentially within cell types with weak adhesion, or along stromal boundaries. We stop at stages that mimic surviving doublets and triplets. At each stage we recompute identifiability and record any non-monotone jumps predicted by the subgraph paradox.

The third component links the audit to real mapping error. On DREAM data we ask whether a cell's signature ambiguity predicts its mapping error under the top challenge methods, after controlling for the gene-level properties Tanevski et al. identified. We then add a simple neighbor-aware mapper: expression-based mapping followed by a consistency step that rescores candidate bins using simulated doublet and triplet partners. This tests whether the identifiability gain can actually be captured in practice.

The fourth component builds extremal test tissues. We embed the sharpness constructions as planar layouts with the same type counts and degree distribution as real tissues. We then measure how mapping methods and STELLAR degrade relative to degree-matched random planar graphs.

Baselines

The naive reference point is expression-only mapping. Each dissociated cell is assigned to its best-correlated atlas bin using the 60, 40, or 20 DREAM landmark gene sets, with no neighbor information at all. The strongest existing method on this benchmark is the DREAM Wisdom-of-the-Crowds consensus of the top ten methods, which Tanevski et al. report reaches an atlas-correlation score $s_1$ of about 0.73 with 60 genes. We will rerun the publicly described top methods on identical cells, gene subsets, and scoring code. Our neighbor-aware mapper gets the same tuning budget, a grid search on the same held-out split. Beating the baseline means improving $s_1$ and the distance-accuracy score $s_2$ at 20 genes, where the consensus collapses, while not losing ground at 60 genes.

For spatial annotation on CODEX Barrett's esophagus, the strongest baseline is STELLAR at 93% accuracy (STELLAR). There we do not try to beat STELLAR. Instead we test whether our per-cell ambiguity score predicts STELLAR's errors better than cell-type frequency does. For the zebrafish DREAM data and Squidpy's seqFISH gastrulation data, we found no reported per-cell numerical result on Lacuna, so we rerun all baselines ourselves.

The key ablation separates neighbor information from the combinatorial structure. We compare signatures that use neighbor-type sets, multisets, and shuffled neighbors that keep each cell's degree but randomize which types it touches. Only the real-neighbor conditions should carry identifiability.

Why not just…?

Why not just count unique neighborhood signatures empirically and skip the extremal theory? This is a real threat, and the audit itself is that empirical count. The theory adds two things counting cannot. First, it gives a necessary condition that holds before any data are seen: fewer than eight classes cannot resolve about 3,000 planar positions. Second, it supplies adversarial graphs that show worst-case rather than typical behavior. We will test directly whether bound-derived capacity, measured as the ratio of $n$ to the $k$-color limit, predicts mapping error beyond the empirical uniqueness fraction. If it adds nothing, we will report the audit as the contribution and present the theory as interpretation only.

Why not just add more landmark genes? More genes raise $k$, the number of separable classes, and the DREAM results already show that 60 genes beat 20. But dissociated cells measured on the full transcriptome still map poorly whenever distinct positions share expression. Neighbor fragments break those ties without new genes. The 20-gene regime tests whether neighbor signatures recover what the gene reduction lost.

Why not just profile the tissue with spatial transcriptomics instead? Spot-based platforms mix 10–50 cells per spot (Stereoscope) and give up the depth that dissociation provides. Partial dissociation that keeps doublets and triplets is a middle route. Our simulator quantifies what fragment sizes buy, which tells experimentalists whether that route is worth pursuing.

Why not just use gene entropy and spatial autocorrelation, which already explain DREAM performance? Those are per-gene properties. Our score is a per-cell, graph-level property. The decisive check is a regression of per-cell error on both kinds of predictors. If our score adds no explained variance, the claim fails.

Decisive Checks

Three outcomes would settle the proposal. The first is whether per-cell signature ambiguity predicts DREAM mapping error after controlling for gene-level properties. The second is whether simulated dissociation shows the non-monotone identifiability jumps that the subgraph paradox predicts on real tissue graphs, as opposed to only on contrived ones. The third is whether the neighbor-aware mapper recovers $s_1$ at 20 genes toward the 60-gene consensus level of 0.73. A negative result on the first check would mean neighborhood combinatorics are not the limiting factor in current reconstruction, which is itself a useful and publishable conclusion.