Skip to content

Home

Jump to bottom
Abdullah edited this page Mar 5, 2026 · 36 revisions

GraphBrew Wiki

Welcome to the GraphBrew wiki! This comprehensive guide will help you understand, use, and extend the GraphBrew framework for graph reordering and benchmark analysis.

🍺 What is GraphBrew?

GraphBrew is a high-performance graph reordering framework that combines community detection with cache-aware vertex reordering to dramatically improve graph algorithm performance. It implements 17 algorithm IDs (0-16): 2 baselines (ORIGINAL, RANDOM), 13 reordering algorithms, and 2 reserved meta-algorithms (MAP, AdaptiveOrder).

Key Features

  • 17 Algorithm IDs: From simple sorting to advanced ML-based selection (IDs 0-16; 15 benchmark-eligible, 13 produce reorderings)
  • Leiden Community Detection: State-of-the-art community detection for graph partitioning
  • AdaptiveOrder: ML-powered adaptive selection (perceptron, decision tree, hybrid, database) with 7 selection modes, 16 linear features, 5 quadratic cross-terms, convergence-aware scoring, OOD guardrail, and LOGO cross-validation
  • Comprehensive Benchmarks: 8 available (PR, PR_SPMV, BFS, CC, CC_SV, SSSP, BC, TC); experiments default to 7 (TC excluded — combinatorial counting, not cache-sensitive traversal)
  • Random Baseline: Graphs auto-converted to .sg with RANDOM ordering so all measurements are relative to a worst-case baseline
  • Pre-generated Reordered .sg: Each algorithm's reordered graph is pre-generated as {graph}_{ALGO}.sg and loaded at benchmark time with -o 0, eliminating runtime reorder overhead
  • Amortization Analysis: Break-even iterations (N*), end-to-end speedup at N, and minimum efficient workload (MinN@95%)
  • Python Analysis Tools: Correlation analysis, benchmark automation, and weight training with multi-restart perceptrons, regret-aware optimization, and weight evaluation
  • Iterative Training: Feedback loop to optimize adaptive algorithm selection

📚 Wiki Contents

Getting Started

Understanding the Algorithms

Running Experiments

Advanced Topics

Developer Guide

Reference

🚀 Quick Example

One-Click Full Pipeline (Recommended)

# Clone, download graphs, build, and run complete experiment
git clone https://github.com/UVA-LavaLab/GraphBrew.git
cd GraphBrew
python3 scripts/graphbrew_experiment.py --full --size small

This single command will:

  1. Download benchmark graphs from SuiteSparse (87 graphs available)
  2. Build binaries automatically
  3. Convert .mtx → .sg with RANDOM baseline ordering
  4. Pre-generate reordered .sg per algorithm (13 algorithms, loaded at benchmark time with no runtime reorder overhead)
  5. Run all benchmarks with all 15 eligible algorithms
  6. Execute cache simulations (L1/L2/L3 hit rates)
  7. Store benchmark data to results/data/ — C++ trains ML models (perceptron, DT, hybrid) at runtime from this data

Options

# Auto-detect RAM and disk limits
python3 scripts/graphbrew_experiment.py --full --size all --auto

# Train perceptron weights
python3 scripts/graphbrew_experiment.py --train --size small

# Manual: run PageRank with GraphBrewOrder
./bench/bin/pr -f your_graph.el -s -o 12 -n 3

# Let AdaptiveOrder choose the best algorithm
./bench/bin/pr -f your_graph.el -s -o 14 -n 3

See Quick-Start for detailed examples, Benchmark-Suite for size categories, and Command-Line-Reference for all flags.

📊 Performance Overview

GraphBrew's performance gains depend on your graph's topology and the benchmark algorithm. Run the full pipeline on your target graphs to measure actual speedups.

The best reordering algorithm depends on your graph's structure — see Correlation-Analysis for details.

📋 Page Index

Page Description
Home This page - wiki overview
Installation Build requirements and instructions
Quick-Start 5-minute getting started guide
Supported-Graph-Formats EL, MTX, GRAPH format specs
Reordering-Algorithms All 16 algorithms explained
Graph-Benchmarks PR, PR_SPMV, BFS, CC, CC_SV, SSSP, BC, TC
Community-Detection Leiden algorithm details
Running-Benchmarks Manual benchmark execution
Benchmark-Suite Automated experiment runner
VLDB-Experiments VLDB 2026 experiment guide
Correlation-Analysis Feature-algorithm correlation
AdaptiveOrder-ML ML-based algorithm selection
Perceptron-Weights Weight file format & tuning
GraphBrewOrder Per-community hub ordering
Cache-Simulation Cache performance analysis
Adding-New-Algorithms Developer: add algorithms
Adding-New-Benchmarks Developer: add benchmarks
Code-Architecture Codebase structure
Python-Scripts Analysis & utility tools
Command-Line-Reference All CLI flags
Configuration-Files JSON config reference
Troubleshooting Common issues
FAQ Frequently asked questions

🔗 Quick Links

Last updated: February 2026

Clone this wiki locally