The unique-fixed-point conjecture for local belief propagation

About 11 years old · traced to

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.