Monotone k-Submodular Function Maximization with Size Constraints

Naoto Ohsaka, Yuichi YoshidaNeurIPS 2015 · OpenReview

TL;DR

This paper introduces efficient algorithms for maximizing monotone $k$-submodular functions—a powerful mathematical framework for problems where you must choose multiple disjoint sets of items (like placing different types of sensors). The authors provide greedy and stochastic algorithms that offer provable approximation guarantees (1/2 or 1/3 of the optimal solution) while running in almost linear time, significantly outperforming existing methods in both speed and solution quality.

What Problem Does This Paper Address?

Many machine learning tasks involve selecting a subset of items to maximize a goal, such as picking the best locations for sensors to monitor a building. These often follow the principle of diminishing returns (submodularity): adding a sensor to a small network helps more than adding it to a large, already-saturated network.

However, real-world problems are often more complex. What if you have $k$ different types of sensors (temperature, humidity, light) and each location can only hold one? This is where $k$-submodularity comes in. It generalizes standard submodularity to cases where we need to partition elements into $k$ disjoint sets.

Prior to this paper, algorithms for $k$-submodular maximization were either non-existent for specific constraints or prohibitively slow (e.g., $O(n^8)$ complexity). The authors tackle two specific constraints:

  1. Total Size Constraint: The sum of all items across all $k$ sets is limited by a total budget $B$.
  2. Individual Size Constraint: Each of the $k$ sets has its own specific limit $B_i$.

Methods

The authors propose four main algorithms to tackle these constraints:

  • $k$-Greedy-TS (Total Size): A straightforward greedy approach that iteratively picks the element and category that yields the largest marginal gain. It achieves a 1/2-approximation ratio.
  • $k$-Stochastic-Greedy-TS: To handle massive datasets, this version samples a small random subset of elements in each step instead of searching the entire domain. It maintains the 1/2-approximation but runs in almost linear time relative to the domain size.
  • $k$-Greedy-IS (Individual Size): A modified greedy algorithm that respects per-category budgets, achieving a 1/3-approximation.
  • $k$-Stochastic-Greedy-IS: The stochastic version for individual constraints, also achieving a 1/3-approximation in near-linear time.

The "secret sauce" is the adaptation of the random sampling technique (originally for standard submodular functions) to the $k$-set domain, proving that you don't need to look at every possible placement to get a near-optimal result.

Datasets and Applications

The researchers evaluated their algorithms on two real-world applications:

  1. Influence Maximization: Using the Digg dataset (a social news website), they modeled the spread of $k=10$ different topics through a social network. The goal was to pick "seed" users to maximize the total expected reach across all topics.
  2. Sensor Placement: Using the Intel Lab dataset, which contains 2.3 million readings (temperature, humidity, light) from 54 sensors. They modeled the problem of placing $k=3$ types of sensors to maximize the "information gain" (entropy).

Key Results

Influence Maximization Performance

In the influence maximization experiments, the $k$-Greedy algorithms significantly outperformed baselines like picking users based on their number of followers ("Degree") or focusing on only one topic ("Single").

Influence Spread vs. Budget

Sensor Placement and Speedup

For the sensor placement task, the algorithms successfully maximized entropy while respecting individual size constraints. Furthermore, the stochastic versions proved to be much faster. The stochastic algorithm reduced the number of expensive entropy evaluations by 31% compared to the standard greedy version, with a negligible loss in solution quality (less than 0.18% difference).

Entropy vs. Budget for Sensor Placement

Scalability

The running time of the stochastic algorithms is shown to be almost linear, making them viable for "big data" social networks where $n$ (number of users) is in the millions.

Key Insights and Ideas

  • The Power of Disjointness: $k$-submodularity perfectly captures the "unfairness" or physical impossibility of assigning multiple items to one slot (e.g., one person receiving ten free samples or one socket holding three sensors).
  • Tightness of Bounds: The authors note that their 1/2-approximation for the total size constraint is asymptotically tight—meaning you mathematically cannot do better than 1/2 with a polynomial-time algorithm in the general case.
  • Efficiency via Sampling: The stochastic algorithms show that even with a very small sample size, the probability of missing the "best" elements is low enough that the overall approximation guarantee holds. This turns a potentially quadratic bottleneck into a near-linear one.

Limitations and Future Work

  • Individual Constraint Gap: While the total size constraint has a tight 1/2 bound, the individual size constraint currently sits at 1/3. The authors identify closing this gap—either by finding a 1/2-approximation or proving that 1/3 is the best possible—as a major open problem.
  • Monotonicity: These algorithms assume the function is "monotone" (adding more items never decreases the value). While true for many ML tasks, some problems are non-monotone, which would require different algorithmic strategies.
  • Curse of $k$: While the algorithms are near-linear in $n$, the complexity still scales with $k$. For a very large number of categories, further optimizations might be needed.

Summary updated

Abstract

A $k$-submodular function is a generalization of a submodular function, where the input consists of $k$ disjoint subsets, instead of a single subset, of the domain.Many machine learning problems, including influence maximization with $k$ kinds of topics and sensor placement with $k$ kinds of sensors, can be naturally modeled as the problem of maximizing monotone $k$-submodular functions.In this paper, we give constant-factor approximation algorithms for maximizing monotone $k$-submodular functions subject to several size constraints.The running time of our algorithms are almost linear in the domain size.We experimentally demonstrate that our algorithms outperform baseline algorithms in terms of the solution quality.
BibTeX
@inproceedings{ohsaka2015monotone,
  author = {Naoto Ohsaka and Yuichi Yoshida},
  title = {{Monotone k-Submodular Function Maximization with Size Constraints}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=rk4tQvbdZB},
}
Figure