Skip to content
@KaHIP

High Quality Decomposition

This is the org for open source frameworks to compute high quality decompositions fast.
README.md

KaHIP — High Quality Decomposition

KaHIP Logo

We develop scalable algorithms for graph decomposition: partitioning, clustering, cuts, process mapping, and more.

What We Work On

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. Applications include network reliability, connectivity analysis, and image segmentation. We provide shared-memory parallel algorithms for exact and inexact minimum cuts, cactus representations of all minimum cuts, and multiterminal cuts.
  • 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.

Projects

Graph Partitioning

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

Process Mapping

Repository Description
VieM Vienna Mapping and Sparse Quadratic Assignment (superseded by SharedMap)
IntegratedProcessMapping Integrated multilevel process mapping on hierarchical topologies
OnlineMultiSection Streaming process mapping and hierarchical graph partitioning
SharedMap Shared-memory algorithm for process mapping
mpicartreorderlib Reordering algorithms for the MPI_Cart_comm reorder flag

Graph Cuts

Repository Description
VieCut Shared-memory parallel minimum cut algorithms (inexact, exact, cactus)
HeiCut Exact minimum cuts in hypergraphs at scale using data reduction
fpt-max-cut FPT-based data reduction and exact/heuristic solvers for the maximum cut problem

Graph Clustering

Repository Description
HeidelbergMotifClustering Local motif clustering via triangle-based flow and partitioning methods
VieClus State-of-the-art for highest possible modularity values (formerly VieClus org)
CluStRE Get good clusters fast via streaming with multi-stage refinement
ScalableCorrelationClustering Multilevel and memetic signed/correlation graph clustering

Quick Start

KaHIP

brew install KaHIP/kahip/kahip
kaffpa network.graph --k 8 --preconfiguration=strong --output_filename=partition.txt

KaMinPar

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

HeiStream

git clone https://github.com/KaHIP/HeiStream.git && cd HeiStream && make
./heistream network.graph --k 8 --stream_buffer=1024

SharedMap

brew install KaHIP/kahip/sharedmap
SharedMap -g network.graph -h 4:8:8 -d 1:10:100 -e 0.03 -c strong -t 16

VieClus

brew install KaHIP/kahip/vieclus
vieclus network.graph --time_limit=60 --output_filename=clustering.txt

CluStRE

brew install KaHIP/kahip/clustre
clustre network.graph --one_pass_algorithm=modularity --mode=strong

FREIGHT

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

HeiCut

git clone https://github.com/KaHIP/HeiCut.git && cd HeiCut
./install_mtkahypar.sh
mkdir build && cd build && cmake -DCMAKE_BUILD_TYPE=Release .. && make
./build/heicut_kernelizer path/to/hypergraph.hgr --ordering_type=tight --lp_num_iterations=1

fpt-max-cut

brew install KaHIP/kahip/fpt-max-cut
fpt_max_cut -action kernelization -f network.graph -iterations 1 -total-allowed-solver-time 10

VieCut

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

HeidelbergMotifClustering

brew install KaHIP/motifclustering/motifclustering
heidelberg_motif_clustering --algorithm social --graph network.graph --seed_node 42 --output community.txt

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

Pinned Loading

  1. KaHIP KaHIP Public

    KaHIP -- Karlsruhe HIGH Quality Partitioning.

    C++ 474 108

  2. KaMinPar KaMinPar Public

    Shared-Memory and Distributed-Memory Parallel Graph Partitioning

    C++ 49 15

  3. FREIGHT FREIGHT Public

    FREIGHT: Fast Streaming Hypergraph Partitioning — SEA 2023 Best Paper Award

    C++ 15 4

  4. VieCut VieCut Public

    Shared-memory parallel minimum cut algorithms (inexact, exact, cactus, multiterminal)

    C++ 48 11

  5. VieClus VieClus Public

    Vienna Graph Clustering

    C++ 17 3

  6. CluStRE CluStRE Public

    Streaming Graph Clustering with Multi-Stage Refinement

    C++ 3

Repositories

Showing 10 of 22 repositories
View all repositories

Top languages

Loading…

Most used topics

Loading…