Reproducible Experiments

Reproducible GraphBrew Experiments

This guide documents the frozen study runner retained for exact artifact reproduction. Use scripts/graphbrew_experiment.py rather than one-off runners; new research should follow the current roadmap instead of extending paper-specific matrices.

It covers the frozen matrix and the commands that regenerate its measurements, figures, tables, and manifests. Large graphs and artifacts live under /media/Data/00_GraphDatasets/GraphBrew, not repository-local results/graphs/.

1. Quick Start

# Preview
python3 scripts/graphbrew_experiment.py --vldb --paper-preview \
  --paper-graph-dir /media/Data/00_GraphDatasets/GraphBrew \
  --paper-artifact-root /media/Data/00_GraphDatasets/GraphBrew/artifacts \
  --paper-threads 4 --paper-cpu-list 24-27

# Full frozen matrix
python3 scripts/graphbrew_experiment.py --vldb \
  --paper-graph-dir /media/Data/00_GraphDatasets/GraphBrew \
  --paper-artifact-root /media/Data/00_GraphDatasets/GraphBrew/artifacts \
  --paper-threads 16 --paper-cpu-list 0-15

# Aggregate and publish figures from existing results
python3 scripts/graphbrew_experiment.py --vldb 5 \
  --paper-graph-dir /media/Data/00_GraphDatasets/GraphBrew \
  --paper-artifact-root /media/Data/00_GraphDatasets/GraphBrew/artifacts \
  --paper-dir /path/to/private-paper \
  --paper-publish-figures

Use the independent scripts under scripts/experiments/vldb/stages/ only for restartable long runs, with the same graph/artifact roots and thread/affinity policy.

2. Prerequisites

System Requirements

Linux x86-64 with GCC ≥ 7 (tested on Ubuntu 22.04 / 24.04)
At least 16 GB RAM for preview; the frozen full matrix targets the dedicated 256 GB-class evaluation host
Python ≥ 3.8

Graph Folder Layout (canonical reference)

All scripts resolve graphs through resolve_graph_path(), which tries two filesystem layouts and uses the first that exists:

# Nested layout (PREFERRED — what auto-download produces)
results/graphs/<name>/<name>.sg            # serialized graph (used by benchmarks)
results/graphs/<name>/<name>.el            # raw edge list (input to converter)
results/graphs/<name>/<name>.wel           # weighted edge list (sssp)
results/graphs/<name>/<name>.mtx           # MatrixMarket (intermediate from SuiteSparse)

# Flat layout (also accepted)
results/graphs/<name>.sg

Graph <name> must exactly match the "name" field in the graph catalog (EVAL_GRAPHS, EVAL_GRAPHS_64GB, etc. in scripts/experiments/vldb/config.py) — e.g. cit-Patents, soc-pokec, hollywood-2009, USA-road-d.USA, com-Orkut.

Three ways to populate this folder:

Method	Command	When
1. Auto-download (recommended)	`python3 scripts/experiments/vldb/runner.py --exp 2 --graphs cit-Patents --64gb --no-figures`	All 11 `--64gb` graphs except the 2 manual-download ones; fetches `.mtx` from SuiteSparse, converts to `.el` then `.sg`
2. Bulk pre-stage (login node before SLURM)	The for-loop in §8.1.5 below	One-time staging for cluster jobs
3. Manual placement	`mkdir -p results/graphs/<name> && cp my-graph.el results/graphs/<name>/<name>.el` then `bench/bin/converter -f .../<name>.el -b .../<name>.sg`	Custom datasets or twitter7/webbase-2001/Gong-gplus/wikipedia_link_en

Where graph derivatives are written (created automatically):

