Belief propagation for graph partitioning

P. Sulc, Lenka ZdeborováarXiv 2009 · DOI · OpenReview

TL;DR

This paper introduces a novel belief propagation (BP) algorithm for graph partitioning, specifically addressing the challenge of fixing the size of the two partitions. The authors demonstrate that this algorithm can effectively determine the full phase diagram of graph bi-partitioning on random graphs and provides an efficient heuristic solver.

What Problem Does This Paper Address?

Graph partitioning, the problem of dividing a graph's vertices into two sets to minimize connections between them, is a fundamental problem with applications in diverse fields like circuit design and parallel computing. While many heuristic algorithms exist, a key challenge has been efficiently handling the global constraint of fixing the exact size of the two partitions (e.g., a graph bisection where both partitions must have equal size). This is equivalent to finding the ground state of an Ising model with a fixed magnetization. Previous methods often struggled to generalize to non-zero magnetization or graphs with fluctuating degrees.

Methods

The core of this paper is the development of a belief propagation (BP) algorithm tailored for graph partitioning with a fixed global constraint on partition sizes. The authors adapt the standard BP framework, which is typically used for problems without such global constraints, by introducing a method to fix the magnetization (and thus partition sizes) in a local way within the BP equations. This involves dynamically adjusting an external magnetic field during the iterative BP process. They also employ a "population dynamics" method to explore the phase diagram and a "decimation" algorithm as a heuristic solver, which refines the BP solution by fixing individual spins.

Datasets

The paper evaluates the proposed algorithms on Erdős-Rényi random graphs and random regular graphs. No new datasets are introduced; instead, the focus is on analyzing the behavior of the algorithms on these well-studied random graph ensembles.

Key Insights and Ideas

  • Local Control of Global Constraint: The most significant insight is the development of a method to enforce a global constraint (fixed partition size) within a local message-passing framework like BP. This is achieved by iteratively adjusting an external field.
  • Full Phase Diagram: The BP approach allows for the computation of the complete phase diagram for graph bi-partitioning on random graphs, revealing transitions between different solution regimes (e.g., replica-symmetric vs. glassy phases).
  • BP as a Heuristic Solver: The BP algorithm, especially when combined with decimation, proves to be a highly effective heuristic for finding near-ground-state solutions for graph partitioning, often outperforming existing bounds.
  • Distinction from Spin Glass Analogy: The paper highlights that while graph partitioning is related to spin glasses, the analogy breaks down at non-zero magnetization or for non-regular graphs, necessitating the developed BP approach.

Key Results

  • The proposed BP algorithm successfully computes the phase diagram of graph bi-partitioning for Erdős-Rényi random graphs, identifying a "glassy phase" where standard BP fails and replica symmetry breaking is needed.
  • The decimation solver, built upon the BP algorithm, achieves results very close to the ground states for graph partitioning, significantly outperforming known algorithmic bounds for 3-regular graphs. For instance, it finds partition costs much lower than the best provable bound of 0.16 for 3-regular graphs.
  • The algorithm provides valuable information about the probability of nodes belonging to specific partitions, which can be useful for identifying communities in real-world networks.

Limitations and Future Work

  • Convergence on Trees: The standard BP algorithm without decimation does not perform well on tree-like graphs, providing inaccurate magnetization values. The decimation algorithm, however, mitigates this issue.
  • General Graphs: While the authors anticipate the algorithm's usefulness for other graph families, the detailed analysis is primarily on random regular and Erdős-Rényi graphs. The behavior of the BP algorithm on general graphs with less regular structures might require further investigation.
  • Future Work: The authors suggest that their approach is straightforwardly generalizable to k-partitioning (dividing into k groups) and can be applied to other families of graphs and complex networks. They also note that the BP algorithm can be a useful component within multi-level partitioning methods.

Summary updated

Abstract

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.
BibTeX
@misc{sulc2009belief,
  author = {P. Sulc and Lenka Zdeborová},
  title = {{Belief propagation for graph partitioning}},
  year = {2009},
  eprint = {0912.3563},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0912.3563},
}
Figure