A graph reordering and benchmarking framework built on the GAP Benchmark Suite (GAPBS). GraphBrew reorders graph vertices to improve cache locality and speed up graph algorithms — with 16 reordering algorithms, an ML-based adaptive selector, and a one-click experiment pipeline.
📖 Full documentation: Wiki · Quick Start · Command-Line Reference
# Clone and build
git clone https://github.com/UVA-LavaLab/GraphBrew.git
cd GraphBrew
make all
# Run PageRank with AdaptiveOrder (ML-selected best algorithm)
./bench/bin/pr -g 20 -o 14
# Run BFS with GraphBrewOrder (community-based reordering)
./bench/bin/bfs -f graph.mtx -o 12Requires Boost, libnuma, and google-perftools. See Installation Wiki for details.
make RABBIT_ENABLE=1 allGraphBrew provides 16 reordering strategies. Use -o <id> to select one (or chain multiple with -o <id1> -o <id2>):
| ID | Algorithm | Description |
|---|---|---|
| 0 | ORIGINAL | No reordering |
| 1 | RANDOM | Random permutation |
| 2 | SORT | Sort by degree |
| 3 | HUBSORT | Hub-based sorting |
| 4 | HUBCLUSTER | Hub-score clustering |
| 5 | DBG | Degree-based grouping |
| 6 | HUBSORTDBG | HubSort + DBG |
| 7 | HUBCLUSTERDBG | HubCluster + DBG |
| 8 | RABBITORDER | Community clustering (variants: csr / boost) |
| 9 | GORDER | Window-based BFS ordering |
| 10 | CORDER | Workload-balanced reordering |
| 11 | RCM | Reverse Cuthill-McKee |
| 12 | GRAPHBREWORDER | Leiden clustering + configurable per-community order |
| 13 | MAP | Load ordering from file (-o 13:mapping.lo) |
| 14 | ADAPTIVEORDER | ML perceptron — automatically picks the best algorithm ⭐ |
| 15 | LEIDENORDER | Leiden via GVE-Leiden library (15:resolution) — baseline reference |
| Graph Type | Recommended | Why |
|---|---|---|
| Social networks | 12 or 14 |
Best community detection + cache locality |
| Web graphs | 12:hrab or 12 |
Hybrid Leiden+Rabbit for best locality |
| Road networks | 11 or 9 |
BFS-based approaches for sparse graphs |
| Unknown / mixed | 14 |
Let the ML perceptron decide |
Run the complete benchmark + training workflow with one command:
# Install Python dependencies
pip install -r scripts/requirements.txt
# Full pipeline: download graphs → build → benchmark → train ML weights
python3 scripts/graphbrew_experiment.py --train --all-variants --size medium --auto --trials 5| Parameter | Description |
|---|---|
--train |
Train perceptron weights (runs the complete pipeline) |
--full |
Run full evaluation pipeline (no training) |
--all-variants |
Test all algorithm variants |
--size SIZE |
Graph category: small (62 MB), medium (1.1 GB), large (25 GB), xlarge (63 GB), all (89 GB) |
--auto |
Auto-detect RAM/disk limits |
--trials N |
Benchmark trials (default: 2) |
--quick |
Test only key algorithms (faster) |
--brute-force |
Compare adaptive selection vs all 16 algorithms |
--download-only |
Download graphs without running benchmarks |
Results are saved to ./results/. Trained weights go to ./scripts/weights/active/.
# See all options
python3 scripts/graphbrew_experiment.py --help📖 See Running Benchmarks Wiki for advanced workflows.
Built on GAPBS, GraphBrew includes these benchmarks:
| Benchmark | Algorithm |
|---|---|
pr |
PageRank |
bfs |
Breadth-First Search (direction optimized) |
cc |
Connected Components (Afforest) |
cc_sv |
Connected Components (Shiloach-Vishkin) |
sssp |
Single-Source Shortest Paths |
bc |
Betweenness Centrality |
tc |
Triangle Counting |
pr_spmv |
PageRank (SpMV variant) |
# Run a single benchmark
make run-bfs
# Run with parameters
./bench/bin/pr -f graph.mtx -n 16 -o 12
# Generate a reordered graph
./bench/bin/converter -f graph.mtx -p reordered.mtx -o 12📖 See Graph Benchmarks Wiki for details.
GraphBrew can load graphs in these formats:
| Extension | Format |
|---|---|
.el |
Edge list (node1 node2) |
.wel |
Weighted edge list |
.mtx |
Matrix Market |
.gr |
DIMACS |
.graph |
Metis |
.sg / .wsg |
Serialized (pre-built via converter) |
Graphs can also be generated synthetically:
-g 20— Kronecker graph with 2²⁰ vertices (Graph500)-u 20— Uniform random graph with 2²⁰ vertices
📖 See Supported Graph Formats Wiki for details.
- OS: Ubuntu 22.04+ (or any Linux with GCC ≥ 9)
- Compiler:
g++with C++17 and OpenMP support - Build:
make - Python: 3.8+ (for experiment scripts)
Optional (for RabbitOrder): Boost 1.58+, libnuma, google-perftools.
📖 See Installation Wiki for full setup instructions including Boost.
bench/
├── src/ # Benchmark source files (bc.cc, bfs.cc, pr.cc, ...)
├── src_sim/ # Cache simulation variants
├── bin/ # Compiled binaries
└── include/
├── graphbrew/ # Reordering algorithms & partitioning
├── external/ # Bundled libraries (GAPBS, RabbitOrder, GOrder, COrder, Leiden)
└── cache_sim/ # Cache simulation headers
scripts/
├── graphbrew_experiment.py # Main experiment orchestration
├── lib/ # Core Python modules
├── weights/ # Trained ML weights
└── test/ # Test suite
results/ # Benchmark outputs, graph features, mappings
📖 See Code Architecture Wiki for the full layout.
pip install -r scripts/requirements.txt
pytest scripts/test -q
# Topology verification (ensures reordering preserves graph structure)
make test-topologymake lint-includes # Check for legacy include paths
make help # Show all Make targets
make help-pr # Show parameters for a specific benchmarkIf you use GraphBrew in your research, please cite:
- S. Beamer, K. Asanović, D. Patterson, "The GAP Benchmark Suite," arXiv:1508.03619, 2017.
- J. Arai, H. Shiokawa, T. Yamamuro, M. Onizuka, S. Iwamura, "Rabbit Order: Just-in-time Parallel Reordering for Fast Graph Analysis."
- P. Faldu, J. Diamond, B. Grot, "A Closer Look at Lightweight Graph Reordering," arXiv:2001.08448, 2020.
- S. Sahu, "GVE-Leiden: Fast Leiden Algorithm for Community Detection in Shared Memory Setting," arXiv:2312.13936, 2024.
- V. A. Traag, L. Waltman, N. J. van Eck, "From Louvain to Leiden: guaranteeing well-connected communities," Sci Rep 9, 5233, 2019.
- H. Wei, J. X. Yu, C. Lu, X. Lin, "Speedup Graph Processing by Graph Ordering," SIGMOD 2016.
- Y. Chen, Y.-C. Chung, "Workload Balancing via Graph Reordering on Multicore Systems," IEEE TPDS, 2021.
See LICENSE for details.