Ctrl K

KaHyPar is a fast, high-quality, and scalable algorithm for partitioning graphs and hypergraphs with billions of edges. It finds applications in minimizing communication costs for distributed (hyper)graph computations, quantum circuit simulations, storage sharding in databases, and VLSI design.

17

mentions

6

contributors

Get started

Hypergraphs are a generalization of graphs, where each (hyper)edge (also called net) can connect more than two nodes. The *k*-way hypergraph partitioning problem is the generalization of the well-known graph partitioning problem: partition the node set into k disjoint blocks of bounded size (at most 1 + ε times the average block size), while minimizing an objective function defined on the nets. Hypergraph partitioning finds application in minimizing communication costs and balancing the computational work in distributed scientific simulations (e.g., for parallel sparse matrix-vector multiplication), simulations of distributed quantum circuits, storage sharding in distributed databases, or as a placement strategy in VLSI design.

The Karlsruhe Hypergraph Partitioning Suite (KaHyPar) is a fast, high-quality, and scalable algorithm for partitioning graphs and hypergraphs. It consists of the sequential solver KaHyPar and the shared-memory partitioner Mt-KaHyPar. Mt-KaHyPar can be seen as a feature complete parallelization of KaHyPar. (Mt-)KaHyPar runs on Linux, Windows, and MacOS (only KaHyPar), and besides its standalone application, it provides a C, Python, Julia (only KaHyPar), and Java interface (only KaHyPar).

The highest-quality configuration of Mt-KaHyPar computes partitions that are on par with those produced by the best sequential partitioning algorithms, while being almost an order of magnitude faster with only *ten* threads (e.g., when compared to KaFFPa or KaHyPar). Besides our high quality configuration, we provide several other faster configurations that are already able to outperform most of the existing partitioning algorithms with regard to solution quality and running time.

The figure below summarizes the time-quality trade-off of different hypergraph (left, connectivity metric) and graph partitioning algorithms (right, cut-net metric). The plot is based on an experiment with over 800 graphs and hypergraphs and relates the average solution quality and running time of each algorithm to the best achievable results. Points on the lower-left are considered better. Partially transparent markers indicate solvers producing more than 15% infeasible partitions (either imbalanced or timeout). For more details, we refer the reader to our publications.

Besides its fast and high-quality partitioning algorithm, (Mt-)KaHyPar provides many other useful features:

**Scalability**: Mt-KaHyPar has excellent scaling behavior (up to 25 with 64 threads), while increasing the number of threads does not adversely affect the solution quality.**Deterministic Partitioning**: Mt-KaHyPar offers a deterministic partitioning algorithm, ensuring consistent solutions for the same input and random seed.**Large K Partitioning**: We provide a partitioning configuration for partitioning (hyper)graphs into a large number of blocks (e.g., k > 1024).**Graph Partitioning**: Mt-KaHyPar includes optimized data structures for graph partitioning, achieving a speedup by a factor of two for plain graphs.**Objective Functions**: Mt-KaHyPar can optimize the cut-net, connectivity, and sum-of-external-degree metric (for more details, see Supported Objective Functions)**Mapping (Hyper)Graphs Onto Graphs**: In many applications of (hyper)graph partitioning, the blocks of a partition need to be assigned to architectures that can be represented as graphs. For instance, in parallel computations, the blocks may be assigned to processors on a computing cluster interconnected via communication links. It becomes advantageous to position nodes close to each other on the target graph if they are adjacent in the original (hyper)graph. However, conventional objective functions do not consider the topology of the target graph during partitioning. We therefore provide a mode that maps the nodes of a (hyper)graph onto the nodes of a target graph. During this process, the partitioning algorithm optimizes the Steiner tree metric. The objective here is to minimize the total weight of all minimal Steiner trees induced by the (hyper)edges of the hypergraph on the target graph. For more information about this metric, we refer the reader to the Supported Objective Functions section.**Fixed Vertices**: Fixed vertices are nodes that are preassigned to a particular block and are not allowed to change their block during partitioning.

Mt-KaHyPar can optimize several objective functions which we explain in the following in more detail. An objective function takes a partition Π = {V_1, ..., V_k} into k blocks of a weighted hypergraph H = (V,E,c,ω) with node weights c: V -> R and net weights ω: E -> R as input. The number of blocks spanned by a net e is denoted with λ(e) and the set of all cut nets with E_Cut(Π) (λ(e) > 1).

The cut-net metric is defined as total weight of all nets spanning more than one block of the partition Π (also called *cut nets*).

The connectivity metric additionally multiplies the weight of each cut net with the number of blocks λ(e) spanned by that net minus one. Thus, the connectivity metric tries to minimize the number of blocks connected by each net.

The sum-of-external-degree metric is similar to the connectivity metric, but does not subtract one from the number of blocks λ(e) spanned by a net. A peculiarity of this objective function is that removing a net from the cut reduces the metric by 2ω(e), while reducing the connectivity by one reduces the metric only by ω(e). Thus, the objective function prefers removing nets from the cut, while as secondary criteria it tries to reduce the connectivity of the nets.

