# Sparsification of Decomposable Submodular Functions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 60 references that are in the map.
- First posted on arXiv 18 Jan 2022.

## Builds on (most cited first, 23 of 23)

- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Inhomogeneous Hypergraph Clustering with Applications](https://mlsanity.com/paper/1709.01249/) (2017)
- [Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering](https://mlsanity.com/paper/1803.03833/) (2018)
- [Distributed Submodular Maximization](https://mlsanity.com/paper/1411.0541/) (2014)
- [Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time](https://mlsanity.com/paper/1508.03261/) (2015)
- [Data Summarization at Scale: A Two-Stage Submodular Approach](https://mlsanity.com/paper/1806.02815/) (2018)
- [Hypergraph Cuts with General Splitting Functions](https://mlsanity.com/paper/2001.02817/) (2020)
- [Cheeger Inequalities for Submodular Transformations](https://mlsanity.com/paper/1708.08781/) (2017)
- [Spectral Sparsification of Hypergraphs](https://mlsanity.com/paper/1807.04974/) (2018)
- [Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs](https://mlsanity.com/paper/1611.00755/) (2016)
- [Fast and Private Submodular and k-Submodular Functions Maximization with Matroid Constraints](https://mlsanity.com/paper/2006.15744/) (2020)
- [Leveraging Sparsity for Efficient Submodular Data Summarization](https://mlsanity.com/paper/1703.02690/) (2017)
- [Decomposable Submodular Function Minimization: Discrete and Continuous](https://mlsanity.com/paper/1703.01830/) (2017)
- [Spectral Hypergraph Sparsifiers of Nearly Linear Size](https://mlsanity.com/paper/2106.02353/) (2021)
- [Structured learning of sum-of-submodular higher order energy functions](https://mlsanity.com/paper/1309.7512/) (2013)
- [Differentially Private Decomposable Submodular Maximization](https://mlsanity.com/paper/2005.14717/) (2020)
- [Near-linear Size Hypergraph Cut Sparsifiers](https://mlsanity.com/paper/2009.04992/) (2020)
- [Towards Tight Bounds for Spectral Sparsification of Hypergraphs](https://mlsanity.com/paper/2011.06530/) (2020)
- [New Notions and Constructions of Sparsification for Graphs and Hypergraphs](https://mlsanity.com/paper/1905.01495/) (2019)
- [Decomposable Submodular Function Minimization via Maximum Flow](https://mlsanity.com/paper/2103.03868/) (2021)
- [Sketching Cuts in Graphs and Hypergraphs](https://mlsanity.com/paper/1409.2391/) (2014)
- [On Sketching Quadratic Forms](https://mlsanity.com/paper/1511.06099/) (2015)

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

- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [Mini-batch Submodular Maximization](https://mlsanity.com/paper/2401.12478/) (2024)
- [Decomposable Submodular Maximization in Federated Setting](https://mlsanity.com/paper/2402.00138/) (2024)

## Abstract (arXiv)

Submodular functions are at the core of many machine learning and data mining tasks. The underlying submodular functions for many of these tasks are decomposable, i.e., they are sum of several simple submodular functions. In many data intensive applications, however, the number of underlying submodular functions in the original function is so large that we need prohibitively large amount of time to process it and/or it does not even fit in the main memory. To overcome this issue, we introduce the notion of sparsification for decomposable submodular functions whose objective is to obtain an accurate approximation of the original function that is a (weighted) sum of only a few submodular functions. Our main result is a polynomial-time randomized sparsification algorithm such that the expected number of functions used in the output is independent of the number of underlying submodular functions in the original function. We also study the effectiveness of our algorithm under various constraints such as matroid and cardinality constraints. We complement our theoretical analysis with an empirical study of the performance of our algorithm.