# Scaling Submodular Maximization via Pruned Submodularity Graphs

arXiv: https://arxiv.org/abs/1606.00399 · HTML: https://mlsanity.com/paper/1606.00399/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2016.

## Built on by (most cited first, 3 of 3)

- [On Distributed Larger-Than-Memory Subset Selection With Pairwise Submodular Functions](https://mlsanity.com/paper/2402.16442/) (2024)
- [Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization](https://mlsanity.com/paper/2410.17945/) (2024)
- [Scalable Submodular Policy Optimization via Pruned Submodularity Graph](https://mlsanity.com/paper/2507.13834/) (2025)

## Abstract (arXiv)

We propose a new random pruning method (called "submodular sparsification (SS)") to reduce the cost of submodular maximization. The pruning is applied via a "submodularity graph" over the n ground elements, where each directed edge is associated with a pairwise dependency defined by the submodular function. In each step, SS prunes a 1-1/√c (for c>1) fraction of the nodes using weights on edges computed based on only a small number (O(log n)) of randomly sampled nodes. The algorithm requires log_√cn steps with a small and highly parallelizable per-step computation. An accuracy-speed tradeoff parameter c, set as c = 8, leads to a fast shrink rate √2/4 and small iteration complexity log_2√2n. Analysis shows that w.h.p., the greedy algorithm on the pruned set of size O(log2 n) can achieve a guarantee similar to that of processing the original dataset. In news and video summarization tasks, SS is able to substantially reduce both computational costs and memory usage, while maintaining (or even slightly exceeding) the quality of the original (and much more costly) greedy algorithm.