# Belief propagation for permutations, rankings, and partial orders

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 33 references that are in the map.
- First posted on arXiv 1 Oct 2021.

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

- [A physical model for efficient ranking in networks](https://mlsanity.com/paper/1709.09002/) (2017)
- [Feedback arcs and node hierarchy in directed networks](https://mlsanity.com/paper/1612.05347/) (2016)

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

- [Estimation of partial rankings from sparse, noisy comparisons](https://mlsanity.com/paper/2501.02505/) (2025)
- [Exact and rapid linear clustering of networks with dynamic programming](https://mlsanity.com/paper/2301.10403/) (2023)
- [Model inference for ranking from pairwise comparisons](https://mlsanity.com/paper/2512.15269/) (2025)
- [Generalized Priority-Aware Shapley Value](https://mlsanity.com/paper/2605.15018/) (2026)

## Abstract (arXiv)

Many datasets give partial information about an ordering or ranking by indicating which team won a game, which item a user prefers, or who infected whom. We define a continuous spin system whose Gibbs distribution is the posterior distribution on permutations, given a probabilistic model of these interactions. Using the cavity method we derive a belief propagation algorithm that computes the marginal distribution of each node's position. In addition, the Bethe free energy lets us approximate the number of linear extensions of a partial order and perform model selection between competing probabilistic models, such as the Bradley-Terry-Luce model of noisy comparisons and its cousins.