<artifact-root>/vldb_mappings/<name>/<algo>.lo
<artifact-root>/vldb_mappings/<name>/<algo>.json
<artifact-root>/vldb_runs/<name>/<algo>__<bench>.json
<artifact-root>/vldb_paper/exp<N>_<name>/*.json
<artifact-root>/INDEX.json
results/data/graph_properties.json         # lib ML-feature cache (auto-managed)

Use python3 -m scripts.lib.analysis.results_index --build-index to refresh the manifest on demand.

Override with --graph-dir if you keep graphs elsewhere (e.g. shared filesystem on HPC):

python3 scripts/experiments/vldb/runner.py --exp 2 --64gb \
    --graph-dir /scratch/$USER/graphs        # nested layout under here

Automatic Steps (handled by `--all`)

The script calls make -j$(nproc) and make all-sim -j$(nproc) automatically. If you prefer to build manually:

make all RABBIT_ENABLE=1      # standard benchmark binaries
make all-sim                   # cache simulation binaries
pip install matplotlib numpy   # optional: figure generation

Manual-Download Graphs (2 of 11)

Nine evaluation graphs are downloaded automatically from SuiteSparse. Two require manual preparation:

wikipedia_link_en

Source: KONECT — Wikipedia link (en)

Download the dataset, extract it, and convert the edge list to a file the converter can read (tab-separated edge list → .el):

mkdir -p results/graphs/wikipedia_link_en
# Download from KONECT, extract, and rename to .el
# Place the edge-list file at:
#   results/graphs/wikipedia_link_en/wikipedia_link_en.el

Gong-gplus

Source: Duke University — Google+ Social Networks (Google Drive link)

The dataset contains 4 temporal snapshots. To reconstruct snapshot 4 (28.9M vertices, 463M edges), keep all edges with TimeID 0–3:

mkdir -p results/graphs/Gong-gplus
# 1. Download from the Google Drive link above
# 2. Extract and keep all directed social links (TimeID 0–3)
# 3. Strip the TimeID column to produce a two-column edge list
# 4. Place as: results/graphs/Gong-gplus/Gong-gplus.el

Note: The auto-setup will print clear instructions for any missing manual-download graphs and proceed with the available ones.

3. Experiment Overview

The frozen evaluation consists of six sections, each mapped to specific experiments in the runner:

§	Study section	Experiment	What it measures
4.2	Cache Performance	Exp 1	Hierarchy lookups across cache sizes (fixed-work PR, representative matrix)
4.3	Kernel Speedup	Exp 2	Algorithm execution time normalized to the fixed Shuffled layout (7 benchmarks)
4.4	Overhead & E2E	Exp 3+4	Reorder preprocessing time + amortization analysis
4.5	Sensitivity & Composability	Exp 5+6+7	Graph-type sensitivity, controlled one-axis contrasts, chained orderings
4.6	Scalability	Exp 8	Thread scaling of reorder step (1–32 threads)

Algorithms Evaluated

Algorithms Evaluated (13): Shuffled, Random, SORT, HubSort, HubCluster, DBG, HubSortDBG, HubClusterDBG, RabbitOrder (CSR), RabbitOrder (Boost), Gorder (9:csr, mapping-equivalent CSR implementation), RCM, GoGraph

<<<<<<< HEAD GraphBrew Variants (10): Leiden, Rabbit, HubCluster, HRAB, TQR, HCache, Streaming, Rabbit-DBG, Rabbit-HubCluster, RCM

GraphBrew Variants (10): Leiden, Rabbit, HubCluster, HRAB, HRAB-BFS, TQR, HCache, Streaming, Rabbit-DBG, Rabbit-HubCluster

2b11415 (Bind ordering guidance to measured evidence)

Chained Orderings (5): GB-Leiden→DBG, GB-Leiden→HubCluster, GB-HRAB→DBG, GB-Leiden→GoGraph, RabbitOrder→DBG

Benchmark Algorithms (7)

BFS, PR (PageRank), PR-SpMV, SSSP, CC (Afforest), CC-SV, BC

<<<<<<< HEAD

Recommendation proof contract

A “when to use” row is publication-eligible only when it records:

the exact ordered -o specification, not a development nickname;
whether the objective is kernel-only ordering quality or end-to-end time;
graph, kernel, labeling, thread, source/work, and reuse scope;
mapping generation, validation, and CSR-application cost separately;
both Rabbit CSR and Rabbit Boost when making a Rabbit comparison;
a graph-level paired confidence interval for aggregate claims;
a negative or inconclusive result when the interval crosses one; and
a content hash of the raw result matrix.

Pre-generated mappings are reused byte-for-byte across kernels. BFS, BC, and SSSP must report original source IDs; weighted SSSP also validates weight checksum, delta, and cross-ordering answer fingerprints. Documentation claims are regression-checked against the frozen matrices by scripts/test/test_documented_recommendations.py.

2b11415 (Bind ordering guidance to measured evidence)

Evaluation Graphs (11)

Graph	Vertices (M)	Edges (M)	Type
cit-Patents	6.01	16.52	Citation
soc-pokec	1.63	30.62	Social
USA-road-d.USA	23.95	58.33	Road
soc-LiveJournal1	4.85	68.99	Social
delaunay_n24	16.78	100.66	Mesh
hollywood-2009	1.14	113.89	Collaboration
com-Orkut	3.07	117.19	Social
wikipedia_link_en	12.15	378.14	Content
Gong-gplus	28.94	462.99	Social
webbase-2001	118.14	1,019.90	Web
twitter7	61.79	1,468.36	Social

4. Running Experiments

4.0 Recipe Cheatsheet (most common tasks)

Each row is a copy-pasteable command — run from the repo root with the venv activated. Bold = which artefacts the recipe produces.

Goal	Command	Produces
Smoke test (2 graphs, ~10 min)	`python3 scripts/experiments/vldb/stages/02_reorder.py --exp 2 --preview && python3 scripts/experiments/vldb/stages/03_cpu_perf.py --exp 2 --preview && python3 scripts/experiments/vldb/stages/05_aggregate.py --exp 0`	mappings, runs, exp2 table, figures, INDEX.json
Reorder `.lo` only — cache the permutation, no kernels	`python3 scripts/experiments/vldb/stages/02_reorder.py --exp 2 --graphs cit-Patents soc-pokec`	`results/vldb_mappings/<g>/<algo>.{lo,json}`
Speedups only (assumes `.lo` already cached)	`python3 scripts/experiments/vldb/stages/03_cpu_perf.py --exp 2 --graphs cit-Patents`	`results/vldb_runs/<g>/<algo>__<bench>.json` + `vldb_paper/exp2_speedup/speedup_results.json`
Reorder + kernels in one shot for new graph	`python3 scripts/experiments/vldb/stages/02_reorder.py --exp 2 --graphs <g> && python3 scripts/experiments/vldb/stages/03_cpu_perf.py --exp 2 --graphs <g>`	both of the above
Final cache cohort (sim binary)	`python3 scripts/experiments/vldb/stages/04_cache_sim.py --exp 1`	`results/vldb_paper/exp1_cache/cache_results.json`
Aggregate figures and tables	`python3 scripts/experiments/vldb/stages/05_aggregate.py --exp 0`	`INDEX.json`, final figures, and tables
Full frozen sweep (11-graph CPU stages, 4-graph cache stage)	`python3 scripts/experiments/vldb/runner.py --all --64gb`	complete frozen artifacts
Just figures from existing data	`python3 scripts/experiments/vldb/runner.py --figures-only`	regenerates structured figure outputs

The stages are independent and resumable — re-running 02 with .lo already present skips quickly; re-running 03 picks up exactly where it stopped (via ResultsStore in scripts/experiments/vldb/runner.py).

4.1 SLURM submission

All stages have matching sbatch wrappers under scripts/experiments/vldb/stages/slurm/.

SLURM smoke test (validates env + the 2-graph preview pipeline, ~10–30 min):

sbatch scripts/experiments/vldb/stages/slurm/smoke.sbatch
squeue -u $USER                       # track
tail -f results/slurm_logs/gbrew-smoke-*.out

Chained full pipeline (01 → 02 → 03 → 04 → 05 with proper deps):

# Full --64gb sweep (default)
EXTRA_ARGS="--64gb" bash scripts/experiments/vldb/stages/slurm/run_all.sh

# Skip the cache simulator (much faster — exp1 not needed)
SKIP_CACHE=1 EXTRA_ARGS="--64gb" bash scripts/experiments/vldb/stages/slurm/run_all.sh

# Preview on cluster (sanity-check job environment)
EXTRA_ARGS="--preview" bash scripts/experiments/vldb/stages/slurm/run_all.sh

# Specific subset (e.g. cit-Patents only)
GRAPHS="cit-Patents" bash scripts/experiments/vldb/stages/slurm/run_all.sh

Individual stages with env overrides:

# Just reorder cache for a single big graph
sbatch --export=ALL,GRAPHS=twitter7 \
       scripts/experiments/vldb/stages/slurm/02_reorder.sbatch

# Just speedups (requires .lo files from stage 02)
sbatch --export=ALL,GRAPHS=com-Orkut,EXP=2 \
       scripts/experiments/vldb/stages/slurm/03_cpu_perf.sbatch

# Cache sim on a slow / shared partition (CPU-speed independent)
sbatch --partition=largemem --mem=512G \
       --export=ALL,GRAPHS=twitter7 \
       scripts/experiments/vldb/stages/slurm/04_cache_sim.sbatch

# Final figures + INDEX.json
sbatch scripts/experiments/vldb/stages/slurm/05_aggregate.sbatch

Override knobs supported by every sbatch wrapper via --export=ALL,KEY=VAL:

Var	Default	Notes
`EXP`	2 (or 1 for cache_sim)	Experiment selector
`GRAPHS`	`""` → uses `EVAL_GRAPHS`	Space-separated graph names
`EXTRA_ARGS`	`""`	Extra CLI flags, e.g. `"--preview"`, `"--64gb"`, `"--local"`
`OMP_NUM_THREADS`	`SLURM_CPUS_PER_TASK`	Override for thread sweeps

4.2 Direct Python entry points

The legacy monolithic runner is still available for development:

# Run all 8 experiments (auto-setup included):
python3 scripts/experiments/vldb/runner.py --all

# Run all experiments with graphs in a specific directory:
python3 scripts/experiments/vldb/runner.py \
    --all --skip-setup --graph-dir /data/graphs

# Run specific experiments (e.g., cache + speedup only):
python3 scripts/experiments/vldb/runner.py \
    --exp 1 2

# Skip figure generation:
python3 scripts/experiments/vldb/runner.py \
    --all --no-figures

Preview Mode

For fast validation before the full run:

python3 scripts/experiments/vldb/runner.py --all --preview

Preview uses: 2 small graphs, 1 trial, 2 benchmarks (PR, BFS), 300s timeout.

Custom Graph Set

python3 scripts/experiments/vldb/runner.py \
    --all --graphs cit-Patents soc-pokec

Figure Generation Only

# From real experiment data:
python3 scripts/experiments/vldb/runner.py --figures-only

# With sample/placeholder data (for layout preview):
python3 scripts/experiments/vldb/figures.py --sample-data

5. Generated Outputs

results/vldb_paper/
├── MANIFEST.json              # Reproducibility metadata (git revision, config, timing)
├── exp1_cache/                # Cache simulation results (JSON)
│                              #   Per-record fields: timing (average_time, reorder_time, …)
│                              #   + L1/L2/L3 cache metrics (l1_hits, l1_misses, l1_hit_rate, …)
├── exp2_speedup/              # Kernel speedup results (JSON)
├── exp3_overhead/             # Reorder overhead results (JSON, .sg input with .el fallback)
├── exp4_e2e/                  # End-to-end derived data
├── exp5_ablation/             # Controlled one-axis contrast results (JSON)
├── exp6_sensitivity/          # Graph-type sensitivity metadata
├── exp7_chained/              # Chained ordering results (JSON)
├── exp8_scalability/          # Thread scaling results (JSON, .sg input with .el fallback)
├── figures/                   # Generated PNG / PDF figures
│   ├── fig1_cache_performance.png
│   ├── fig2_kernel_speedup.png
│   ├── fig3_reorder_overhead.png
│   └── fig_h2h_pareto.{png,pdf}  # head-to-head vs Gorder + Rabbit Pareto
└── tables/                    # Generated LaTeX table snippets
    ├── table_ablation.tex
    ├── table_sensitivity.tex
    ├── table_chained.tex
    ├── table_h2h_per_graph.tex  # paper headline comparison
    └── table_h2h_summary.tex    # cross-graph geo-mean + wins

Optional publication export requires an explicit private paper workspace. See comparison_vs_baselines() in scripts/experiments/vldb/figures.py for head-to-head artifact generation.

5.1 Per-cell sidecars (raw measurements)

Every algorithm run also writes a self-describing JSON sidecar next to its cached artefacts, in addition to the aggregated tables above. Each sidecar holds the exact cmd, environment, parsed timings, and a stdout tail — enough to replay a single (graph, algo, benchmark) cell in isolation.

Sidecar	Path	Schema	Written by
Reorder cache	`<artifact-root>/vldb_mappings/<graph>/<algo>.json`	`reorder_meta/v1`	stage 02
Kernel run	`<artifact-root>/vldb_runs/<graph>/<algo>__<bench>.json`	`kernel_run/v1`	stage 03
Manifest	`<artifact-root>/INDEX.json`	`results_index/v1`	stage 05

<algo> is the algorithm key with : and / replaced by _ (e.g. 9_leiden_compose_intra_hubsort).

5.2 Analysing results — canonical loader

The shared library exposes one entry point that flattens any sidecar tree to row-shaped dicts (and pandas DataFrames when pandas is installed):

from scripts.lib.analysis.results_index import (
    walk_kernel_runs, walk_reorder_meta, walk_aggregates,   # dict-list (no deps)
    load_runs_df,    load_reorder_df,    load_aggregates_df, # pandas (optional)
    build_index,
)

runs = load_runs_df()        # one row per kernel run
agg  = load_aggregates_df()  # one row per cell across all exp tables

# Example: PR speedup vs SHUFFLED across all graphs
import pandas as pd
pr = runs[runs.benchmark == "pr"]
base = pr[pr.algo_key == "0"].set_index("graph").average_time
pr["speedup"] = pr.apply(lambda r: base[r.graph] / r.average_time, axis=1)
print(pr.groupby("algo_key").speedup.mean().sort_values(ascending=False).head(10))

Available row columns (when present in stdout): graph, algo_key, benchmark, average_time, trial_times, reorder_time, reorder_time_passes, reorder_source, map_load_time, read_time, topology_analysis_time, relabel_map_time, mteps, iterations, modularity, degree_variance, hub_concentration, clustering_coefficient, avg_path_length, ….

Rebuild the top-level manifest on demand:

python3 -m scripts.lib.analysis.results_index --build-index
# wrote /…/results/INDEX.json

5.3 Replaying a single cell

Every sidecar embeds the exact command and env. To re-run one (graph, algo, benchmark) cell:

F=results/vldb_runs/email-Eu-core/9_leiden_compose_intra_hubsort__bfs.json
cmd=$(jq -r '.cmd | join(" ")' "$F")
env $(jq -r '.env | to_entries | map("\(.key)=\(.value)") | join(" ")' "$F") $cmd

5.4 Adding a new analysis figure

Load the data once via load_runs_df() or load_aggregates_df().
Filter / group with pandas.
Write the figure under the configured structured artifact directory.
Stage 05 will regenerate INDEX.json on the next run; the new file does not need to be tracked by the pipeline.

6. Configuration Reference

All experiment parameters are defined in scripts/experiments/vldb/config.py:

Parameter	Full	Preview
Trials	3	1
Benchmarks	7 (bfs, pr, pr_spmv, sssp, cc, cc_sv, bc)	2 (pr, bfs)
Graphs	11	2
Timeout (per command)	3600s	300s
Thread counts (scaling)	1, 2, 4, 8, 16, 32	1, 2, 4, 8, 16, 32

CLI Flags

Flag	Description
`--all`	Run all 8 experiments
`--exp N [N ...]`	Run specific experiment(s) by number (1-8)
`--preview`	2 small graphs, 1 trial, 2 benchmarks (validation)
`--local`	6 graphs ≤117M edges (cit-Patents → com-Orkut, fits 64 GB)
`--64gb`	11 auto-downloadable graphs (no >1B-edge graphs)
`--dry-run`	Print commands without executing
`--graph-dir PATH`	Directory containing graph files (default: `results/graphs` with `--skip-setup`)
`--graphs NAME [...]`	Override graph list by name
`--skip-setup`	Skip the auto-setup phase (build, download, convert)
`--skip-download`	Skip graph download but still build + convert
`--no-figures`	Skip automatic figure generation
`--figures-only`	Generate figures from existing results (no experiments)

64 GB Graph Set

For machines with 32–64 GB RAM, use --64gb to select an alternative set of 11 auto-downloadable graphs that avoids twitter7 and webbase-2001 (both >1B edges, require >64 GB RAM). This set adds as-Skitter, kron_g500-logn21, indochina-2004, and uk-2002 for type diversity:

python3 scripts/experiments/vldb/runner.py --all --64gb

7. Troubleshooting

Common Issues

"Binary not found" — The script builds binaries automatically. If auto-build fails, run make all RABBIT_ENABLE=1 && make all-sim manually.

"Graph file not found" — Either let auto-setup download the graphs, or ensure --graph-dir points to a directory with .sg files matching the graph names in the config. Both flat layout (cit-Patents.sg) and nested layout (cit-Patents/cit-Patents.sg) are supported. Experiments 3 and 8 try .sg first and fall back to .el automatically.

"Conversion failed" for SuiteSparse graphs — Some SuiteSparse archives contain auxiliary .mtx files (e.g., *_nodename.mtx) alongside the actual graph matrix. The converter prefers files named exactly {graph_name}.mtx. If conversion fails, check that the correct .mtx file exists in the nested directory (results/graphs/{name}/{name}/{name}.mtx).

Graphs that need manual download — wikipedia_link_en (KONECT) and Gong-gplus (Google Drive) cannot be auto-downloaded. See Prerequisites §2 for download instructions. The script will skip these graphs and proceed with the rest.

"matplotlib not available" — Install with pip install matplotlib numpy. Tables will still be generated without matplotlib.

"Timeout" — Large graphs (twitter7, webbase-2001) may need longer timeouts. Edit TIMEOUT_FULL in vldb_config.py.

Extending

To add a new graph or algorithm, edit scripts/experiments/vldb/config.py:

EVAL_GRAPHS — add graph metadata
BASELINE_ALGORITHMS — add algorithm ID and name
GRAPHBREW_VARIANTS — add variant string
CHAINED_ORDERINGS — add (name, flags) tuple

Result JSON Schema

All experiment JSON files share a common set of timing fields extracted by parse_timing(): trial_time, reorder_time, average_time, preprocessing_time, total_time, topology_analysis_time, read_time, relabel_map_time.

Experiment 1 additionally includes per-cache-level metrics extracted by parse_cache_sim(): l1_hits, l1_misses, l1_hit_rate, l2_hits, l2_misses, l2_hit_rate, l3_hits, l3_misses, l3_hit_rate, total_accesses, memory_accesses, overall_hit_rate, property working-set bytes, and traced edge-array bytes. The paper derives the hierarchy-lookup score H = total_accesses + l1_misses + l2_misses + l3_misses and normalizes it to Shuffled. LLC misses alone are not used to rank algorithms once the streamed edge array reaches its compulsory floor.

LaTeX tables (table_ablation.tex, table_sensitivity.tex, table_chained.tex) are populated from the JSON data automatically; fields that have no data yet show \emph{TBD}.

8. SLURM Runbook — UVA Cluster

Two-phase recipe: (a) a 30-minute smoke test that proves the harness, binaries, and ResultsStore work on the cluster, then (b) the full evaluation parallelised over per-(experiment, graph) jobs.

8.1 One-time UVA setup

<<<<<<< HEAD UVA Research Computing's Slurm reference:

UVA HPC Slurm reference:

2b11415 (Bind ordering guidance to measured evidence) https://www.rc.virginia.edu/userinfo/hpc/slurm/

# Clone + checkout
git clone https://github.com/<you>/GraphBrew.git
cd GraphBrew

# Inspect available partitions and your allocation accounts
qlist                          # partition list (UVA convenience wrapper)
qlimits                        # per-partition core/memory/time caps
sacctmgr -p show user $USER    # accounts you can charge
module avail gcc               # confirm gcc module name on the cluster
module avail miniforge         # confirm python/conda module name

# Edit scripts/experiments/vldb/slurm/monolithic.sbatch:
#   - --account=YOUR_UVA_ALLOC
#   - --partition=... (standard for single-node threaded jobs is the default)
#   - module load gcc miniforge   # change names if `module avail` shows different

Why standard partition? UVA's standard is the single-node serial/threaded queue, which is exactly what our 32-core OpenMP runs need. Use parallel only for true MPI multi-node work.

Data safety reminder: every job writes per-cell results via ResultsStore with atomic tmp + rename. If a job times out you can resubmit it verbatim — already-completed cells are skipped.

#SBATCH gotcha (UVA-confirmed): SLURM directives do not expand shell variables. Lines like #SBATCH --output=...-${GRAPH}.out produce filenames with literal ${GRAPH}. Use only %x (job-name) and %j (jobid) in --output=, and pass --job-name=gbrew-exp${exp}-${g} on the sbatch command line so the EXP/GRAPH appear in the log filename via %x. The template and examples below already do this.

8.1.5 Stage graphs on the login node (REQUIRED — compute nodes have no internet)

UVA Rivanna compute nodes do not have outbound internet, so SLURM jobs cannot themselves fetch graphs from SuiteSparse. The vldb_slurm.sbatch template therefore runs with --skip-setup --skip-download and aborts with a clear error if the .sg file is missing. Stage every graph once on the login node before submitting:

# Stage all 64GB graphs at once (builds binaries, downloads, converts to .sg).
# Each graph is small (~100MB-2GB .sg); total ~10GB; ~20-40 min on the
# login node depending on SuiteSparse mirror speed.
for g in cit-Patents soc-pokec hollywood-2009 soc-LiveJournal1 \
         com-Orkut USA-road-d.USA kron_g500-logn21 \
         indochina-2004 uk-2002; do
  python3 scripts/experiments/vldb/runner.py \
      --exp 2 --graphs "$g" --64gb --no-figures
done

# Verify all .sg files exist before sbatch:
for g in cit-Patents soc-pokec hollywood-2009 soc-LiveJournal1 \
         com-Orkut USA-road-d.USA kron_g500-logn21 \
         indochina-2004 uk-2002; do
  ls -la "results/graphs/$g/$g.sg" 2>/dev/null || echo "MISSING: $g"
done

The login-node --exp 2 invocation does double duty: it triggers auto-setup (build + download + .el → .sg conversion) and runs the experiment for that one graph. Because ResultsStore saves cells atomically, those results carry into the later SLURM run for free.

Big-graph addendum (twitter7, webbase-2001): these are not on SuiteSparse and need manual download from KONECT/Google-Drive — see VLDB_GRAPH_SOURCES in scripts/experiments/vldb/config.py. Place the .el under results/graphs/<name>/<name>.el on the login node and the SLURM job's converter step will pick it up.

Escape hatch: if your cluster does allow outbound HTTPS from compute nodes, set AUTO_SETUP=1 in --export to let the SLURM job download itself (not recommended on UVA standard partition).

8.2 Phase A — SLURM smoke test (30 min, one graph, one experiment)

The goal here is to validate environment / modules / scratch I/O / SLURM account before spending real allocation on the full sweep.

# Submit ONE job: smallest experiment × smallest graph.
# Pass --job-name with EXP/GRAPH baked in so the log filename is descriptive.
sbatch --time=00:30:00 \
       --job-name=gbrew-exp2-cit-Patents \
       --export=ALL,EXP=2,GRAPH=cit-Patents,GRAPHSET=local \
       scripts/experiments/vldb/slurm/monolithic.sbatch

# Watch it land
squeue -u $USER
tail -f results/slurm_logs/gbrew-exp2-cit-Patents-*.out

Success criteria — check after job completes:

# 1. Did it write the JSON?
ls -la results/vldb_paper/exp2_speedup/speedup_results.json

# 2. Are all cells valid (60 rows expected for --preview-ish single-graph)?
python3 -c "
import json
d = json.load(open('results/vldb_paper/exp2_speedup/speedup_results.json'))
valid = [r for r in d if r.get('average_time') is not None]
compose = [r for r in d if 'compose' in str(r.get('algo_id') or '')]
print(f'rows={len(d)} valid={len(valid)}/{len(d)} compose={len(compose)}')
assert len(valid) == len(d), 'some cells have no timing — check logs'
assert len(compose) > 0, 'compose configs did not run — parser failure?'
print('SMOKE TEST PASSED')
"

# 3. Test resume — resubmit; should finish in <1 min thanks to ResultsStore
sbatch --time=00:10:00 \
       --job-name=gbrew-exp2-cit-Patents-resume \
       --export=ALL,EXP=2,GRAPH=cit-Patents,GRAPHSET=local \
       scripts/experiments/vldb/slurm/monolithic.sbatch
# Look for "Resume: loaded N existing results" in the new log.

UVA-specific health checks (the canonical commands from https://www.rc.virginia.edu/userinfo/hpc/slurm/#displaying-job-status):

squeue -u $USER                              # is it queued / running?
scontrol show job <jobid>                    # detailed state
seff <jobid>                                 # CPU + memory efficiency after completion
sacct -u $USER --format=JobID,JobName,State,ExitCode,Elapsed

If any of the three checks fails, stop and fix before Phase B. Common gotchas:

Symptom	Cause	Fix
`module: command not found`	wrong module env on partition	check `module avail` and edit `vldb_slurm.sbatch`
`gcc/12: Unable to locate`	module name differs on cluster	run `module avail gcc` and update the `module load` line
`bench/bin/converter: not found`	build failed silently	run `make -j$SLURM_CPUS_PER_TASK pr bfs cc sssp bc tc converter` manually first
`Permission denied` on `results/slurm_logs/`	log dir doesn't exist	`mkdir -p results/slurm_logs` before sbatch
`Invalid account`	wrong `--account=`	`sacctmgr -p show user $USER` to list yours
Log file literally named `*-exp${EXP}-${GRAPH}.out`	shell vars don't expand in `#SBATCH`	use `--job-name=gbrew-exp${exp}-${g}` on the sbatch command line; the template's `--output=%x-%j.out` then bakes EXP/GRAPH in via `%x`
All cells valid timing but 0 compose rows	old `vldb_config.py` deployed	`git pull` on the cluster

8.3 Phase B — Full frozen evaluation (parallel fan-out)

After smoke test passes, fan out the priority A experiments (exp2 kernel speedup, exp3 reorder amortisation, exp8 thread scalability) across 9 graphs from the 64-GB set. That's 27 jobs, each runs independently, each ≤ 4h wall.

# Skip the smallest graphs you already smoked + the manual-download ones
GRAPHS_64GB=(
  cit-Patents soc-pokec USA-road-d.USA soc-LiveJournal1
  delaunay_n24 hollywood-2009 com-Orkut
  kron_g500-logn21 indochina-2004 uk-2002
)

# Three priority experiments cover kernel speedup, amortisation, and
# scalability. Each iteration pre-sets --job-name so EXP/GRAPH show up
# in squeue and in the log filename via the %x token.
for g in "${GRAPHS_64GB[@]}"; do
  for exp in 2 3 8; do
    sbatch --time=04:00:00 \
           --job-name=gbrew-exp${exp}-${g} \
           --export=ALL,EXP=$exp,GRAPH=$g,GRAPHSET=64gb \
           scripts/experiments/vldb/slurm/monolithic.sbatch
  done
done

# Check submission count (should be 30 jobs)
squeue -u $USER -h | wc -l

Alternative — Job Arrays (UVA-recommended for large fan-outs). SLURM job arrays (--array=1-N) submit hundreds of tasks under one jobid, and cancel/requeue is per-task. They require an options.txt with one (EXP,GRAPH) per line and a small wrapper around the template. See https://www.rc.virginia.edu/userinfo/hpc/slurm/#using-files-with-job-arrays. For 30 jobs the simple for loop above is fine; switch to arrays if you ever scale to hundreds of cells.

Re-submit timeouts. SLURM returns exit code 124 for timeout; just rerun the exact same sbatch line — ResultsStore picks up where it left off. Find timeouts with:

sacct -u $USER --format=JobID,JobName,State,ExitCode,Elapsed --state=TIMEOUT

8.4 What NOT to run (or run only if budget allows)

Experiment	Why skip	If you have time
exp1 cache-sim	3+ days on 64gb (cycle-accurate sim per cell). v5 §17 already gives the cache-mechanism story.	Run only on 3 representative graphs: `cit-Patents`, `hollywood-2009`, `com-Orkut`.
exp4 end-to-end	Derivable from exp2 + exp3 JSON by `vldb_generate_figures.py` — no new measurement needed.	(already auto-computed)
exp5 contrasts	Five registered pairwise COMPOSE contrasts.	Run the frozen graph set; do not substitute the retired incremental matrix.

The optional two-swap contrast excludes only Twitter7 after both implementations exceeded the fixed six-hour optional-refinement applicability budget. Core mapping generation has a separate twelve-hour timeout. The exclusion is recorded in ALGORITHM_GRAPH_EXCLUSIONS; no core Twitter7 configuration is removed. The evidence is retained at scripts/experiments/vldb/twitter_refine_2swap_timeout_evidence.json. The matched no-refinement configuration finishes in 70.48 seconds (3.77 seconds for COMPOSE), with only 11 non-isolated communities; two-swap therefore has little block-level parallelism and repeatedly scans concentrated intra-community edges. | exp6 sensitivity | Already covered by exp2's per-graph breakdown. | (skip) | | exp7 chained | Small (210 cells). Adds the chained-ordering comparison. | Optional diagnostic. |

8.5 Big-graph addendum (256 GB nodes)

Twitter7 (1.5B edges) and webbase-2001 (1B edges) are the most impactful generalization checks but only fit on 256-GB partitions.

# Submit to a high-memory partition with extra wall time.
# Check `qlist` for the exact high-mem partition name on your cluster
# (commonly `largemem` on UVA Rivanna).
sbatch --partition=largemem --mem=256G --time=24:00:00 \
       --job-name=gbrew-exp2-twitter7 \
       --export=ALL,EXP=2,GRAPH=twitter7,GRAPHSET=full \
       scripts/experiments/vldb/slurm/monolithic.sbatch

sbatch --partition=largemem --mem=256G --time=24:00:00 \
       --job-name=gbrew-exp2-webbase-2001 \
       --export=ALL,EXP=2,GRAPH=webbase-2001,GRAPHSET=full \
       scripts/experiments/vldb/slurm/monolithic.sbatch

These two graphs require manual download (KONECT / Google Drive links in VLDB_GRAPH_SOURCES). Stage them under <graph-root>/<name>/<name>.el before submitting, then add --skip-download so the harness doesn't try to fetch.

8.6 Aggregation & figure generation

Once all jobs finish (or even mid-run), pull JSONs locally and generate figures. Because every job writes to the same <artifact-root>/vldb_paper/exp{N}_*/...json paths, the cluster filesystem already has the merged dataset.

