Spectral-truncated noncommutative graph operators for few-label single-cell transition forecasting and rare-state recovery

1Background and Motivation

Single-cell measurements resolve differentiation, activation and treatment response as continuous trajectories. A recurring goal is to forecast the state a cell will occupy under conditions absent from the training set — a donor not yet profiled, a batch run later, a later point along a developmental trajectory, an untested perturbation.

The standard tool for this few-label regime is graph-based semi-supervised learning: predictions are diffused over the cell k-nearest-neighbour (kNN) graph so that each cell borrows statistical strength from its manifold neighbourhood. The diffusion operator used throughout single-cell analysis is the symmetric normalised adjacency $S=D^{-1/2}AD^{-1/2}$. Two properties of this object limit it for transition forecasting.

We take both properties as design targets and build a different object: a pseudotime-directed, spectrally truncated, inductive graph operator. Rare states — transient progenitors, treatment-resistant clones — are the biologically decisive targets, and recovering them with calibrated uncertainty is the open problem the operator is designed to solve.

2The Operator

Fix $n$ cells embedded in $\mathbb{R}^{d}$ with a symmetric kNN adjacency $A$, degrees $D=\operatorname{diag}(d_i)$ and pseudotime $t\in\mathbb{R}^n$. The forecaster is built from three coupled constructions, each tied to a measured effect.

Pseudotime-directed propagator (noncommutativity)

Each directed edge $i\!\to\! j$ is reweighted by a bounded forward kernel of the pseudotime increment and row-normalised, $$ W_{ij}=A_{ij}\,\exp\!\bigl(\beta\tanh\tfrac{t_j-t_i}{\tau}\bigr),\qquad P=D_W^{-1}W, $$ giving a row-stochastic but non-self-adjoint propagator that transports labels along the trajectory. Its relative non-normality $\nu(P)=\|PP^{\top}-P^{\top}P\|_F/\|P\|_F^2$ is strictly positive and increases with the directional strength $\beta$; this is the single-cell instance of the operator noncommutativity exploited by $C^{*}$-algebraic kernel machines.

Spectral truncation (band-limiting)

Let $U_r$ collect the leading $r$ graph-Fourier modes (the eigenvectors of $S$ for its largest eigenvalues). Restricting the diffusion to their span $\Pi_r=U_rU_r^{\top}$ is a spectral truncation: it is the provably optimal rank-$r$ low-pass approximation of $S$, and the truncated, lazy directed transport $$ B=U_r^{\top}\bigl((1-\varepsilon)I+\varepsilon P\bigr)U_r $$ is an $r\times r$ matrix admitting a closed-form solve. Truncation also makes the operator algebra noncommutative: the truncated multiplication operators $M_\phi^{(r)}=U_r^{\top}\operatorname{diag}(\phi)U_r$ do not commute — the spectral-truncation noncommutativity of noncommutative geometry, here on the cell graph.

Inductive Nyström extension (no transductive confound)

The band-limited field is solved on the training cells, $F^{\star}=U_r(I-\alpha B)^{-1}(1-\alpha)U_r^{\top}F_0$, and a held-out cell is labelled by a Gaussian-weighted average of that field over its nearest training cells. No test–test edge and no held-out connectivity is ever used at inference, so the forecaster is genuinely inductive — the matched inductive control that resolves the transductive confound of symmetric smoothing.

A split-conformal layer calibrates the rare-state forecast with distribution-free coverage, and the degree-0 persistence barcode of the cell cloud replaces the passive connected-component count of prior work with an informative multiscale topology signal that guides active sampling.

3Principal Contributions

1. A pseudotime-directed, noncommutative graph propagator. Reweighting kNN edges by a bounded forward kernel of the pseudotime increment yields a non-self-adjoint operator whose non-normality is strictly positive and grows with the directional strength; the directed transport carries labels along the trajectory, which a symmetric smoother cannot do.
2. Spectral truncation with proved optimality. Band-limiting the diffusion to the leading $r$ graph-Fourier modes is the optimal rank-$r$ low-pass approximation of the symmetric backbone (Eckart–Young–Mirsky), and the truncated multiplication operators on the cell graph do not commute — the spectral-truncation noncommutativity carried into the single-cell setting.
3. An inductive operator that removes the transductive confound. An out-of-sample Nyström extension labels held-out cells from the training field alone; the operator beats a matched inductive kNN classifier on accuracy on all four transfer protocols (mean $0.6856$ vs $0.5992$, gain $0.0864$), with the gain not attributable to a transductive information advantage.
4. Rare-state recovery and forward-in-time rescue. The operator lifts mean rare-state recall to $0.3322$ from a near-zero baseline ($0.0151$), and the directional transport raises forward-in-time (time-split) accuracy by $0.1749$ over the point classifier and by $0.0849$ over symmetric label propagation.
5. Distribution-free conformal calibration. A split-conformal layer attains realised marginal coverage $0.8968$ against a target of $0.90$ on an exchangeable hold-out, and temperature scaling cuts expected calibration error from $0.1375$ to $0.0369$ — turning the calibration penalty of graph smoothing into a calibration guarantee.
6. A genuine multiscale topology signal. The degree-0 persistence barcode (computed exactly by union–find) replaces a constant connected-component count; a persistence-guided active sampler raises rare-state recall to $0.3941$ against $0.0481$ for random querying.
7. Operator-theoretic guarantees and deterministic reproducibility. Five theorems certify truncation optimality, noncommutativity, well-posedness, inductive consistency and conformal coverage; a pip-installable package (topocell 0.2.0) regenerates every table, figure and number from a single seeded summary.json.

