High-throughput single-cell data is now collected across large patient cohorts.
Understanding patient-level heterogeneity from cellular-level data motivates phenoscaping: embedding each single-cell distribution as a "datapoint," with distances given by optimal transport (OT).
Computing geometry-aware OT at this scale, between all pairs of patient datasets, remains an open challenge, since existing methods either rely on Euclidean ground metrics that distort manifold structure or fail under sparse, unevenly sampled, or large-scale data.
We present Pheno-GS (Phenoscape-scale Geodesic Sinkhorn), which computes accurate, scalable geodesic transport distances under noisy, unbalanced, large-scale settings via three components:
- graph connectivity regularization for well-defined geodesics on sparse/disconnected manifolds;
- an unbalanced OT formulation via KL marginal penalties;
- a batched matrix algorithm computing all pairwise distances in one heat diffusion (over 200 × faster than Geodesic Sinkhorn for 500 distributions).
We validate Pheno-GS on synthetic benchmarks and a CyTOF perturbation dataset.