Exact dynamic graph analytics in C++20.
Maintain exact graph analytics as your graph changes — repairing affected work when that is cheaper and falling back to full recomputation when it is not.
VeloGraphX is a high-performance CPU engine for analytics on evolving graphs. It combines mutable graph storage, localized incremental maintenance, adaptive repair/recompute decisions, and reproducible systems evaluation.
2,000,000 updates · 0 BFS mismatches · 0 triangle mismatches
Adaptive repair/recompute · Multicore CPU · Storage-independent algorithms · Reproducible benchmarks
Engineering quality: 29 CTest targets · Linux/macOS CI · ASan/UBSan · Python interoperability
Quick links: Release · C++ examples · Python · Architecture · Dynamic storage · Benchmarks · Reproduction
Want to try it? Build and run the dynamic example in under a minute → 30-second start
VeloGraphX is designed for workloads where a graph changes over time and analytics must be maintained across updates without assuming that incremental repair is always the fastest choice. Relevant use cases include evolving network analysis, relationship and fraud graphs, changing knowledge graphs, infrastructure/dependency graphs, and graph-systems research.
If your graph is static, a specialized static CSR engine may be simpler or faster. If approximate answers are acceptable, streaming or approximate graph methods may offer different trade-offs. VeloGraphX focuses on correctness-preserving analytics under graph mutation and explicit measurement of the repair-vs-recompute crossover.
VeloGraphX brings four concerns into one systems design:
- Mutable graph storage: segmented CSR, packed deltas, sparse row patches and explicit consolidation.
- Incremental analytics: maintained state for dynamic BFS/SSSP, connected components, triangles, k-core, weighted SSSP and PageRank-related paths.
- Adaptive execution: measure affected work and observed cost instead of assuming incremental execution always wins.
- Auditable evaluation: correctness gates, pinned datasets/competitors, retained artifacts and explicit negative results.
- Correctness first: incremental paths are checked against fresh or converged reference computation where required.
- Measure crossover: choose localized repair or full recomputation according to workload and observed cost.
- Separate algorithms from storage: graph-access abstractions let the same algorithmic path work across multiple representations.
- Make evidence reproducible: benchmark provenance, timing contracts and claim boundaries are part of the project design.
GitHub-hosted numbers are reproducible engineering evidence, not publication-grade hardware claims.
| Evidence | Verified result |
|---|---|
| Dynamic exactness stress | 2,000,000 updates; 0 BFS / 0 triangle mismatches |
| Adaptive BFS selector | 108/108 exact; 1.66% mean overhead from regime-best |
| VeloGraphX vs GraphBolt/DZiG | 15.35× / 4.28× / 2.33× faster on tiny / medium / large hosted update regimes |
| VeloGraphX vs NetworKit vs RisGraph | 91/91 exact; 45 / 27 / 19 raw-policy wins |
| Dynamic BFS vs NetworKit | web-Google: VeloGraphX ~1.38× faster; ca-GrQc: NetworKit ~1.35× faster |
| Static BFS vs GAP / LAGraph | VeloGraphX fastest in tested 1T and 4T BFS cases |
| Static SSSP vs GAP / LAGraph | GAP fastest in tested 1T and 4T SSSP cases |
| Multicore | BFS 2.74×, CC 2.50×, triangles 2.24× at 4 threads |
| Compression | 3.25×–3.78× smaller, with a current BFS traversal cost |
| Public scale exercised | 875,713 vertices / 5,105,039 edges (web-Google) |
GitHub-hosted measurements below are reproducible engineering evidence, not publication-grade hardware claims. All reported dynamic results are correctness-gated.
Both systems consume the same deterministic directed graph and mutation stream. The comparable timing envelope includes graph mutation + maintained answer update; GraphBolt stream-reading time is excluded.
| Update operations | VeloGraphX median | GraphBolt/DZiG median | VeloGraphX speedup |
|---|---|---|---|
| 400 | 83.45 µs | 1,281 µs | 15.35× |
| 4,000 | 1,427.86 µs | 6,106 µs | 4.28× |
| 20,000 | 6,875.96 µs | 16,012 µs | 2.33× |
Correctness: all reported VeloGraphX results were exact, and every GraphBolt/DZiG final answer passed independent fresh-recompute directed-reachability verification.
GraphBolt/DZiG is pinned to commit 2d56f39cb17c85d624bee6a63f8fc34a8f149a36 and executed with CILK_NWORKERS=1.
These measurements compare fresh BFS kernels on prepared graph representations.
| Threads | VeloGraphX | GAPBS | LAGraph | Fastest |
|---|---|---|---|---|
| 1 | 0.425 ms | 0.790 ms | 4.0 ms | VeloGraphX |
| 4 | 0.406 ms | 0.830 ms | 4.8 ms | VeloGraphX |
The same campaign also retains cases where a competitor wins.
| Threads | VeloGraphX | GAPBS | Fastest |
|---|---|---|---|
| 1 | 8.982 ms | 1.060 ms | GAPBS |
| 4 | 9.003 ms | 1.290 ms | GAPBS |
These results intentionally include both wins and losses. They demonstrate workload-specific behavior rather than a universal performance advantage.
Timing boundary: GAPBS results are fresh static recomputation on an already-materialized post-update graph and therefore are not presented as a direct dynamic-system comparison with VeloGraphX. Dataset loading, one-time preparation, and correctness verification are excluded from the primary kernel timing where specified by the benchmark contract.
For exact competitor revisions, dataset provenance, raw samples, correctness gates, timing contracts, and reproduction instructions, see the benchmark methodology and GraphBolt/DZiG + GAPBS benchmark contract.
Detailed comparison methodology, competitor revisions, timing contracts, artifacts and negative results are kept in the benchmark documentation rather than duplicated here.
| Algorithm | Full/reference path | Dynamic/incremental path | Correctness contract |
|---|---|---|---|
| BFS / unweighted SSSP | ✓ | ✓ | Exact distances |
| Weighted SSSP | ✓ | ✓ | Exact distances; destructive/increasing-weight updates can fall back to recomputation |
| Connected components | ✓ | ✓ | Exact maintained connectivity |
| Triangle count | ✓ | ✓ | Exact count |
| k-core | ✓ | ✓ | Exact core-number maintenance |
| PageRank | ✓ | ✓ | Localized maintenance with residual/tolerance validation and conservative full fallback |
The implementation also includes graph-access abstraction, SIMD-oriented intersection paths, multicore scheduling, NUMA-aware policies, compression, partition caching and asynchronous partition loading.
Requires CMake ≥ 3.20 and a C++20 compiler.
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
./build/velographx_example
./build/velographx_dynamic_exampleMinimal static C++ API:
#include "velographx/algorithms.hpp"
velographx::CsrGraph graph({{0,1}, {1,2}, {2,3}}, false);
auto distance = velographx::bfs_distances(graph, 0);
auto triangles = velographx::triangle_count(graph);Minimal dynamic C++ API:
#include "velographx/storage/dynamic_graph.hpp"
#include "velographx/incremental/triangles.hpp"
velographx::DynamicGraph graph(6, false);
velographx::UpdateBatch initial;
initial.add(0, 1);
initial.add(1, 2);
initial.add(2, 0);
graph.apply(initial);
velographx::IncrementalTriangleCount triangles(graph);
velographx::UpdateBatch update;
update.add(2, 3);
triangles.apply(update);
auto current_triangles = triangles.value();For the complete dynamic example, see examples/dynamic_transactions.cpp. Optional Python bindings are enabled with -DVELOGRAPHX_BUILD_PYTHON=ON; see python/README.md.
flowchart LR
U[Update batch] --> G[Mutable graph\nbase CSR + deltas / row patches]
G --> S{Adaptive selector}
S -->|localized affected work| R[Exact incremental repair]
S -->|repair cost too high| F[Full recomputation]
R --> E[Maintained result]
F --> E
The current storage layer uses segmented CSR, packed deltas, sparse row-level patches, forward/reverse adjacency, and explicit canonical CSR consolidation for long-running patch accumulation.
The selector uses update fraction, affected work, graph scale, root locality and observed cost to decide when incremental repair is worthwhile. See the architecture and dynamic-storage design for implementation details.
- Dynamic analytics: BFS/unweighted SSSP, weighted SSSP, connected components, triangle count, k-core and PageRank-related maintenance paths.
- Storage-independent execution: the graph-access contract supports mutable storage, CSR and foreign graph representations.
- CPU systems runtime: multicore execution, SIMD intersections, NUMA-aware policies, compression, partition caching and asynchronous partition loading.
- C++ first, Python optional: native hot paths remain in C++; pybind11 bindings can be enabled at build time.
The headline results above are backed by retained benchmark contracts, pinned datasets/competitors, correctness gates and machine-readable artifacts. Detailed results are intentionally kept outside the landing page:
- Benchmark methodology — timing, repetition, provenance and claim boundaries.
- Competitor benchmarking — external-system comparison rules and adapters.
- GraphBolt/DZiG + GAPBS contract — dynamic BFS comparison contract and static GAPBS context.
- Three-system dynamic BFS campaign — VeloGraphX, NetworKit and RisGraph crossover evidence.
- Ablation study — policy/component contribution analysis.
- Controlled-hardware execution — requirements for publication-quality hardware claims.
Known negative results are retained rather than hidden: competitors win some small-update regimes; GAP is much faster on the tested static SSSP workload; CSR is faster for full recompute; and compression currently trades traversal speed for memory reduction.
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release \
-DVELOGRAPHX_BUILD_TESTS=OFF -DVELOGRAPHX_BUILD_BENCHMARKS=OFF
cmake --build build --target velographx -j 2
c++ -O3 -DNDEBUG -std=c++20 -Iinclude benchmarks/exactness_stress.cpp \
build/libvelographx.a -pthread -o build/exactness_stress
./build/exactness_stress 2000000 256The default build currently defines 29 CTest targets plus benchmark executables.
| Area | Documentation |
|---|---|
| Architecture | Architecture · Dynamic storage · Graph abstraction |
| Benchmarks | Methodology · Competitor benchmarking · Ablation study |
| Reproduction | GraphBolt/DZiG + GAPBS contract · Three-system campaign |
| Publication boundary | Canonical publication campaign · Controlled-hardware execution · Limitations |
| Python | Python bindings |
| Research citation | CITATION.cff |
The hosted campaigns establish correctness, reproducibility and crossover behavior, but shared GitHub runners are noisy and hardware can vary. Controlled-hardware publication tables remain pending. The canonical campaign is designed for pinned datasets and hardware, 1/2/4/8/16/32-thread scaling, NUMA placement, hardware counters and larger real-world/R-MAT workloads.
VeloGraphX is an active research and engineering project. Current source version: 0.8.0. APIs may evolve before 1.0, so pin a version or commit for reproducible experiments.
Research citation metadata is available in CITATION.cff. The current GitHub release is v0.8.0; pin the release or a specific commit when using results in reproducible experiments.
Contributions are welcome, particularly around dynamic graph algorithms, CPU optimization, storage policies, benchmark reproducibility, interoperability and documentation. See CONTRIBUTING.md before opening a contribution.
New to VeloGraphX? Start with a good first issue or join the Discussions to share a workload, idea or benchmark suggestion.
Apache-2.0 licensed. See CODE_OF_CONDUCT.md, SECURITY.md, and CHANGELOG.md.