FREIGHT (Fast stREamInG Hypergraph parTitioning) is a streaming algorithm for hypergraph partitioning based on the Fennel algorithm. Part of the KaHIP organization.
| What it solves | Partition hypergraphs and graphs too large to fit in memory, or when you need fast partitioning |
| Objective | Minimize cut-net or connectivity metric with balanced block sizes |
| Key results | Superior to all existing streaming algorithms and the in-memory algorithm HYPE; competitive with Hashing in speed |
| Algorithm | Fennel-based streaming with efficient data structures for linear time and memory |
| Award | SEA 2023 Best Paper Award |
| Interfaces | CLI |
| Requires | C++17 compiler, CMake 3.10+ |
brew install KaHIP/kahip/freightgit clone https://github.com/KaHIP/FREIGHT.git && cd FREIGHT
./compile.sh# Partition a hypergraph into 8 blocks (connectivity metric)
freight_con myhypergraph.hgr --k=8
# Partition a hypergraph into 8 blocks (cut-net metric)
freight_cut myhypergraph.hgr --k=8
# Partition a graph (METIS format) into 8 blocks
freight_graphs mygraph.graph --k=8When building from source, binaries are in ./deploy/ (use ./deploy/freight_con etc.).
FREIGHT builds three partitioners and a format converter:
| Binary | Input format | Metric | Description |
|---|---|---|---|
freight_con |
Net-list | Connectivity | Hypergraph partitioning optimizing connectivity |
freight_cut |
Net-list | Cut-net | Hypergraph partitioning optimizing cut-net |
freight_graphs |
METIS | Edge-cut | Graph partitioning (Fennel-based streaming) |
hmetis_to_freight |
hMETIS | -- | Convert hMETIS to FREIGHT net-list (in-memory) |
hmetis_to_freight_stream |
hMETIS | -- | Convert hMETIS to FREIGHT net-list (two-pass, low memory) |
./deploy/freight_con <hypergraph-file> [options]
./deploy/freight_cut <hypergraph-file> [options]
./deploy/freight_graphs <graph-file> [options]
| Option | Description | Default |
|---|---|---|
--k=<int> |
Number of blocks to partition into | required |
--imbalance=<double> |
Allowed imbalance (e.g. 3 = 3%) | 3 |
--num_streams_passes=<int> |
Number of streaming passes (restreaming improves quality) | 1 |
--restream_vcycle |
Keep recursive bisections across restream passes | disabled |
--seed=<int> |
Random seed for the PRNG | 0 |
--ram_stream |
Stream from RAM instead of disk | disabled |
--output_filename=<string> |
Output file for the partition | tmppartition<k> |
--suppress_output |
Suppress console output | disabled |
--suppress_file_output |
Suppress writing partition to file | disabled |
--help |
Print all available options |
For a full list of parameters, run any executable with --help.
FREIGHT uses a node-centric net-list format for hypergraphs. Each line represents one node and lists which nets (hyperedges) it belongs to. This enables streaming: nodes are processed one at a time as lines are read, without loading the full hypergraph into memory.
Note: This is different from the standard hMETIS format, which is net-centric (one line per hyperedge). Use
hmetis_to_freightto convert, see Converting from hMETIS below.
Header line:
n m [f]
n= number of nodes,m= number of netsf= format flag (optional):0= unweighted,1= net weights,10= node weights,11= both
Node lines (one per node):
Each of the following n lines lists the nets that the node belongs to (1-indexed). With format flag 1 or 11, each net ID is followed by its weight. With flag 10 or 11, each line starts with the node weight.
Example (4 nodes, 3 nets, unweighted):
4 3
1 2
1 3
2
2 3
Node 1 belongs to nets 1 and 2, node 2 belongs to nets 1 and 3, node 3 belongs to net 2, node 4 belongs to nets 2 and 3.
For more details, see code_for_hypergraphs/examples/.
The standard hMETIS format is net-centric: the header is m n [f] (nets first, nodes second) and each line lists the pins (nodes) of a hyperedge.
The same hypergraph in hMETIS format (3 nets, 4 nodes):
3 4
1 2 ← net 1 contains nodes 1, 2
1 3 ← net 2 contains nodes 1, 3
2 4 ← net 3 contains nodes 2, 4
Converted to FREIGHT net-list format (4 nodes, 3 nets):
4 3
1 2 ← node 1 belongs to nets 1, 2
1 3 ← node 2 belongs to nets 1, 3
2 ← node 3 belongs to net 2
2 3 ← node 4 belongs to nets 2, 3
Both files describe the same hypergraph, but the net-list format is node-centric, enabling streaming. FREIGHT includes two converters:
# In-memory converter (loads full hypergraph, simple and fast)
hmetis_to_freight input.hgr output.netl
# Streaming converter (two-pass, O(n+m) memory instead of O(pins))
hmetis_to_freight_stream input.hgr output.netl
# Then partition
freight_cut output.netl --k=8Both converters produce identical output and handle all weight combinations (unweighted, node weights, net weights, or both). Use hmetis_to_freight_stream for hypergraphs too large to fit in memory. Example files in both formats are in code_for_hypergraphs/examples/.
FREIGHT uses the standard METIS graph format for graph partitioning. See the KaHIP manual for details.
Example (4 vertices, 5 edges, unweighted):
4 5
2 3
1 3 4
1 2 4
2 3
- C++17 compiler (GCC 7+ or Clang 11+)
- CMake 3.10+
From the repository root:
./compile.shOr using CMake directly:
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallelBinaries are placed in ./build/ (CMake) or ./deploy/ (compile.sh).
You can also build each code base independently:
cd code_for_hypergraphs && ./compile.sh # builds freight_cut, freight_con
cd code_for_graphs && ./compile.sh # builds freight_graphsFREIGHT processes hypergraph nodes in a streaming fashion, assigning each node to a block as it arrives:
- Streaming assignment: Each node is assigned to the block that maximizes a Fennel-based objective function, balancing partition quality against block sizes.
- Efficient data structures: Running time is linearly dependent on the pin-count; memory consumption is linearly dependent on the number of nets and blocks.
- No in-memory requirement: The full hypergraph never needs to be in memory, enabling partitioning of arbitrarily large inputs.
The algorithm is superior to all existing streaming hypergraph partitioners and even the in-memory algorithm HYPE, on both cut-net and connectivity metrics.
| Directory | Description |
|---|---|
| code_for_hypergraphs/ | FREIGHT for hypergraph partitioning (freight_cut, freight_con) |
| code_for_graphs/ | FREIGHT optimized for graph partitioning (freight_graphs) |
| experimental_results/ | Full experimental results from the paper |
| misc/ | SEA 2023 presentation slides |
| Project | Description |
|---|---|
| KaHIP | Karlsruhe High Quality Graph Partitioning (flagship framework) |
| HeiStream | Buffered streaming graph and edge partitioner |
| KaHyPar | Karlsruhe Hypergraph Partitioning |
FREIGHT is free software provided under the MIT License. If you publish results using our algorithms, please acknowledge our work by citing our paper:
@InProceedings{EyubovFS23,
author = {Eyubov, Kamal and Fonseca Faraj, Marcelo and Schulz, Christian},
title = {{FREIGHT: Fast Streaming Hypergraph Partitioning}},
booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)},
pages = {15:1--15:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
volume = {265},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
year = {2023},
doi = {10.4230/LIPIcs.SEA.2023.15}
}