KaHyPar - Karlsruhe Hypergraph Partitioning

A multilevel hypergraph partitioning framework providing direct k-way and recursive bisection based partitioning algorithms that compute solutions of very high quality.

View the Project on GitHub SebastianSchlag/kahypar

KaHyPar - Karlsruhe Hypergraph Partitioning

License Linux & macOS Build Windows Build Code Coverage Coverity Scan SonarCloud Fossa
License: GPL v3 Travis-CI Status Appveyor Status codecov Coverity Status Quality Gate FOSSA Status

Table of Contents

What is a Hypergraph? What is Hypergraph Partitioning?

Hypergraphs are a generalization of graphs, where each (hyper)edge (also called net) can connect more than two vertices. The k-way hypergraph partitioning problem is the generalization of the well-known graph partitioning problem: partition the vertex 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.

The two most prominent objective functions are the cut-net and the connectivity (or λ − 1) metrics. Cut-net is a straightforward generalization of the edge-cut objective in graph partitioning (i.e., minimizing the sum of the weights of those nets that connect more than one block). The connectivity metric additionally takes into account the actual number λ of blocks connected by a net. By summing the (λ − 1)-values of all nets, one accurately models the total communication volume of parallel sparse matrix-vector multiplication and once more gets a metric that reverts to edge-cut for plain graphs.

alt textalt text

What is KaHyPar?

KaHyPar is a multilevel hypergraph partitioning framework for optimizing the cut- and the (λ − 1)-metric. It supports both recursive bisection and direct k-way partitioning. As a multilevel algorithm, it consist of three phases: In the coarsening phase, the hypergraph is coarsened to obtain a hierarchy of smaller hypergraphs. After applying an initial partitioning algorithm to the smallest hypergraph in the second phase, coarsening is undone and, at each level, a local search method is used to improve the partition induced by the coarser level. KaHyPar instantiates the multilevel approach in its most extreme version, removing only a single vertex in every level of the hierarchy. By using this very fine grained n-level approach combined with strong local search heuristics, it computes solutions of very high quality. Its algorithms and detailed experimental results are presented in several research publications.

Additional Features

KaHyPar now has support for variable block weights. If command line option --use-individual-blockweights=true is used, the partitioner tries to partition the hypergraph such that each block Vx has a weight of at most Bx, where Bx can be specified for each block individually using the command line parameter --blockweights= B1 B2 B3 ... Bk-1. Since the framework does not yet support perfectly balanced partitioning, upper bounds need to be slightly larger than the total weight of all vertices of the hypergraph. Note that this feature is still experimental.

Experimental Results

We use the performance plots introduced in ALENEX’16 to compare KaHyPar to other partitioning algorithms in terms of solution quality: For each algorithm, these plots relate the smallest minimum cut of all algorithms to the corresponding cut produced by the algorithm on a per-instance basis. For each algorithm, these ratios are sorted in increasing order. The plots use a cube root scale for both axes to reduce right skewness and show 1 − (best/algorithm) on the y-axis to highlight the instances were each partitioner performs badly. A point close to one indicates that the alt text partition produced by the corresponding algorithm was considerably worse than the partition produced by the best algorithm. A value of zero therefore indicates that the corresponding algorithm produced the best solution. Points above one correspond to infeasible solutions that violated the balance constraint. Thus an algorithm is considered to outperform another algorithm if its corresponding ratio values are below those of the other algorithm.

Performance plots and detailed per-instance results can be found on the website accompanying each publication.

Additional Resources

|KaHyPar-MF (latest version of KaHyPar)|SEA’18| TR|-|Experimentel Results| |:–|:–|:–:|:–:|:–:| |KaHyPar-E / EvoHGP|GECCO’18|TR|-|Experimental Results| |KaHyPar-CA|SEA’17|Paper|Slides|Experimentel Results| |KaHyPar-K|ALENEX’17|Paper|Slides|Experimental Results| |KaHyPar-R|ALENEX’16|Paper|Slides|Experimental Results|


The Karlsruhe Hypergraph Partitioning Framework requires:

Building KaHyPar

  1. Clone the repository including submodules:

    git clone --depth=1 --recursive git@github.com:SebastianSchlag/kahypar.git

  2. Create a build directory: mkdir build && cd build
  3. Run cmake: cmake .. -DCMAKE_BUILD_TYPE=RELEASE
  4. Run make: make

