Abstract: Graph partitioning algorithms play a central role in data analysis and machine learning. Most useful graph partitioning criteria correspond to optimizing a ratio between the cut and the size of the partitions. This paper presents a framework for finding the global optimum of NP-hard graph partitioning problems, such as Normalized Cut and Average Cut. By transforming the ratio-based objective into a sequence of discrete optimization problems and solving them using convex message passing in graphical models, the authors move beyond the standard "spectral relaxation" to provide provably optimal or near-optimal solutions.
Introduction
Graph partitioning—the task of dividing a network of nodes into groups while minimizing the edges between them—is a cornerstone of data analysis and image segmentation. However, a simple "minimum cut" often fails in practice because it tends to slice off tiny, isolated clusters of nodes. To address this, researchers use "ratio" criteria, such as Normalized Cut or Average Cut, which penalize small partitions and encourage more balanced clusters.
The primary challenge is that these ratio-based problems are NP-hard. The standard industry solution is spectral relaxation, which uses eigenvectors to find an approximate solution. However, approximations introduce uncertainty: if a segmentation result is poor, it is unclear whether the mathematical criterion itself is flawed or if the optimization algorithm simply converged to a local minimum. This research aims to eliminate that uncertainty by seeking the global optimum.
Methodology
The authors employ a multi-step strategy to tackle the NP-hardness of ratio optimization:
- Linearization: Instead of directly minimizing a ratio $f(x)/g(x)$, they solve a sequence of problems of the form $f(x) - \lambda g(x)$. By using a bisection algorithm to adjust $\lambda$, they can iteratively home in on the optimal ratio.
- Graphical Model Mapping: Solving the "$\lambda$ question" is shown to be equivalent to performing MAP (Maximum A Posteriori) inference in a Markov Random Field (MRF).
- High-Order Potentials (HOPs): The MRF includes standard pairwise potentials (the edges) and a "High-Order Potential" that evaluates all nodes simultaneously to enforce the size-based penalty.
- Convex Belief Propagation (BP): While high-order potentials are usually computationally explosive ($2^n$), the authors demonstrate that for partitioning criteria like Average Cut, the potential is "cardinality-based." This allows for efficient message computation in $O(n \log n)$ time using sorting or dynamic programming.
- Conditioning: If the message-passing algorithm returns "tied" results (indicating the relaxation isn't tight), a branch-and-bound style "conditioning" technique is used to fix specific nodes and resolve the problem.
Key Insights: The Power of Bounds
Unlike spectral methods, which provide a "soft" approximate answer, this message-passing approach provides a rigorous lower bound on the objective function. This is a critical advantage: if the energy of the current solution matches the lower bound, it serves as mathematical proof that the global optimum has been found.
The "Aha!" moment of the paper is realizing that even though the size penalty involves every node in the graph, if that penalty only depends on the sum of the labels (the number of nodes in each group), it can be solved in polynomial time. This framework demonstrates that spectral methods often leave a significant "gap" between their approximate solution and the true optimum, a gap this method can often close.
Experimental Results
The authors evaluated their method on several diverse benchmarks, including 2D synthetic points, the Olivetti Face Database, and the Berkeley Segmentation Dataset. Key findings include:
- Global Optimality: On the Berkeley dataset, the method found the global optimum (within 0.1 accuracy) for 88% of the images.
- Tightened Intervals: For 59% of the Berkeley images, the message-passing approach significantly tightened the interval between the upper and lower bounds compared to spectral methods.
- Large-Scale Data: On the
finance256graph (37,376 nodes), the algorithm found a better cut than the spectral method, although the size of the graph prevented a proof of global optimality. - Face Clustering: The method successfully partitioned the Olivetti faces and proved that the spectral solution was already optimal in that specific case by matching the lower bound.
Limitations and Future Work
While highly accurate, this method is significantly slower than spectral relaxation, taking seconds to tens of minutes compared to the near-instantaneous results of spectral methods. Additionally, in very complex graphs with "frustrated cycles," the simple conditioning algorithm may not be enough to tighten the LP relaxation. Future work may incorporate more advanced techniques to handle these cycles and extend the efficiency gains to arbitrary real-valued weights for criteria like Normalized Cut.
Summary updated