Some Graph Partitioning Algorithms based on belief propagation

Abstract

In this thesis project we have focused on a kind of graph partitioning problem com- monly called bi-categorical clustering, however, we also show that all results are easily extended to general graph partitioning. In this problem we get a graph asked to output a partitioning and such that the partitions are of equal (or fixed given) size and so as to minimize the number of edges running between them. The problem is analyzed under an input model called the planted partitioning model since it has been shown that under a uniform distribution all feasible solution are likely to be equally good or very close. Under the planted partitioning model we find that it is natural to formulate the problem a bit differently and we therefore propose a new prob- lem, namely the Maximum Likelihood partitioning problem which given the observed graph from the known distribution, aims to find a ML solution. Our algorithms are derived using the well known belief propagation method. This method is very well suited for the scenario. Unfortunately, however, it is not yet well understood and therefore we must present our own analysis. Contrary, our research constitutes one of the first in-depth analysis of a specialized use of belief propagation. We present linear and quadratic time algorithms for solving the problem and show strong theoretical as well as experimental results. What we find is, in short, that when- ever the planted partitioning model is appropriate, our algorithm succeeds to nearly 100%.