Maximizing submodular functions using probabilistic graphical models

K. S. Sesh Kumar, Francis Bach

Here is a concise, engaging summary of the paper.

TL;DR

While minimizing submodular functions is easy, maximizing them is NP-hard. This paper introduces a novel generic convex relaxation framework for submodular maximization by drawing a clever parallel to entropy bounds in probabilistic graphical models (PGMs). By framing the problem as a minimax saddle-point optimization, the authors allow researchers to systematically trade off computational complexity for tighter bounds via graph treewidth.

What Problem Does This Paper Address?

Submodularity is often described as the discrete analogue of convexity or concavity, characterized by a "diminishing returns" property. It shows up everywhere in machine learning, from sensor placement and image segmentation to document summarization.

While minimizing submodular functions can be done efficiently in polynomial time, maximizing them is notoriously NP-hard. Existing approaches rely heavily on randomized local search or greedy heuristics that offer approximation guarantees but lack a flexible, principled framework for exact optimization. The authors tackle this gap by introducing a generic convex relaxation for submodular maximization. This framework provides online bounds that can be used within branch-and-bound optimization and makes it easier to integrate submodular maximization into structured prediction frameworks.

Methods

The authors leverage a fascinating connection: discrete entropy is a well-known submodular function, and in PGMs, the joint entropy decomposes cleanly based on the graph structure. They reverse-engineer this property to define a graph-based upper bound ($F_G(A)$) for any submodular function ($F$), regardless of whether it relates to probability or entropy.

To find the tightest possible bound, they set up a variational optimization problem: maximize the upper bound over the set $A$ while minimizing it over the graph structure $G$. They achieve this by:

  1. Relaxing the discrete set selection using an outer approximation of the marginal polytope (a tool borrowed from PGM variational inference).
  2. Restricting the graph search to bounded-treewidth decomposable graphs.

This formulation yields a convex saddle-point (minimax) problem that can be solved in polynomial time using a simplicial method. By tuning the treewidth parameter ($k$), users can systematically trade off computational cost for tighter bounds, connecting this method to known combinatorial hierarchies like the Sherali-Adams hierarchy.

Datasets

The paper evaluates the approach on synthetic graph configurations optimized for the "max-cut" problem (a classic non-monotone submodular maximization problem). They generated graphs with $|V| = 100$ nodes across three topologies:

  • Trees
  • 2D-grids ($10 \times 10$)
  • Random graphs (where edges exist between nodes with a probability of 0.9)

No real-world datasets were used in this study.

Key Insights and Ideas

  • Submodularity as Generalized Entropy: The core "aha" moment is realizing that the algebraic properties allowing entropy to decompose over a PGM are actually direct consequences of its submodularity. This means PGM bounding techniques can be generalized to all submodular functions.
  • The Minimax Game: Turning the problem into a game where you maximize over the relaxed set variables but minimize over the graph structures creates a clean, solvable convex saddle-point problem.
  • Hierarchical Tightness: The framework provides a clear roadmap to arbitrarily tight bounds. If a simple tree structure ($k=1$) doesn't yield a tight enough bound for a complex graph, you can systematically increase the treewidth ($k$) to reduce the approximation gap.

Key Results

The authors empirically tested their algorithm using simple spanning trees ($k=1$):

  • Tree-based cuts: The algorithm converged to the exact optimal solution in the very first iteration.
  • 2D-grids: The algorithm successfully converged to the optimal solution, performing competitively alongside established constant-factor approximation algorithms.
  • Random graphs: While the algorithm successfully solved the convex optimization problem, it left a larger integrality gap. This demonstrated the clear limitation of using a simple tree ($k=1$) structure for highly connected, dense graphs.

Limitations and Future Work

  • Computational Scaling for Higher Treewidths: While the theory elegantly supports higher treewidths ($k > 1$) to tighten bounds on complex graphs, finding the optimal graph structure itself becomes NP-hard when $k > 1$. The authors suggest using approximate minimization or generating a large pool of random graphs to bypass this, but it remains a challenge.
  • Limited Empirical Scope: The experiments in the paper were restricted entirely to the simplest case ($k = 1$, spanning trees) on small synthetic datasets ($|V| = 100$). Scaling the implementation to higher treewidths and testing it on large-scale, real-world problems is left for future research.

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 Bach},
  title = {{Maximizing submodular functions using probabilistic graphical models}},
  year = {2013},
  eprint = {1309.2593},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1309.2593},
}
Figure