# Leveraging Sparsity for Efficient Submodular Data Summarization

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2017.

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

- [Fair Submodular Cover](https://mlsanity.com/paper/2407.04804/) (2024)
- [Sparsification of Decomposable Submodular Functions](https://mlsanity.com/paper/2201.07289/) (2022)
- [Instance Specific Approximations for Submodular Maximization](https://mlsanity.com/paper/2102.11911/) (2021)
- [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022)
- [SCALA: Sparsification-based Contrastive Learning for Anomaly Detection on Attributed Networks](https://mlsanity.com/paper/2401.01625/) (2024)
- [Linear Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2407.02601/) (2024)
- [E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time](https://mlsanity.com/paper/2506.07747/) (2025)
- [Data-dependent Evaluations for Budgeted Submodular Maximization](https://mlsanity.com/paper/2607.05759/) (2026)

## Abstract (arXiv)

The facility location problem is widely used for summarizing large datasets and has additional applications in sensor placement, image retrieval, and clustering. One difficulty of this problem is that submodular optimization algorithms require the calculation of pairwise benefits for all items in the dataset. This is infeasible for large problems, so recent work proposed to only calculate nearest neighbor benefits. One limitation is that several strong assumptions were invoked to obtain provable approximation guarantees. In this paper we establish that these extra assumptions are not necessary---solving the sparsified problem will be almost optimal under the standard assumptions of the problem. We then analyze a different method of sparsification that is a better model for methods such as Locality Sensitive Hashing to accelerate the nearest neighbor computations and extend the use of the problem to a broader family of similarities. We validate our approach by demonstrating that it rapidly generates interpretable summaries.