Active Seriation: Efficient Ordering Recovery with Statistical Guarantees

James Cheshire; Yann Issartel

stat.MLMar 16, 2026

Active Seriation: Efficient Ordering Recovery with Statistical Guarantees

Authors: James Cheshire, Yann Issartel

Organizations: LTCI, Télécom Paris, Institut Polytechnique de Paris

Abstract

Active seriation aims at recovering an unknown ordering of $n$ items by adaptively querying pairwise similarities. The observations are noisy measurements of entries of an underlying $n$ x $n$ permuted Robinson matrix, whose permutation encodes the latent ordering. The framework allows the algorithm to start with partial information on the latent ordering, including seriation from scratch as a special case. We propose an active seriation algorithm that provably recovers the latent ordering with high probability. Under a uniform separation condition on the similarity matrix, optimal performance guarantees are established, both in terms of the probability of error and the number of observations required for successful recovery.

Figures & tables

Figure 1: R-matrix & a permuted version.

Figure 2: Robinson matrices for scenarios (1)-(4), from left to right.

Panel of Figure 3 — Figure 3: Empirical error probabilities for ASII and three benchmark methods as the parameter $\Delta$ varies. Scenarios (1-2-3-4) are displayed from left to right and top to bottom. Each experiment uses $n=10$ items and $T=10{,}000$ observations. For each value of $\Delta$ , 100 Monte Carlo runs are split into $10$ equal groups; error bars show the $0.1$ and $0.9$ quantiles of the empirical error across groups.

Panel of Figure 4 — Figure 4: Similarity matrix $M$ of a single-cell RNA-seq dataset before and after reordering by ASII. The recovered ordering reveals a clear block-diagonal structure consistent with developmental progression: dissimilar regions (blue) are pushed to the boundaries, while groups of highly similar cells (yellow and green) align along the diagonal.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Representation of the Robinson matrices $R^{(s)}$ , $s\in\{1,2,3,4\}$ , corresponding to the four scenarios. Scenarios (1)–(3) have a minimal gap $\Delta$ , while in scenario (4) the minimal gap is random but lower bounded by $\Delta$ . The matrix $R^{(1)}$ is Toeplitz, while $R^{(2)}$ , $R^{(3)}$ , and $R^{(4)}$ are not. Here, $\Delta=0.2$ .

Panel of Figure 6 — Figure 6: Empirical error probabilities for Adaptive Sorting , ASII , Spectral Seriation , and Naive Insertion as the parameter $\Delta$ varies. Scenarios (1)–(4) are displayed from left to right and top to bottom. Each experiment involves $n=10$ items and $T=10{,}000$ observations. Each point is averaged over 100 Monte Carlo runs.

Panel of Figure 7 — Figure 7: Same experiment as in Fig. 6 , with error bars added. Empirical error probabilities for Adaptive Sorting , ASII , Spectral Seriation , and Naive Insertion as the parameter $\Delta$ varies. For each value of $\Delta$ , the 100 Monte Carlo runs are split into 10 equal groups; the error bars indicate the 0.1 and 0.9 quantiles of the empirical error across these groups.

Panel of Figure 8 — Figure 8: PGC similarity matrix before and after reordering by ASII . Left: random permutation; right: ordering inferred by ASII . The recovered structure highlights coherent developmental trajectories among cells.

Active Learning

Active learning selects the examples, labels, features, or experiments most useful for improving a model under limited budgets.

See all 288 papers

Sorting from Counterexamples
Aug 21, 2026Noga Alon, Shay Moran, Shlomo MoranQuery Complexity Pairwise Ranking
Princeton University, Princeton, NJ 08544, USA, and Tel Aviv University, Tel Aviv 69978, Israel. · Technion – Israel Institute of Technology and Google Research. · Technion – Israel Institute of Technology.
Active multiple matrix completion with adaptive confidence sets
May 4, 2026Andrea Locatelli, Alexandra Carpentier, Michal ValkoActive Learning Multi-Task Learning
OvGU Magdeburg · SequeL team, Inria Lille
Learning Permutation from Structure Without Supervision
May 25, 2026Ran Eisenberg, Ofir LindenbaumUnsupervised Learning Jigsaw Puzzle Solving
Faculty of Engineering, Bar-Ilan University, Ramat Gan, Israel. · Faculty of Engineering, Bar-Ilan

Aug 21, 2026J/K move · Enter open · S save

Sorting from Counterexamples

Noga Alon, Shay Moran, Shlomo Moran

Princeton University, Princeton, NJ 08544, USA, and Tel Aviv University, Tel Aviv 69978, Israel. · Technion – Israel Institute of Technology and Google Research. · Technion – Israel Institute of Technology.

Query Complexity Pairwise Ranking Active Learning

Open paper AskPDF arXiv

Consider the following problem of learning an unknown linear order on

n

items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to identify the unknown order using as few queries as possible. We study this problem when up to

k

of the returned counterexamples may be untruthful, where

k

is not known in advance. We determine the optimal query complexity up to constant factors:

Θ(n\log n + nk).

Thus, while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order

n

. The upper bound is based on a geometric representation of permutations and Grünbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in

\mathbb{R}^d

, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of

O(d^2\log n+dk)

and a lower bound of

Ω(d\log n+dk)

, leaving a factor of

d

gap in the noiseless term.

Abstract

Active Learning

Explore similar work

Sorting from Counterexamples

Active multiple matrix completion with adaptive confidence sets

Learning Permutation from Structure Without Supervision