# On the cluster (or rsync to local)
python3 scripts/experiments/vldb/runner.py --figures-only --64gb

# Outputs:
ls <artifact-root>/vldb_paper/figures/
ls <artifact-root>/vldb_paper/tables/

For multi-machine merges (some jobs on UVA, others elsewhere), each ResultsStore JSON is a flat list of result dicts — concat them with jq -s '.[0]+.[1]' or a 3-line Python script before running --figures-only.

8.7 Time budget at a glance

With 32-core nodes, 1 trial, all eight COMPOSE configs added to exp2/exp8:

Phase	Cells	Parallel jobs	Wall (worst-job)	Total alloc time
8.2 Smoke (1 graph × exp2)	60	1	~30 min	30 min
8.3 Priority A (10 graphs × exp 2,3,8)	~5,000	30	≤ 4 h	~120 CPU-hr
8.5 Big graphs (twitter, webbase × exp2)	~420	2	≤ 24 h	~48 CPU-hr
8.4 (optional) exp1 cache-sim on 3 graphs	~840	3	≤ 24 h	~72 CPU-hr

Total wall ≤ 1 day thanks to parallelism. Total alloc ≈ 270 CPU-h if you include the optional cache-sim.

See also: GraphBrewOrder, Running-Benchmarks, Command-Line-Reference, Cache-Simulation, Python-Scripts

