Belief propagation for graph partitioning

Understand

We study the belief propagation algorithm for the graph bi-partitioning problem, i.e.

• the ground state of the ferromagnetic Ising model at a fixed magnetization.
• Application of a message passing scheme to a model with a fixed global parameter is not banal and we show that the magnetization can in fact be fixed in a local way within the belief propagation equations.
• Our method provides the full phase diagram of the bi-partitioning problem on random graphs, as well as an efficient heuristic solver that we anticipate to be useful in a wide range of application of the partitioning problem.