KaHIP — High Quality Decomposition
We develop scalable algorithms for graph decomposition: partitioning, clustering, cuts, process mapping, and more. Developed at the Algorithm Engineering Group, Heidelberg University.
Our research covers a broad range of graph decomposition problems:
- Graph Partitioning -- divide a graph into k balanced blocks while minimizing the edges cut between them. NP-hard and central to parallel computing, VLSI design, scientific simulations, sparse matrix factorization, and route planning. Our tools range from high-quality multilevel methods with evolutionary search, to shared-memory and distributed-memory parallel partitioners, to streaming algorithms for graphs that do not fit in memory.
- Graph Cuts -- find minimum and maximum edge cuts in undirected graphs, and increase graph connectivity by augmentation. Applications include network reliability, connectivity analysis, image segmentation, and robust network design. We provide shared-memory parallel algorithms for exact and inexact minimum cuts, cactus representations of all minimum cuts, multiterminal cuts, and weighted connectivity augmentation algorithms.
- Graph Clustering -- identify densely connected communities without requiring a predefined number of clusters. Our tools optimize modularity, support motif-based local clustering, correlation clustering on signed graphs, and streaming approaches for large-scale inputs.
- Process Mapping -- assign communicating processes to hardware topologies so that communication cost is minimized. Closely related to graph partitioning, but accounts for hierarchical network distances.
- Hypergraph Partitioning -- partition hypergraphs where edges can connect more than two vertices. We provide FREIGHT, a fast streaming hypergraph partitioner. For high-quality hypergraph partitioning, see our sister organization KaHyPar.
| Repository |
Description |
| KaHIP |
Flagship framework: multilevel partitioning (KaFFPa), evolutionary algorithms (KaFFPaE), distributed-memory parallel partitioning (ParHIP), edge partitioning, node ordering, and ILP-based improvement |
| KaMinPar |
Shared-memory and distributed-memory parallel partitioner optimized for speed and low memory usage |
| mt-KaHIP |
Shared-memory parallel multilevel graph partitioning using TBB and OpenMP |
| HeiStream |
Buffered streaming graph and edge partitioner for graphs that do not fit in memory |
| FREIGHT |
Fast streaming hypergraph partitioner (SEA 2023 Best Paper Award) |
| CompressedStreamingGraphPartitioning |
Memory-efficient streaming partitioning via compressed block assignments |
| Repository |
Description |
| VieCut |
Shared-memory parallel minimum cut algorithms (inexact, exact, cactus) |
| HeiCut |
Exact minimum cuts in hypergraphs at scale using data reduction |
| HeiConnect |
Weighted connectivity augmentation algorithms: heuristics, local search, and ILP-based exact approaches |
| fpt-max-cut |
FPT-based data reduction and exact/heuristic solvers for the maximum cut problem |
brew install KaHIP/kahip/kahip
kaffpa network.graph --k 8 --preconfiguration=strong --output_filename=partition.txt
git clone --recursive https://github.com/KaHIP/KaMinPar.git && cd KaMinPar
cmake -B build -DCMAKE_BUILD_TYPE=Release && cmake --build build -j
./build/apps/KaMinPar -G network.graph -k 8 -t 16
brew install KaHIP/kahip/heistream
heistream network.graph --k=8 --batch_size=32768 # node partitioning
heistream network.graph --k=8 --batch_size=32768 --buffer_size=65536 --run-parallel # BuffCut (parallel)
heistream_edge network.graph --k=8 --batch_size=32768 # edge partitioning
brew install KaHIP/kahip/freight
hmetis_to_freight_stream hypergraph.hgr hypergraph.netl # convert hMETIS to net-list format
freight_cut hypergraph.netl --k=8 # hypergraph partitioning (cut-net)
freight_con hypergraph.netl --k=8 # hypergraph partitioning (connectivity)
freight_graphs network.graph --k=8 # graph partitioning
brew install KaHIP/kahip/streamcpi
stream_cpi network.graph --k=8 --rle_length=0 --kappa=20
brew install KaHIP/kahip/sharedmap
SharedMap -g network.graph -h 4:8:8 -d 1:10:100 -e 0.03 -c strong -t 16
brew install KaHIP/kahip/oms
streammultisection network.graph --k=1024 --enable_mapping --hierarchy_parameter_string=4:16:16 --distance_parameter_string=1:10:100
brew install KaHIP/kahip/viecut
viecut_mincut network.graph vc # heuristic minimum cut
viecut_mincut_parallel network.graph exact # exact parallel minimum cut
viecut_mincut_parallel -s -b network.graph cactus # most balanced minimum cut
brew install KaHIP/kahip/heicut
heicut_kernelizer hypergraph.hgr --ordering_type=tight --lp_num_iterations=1
heicut_kernelizer_parallel hypergraph.hgr --ordering_type=tight --lp_num_iterations=1 # parallel
heicut_submodular hypergraph.hgr --ordering_type=tight # vertex-ordering based
git clone --recursive https://github.com/KaHIP/HeiConnect.git && cd HeiConnect
./build.sh
# compute cactus graph using VieCut, then run solver
./extern/VieCut/build/mincut network.graph cactus -t network.xml
./deploy/solver -g network.graph -c network.xml -a gwc -o augmented.graph # greedy heuristic
./deploy/solver -g network.graph -c network.xml -a mst-connect-ls --depth 3 # MST + local search
./deploy/solver -g network.graph -c network.xml -a eilp --use-initial # exact ILP
brew install KaHIP/kahip/fpt-max-cut
fpt_max_cut -action kernelization -f network.graph -iterations 1 -total-allowed-solver-time 10
HeidelbergMotifClustering
brew install KaHIP/motifclustering/motifclustering
heidelberg_motif_clustering --algorithm social --graph network.graph --seed_node 42 --output community.txt
brew install KaHIP/kahip/vieclus
vieclus network.graph --time_limit=60 --output_filename=clustering.txt
brew install KaHIP/kahip/clustre
clustre network.graph --one_pass_algorithm=modularity --mode=strong
SCC (Scalable Correlation Clustering)
brew install KaHIP/kahip/scc
scc signed_network.graph --seed=0 # multilevel clustering
mpirun -n 4 scc_evolutionary signed_network.graph --time_limit=120 # memetic algorithm