Multi-constraint graph partitioning problems via recursive bipartition algorithm based on subspace minimization conjugate gradient method

Wumei Sun, Hongwei Liu, Xiaoyu WangJournal of Applied Mathematics and Computing 2022

TL;DR

This paper introduces a highly efficient recursive bipartitioning algorithm for solving complex graph partitioning problems with multiple constraints (like vertex weights and fixed nodes). By cleverly transforming a discrete 0-1 integer programming problem into a continuous, unconstrained optimization problem using trigonometric properties and "equilibrium terms," the authors achieve solution speeds orders of magnitude faster than state-of-the-art semidefinite programming (SDP) methods while maintaining comparable or superior accuracy.

What Problem Does This Paper Address?

Graph partitioning—dividing a network into smaller, balanced groups while minimizing the connections (edges) between them—is a fundamental NP-hard problem. It is critical for everything from parallel computing to VLSI (Very Large Scale Integration) circuit design.

However, real-world applications often add "knapsack constraints" (each group has a maximum total weight) and "fixed vertex constraints" (certain nodes must stay in specific groups). Traditional exact methods, like those based on SDP relaxations, provide high-quality results but are computationally expensive, often taking hours to solve relatively small graphs (e.g., 500 vertices). This paper aims to bridge the gap between speed and quality for these multi-constraint scenarios.

Methods

The authors propose a multi-stage approach called the Recursive Bipartition Algorithm (Rba):

  1. Mathematical Transformation: They formulate the problem as a 0-1 quadratic integer program. To make it solvable, they use a "trigonometric trick," substituting discrete variables with $\cos(\theta)$ and $\sin(\theta)$. This maps the discrete 0-1 choice onto a continuous circle.
  2. Constraint Relaxation: Instead of battling hard inequality constraints for vertex weights, they introduce an equilibrium term into the objective function. This term penalizes unbalanced partitions, effectively guiding the solver toward feasible regions without the overhead of complex constrained optimization.
  3. The Solver (ASMCG_BB): They employ an Accelerated Subspace Minimization Conjugate Gradient method. This algorithm uses Barzilai-Borwein (BB) steps to dynamically adjust the search direction and step size, making it exceptionally fast at finding local optima in the relaxed continuous space.
  4. Rounding and Refinement: Once a continuous solution is found, they use hyperplane rounding to snap the results back to discrete 0-1 values. Finally, they apply heuristic "one-neighborhood" and "two-interchange" adjustments (local search) to fine-tune the partition and ensure all hard constraints are met.

Datasets

The algorithm was evaluated on three types of benchmarks:

  • GPKCrand20/50/80: Randomly generated graphs with varying edge densities (20%, 50%, and 80%) and one-dimensional vertex weights, following the setup of previous literature.
  • Industrial VLSI Examples: Eight real-world circuit design problems (Industry 1-8) converted from hypergraphs to graphs, featuring multidimensional weights and fixed vertex constraints.
  • ISPD98 Benchmark: A standard industry benchmark for circuit partitioning (ibm01 through ibm18), used to test the refinement capabilities of the proposed heuristic.

Key Insights and Ideas

  • Trigonometric Mapping: The use of sine and cosine functions to represent 0-1 variables is a clever way to turn a "jumpy" discrete problem into a "smooth" continuous one that gradient-based solvers can digest.
  • Equilibrium vs. Penalty: Rather than using traditional penalty functions for constraints, the authors found that an equilibrium term—specifically $\rho((e^T y_1)^2 + (e^T y_2)^2)$—performed better numerically by keeping the partition balanced throughout the optimization process.
  • Recursive Efficiency: By solving a sequence of smaller bipartitioning problems rather than one massive multi-way partition, the algorithm keeps the problem scale manageable at every step.

Key Results

  • Massive Speedup: On 500-vertex random graphs, the proposed Rba algorithm took approximately 33 seconds, whereas the competing ADMM-based method (Vc+2opt) required over 2,000 seconds (more than 33 minutes).
  • Superior Quality: In many cases, the Rba algorithm achieved a smaller "cut-size" (fewer edges between groups) than the state-of-the-art. For instance, on the industry 8 dataset, Rba achieved a cut-size of 1,920 compared to the competitor's 11,983—a massive improvement.
  • Refinement Power: When applied to the ISPD98 benchmark, the authors' heuristic refinement strategies successfully improved the results of KaHyPar (a leading hypergraph partitioner) in 16 out of 18 test cases.

Limitations and Future Work

  • Non-Convexity: The objective function remains non-convex, meaning the solver can still get stuck in local optima. The authors suggest integrating stochastic optimization or multi-start techniques to explore the search space better.
  • Sparsity Issues: Very sparse or irregular hypergraph structures can lead to instability during the subspace construction phase of the conjugate gradient method.
  • Parallelization: While fast, the current implementation is single-threaded. The authors note that developing parallelization strategies for the ASMCG method is a critical next step for handling "mega-scale" graphs with millions of vertices.

Summary updated

Abstract

The graph partitioning problem is a well-known NP-hard problem. In this paper, we formulate a 0-1 quadratic integer programming model for the graph partitioning problem with vertex weight constraints and fixed vertex constraints, and propose a recursive bipartition algorithm based on the subspace minimization conjugate gradient method. To alleviate the difficulty of solving the model, the constrained problem is transformed into an unconstrained optimization problem using equilibrium terms, elimination methods, and trigonometric properties, and solved via an accelerated subspace minimization conjugate gradient algorithm. Initial feasible partitions are generated using a hyperplane rounding algorithm, followed by heuristic refinement strategies, including one-neighborhood and two-interchange adjustments, to iteratively improve the results. Numerical experiments on knapsack-constrained graph partitioning and industrial examples demonstrate the effectiveness and feasibility of the proposed algorithm.
BibTeX
@article{sun2022multi,
  author = {Wumei Sun and Hongwei Liu and Xiaoyu Wang},
  title = {{Multi-constraint graph partitioning problems via recursive bipartition algorithm based on subspace minimization conjugate gradient method}},
  journal = {Journal of Applied Mathematics and Computing},
  year = {2022},
}
Figure