# High-Quality Hypergraph Partitioning

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2021.

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

- [More Recent Advances in (Hyper)Graph Partitioning](https://mlsanity.com/paper/2205.13202/) (2022)
- [DCP: Addressing Input Dynamism In Long-Context Training via Dynamic Context Parallelism](https://mlsanity.com/paper/2510.10620/) (2025)
- [A Versatile Framework for Attributed Network Clustering via K-Nearest Neighbor Augmentation](https://mlsanity.com/paper/2408.05459/) (2024)
- [K-SpecPart: Supervised embedding algorithms and cut overlay for improved hypergraph partitioning](https://mlsanity.com/paper/2305.06167/) (2023)
- [Scalable Graph Convolutional Network Training on Distributed-Memory Systems](https://mlsanity.com/paper/2212.05009/) (2022)
- [SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning](https://mlsanity.com/paper/2410.10875/) (2024)
- [TransPlace: Transferable Circuit Global Placement via Graph Neural Network](https://mlsanity.com/paper/2501.05667/) (2025)
- [A Multi-Level Framework for Multi-Objective Hypergraph Partitioning: Combining Minimum Spanning Tree and Proximal Gradient](https://mlsanity.com/paper/2509.22294/) (2025)
- [A PPA-Driven 3D-IC Partitioning Selection Framework with Surrogate Models](https://mlsanity.com/paper/2604.18806/) (2026)
- [Algorithmic algorithm development with LLMs: A Case Study on LLM-Usage for Contraction Order Optimization in Tensor Networks](https://mlsanity.com/paper/2606.01975/) (2026)

## Abstract (arXiv)

This paper considers the balanced hypergraph partitioning problem, which asks for partitioning the vertices into k disjoint blocks of bounded size while minimizing an objective function over the hyperedges. Here, we consider the most commonly used connectivity metric. We describe our open source hypergraph partitioner KaHyPar which is based on the successful multi-level approach -- driving it to the extreme of one level for (almost) every vertex. Using carefully designed data structures and dynamic update techniques, this approach offers a very good time-quality tradeoff. We present two preprocessing techniques -- pin sparsification using locality sensitive hashing and community detection based on the Louvain algorithm. The community structure is used to guide the coarsening process that incrementally contracts vertices. Portfolio-based partitioning of the contracted hypergraph already achieves good initial solutions. While reversing the contractions, a combination of highly-localized direct k-way local search and flow-based techniques that take a more global view, refine the partition to achieve high quality. Optionally, a memetic algorithm evolves a pool of solution candidates to obtain even higher quality. We evaluate KaHyPar on a large set of instances from a wide range of application domains. With respect to quality, KaHyPar outperforms all previously considered systems that can handle large hypergraphs such as hMETIS, PaToH, Mondriaan, or Zoltan. KaHyPar is also faster than most of these systems except for PaToH which represents a different speed-quality tradeoff. The results even extend to the special case of graph partitioning, where specialized systems such as KaHIP should have an advantage.