# Augmented Sparsifiers for Generalized Hypergraph Cuts with Applications to Decomposable Submodular Function Minimization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2020.

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

- [The Generalized Mean Densest Subgraph Problem](https://mlsanity.com/paper/2106.00909/) (2021)
- [HyperMagNet: A Magnetic Laplacian based Hypergraph Neural Network](https://mlsanity.com/paper/2402.09676/) (2024)
- [Modeling Edge-Specific Node Features through Co-Representation Neural Hypergraph Diffusion](https://mlsanity.com/paper/2405.14286/) (2024)
- [Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components](https://mlsanity.com/paper/2110.14859/) (2021)

## Abstract (arXiv)

In recent years, hypergraph generalizations of many graph cut problems have been introduced and analyzed as a way to better explore and understand complex systems and datasets characterized by multiway relationships. Recent work has made use of a generalized hypergraph cut function which for a hypergraph H = (V,E) can be defined by associating each hyperedge e ∈ E with a splitting function bf we, which assigns a penalty to each way of separating the nodes of e. When each bf we is a submodular cardinality-based splitting function, meaning that bf we(S) = g(|S|) for some concave function g, previous work has shown that a generalized hypergraph cut problem can be reduced to a directed graph cut problem on an augmented node set. However, existing reduction procedures often result in a dense graph, even when the hypergraph is sparse, which leads to slow runtimes for algorithms that run on the reduced graph. We introduce a new framework of sparsifying hypergraph-to-graph reductions, where a hypergraph cut defined by submodular cardinality-based splitting functions is (1+varepsilon)-approximated by a cut on a directed graph. Our techniques are based on approximating concave functions using piecewise linear curves. For varepsilon > 0 we need at most O(varepsilon-1|e| log |e|) edges to reduce any hyperedge e, which leads to faster runtimes for approximating generalized hypergraph s-t cut problems. For the machine learning heuristic of a clique splitting function, our approach requires only O(|e| varepsilon-1/2 log log frac1varepsilon) edges. This sparsification leads to faster approximate min s-t graph cut algorithms for certain classes of co-occurrence graphs. Finally, we apply our sparsification techniques to develop approximation algorithms for minimizing sums of cardinality-based submodular functions.