Testing and Profiling

Tests are automatically executed while project is built. Additionally a test target is provided. End-to-end integration tests can be started with: make integration_tests. Profiling can be enabled via cmake flag: -DENABLE_PROFILE=ON.

Running KaHyPar

The binary is located at: build/kahypar/application/.

KaHyPar has several configuration parameters. For a list of all possible parameters please run: ./KaHyPar --help. We use the hMetis format for the input hypergraph file as well as the partition output file.

Currently we provide four different presets that correspond to the configurations used in the publications at ALENEX’16, ALENEX’17, SEA’17, SEA’18, and GECCO’18.

To start EvoHGP/KaHyPar-E (see pull request #23) optimizing the (connectivity - 1) objective using direct k-way mode run

 	./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_direct_kway_gecco18.ini

To start KaHyPar-MF (using flow-based refinement) optimizing the (connectivity - 1) objective using direct k-way mode run:

./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_direct_kway_sea18.ini

To start KaHyPar-CA (using community-aware coarsening) optimizing the (connectivity - 1) objective using direct k-way mode run:

./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_direct_kway_sea17.ini

To start KaHyPar in direct k-way mode (KaHyPar-K) optimizing the (connectivity - 1) objective run:

./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_direct_kway_alenex17.ini

To start KaHyPar in recursive bisection mode (KaHyPar-R) optimizing the cut-net objective run:

./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m recursive -p ../../../config/cut_rb_alenex16.ini

All preset parameters can be overwritten by using the corresponding command line options.

Bug Reports

We encourage you to report any problems with KaHyPar via the github issue tracking system of the project.


KaHyPar is free software provided under the GNU General Public License (GPLv3). For more information see the COPYING file. We distribute this framework freely to foster the use and development of hypergraph partitioning tools. If you use KaHyPar in an academic setting please cite the appropriate paper. If you are interested in a commercial license, please contact me.

// KaHyPar-R
 author    = {Sebastian Schlag and
              Vitali Henne and
              Tobias Heuer and
              Henning Meyerhenke and
              Peter Sanders and
              Christian Schulz},
 title     = {\emph{k}-way Hypergraph Partitioning via \emph{n}-Level Recursive
 booktitle = {18th Workshop on Algorithm Engineering and Experiments, (ALENEX 2016)},
 pages     = {53--67},
 year      = {2016},

// KaHyPar-K
 author    = {Yaroslav Akhremtsev and
              Tobias Heuer and
              Peter Sanders and
              Sebastian Schlag},
 title     = {Engineering a direct \emph{k}-way Hypergraph Partitioning Algorithm},
 booktitle = {19th Workshop on Algorithm Engineering and Experiments, (ALENEX 2017)},
 pages     = {28--42},
 year      = {2017},

// KaHyPar-CA
 author    = {Tobias Heuer and
              Sebastian Schlag},
 title     = {Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure},
 booktitle = {16th International Symposium on Experimental Algorithms, (SEA 2017)},
 pages     = {21:1--21:19},
 year      = {2017},

// KaHyPar-MF  - accepted at SEA'18
 author = ,
 title = ,
 year = {2018},
 Eprint = {1802.03587},

// KaHyPar-E (EvoHGP) - accepted at GECCO'18
 author = ,
 title = ,
 year = {2018},
 Eprint = {1710.01968},

A preliminary version our ALENEX’16 paper is available here on arxiv.

KaHyPar-MF integrates implementations of the BK and incremental breadth first search (IBFS) maximum flow algorithm into the framework (see /external_tools/maximum_flow/). The BK algorithm has been described in

“An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision.”
    Yuri Boykov and Vladimir Kolmogorov.
    In IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), September 2004.

The IBFS algorithm can be used for research purposes only and is described in

“Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search”
    Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Pushmeet Kohli, Robert E. Tarjan, and Renato F. Werneck
    In Proceedings of the 23rd European conference on Algorithms, ESA'15, 2015
 "Maximum flows by incremental breadth-first search"
    Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Robert E. Tarjan, and Renato F. Werneck.
    In Proceedings of the 19th European conference on Algorithms, ESA'11, 2011.


If you are interested in contributing to the KaHyPar framework feel free to contact me or create an issue on the issue tracking system.