# Network Flow-Based Refinement for Multilevel Hypergraph Partitioning

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

## Key facts

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

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

- [More Recent Advances in (Hyper)Graph Partitioning](https://mlsanity.com/paper/2205.13202/) (2022)
- [K-SpecPart: Supervised embedding algorithms and cut overlay for improved hypergraph partitioning](https://mlsanity.com/paper/2305.06167/) (2023)
- [Balanced Coarsening for Multilevel Hypergraph Partitioning via Wasserstein Discrepancy](https://mlsanity.com/paper/2106.07501/) (2021)

## Abstract (arXiv)

We present a refinement framework for multilevel hypergraph partitioning that uses max-flow computations on pairs of blocks to improve the solution quality of a k-way partition. The framework generalizes the flow-based improvement algorithm of KaFFPa from graphs to hypergraphs and is integrated into the hypergraph partitioner KaHyPar. By reducing the size of hypergraph flow networks, improving the flow model used in KaFFPa, and developing techniques to improve the running time of our algorithm, we obtain a partitioner that computes the best solutions for a wide range of benchmark hypergraphs from different application areas while still having a running time comparable to that of hMetis.