# Dynamic Ranking and Translation Synchronization

arXiv: https://arxiv.org/abs/2207.01455 · HTML: https://mlsanity.com/paper/2207.01455/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 58 references that are in the map.
- First posted on arXiv 4 Jul 2022.

## Builds on (most cited first, 13 of 13)

- [Simple, Robust and Optimal Ranking from Pairwise Comparisons](https://mlsanity.com/paper/1512.08949/) (2015)
- [Spectral Method and Regularized MLE Are Both Optimal for Top-K Ranking](https://mlsanity.com/paper/1707.09971/) (2017)
- [Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues](https://mlsanity.com/paper/1510.05610/) (2015)
- [Tightness of the maximum likelihood semidefinite relaxation for angular synchronization](https://mlsanity.com/paper/1411.3272/) (2014)
- [Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers](https://mlsanity.com/paper/1605.08400/) (2016)
- [Minimax Rates and Efficient Algorithms for Noisy Sorting](https://mlsanity.com/paper/1710.10388/) (2017)
- [Sync-Rank: Robust Ranking, Constrained Ranking and Rank Aggregation via Eigenvector and Semidefinite Programming Synchronization](https://mlsanity.com/paper/1504.01070/) (2015)
- [Solving Orthogonal Group Synchronization via Convex and Low-Rank Optimization: Tightness and Landscape Analysis](https://mlsanity.com/paper/2006.00902/) (2020)
- [Ranking and synchronization from pairwise measurements via SVD](https://mlsanity.com/paper/1906.02746/) (2019)
- [Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality](https://mlsanity.com/paper/1703.08729/) (2017)
- [Nonparametric Estimation in the Dynamic Bradley-Terry Model](https://mlsanity.com/paper/2003.00083/) (2020)
- [Graph Resistance and Learning from Pairwise Comparisons](https://mlsanity.com/paper/1902.00141/) (2019)
- [Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank Centrality Method](https://mlsanity.com/paper/2109.13743/) (2021)

## Built on by (most cited first, 4 of 4)

- [Improved theoretical guarantee for rank aggregation via spectral method](https://mlsanity.com/paper/2309.03808/) (2023)
- [A model for efficient dynamical ranking in networks](https://mlsanity.com/paper/2307.13544/) (2023)
- [Dynamic angular synchronization under smoothness constraints](https://mlsanity.com/paper/2406.04071/) (2024)
- [Joint estimation of smooth graph signals from partial linear measurements](https://mlsanity.com/paper/2505.23240/) (2025)

## Abstract (arXiv)

In many applications, such as sport tournaments or recommendation systems, we have at our disposal data consisting of pairwise comparisons between a set of n items (or players). The objective is to use this data to infer the latent strength of each item and/or their ranking. Existing results for this problem predominantly focus on the setting consisting of a single comparison graph G. However, there exist scenarios (e.g., sports tournaments) where the the pairwise comparison data evolves with time. Theoretical results for this dynamic setting are relatively limited and is the focus of this paper. We study an extension of the translation synchronization problem, to the dynamic setting. In this setup, we are given a sequence of comparison graphs (Gt)t∈ T, where T subset [0,1] is a grid representing the time domain, and for each item i and time t∈ T there is an associated unknown strength parameter z^*t,i∈ ℝ. We aim to recover, for t∈T, the strength vector z^*t=(z^*t,1,dots,z^*t,n) from noisy measurements of z^*t,i-z^*t,j, where i,j is an edge in Gt. Assuming that z^*t evolves smoothly in t, we propose two estimators -- one based on a smoothness-penalized least squares approach and the other based on projection onto the low frequency eigenspace of a suitable smoothness operator. For both estimators, we provide finite sample bounds for the ℓ2 estimation error under the assumption that Gt is connected for all t∈ T, thus proving the consistency of the proposed methods in terms of the grid size |T|. We complement our theoretical findings with experiments on synthetic and real data.