Uh oh!

Reproducible Experiments

Reproducible GraphBrew Experiments

Table of Contents

1. Quick Start

2. Prerequisites

System Requirements

Graph Folder Layout (canonical reference)

Automatic Steps (handled by --all)

Manual-Download Graphs (2 of 11)

wikipedia_link_en

Gong-gplus

3. Experiment Overview

Algorithms Evaluated

<<<<<<< HEAD GraphBrew Variants (10): Leiden, Rabbit, HubCluster, HRAB, TQR, HCache, Streaming, Rabbit-DBG, Rabbit-HubCluster, RCM

Benchmark Algorithms (7)

<<<<<<< HEAD

Recommendation proof contract

Evaluation Graphs (11)

4. Running Experiments

4.0 Recipe Cheatsheet (most common tasks)

4.1 SLURM submission

4.2 Direct Python entry points

Preview Mode

Custom Graph Set

Figure Generation Only

5. Generated Outputs

5.1 Per-cell sidecars (raw measurements)

5.2 Analysing results — canonical loader

5.3 Replaying a single cell

5.4 Adding a new analysis figure

6. Configuration Reference

CLI Flags

64 GB Graph Set

7. Troubleshooting

Common Issues

Extending

Result JSON Schema

8. SLURM Runbook — UVA Cluster

8.1 One-time UVA setup

<<<<<<< HEAD UVA Research Computing's Slurm reference:

8.1.5 Stage graphs on the login node (REQUIRED — compute nodes have no internet)

8.2 Phase A — SLURM smoke test (30 min, one graph, one experiment)

8.3 Phase B — Full frozen evaluation (parallel fan-out)

8.4 What NOT to run (or run only if budget allows)

8.5 Big-graph addendum (256 GB nodes)

8.6 Aggregation & figure generation

8.7 Time budget at a glance

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Start

Core idea

Experiments

Reference

Development

Clone this wiki locally

Automatic Steps (handled by `--all`)