Trajectory Seriation via Spectral Tangent Alignment and Global Embedding

We study linear seriation from noisy point clouds: given samples from an unknown one-dimensional curve embedded in $\mathbb{R}^d$, recover their latent order along the curve, up to reversal. Unlike much of the seriation literature, which starts from a precomputed similarity matrix, this setting retains ambient coordinates and therefore local geometric information. We propose STAGE, a geometric ordering method that estimates local tangent directions by neighborhood PCA, resolves their sign ambiguity through a graph-wide $\mathbb{Z}_2$ synchronization step, and constructs signed local displacement estimates by projecting ambient differences onto the oriented tangents. These increments are then integrated into a global scalar embedding through an inhomogeneous least-squares problem, equivalently a Laplacian linear system with a nonzero right-hand side, and the final order is obtained by sorting the embedding. We prove a finite-sample Kendall's $\tau$ recovery bound that makes explicit the roles of curvature, noise, neighborhood scale, sampling density, and graph connectivity. Empirically, STAGE gives accurate and fast order recovery on high-dimensional synthetic curves, compares favorably with spectral seriation, 1D UMAP, 1D t-SNE, Recanati's method, LTSA, and SABRE, and produces meaningful pseudotime orderings on single-cell RNA-seq datasets.

In single-cell data, it is common to have data sets that seem to follow some sort of "trajectory" when visualized, for example in a sample of cells which represent different stages of development. It can be of interest to find an order to the points in that trajectory, e.g. to understand which cells were at an earlier stage and which came later. We have created a method called STAGE to determine the order of points in a trajectory that works in 3 steps. We start by looking in the neighborhood of a certain point and determining the direction of the trajectory in that small area. We then ensure that all these directions flow the same way along the path. The final step is to put these directions together to assign each point its place on the path, telling us their order. Our method works very well even when the trajectories we're considering are very noisy, making it useful in a variety of situations. Furthermore, we're able to provide conditions under which we know that our method will successfully recover the correct order.