Home / Research / Highway / Benchmark
A self-contained harness for comparing overlapping community detection algorithms: one call scores every algorithm on a graph, one line adds your own.
The Highway OCD Benchmark is a small, self-contained harness for comparing overlapping community detection algorithms on the same graphs under the same metrics — the Highway method, eight baselines, and one of your own. It is built for a researcher who has never seen the project: clone it, register a method in one line, and the comparison runs.
It ships nine algorithms — Highway as vendored C++17 source compiled on demand, plus eight cdlib baselines at the paper's parameters — the paper's five-metric panel, 53 synthetic graphs carrying their own ground truth, and four experiments that render the paper-style figures and their tables in pdf, png, csv and LaTeX.
Score every algorithm on a graph; then add your own and it appears everywhere, scored identically.
import pickle
from benchmark import compare_algorithms, register_algorithm
G = pickle.load(open("data/synthetic/lfr_N200/graph.gpickle", "rb"))
df = compare_algorithms(G) # baselines + Highway, ground truth read from the graph
# your method only has to satisfy: fn(G: nx.Graph) -> List[List[node]]
register_algorithm("my_ocd", my_ocd)
compare_algorithms(G, algos=["highway", "slpa", "my_ocd"])
The return value is a tidy DataFrame — status, runtime, number of communities, and the full metric panel per algorithm. A registered algorithm is not a special case anywhere downstream: it enters every comparison, every experiment and every figure on the same footing as the built-ins, because there is only one path through the code.
| What | Detail |
|---|---|
| Highway | Vendored C++17 source, compiled on demand — no prebuilt binary, no machine-specific path |
| 8 baselines | slpa, demon, kclique, walkscan, conga, congo, lais2, lfm — via cdlib, with the same parameters the paper used |
| The paper's metric panel | Q_ov (extended modularity, needs no ground truth) plus FRI, Dice, F*, ONMI when ground truth exists — the frozen implementations, not re-derived ones |
| 53 graphs | LFR and ABCD+o² corpora with ground truth, small enough to commit and to run through in minutes |
| 4 experiments | Performance, scalability, overlap and real-world — each producing the paper-style figure and its tables |
Each of these is somewhere the harness could have quietly become un-runnable, or quietly produced a comparison that was not one.
Highway is C++. Committing a compiled binary makes the repository work on one machine; committing a download step makes it break when the link moves. The C++17 source is vendored and built on first use through cmake, so what a user runs is compiled from what they can read.
Ground truth lives on the graph as G.nodes[v]["communities"] — a list, because a node may belong to several. There is no side-car file to keep in sync and no argument to get wrong, and a graph without it is scored unsupervised rather than scored against nothing.
One baseline (LFM) does not terminate on very low-mixing graphs. Without a bound, a single pathological cell wedges an overnight sweep and the run is lost. Each algorithm now runs under an in-process alarm; a timeout is recorded as a timeout in the results, which is a finding, not a gap.
COPRA and BigClam need third-party compiled binaries. Rather than bundle something that fails on someone else's machine, or silently drop two strong baselines, they are documented as registrable wrappers with a worked example — the honest state, stated.
The paper's plotting code was bound to the private context object of the research tree. It was vendored and decoupled, so a stranger's registered algorithm lands in the same crimson-on-panel figures, with seed error bands, that the paper uses — without needing anything from the research tree.
The real-world graphs are SNAP subsets in the hundreds of megabytes, and they are not mine to redistribute. The corpus that ships is the small synthetic one; the real-world runner takes a path, and the README says which SNAP datasets to point it at.
Four experiments, each running every algorithm live over a graph corpus and rendering the figure plus its tables. A registered algorithm is included automatically.
python examples/run_experiments.py # all four, shipped corpora
python examples/run_experiments.py --only performance,overlap
python examples/run_experiments.py --algos highway,slpa,my_ocd --timeout 120
| Experiment | What it produces |
|---|---|
performance | 5-metric panel against mixing — muw on LFR, xi on ABCD+o² — plus a best-baseline table and a seed-dispersion table |
scalability | Runtime against graph size on a log axis, plus runtime by size bin |
overlap | 4-metric panel against overlap eta, with per-seed error bands, plus an overlap-stability table |
realworld | Q_ov and runtime as grouped bars on graphs you supply, since real networks come with no ground truth |
Everything lands in results/experiments/ as pdf and png figures and csv and tex tables — the LaTeX is paper-ready, so a result can go from a fresh clone into a manuscript without being retyped. Metric computation, not community detection, dominates the runtime.
benchmark/ __init__.py the public API: compare_algorithms, register_algorithm, evaluate compare.py compare_algorithms(G, ...) -> DataFrame, with the per-algorithm timeout algorithms.py the registry: register_algorithm + the cdlib baselines + highway metrics.py evaluate() and ground_truth_cover(): the metric panel metrics_impl.py frozen metric implementations (Q_ov, FRI, Dice, F*, ONMI) highway/ python wrapper + vendored C++17 source + on-demand build script experiments/ corpus.py, sweep.py, runners.py, tables.py — the four experiments paper_viz/ the paper's figure style, decoupled from the research tree data/synthetic/ 53 LFR / ABCD+o² graphs carrying their own ground truth examples/ run_synthetic.py, run_experiments.py, run_realworld.py, add_your_algorithm.py, quickstart.ipynb
Two files are the whole contract a contributor needs: algorithms.py for how an algorithm enters, and metrics.py for how it is judged. Everything else can be read later or not at all.
git clone https://github.com/AmbitiousK/highway-ocd-benchmark.git
Highway itself is also available inside cdlib, if what you need is the algorithm rather than the comparison. This repository is for the comparison — and specifically for a comparison that includes something of yours.