Maximizing submodular functions using probabilistic graphical models

K. S. Sesh Kumar, Francis R. Bach

Introduction

Submodular functions are often described as the discrete analogues of convex and concave functions. They play a critical role in various domains, including computer vision (image segmentation), sensor placement, and document summarization. While the minimization of submodular functions is solvable in polynomial time, the problem of submodular maximization is NP-hard. In their 2013 work, K. S. Sesh Kumar and Francis Bach introduced a novel framework that bridges the gap between discrete optimization and probabilistic modeling, offering a principled convex relaxation for this challenging problem.

The Problem: Beyond Greedy Heuristics

Traditional approaches to submodular maximization typically rely on greedy algorithms or local search techniques. While these methods provide certain theoretical guarantees (such as the $1 - 1/e$ approximation ratio for monotone functions), they often lack "online bounds"—a mechanism to estimate the proximity of a current solution to the global optimum during execution.

The authors sought to develop a convex relaxation that transforms the discrete selection problem (choosing elements for a set) into a continuous optimization problem. By mapping the discrete space onto a continuous domain (0 to 1), the problem becomes mathematically smoother, allowing for the derivation of tighter bounds and the application of variational inference techniques.

Methodology: The Entropy Connection

The core innovation of this research lies in the "graphical-model-based upper bound." The authors leverage a deep connection between submodularity and information theory:

  1. Submodularity as Entropy: In information theory, the entropy of a set of random variables is a submodular function. For graphical models like trees or grids, the total entropy can be decomposed into a sum of local entropies.
  2. Projection onto Graph Structures: The authors demonstrate that any submodular function can be projected onto a specific graph structure to create a tractable upper bound.
  3. Variational Saddle-Point Problem: The maximization is framed as a saddle-point optimization:
  4. Maximization: The objective is maximized over the "marginal polytope," representing the possible sets.
  5. Minimization: The upper bound is minimized by selecting the optimal graph structure within the "hypertree polytope."
  6. The Role of Treewidth ($k$): The complexity of the relaxation is controlled by the treewidth of the underlying graph. A low treewidth ($k=1$, such as a tree) is computationally efficient but yields a looser bound. Increasing $k$ tightens the bound at the cost of higher computational complexity, creating a hierarchy similar to the Sherali-Adams hierarchy in combinatorial optimization.

Experimental Evaluation

The framework was evaluated using synthetic tasks designed to test different structural properties:

  • Trees: Used as a baseline to verify theoretical exactness.
  • 2D Grids ($10 \times 10$): Used to evaluate the algorithm's performance on loopy, non-tree structures.
  • Dense Random Graphs: 100-node graphs with high edge density (0.9) to test the limits of the relaxation and the resulting integrality gap.

Key Insights and Results

The study yielded several significant findings:

  • Exactness on Tree Structures: For functions that naturally align with a tree structure, the algorithm identifies the optimal solution in a single iteration.
  • Performance on Grids: On 2D grids, the variational approach successfully converged to optimal solutions, matching or exceeding the performance of standard local search heuristics.
  • The Integrality Gap: In dense random graphs, the authors observed a larger "integrality gap"—the difference between the continuous relaxation and the discrete maximum. While this gap can be reduced by increasing the treewidth ($k > 1$), the study primarily focused on $k=1$ for computational feasibility.
  • Generality: By framing the problem as the maximization of the difference between two submodular functions, the authors provided a pathway to optimize virtually any set function.

Limitations and Future Directions

Despite its theoretical elegance, the approach faces scalability challenges. Finding the optimal graph structure for higher treewidths ($k > 1$) is itself an NP-hard problem, necessitating the use of heuristics. Furthermore, the experiments were conducted on a relatively small scale (up to 100 nodes). Applying this variational framework to large-scale real-world problems, such as social network analysis or high-resolution computer vision, remains an area for future research. The authors suggest that future work should focus on more efficient ways to learn graph structures and applying these techniques to structured prediction tasks.

Summary updated

Abstract

We consider the problem of maximizing submodular functions; while this problem is known to be NP-hard, several numerically efficient local search techniques with approximation guarantees are available. In this paper, we propose a novel convex relaxation which is based on the relationship between submodular functions, entropies and probabilistic graphical models. In a graphical model, the entropy of the joint distribution decomposes as a sum of marginal entropies of subsets of variables; moreover, for any distribution, the entropy of the closest distribution factorizing in the graphical model provides an bound on the entropy. For directed graphical models, this last property turns out to be a direct consequence of the submodularity of the entropy function, and allows the generalization of graphical-model-based upper bounds to any submodular functions. These upper bounds may then be jointly maximized with respect to a set, while minimized with respect to the graph, leading to a convex variational inference scheme for maximizing submodular functions, based on outer approximations of the marginal polytope and maximum likelihood bounded treewidth structures. By considering graphs of increasing treewidths, we may then explore the trade-off between computational complexity and tightness of the relaxation. We also present extensions to constrained problems and maximizing the difference of submodular functions, which include all possible set functions.
BibTeX
@misc{kumar2013maximizing,
  author = {K. S. Sesh Kumar and Francis R. Bach},
  title = {{Maximizing submodular functions using probabilistic graphical models}},
  year = {2013},
  eprint = {1309.2593},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1309.2593},
}
Figure