4Theoretical Guarantees

The statements below are transcribed from the manuscript’s self-contained theory section, each annotated with a one-line reading. Together they establish that the operator is well posed, genuinely noncommutative, optimally band-limited, inductively consistent and conformally valid.

5Empirical Validation

The full-scale configuration uses $n=3000$ cells over $n_{\text{seeds}}=5$ seeds, truncation rank $r=80$, directional strength $\beta=1.0$. For each leakage-checked split, accuracy, ECE and rare-state recall are reported as mean $\pm$ 95% CI ($1.96\,s/\sqrt{n}$) for the inductive spectral-truncated directed-diffusion operator (STDD) and the matched inductive kNN baseline (kNN). Higher accuracy and recall are better; lower ECE is better. The better value in each split is in bold. Every entry is generated from the seeded results/summary.json.

6Interactive Illustration

A self-contained, client-side illustration of the central mechanism, mirroring the manuscript’s headline comparison. A schematic cell-graph carries a deliberately rare late-tip state; sweeping the operator strength interpolates from the matched kNN point classifier (no operator) to the full spectral-truncated directed operator. As the operator engages, the displayed accuracy and rare-state recall move from the measured kNN endpoint toward the measured inductive-STDD endpoint for the selected split, making the per-protocol accuracy–recall behaviour of Table 1 directly visible.

7Significance and Impact

Within a controlled benchmark, a pseudotime-directed, spectrally truncated, inductive graph operator improves single-cell transition forecasting where the standard symmetric smoother is weakest — recovering a rare state the point classifier almost never finds, and rescuing forward-in-time extrapolation — while removing the transductive confound and supplying distribution-free calibration.

For computational biology, the result is a directional, calibrated forecaster that converts the arrow of pseudotime into rare-state recovery, with a persistence-guided annotation policy that targets the sparse manifold pockets where rare cells reside. For machine learning under covariate shift more broadly, the operator carries the spectral-truncation and noncommutativity machinery of $C^{*}$-algebraic kernel machines into a graph-diffusion forecaster and pairs it with an inductive extension that makes the diffusion gain attributable to one mechanism rather than to a confounded design choice. The accompanying theory certifies that the deployed solve faithfully realises a well-posed, gauge-invariant estimator with a finite-sample coverage guarantee.

The decisive next step is to repeat exactly this comparison on real scRNA-seq and perturbation-screen data, for which the repository provides intentionally unexercised ingest stubs. The operator extends naturally to inferred, noisy pseudotime, to higher-order persistence, and to a learned directed propagator in place of the fixed-kernel transport.

Limitations (stated in full)

8Reproducibility

The reference implementation is the pip-installable package topocell 0.2.0 at submission/code (CPU-only: NumPy, SciPy, scikit-learn, NetworkX, Matplotlib). A single seeded results/summary.json is the authoritative record for every table, figure and number; two runs produce a byte-identical artifact modulo provenance. The manuscript’s tables are generated verbatim from it. No value here is hand-entered.

# 1. install the CPU reference package
cd submission/code
pip install .            # installs the `topocell` package
# pip install .[gpu]    optional torch backend

# 2. reproduce every number, table and figure
pytest tests/                                  # operator / conformal / persistence property tests
python scripts/run.py --config configs/full.yaml --out results   # -> results/summary.json (~32 s, 621 MB)
python scripts/make_tables.py                  # results/main_results.tex, extended_results.tex
python scripts/make_figures.py                 # figures/fig_{schematic,lineage,forecast,operator,calibration}.pdf
python scripts/audit_claims.py                 # readiness gate: traceable numbers, integrity flags

# 3. build the manuscript (demo of main.tex)
cd .. && tectonic main.tex                      # or: latexmk -pdf main.tex

Three integrity gates must pass before any metric is recorded: grouping splits are leakage-free, the directed propagator is non-normal, and the rare state is present. A failed gate halts the run rather than emitting a number.

No biological data were used or generated. All results derive from a seeded synthetic lineage regenerated deterministically by the code.

9References