The Steiner tree metric is the most versatile metric that we provide at the moment. A Steiner tree is a tree with minimal weight that connects a subset of the nodes on a graph (a more detailed definition can be found here). For a subset with exactly two nodes, finding a Steiner tree reverts to computing the shortest path between the two nodes. When optimizing the Steiner tree metric, we map the node set of a hypergraph H onto the nodes of a target graph G. The objective is to minimize the total weight of all Steiner trees induced by the nets of H on G.

For a net e, dist(Λ(e)) is the weight of the minimal Steiner tree connecting the blocks Λ(e) spanned by net e on G. The Steiner tree metric can be used to accurately model wire-lengths in VLSI design or communication costs in distributed systems when some processors do not communicate with each other directly or with different speeds.

We have implemented a common interface for all gain computation techniques that we use in our refinement algorithms. This enables us to extend Mt-KaHyPar with new objective functions without having to modify the internal implementation of the refinement algorithms. A step-by-step guide how you can implement your own objective function can be found here.

Keywords

Clustering

Data analysis

Graphs

High performance computing

Hypergraphs

KaHyPar

Mt-KaHyPar

Multilevel Algorithm

Parallel Computing

Partitioning

Research Software Engineering

License

- GPL-3.0-or-later
- MIT

</>Source code

Book section

4- 1.Author(s): Lars Gottesbüren, Michael HamannPublished in Lecture Notes in Computer Science, Euro-Par 2022: Parallel Processing by Springer International Publishing in 2022, page: 301-31610.1007/978-3-031-12597-3_19
- 2.Author(s): Lars Gottesbüren, Tobias Heuer, Peter Sanders, Sebastian SchlagPublished in 2022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) by Society for Industrial and Applied Mathematics in 2022, page: 131-14410.1137/1.9781611977042.11
- 3.Author(s): Merten Popp, Sebastian Schlag, Christian Schulz, Daniel SeemaierPublished in 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX) by Society for Industrial and Applied Mathematics in 2021, page: 1-1510.1137/1.9781611976472.1
- 4.Author(s): Lars Gottesbüren, Tobias Heuer, Peter Sanders, Sebastian SchlagPublished in 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX) by Society for Industrial and Applied Mathematics in 2021, page: 16-3010.1137/1.9781611976472.2

Conference papers

7- 1.Author(s): Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz, Bora UçarPublished by Schloss Dagstuhl – Leibniz-Zentrum für Informatik in 202210.4230/lipics.sea.2022.5
- 2.Author(s): Tobias Heuer, Nikolai Maas, Sebastian Schlag, David Coudert, Emanuele NatalePublished by Schloss Dagstuhl – Leibniz-Zentrum für Informatik in 202110.4230/lipics.sea.2021.8
- 3.Author(s): Lars Gottesbüren, Michael Hamann, Sebastian Schlag, Dorothea Wagner, Simone Faro, Domenico CantonePublished by Schloss Dagstuhl – Leibniz-Zentrum für Informatik in 202010.4230/lipics.sea.2020.11
- 4.Author(s): Robin Andre, Sebastian Schlag, Christian SchulzPublished in Proceedings of the Genetic and Evolutionary Computation Conference by ACM in 201810.1145/3205455.3205475
- 5.Author(s): Yaroslav Akhremtsev, Tobias Heuer, Peter Sanders, Sebastian SchlagPublished in 2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX) by Society for Industrial and Applied Mathematics in 201710.1137/1.9781611974768.3
- 6.Author(s): Tobias Heuer, Sebastian Schlag, Costas S. Iliopoulos, Solon P. Pissis, Simon J. Puglisi, Rajeev RamanPublished by Schloss Dagstuhl – Leibniz-Zentrum für Informatik in 201710.4230/lipics.sea.2017.21
- 7.Author(s): Sebastian Schlag, Vitali Henne, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Christian SchulzPublished in 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX) by Society for Industrial and Applied Mathematics in 201510.1137/1.9781611974317.5

Journal articles

2- 1.Author(s): Sebastian Schlag, Tobias Heuer, Lars Gottesbüren, Yaroslav Akhremtsev, Christian Schulz, Peter SandersPublished in ACM Journal of Experimental Algorithmics by Association for Computing Machinery (ACM) in 2022, page: 1-3910.1145/3529090
- 2.Author(s): Tobias Heuer, Peter Sanders, Sebastian SchlagPublished in ACM Journal of Experimental Algorithmics by Association for Computing Machinery (ACM) in 2019, page: 1-3610.1145/3329872

Other

4- 1.Author(s): Lars Gottesbüren, Dorothea Wagner, Henning MeyerhenkePublished by Karlsruher Institut für Technologie (KIT) in 202310.5445/ir/1000157894
- 2.Author(s): Lars Gottesbüren, Tobias Heuer, Nikolai Maas, Peter Sanders, Sebastian SchlagPublished by arXiv in 202310.48550/arxiv.2303.17679
- 3.Author(s): Tobias Heuer, Peter Sanders, Ümit ÇatalyürekPublished by Karlsruher Institut für Technologie (KIT) in 202210.5445/ir/1000152872
- 4.Author(s): Sebastian SchlagPublished by Karlsruhe in 202010.5445/ir/1000105953

LG

LG

Lars Gottesbüren

TH

Tobias Heuer

SS

Sebastian Schlag

Owner

NM

Nikolai Maas

PS

Peter Sanders

CS

Christian Schulz