Belief propagation for permutations, rankings, and partial orders

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.

Figure 1

The convex polytope corresponding to the partial order $3\prec 1,3\prec 2$, i.e., the subset of the unit cube where $x_3<x_1$ and $x_3<x_2$. It contains two simplices corresponding to the linear extensions $3\prec 1\prec 2$ and $3\prec 2\prec 1$, and it has total volume $2/3!=1/3$.

Figure 2

Entropy per site for random graphs. The number of linear extensions scales as $n!e^{sn}$ in the sparse case where $s<0$, so after rescaling the spins to the unit interval as in Eq. (3), the entropy is negative. (a) Values of $s_{\text{ann}}$ and $s_{\text{Bethe}}$ in random graphs of mean degree $\lambda$, estimated by belief propagation on random graphs of size $n={10}^4$ under the assumption that $lnZ$ is normally distributed. The dashed line is the analytic result Eq. (10) for $s_{\text{ann}}$, showing that our results are consistent with theory. The solid line is the value for $s_{\text{Bethe}}$ given by population dynamics. (b) Mean-squared error between $s_{\text{Bethe}}$ and the exact value of $s=\frac{1}{n}lnZ$ computed by exhaustive enumeration on random graphs of size $n\le 50$ and mean degree $\lambda =2$. Even when we approximate the messages with $d=32$ Chebyshev coefficients, $s_{\text{Bethe}}$ rapidly converges to $s$, showing that the cavity method is asymptotically exact. (c) Mean-squared error for our estimate of $s_{\text{Bethe}}$ as a function of the number $d$ of Chebyshev coefficients used in our approximation, for random graphs with $n$ nodes and mean degree $\lambda$. The error is calculated relative to $d=32$. There is a clear dependence on $\lambda$ but not on $n$, and the estimate converges exponentially as $d$ increases.

Figure 3

In (a) we show a randomly grown network with Poisson out-degree. In (b) we show the posterior marginals for four representative nodes, colored to match (a), comparing those obtained by our method with the exact results of exhaustive enumeration. Despite the presence of short cycles, our belief propagation approach approximates the marginals quite closely, matching not just the means but the shapes of these distributions.