# Cut Sparsification and Succinct Representation of Submodular Hypergraphs

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jul 2023.

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

- [Mini-batch Submodular Maximization](https://mlsanity.com/paper/2401.12478/) (2024)
- [Decomposable Submodular Maximization in Federated Setting](https://mlsanity.com/paper/2402.00138/) (2024)
- [From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model](https://mlsanity.com/paper/2602.09457/) (2026)

## Abstract (arXiv)

In cut sparsification, all cuts of a hypergraph H=(V,E,w) are approximated within 1±ε factor by a small hypergraph H'. This widely applied method was generalized recently to a setting where the cost of cutting each hyperedge e is provided by a splitting function ge: 2e→ℝ_+. This generalization is called a submodular hypergraph when the functions gee∈ E are submodular, and it arises in machine learning, combinatorial optimization, and algorithmic game theory. Previous work studied the setting where H' is a reweighted sub-hypergraph of H, and measured the size of H' by the number of hyperedges in it. In this setting, we present two results: (i) all submodular hypergraphs admit sparsifiers of size polynomial in n=|V| and ε-1; (ii) we propose a new parameter, called spread, and use it to obtain smaller sparsifiers in some cases. We also show that for a natural family of splitting functions, relaxing the requirement that H' be a reweighted sub-hypergraph of H yields a substantially smaller encoding of the cuts of H (almost a factor n in the number of bits). This is in contrast to graphs, where the most succinct representation is attained by reweighted subgraphs. A new tool in our construction of succinct representation is the notion of deformation, where a splitting function ge is decomposed into a sum of functions of small description, and we provide upper and lower bounds for deformation of common splitting functions.