# Revisiting Decomposable Submodular Function Minimization with Incidence Relations

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

## Key facts

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

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

- [Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond](https://mlsanity.com/paper/2101.05510/) (2021)
- [Equivariant Hypergraph Diffusion Neural Operators](https://mlsanity.com/paper/2207.06680/) (2022)
- [Decomposable Submodular Function Minimization via Maximum Flow](https://mlsanity.com/paper/2103.03868/) (2021)
- [Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components](https://mlsanity.com/paper/2110.14859/) (2021)

## Abstract (arXiv)

We introduce a new approach to decomposable submodular function minimization (DSFM) that exploits incidence relations. Incidence relations describe which variables effectively influence the component functions, and when properly utilized, they allow for improving the convergence rates of DSFM solvers. Our main results include the precise parametrization of the DSFM problem based on incidence relations, the development of new scalable alternative projections and parallel coordinate descent methods and an accompanying rigorous analysis of their convergence rates.