The unique-fixed-point conjecture for local belief propagation

From papers

Let ρ\rho denote the cluster-size parameter, let θ\theta and u u be model parameters, let θ+u\theta+ u determine the recursion parameter u u, and let θ+uh(v)\theta+ u h(v) be the scalar belief-propagation recursion, where hh is the function defined in the paper. A fixed point is a value vv satisfying

v=θ+λh(v).v=\theta+\lambda h(v).

Unique-fixed-point conjecture. If mu=numu=nu, then this recursion has a unique fixed point for every

ρ(0,1/2)(1/2,1).\rho\in(0,1/2)\cup(1/2,1).

A unique fixed point would imply that local belief propagation is optimal in the corresponding unequal-cluster-size cases. The claim is motivated by numerical experiments and is presented in the paper as an open problem; its resolution is not supplied here.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Elchanan Mossel and Jiaming Xu, “Density Evolution in the Degree-correlated Stochastic Block Model”, arXiv:1509.03281 (2016).

Solutions 0

No solutions have been posted yet.