We investigate an algorithm derived
based on the belief propagation method of Pearl applied to the (Min-)Bisection problem under the standard planted solution model (or more precisely the Most Likely Partition problem under the same planted solution model).
We first point out that
the algorithm (without thresholding) is nothing but the standard power method for computing an eigenvector with the largest eigenvalue used by some spectral method for the Bisection problem.
We then show that
the thresholding helps
to improve an approximate solution (by the spectral method) to the exact solution.
Through our analysis,
we prove that,
at least for the Bisection problem,
the belief propagation can be regarded as a unified spectral type algorithm for obtaining the exact solution with high probability.