# Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 56 references that are in the map.
- First posted on arXiv 28 Oct 2021.

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

- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [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)
- [Hypergraph Cuts with General Splitting Functions](https://mlsanity.com/paper/2001.02817/) (2020)
- [Strongly Local Hypergraph Diffusions for Clustering and Semi-supervised Learning](https://mlsanity.com/paper/2011.07752/) (2020)
- [Reflection methods for user-friendly submodular optimization](https://mlsanity.com/paper/1311.4296/) (2013)
- [Local Hyper-Flow Diffusion](https://mlsanity.com/paper/2102.07945/) (2021)
- [Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao](https://mlsanity.com/paper/2101.07233/) (2021)
- [Decomposable Submodular Function Minimization: Discrete and Continuous](https://mlsanity.com/paper/1703.01830/) (2017)
- [The Generalized Mean Densest Subgraph Problem](https://mlsanity.com/paper/2106.00909/) (2021)
- [Structured learning of sum-of-submodular higher order energy functions](https://mlsanity.com/paper/1309.7512/) (2013)
- [Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions](https://mlsanity.com/paper/1502.02643/) (2015)
- [Revisiting Decomposable Submodular Function Minimization with Incidence Relations](https://mlsanity.com/paper/1803.03851/) (2018)
- [Augmented Sparsifiers for Generalized Hypergraph Cuts with Applications to Decomposable Submodular Function Minimization](https://mlsanity.com/paper/2007.08075/) (2020)
- [On the Convergence Rate of Decomposable Submodular Function Minimization](https://mlsanity.com/paper/1406.6474/) (2014)
- [Decomposable Submodular Function Minimization via Maximum Flow](https://mlsanity.com/paper/2103.03868/) (2021)
- [A simple bipartite graph projection model for clustering in networks](https://mlsanity.com/paper/2007.00761/) (2020)

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

- [Seven open problems in applied combinatorics](https://mlsanity.com/paper/2303.11464/) (2023)

## Abstract (arXiv)

Minimizing a sum of simple submodular functions of limited support is a special case of general submodular function minimization that has seen numerous applications in machine learning. We develop fast techniques for instances where components in the sum are cardinality-based, meaning they depend only on the size of the input set. This variant is one of the most widely applied in practice, encompassing, e.g., common energy functions arising in image segmentation and recent generalized hypergraph cut functions. We develop the first approximation algorithms for this problem, where the approximations can be quickly computed via reduction to a sparse graph cut problem, with graph sparsity controlled by the desired approximation factor. Our method relies on a new connection between sparse graph reduction techniques and piecewise linear approximations to concave functions. Our sparse reduction technique leads to significant improvements in theoretical runtimes, as well as substantial practical gains in problems ranging from benchmark image segmentation tasks to hypergraph clustering problems.