The construction sits at the intersection of several literatures. Its diffusion backbone is graph-based semi-supervised learning — label propagation and learning with local and global consistency (Zhu & Ghahramani; Zhou et al.). Its arrow comes from single-cell pseudotime, RNA-velocity and fate mapping (Haghverdi et al.; La Manno et al.; Lange et al.). It is made inductive by an out-of-sample Nyström extension (Williams & Seeger; Bengio et al.), calibrated by distribution-free conformal prediction (Vovk et al.; Lei et al.), and read out with a persistent-homology descriptor (Edelsbrunner & Harer; Carlsson). The non-self-adjoint propagator is the single-cell instance of the operator noncommutativity that recent $C^{*}$-algebraic spectral-truncation kernel machines exploit for expressiveness (Hashimoto et al.; van Suijlekom).

1. Y. Hashimoto, A. Hafid, M. Ikeda, and H. Kadri, “Spectral truncation kernels: Noncommutativity in $C^{*}$-algebraic kernel machines,” J. Mach. Learn. Res. (2026); arXiv:2405.17823.
2. W. D. van Suijlekom, “Gromov–Hausdorff convergence of state spaces for spectral truncations,” J. Geom. Phys. 162, 104075 (2021).
3. D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf, “Learning with local and global consistency,” Adv. Neural Inf. Process. Syst. 16, 321 (2004).
4. X. Zhu and Z. Ghahramani, “Learning from labeled and unlabeled data with label propagation,” Tech. Rep. CMU-CALD-02-107, Carnegie Mellon University (2002).
5. L. Haghverdi, M. Büttner, F. A. Wolf, F. Buettner, and F. J. Theis, “Diffusion pseudotime robustly reconstructs lineage branching,” Nat. Methods 13, 845 (2016).
6. C. Trapnell, D. Cacchiarelli, J. Grimsby et al., “The dynamics and regulators of cell fate decisions are revealed by pseudotemporal ordering of single cells,” Nat. Biotechnol. 32, 381 (2014).
7. F. A. Wolf, P. Angerer, and F. J. Theis, “SCANPY: Large-scale single-cell gene expression data analysis,” Genome Biol. 19, 15 (2018).
8. G. La Manno, R. Soldatov, A. Zeisel et al., “RNA velocity of single cells,” Nature 560, 494 (2018).
9. M. Lange, V. Bergen, M. Klein et al., “CellRank for directed single-cell fate mapping,” Nat. Methods 19, 159 (2022).
10. E. Becht, L. McInnes, J. Healy et al., “Dimensionality reduction for visualizing single-cell data using UMAP,” Nat. Biotechnol. 37, 38 (2019).
11. L. McInnes, J. Healy, and J. Melville, “UMAP: Uniform Manifold Approximation and Projection for dimension reduction,” arXiv:1802.03426 (2018).
12. R. R. Coifman and S. Lafon, “Diffusion maps,” Appl. Comput. Harmon. Anal. 21, 5 (2006).
13. M. Belkin and P. Niyogi, “Laplacian eigenmaps for dimensionality reduction and data representation,” Neural Comput. 15, 1373 (2003).
14. L. van der Maaten and G. Hinton, “Visualizing data using t-SNE,” J. Mach. Learn. Res. 9, 2579 (2008).
15. U. von Luxburg, “A tutorial on spectral clustering,” Stat. Comput. 17, 395 (2007).
16. F. Chung, “Laplacians and the Cheeger inequality for directed graphs,” Ann. Comb. 9, 1 (2005).
17. C. K. I. Williams and M. Seeger, “Using the Nyström method to speed up kernel machines,” Adv. Neural Inf. Process. Syst. 13, 682 (2001).
18. Y. Bengio, J.-F. Paiement, P. Vincent et al., “Out-of-sample extensions for LLE, Isomap, MDS, eigenmaps, and spectral clustering,” Adv. Neural Inf. Process. Syst. 16, 177 (2004).
19. V. Vovk, A. Gammerman, and G. Shafer, Algorithmic Learning in a Random World (Springer, 2005).
20. J. Lei, M. G’Sell, A. Rinaldo, R. J. Tibshirani, and L. Wasserman, “Distribution-free predictive inference for regression,” J. Am. Stat. Assoc. 113, 1094 (2018).
21. C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger, “On calibration of modern neural networks,” in Proc. Int. Conf. Mach. Learn. (ICML) (2017), p. 1321.
22. H. Edelsbrunner and J. L. Harer, Computational Topology: An Introduction (American Mathematical Society, 2010).
23. G. Carlsson, “Topology and data,” Bull. Am. Math. Soc. 46, 255 (2009).
24. T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in Proc. Int. Conf. Learn. Represent. (ICLR) (2017).
25. B. Settles, “Active learning literature survey,” Comput. Sci. Tech. Rep. 1648, University of Wisconsin–Madison (2009).
26. W. Saelens, R. Cannoodt, H. Todorov, and Y. Saeys, “A comparison of single-cell trajectory inference methods,” Nat. Biotechnol. 37, 547 (2019).
27. M. D. Luecken and F. J. Theis, “Current best practices in single-cell RNA-seq analysis: A tutorial,” Mol. Syst. Biol. 15, e8746 (2019).