# Hypergraph Cuts with General Splitting Functions

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

## Key facts

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

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

- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Equivariant Hypergraph Diffusion Neural Operators](https://mlsanity.com/paper/2207.06680/) (2022)
- [Local Hyper-Flow Diffusion](https://mlsanity.com/paper/2102.07945/) (2021)
- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [The Generalized Mean Densest Subgraph Problem](https://mlsanity.com/paper/2106.00909/) (2021)
- [HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering](https://mlsanity.com/paper/2108.07901/) (2021)
- [Sparsification of Decomposable Submodular Functions](https://mlsanity.com/paper/2201.07289/) (2022)
- [Learning the effective order of a hypergraph dynamical system](https://mlsanity.com/paper/2306.01813/) (2023)
- [Broad Spectrum Structure Discovery in Large-Scale Higher-Order Networks](https://mlsanity.com/paper/2505.21748/) (2025)
- [Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components](https://mlsanity.com/paper/2110.14859/) (2021)
- [Hypergraph Modeling via Spectral Embedding Connection: Hypergraph Cut, Weighted Kernel k-means, and Heat Kernel](https://mlsanity.com/paper/2203.09888/) (2022)
- [Hypergraphs with Edge-Dependent Vertex Weights: p-Laplacians and Spectral Clustering](https://mlsanity.com/paper/2208.07457/) (2022)
- [Seven open problems in applied combinatorics](https://mlsanity.com/paper/2303.11464/) (2023)
- [Hypergraphs with Edge-Dependent Vertex Weights: Spectral Clustering based on the 1-Laplacian](https://mlsanity.com/paper/2305.00462/) (2023)

## Abstract (arXiv)

The minimum s-t cut problem in graphs is one of the most fundamental problems in combinatorial optimization, and graph cuts underlie algorithms throughout discrete mathematics, theoretical computer science, operations research, and data science. While graphs are a standard model for pairwise relationships, hypergraphs provide the flexibility to model multi-way relationships, and are now a standard model for complex data and systems. However, when generalizing from graphs to hypergraphs, the notion of a "cut hyperedge" is less clear, as a hyperedge's nodes can be split in several ways. Here, we develop a framework for hypergraph cuts by considering the problem of separating two terminal nodes in a hypergraph in a way that minimizes a sum of penalties at split hyperedges. In our setup, different ways of splitting the same hyperedge have different penalties, and the penalty is encoded by what we call a splitting function. Our framework opens a rich space on the foundations of hypergraph cuts. We first identify a natural class of cardinality-based hyperedge splitting functions that depend only on the number of nodes on each side of the split. In this case, we show that the general hypergraph s-t cut problem can be reduced to a tractable graph s-t cut problem if and only if the splitting functions are submodular. We also identify a wide regime of non-submodular splitting functions for which the problem is NP-hard. We also analyze extensions to multiway cuts with at least three terminal nodes and identify a natural class of splitting functions for which the problem can be reduced in an approximation-preserving way to the node-weighted multiway cut problem in graphs, again subject to a submodularity property. Finally, we outline several open questions on general hypergraph cut problems.