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.

翻译：本文考虑了平衡的超高分解问题, 它要求将脊椎分割成 $k$ 的不连接区块, 并最大限度地减少高端的客观功能。 这里, 我们考虑最常用的连接度 。 我们描述基于成功的多层次方法的开放源头高分解器 KaHyPar 。 将它推向一个顶点的极端水平, 每个顶点( 几乎) 。 使用精心设计的数据结构和动态更新技术, 这种方法提供了非常高的时间质量的交换。 我们展示了两种预处理技术 -- -- 使用地方敏感散列和根据 Louvain 算法进行社区检测。 我们用社区结构来指导递增压顶点的剖析进程。 包包的超高分解方法已经取得了良好的初步解决方案。 在扭转收缩时, 高本地直接本地搜索和流基技术的组合, 将更接近全球的视野, 改进分区, 实现高质量。 选择, Ka- Per 特殊的算法将一个最高级的解算器, 也就是高端的系统 。