VeloGraphX

Adaptive graph analytics for continuously evolving graphs

Update what changed when possible. Recompute when that is faster.

C++20 · Python · Dynamic Graphs · Reproducible Benchmarks

Docs · PyPI · Benchmarks · Reproducibility · Paper artifact · Releases

Why VeloGraphX?

Large graphs change continuously, but recomputing every analytic from scratch after every update can waste work. VeloGraphX keeps localized maintenance and full recomputation as explicit execution choices and can select between them as the graph and update regime change.

It supports BFS/unweighted SSSP, weighted SSSP, connected components, triangle counting, k-core and PageRank through a native C++20 engine and Python bindings.

Correctness signal: retained engineering stress testing covers 2,000,000 updates with 0 BFS mismatches and 0 triangle mismatches.

Try it in 30 seconds

python -m pip install velographx

import velographx as vx

g = vx.Graph(4, False)

updates = vx.UpdateBatch()
updates.add(0, 1)
updates.add(1, 2)
g.apply(updates)

bfs = vx.IncrementalBFS(g, 0)
print(bfs.distances)

If your workload has an evolving graph, start with the Python API above, then use the benchmark and reproducibility links for deeper evaluation.

What you get

• Adaptive execution: localized exact repair or exact full recomputation for dynamic BFS.
• Dynamic graph storage: segmented CSR, delta structures, sparse patches and explicit consolidation.
• Correctness-first analytics: exact maintained paths where supported, with validation and conservative fallback where required.
• C++ and Python: native API plus Python bindings.
• Reproducible evidence: pinned datasets, timing contracts, raw repetitions, checksums and machine-readable result artifacts.

Useful contributions are welcome: try VeloGraphX on a graph you care about, report a workload where the selector behaves poorly, reproduce a benchmark, or open a PR.

Architecture

The architecture keeps localized maintenance and full recomputation as explicit physical-plan choices, applies correctness and fallback checks, and links the implementation to reproducible benchmark evidence.

Key features

• Adaptive exact-plan execution for BFS: choose localized exact repair or exact full recomputation before repair begins; conservative internal fallback remains a separate safety/performance mechanism.
• Dynamic graph storage: segmented CSR, packed delta arenas, sparse row patches, forward/reverse adjacency, overlay cancellation, and explicit canonical CSR consolidation.
• Correctness-first analytics: exact maintained BFS/unweighted SSSP, connected components, triangle counting, and k-core; weighted SSSP preserves exact distances with conservative recomputation fallback; PageRank uses residual/tolerance validation with conservative fallback rather than a mathematical exactness claim.
• CPU execution and interoperability: multicore kernels, compression and partitioning support, graph-access abstractions, a native C++ API, and Python bindings.
• Reproducible systems evaluation: checksum-pinned datasets, pinned competitor revisions, explicit timing contracts, exactness gates, retained raw repetitions, machine-readable evidence registries, and documented negative results.

Installation and native build

For Python, install from PyPI:

python -m pip install velographx

C++ / build from source

For native C++ development or building VeloGraphX locally:

git clone https://github.com/sauravsingla/VeloGraphX.git
cd VeloGraphX

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
ctest --test-dir build --output-on-failure

Publication evidence at a glance

Evidence boundary: GitHub-hosted runs are reproducible hosted evidence. Claims that require stable many-core, NUMA, hardware-counter, NVMe, or machine-specific peak-performance conditions remain outside the headline scope unless separately executed on controlled hardware.

Evidence	Current audited result
Primary adaptive BFS selector	1,610 sequential batch observations across 9 graph/update regimes and 45 graph-regime repetitions; all outputs exact. 3.939% equal-regime mean oracle regret, 2.309% sample-weighted regret, 1.739% sample-weighted wrong-arm rate, and about 0.286 µs sample-weighted decision cost. The largest web-Google regime is retained as a visible tail at 17.477% mean and 54.424% p95 regret.
Dynamic BFS vs NetworKit	web-Google: VeloGraphX about 1.38× lower latency; ca-GrQc: NetworKit about 1.35× lower latency; all 30 paired executions exact.
Dynamic BFS vs RisGraph	In the retained separate web-Google campaign, RisGraph is about 1.90× faster than VeloGraphX localized repair. This campaign is not combined with the NetworKit campaign into a synthetic ranking.
Static BFS / weighted SSSP vs GAP + LAGraph	BFS: VeloGraphX 1.60×–2.04× vs GAP and 9.4×–11.8× vs LAGraph in the tested hosted 1–4-thread cases. Weighted SSSP: GAP wins; VeloGraphX is 2.6×–3.0× faster than LAGraph but 7.0×–8.5× slower than GAP.
Exact dynamic triangles vs published exact reference	15/15 paired comparisons exact; 40.95× / 6.94× / 3.48× lower median answer-ready latency than the pinned GoldenCounter exact reference at 1% / 5% / 10% insertion batches on the evaluated workload.
100M+ storage maintenance	On com-Orkut (234.4M directed arcs), a bounded 1.50× storage envelope produced 2.25× maintenance-amortized throughput and 59.6% less consolidation time than the 1.25× envelope, at about 6.6% higher peak RSS.
Dynamic exactness stress	2,000,000 updates · 0 BFS mismatches · 0 triangle mismatches in the retained engineering stress result.

The authoritative paper-facing mapping from each quantitative statement to its retained run, artifact, checksum, timing contract, and claim boundary is in PAPER.md, paper/results-ledger.md, and benchmarks/paper-evidence.json. Historical development numbers are not substitutes for the current publication-selector result above.

Algorithm contracts

Algorithm	Full / reference	Dynamic / maintained	Contract
BFS / unweighted SSSP	✓	✓	Exact distances
Weighted SSSP	✓	✓	Exact distances with conservative recomputation fallback
Connected components	✓	✓	Exact maintained connectivity
Triangle count	✓	✓	Exact count
k-core	✓	✓	Exact core-number maintenance
PageRank	✓	✓	Residual/tolerance-validated maintenance with conservative fallback; not presented as mathematically exact

Research and benchmarking

VeloGraphX treats benchmark provenance and negative results as part of the system contract. Reviewer-facing references include:

• Paper artifact guide
• Results ledger
• Benchmark methodology
• Hosted native competitor evidence
• Published exact triangle baseline
• 100M+ canonicalization evidence
• GraphBolt / DZiG + GAPBS benchmark contract
• Controlled-hardware execution boundary
• Current limitations
• Workflow catalog
• Submission archival status

Project status and citation

VeloGraphX is an active research and engineering project. APIs may evolve before 1.0; reproducible experiments should pin the exact release tag or commit SHA. v0.8.2 is the current software release, while pvldb-2027-submission-v4 is the frozen reviewer/reproducibility snapshot archived at DOI 10.5281/zenodo.22842292. See submission archival status for archive and provenance details.

For the software generally:

@software{singla_velographx_2026,
  author  = {Saurav Singla},
  title   = {VeloGraphX},
  year    = {2026},
  url     = {https://github.com/sauravsingla/VeloGraphX},
  license = {Apache-2.0}
}

For the exact PVLDB 2027 v4 research artifact:

@software{singla_velographx_pvldb_2027_v4,
  author  = {Saurav Singla},
  title   = {VeloGraphX: Adaptive Exact Analytics for Evolving Graphs},
  year    = {2026},
  version = {pvldb-2027-submission-v4},
  doi     = {10.5281/zenodo.22842292},
  url     = {https://doi.org/10.5281/zenodo.22842292}
}

VeloGraphX is licensed under the Apache License 2.0. See LICENSE.