# k-way Hypergraph Partitioning via n-Level Recursive Bisection

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2015.

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

- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [More Recent Advances in (Hyper)Graph Partitioning](https://mlsanity.com/paper/2205.13202/) (2022)
- [Optimizing Tensor Network Contraction Using Reinforcement Learning](https://mlsanity.com/paper/2204.09052/) (2022)
- [K-SpecPart: Supervised embedding algorithms and cut overlay for improved hypergraph partitioning](https://mlsanity.com/paper/2305.06167/) (2023)
- [Local Motif Clustering via (Hyper)Graph Partitioning](https://mlsanity.com/paper/2205.06176/) (2022)
- [Balanced Coarsening for Multilevel Hypergraph Partitioning via Wasserstein Discrepancy](https://mlsanity.com/paper/2106.07501/) (2021)
- [OPTDTALS: Approximate Logic Synthesis via Optimal Decision Trees Approach](https://mlsanity.com/paper/2408.12304/) (2024)

## Abstract (arXiv)

We develop a multilevel algorithm for hypergraph partitioning that contracts the vertices one at a time. Using several caching and lazy-evaluation techniques during coarsening and refinement, we reduce the running time by up to two-orders of magnitude compared to a naive n-level algorithm that would be adequate for ordinary graph partitioning. The overall performance is even better than the widely used hMetis hypergraph partitioner that uses a classical multilevel algorithm with few levels. Aided by a portfolio-based approach to initial partitioning and adaptive budgeting of imbalance within recursive bipartitioning, we achieve very high quality. We assembled a large benchmark set with 310 hypergraphs stemming from application areas such VLSI, SAT solving, social networks, and scientific computing. We achieve significantly smaller cuts than hMetis and PaToH, while being faster than hMetis. Considerably larger improvements are observed for some instance classes like social networks, for bipartitioning, and for partitions with an allowed imbalance of 10%. The algorithm presented in this work forms the basis of our hypergraph partitioning framework KaHyPar (Karlsruhe Hypergraph Partitioning).