Introduction
Finding the "most probable explanation" (MPE)—or minimizing the energy function—in a probability distribution is a fundamental task in machine learning and computer vision. In general, this problem is NP-hard and notoriously difficult to approximate efficiently without imposing strict limitations on the model.
Historically, researchers have made inference tractable by restricting either the model's structure (e.g., enforcing a low treewidth) or its function (e.g., requiring the energy to be strictly submodular). However, these restrictions severely limit the model's expressiveness. For instance, standard graph cuts struggle to penalize global properties, such as the number of unique object boundaries, without causing the treewidth to explode and rendering the problem intractable.
This paper bridges that gap by introducing cooperative cuts, a novel class of energy functions that are neither submodular nor restricted in treewidth, yet remain efficiently approximable in polynomial time.
The Cooperative Cut Framework
The core innovation of this paper is the generalization of standard graph cuts. In a traditional $s-t$ min-cut problem, the cost of a cut is simply the modular sum of its individual edge weights: $\sum_{e \in C} w(e)$.
In a cooperative cut, the cost is defined as $f(C)$, where $f$ is a submodular function applied to the set of cut edges. Because submodular functions exhibit diminishing returns, the edges become "coupled." For example, cutting multiple edges of the same type or group might cost significantly less than the sum of their individual costs.
This clever construction yields a crucial insight: submodularity on edges does not equal submodularity on nodes. By applying a submodular function to the edges of a cut, the resulting energy function on the nodes becomes subadditive, but not submodular. This allows the model to capture complex, high-treewidth dependencies—like grouping pixels by object boundaries in an image—that standard submodular functions cannot handle.
Approximation Algorithms
Because the global coupling of edges breaks standard min-cut algorithms, the authors propose four distinct approximation algorithms to solve the cooperative cut problem:
- Polymatroidal Network Flows: Replaces the globally coupled function $f$ with a locally tight, separable approximation that decomposes across nodes, solvable via generalized max-flow algorithms.
- Global Approximation: Utilizes a known square-root approximation derived from the submodular polyhedron, reducing the problem to a standard sum-of-weights min-cut (though computing the approximation is computationally heavy).
- Greedy Randomized Path Cover: Treats the cut as a "hitting set" that must intersect every possible path from $s$ to $t$. It iteratively finds the shortest path and randomly selects an edge to cut based on its marginal cost.
- Convex Relaxation: Extends the discrete edge function to a continuous domain using the Lovász extension, solves the resulting non-smooth convex program, and rounds the fractional solution.
Theoretical Limits and Empirical Results
The authors establish a hard mathematical ceiling for this class of problems, proving an information-theoretic lower bound: no polynomial-time algorithm can approximate this problem better than a factor of $o(\sqrt{m}/\log m)$.
Despite this strict theoretical limit, the proposed algorithms offer solid worst-case guarantees:
- Polymatroidal Flow: Bounded by $|V|/2$.
- Global Approximation: Bounded by $O(\sqrt{m} \log m)$.
- Greedy Cover & Convex Relaxation: Bounded by $O(n)$ (specifically, the length of the longest simple path).
To test these bounds, the authors evaluated the algorithms on synthetic clustered graphs ($n=30$ nodes, $m=90$ edges) using various submodular cost functions, including adversarial "hard cases."
Theory vs. Practice: While the theoretical worst-case bounds scale with the size of the graph, empirical performance is vastly superior. On the synthetic tests, the proposed algorithms achieved empirical approximation factors generally between 1.0 and 2.0 (meaning the found energy was at most twice the true minimum). In stark contrast, a naive standard min-cut approach yielded errors scaling up to $\Omega(n^2/4)$.
Limitations and Future Work
While the empirical performance is strong, the theoretical worst-case approximation bounds remain relatively loose, scaling with the number of nodes or edges. Additionally, some methods—particularly the global approximation—are computationally expensive ($O(m^4 \log^2 m)$), making them challenging to scale to massive graphs like high-resolution images.
However, these theoretical foundations open the door for powerful practical applications. The authors note that applying cooperative cuts to computer vision tasks, such as image segmentation where edge coupling naturally represents object boundaries, yields substantial improvements—a promising direction for future applied research.
Summary updated