VeloGraphX is a CPU-native research and engineering platform for incremental graph analytics on continuously changing graphs. It combines dynamic graph algorithms, adaptive recomputation, SIMD-aware kernels, multicore scheduling, NUMA-aware execution policies, compression, Python interoperability, out-of-core infrastructure, and reproducible benchmarking in a modern C++20 codebase.
Guiding question: when a large graph changes only slightly, how little work can a modern CPU perform while still producing the correct updated answer?
VeloGraphX is intended for researchers and systems engineers exploring dynamic graph analytics, incremental graph processing, CPU graph engines, SIMD graph processing, NUMA-aware execution, and reproducible graph-system benchmarking.
Many graph workloads repeatedly recompute an answer from scratch even when only a small part of the graph has changed. VeloGraphX explores a different execution model: identify affected work, repair only what is necessary when correctness permits, and fall back to full recomputation when localized repair is unsafe or estimated to be unhelpful.
The project is deliberately CPU-first. Its optimization order is:
- Avoid unnecessary graph work.
- Improve memory locality.
- Scale across CPU cores and NUMA domains.
- Optimize instructions with SIMD and compression-aware kernels.
Correctness comes before speed: incremental results are checked against full recomputation, optimized kernels are compared with scalar references, and benchmark claims are explicitly separated from CI fixtures and unmeasured research hypotheses.
The table below describes implemented engineering capability. It should not be read as a claim that every capability has already been validated at publication scale.
| Area | Implemented capability |
|---|---|
| Dynamic graph storage | Versioned graph storage with batched insert/delete deltas, threshold compaction, weighted updates, temporal history and snapshots |
| Incremental algorithms | BFS / unweighted SSSP, weighted SSSP, triangle counting, connected components, k-core and localized PageRank repair |
| Adaptive execution | Affected-work estimates and explainable incremental-vs-full-recompute selection |
| Graph kernels | Scalar, galloping, bitmap and architecture-specific AVX2 / AVX-512 / ARM NEON paths with runtime ISA detection and scalar fallback |
| Multicore execution | Sparse/dense frontiers, push/pull selection, work stealing, adaptive grain sizing and degree/frontier-aware scheduling |
| NUMA | Linux topology discovery, affinity, first-touch, mbind, partition placement, local queues and local-first stealing observability, with portable fallback |
| Compression | Delta, variable-byte, blocked variable-byte and SIMD-friendly fixed-width adjacency coding with adaptive codec recommendation |
| Python | Optional pybind11 bindings with NumPy, SciPy CSR and Apache Arrow ingestion plus dynamic/incremental APIs |
| Out-of-core | Partition-file backend, mmap/fallback reads, async loading, bounded cache, readahead and optional Linux io_uring prefetch |
| Reproducibility | Checksum-verified datasets, competitor adapters, version-pin readiness contracts, environment capture, campaign orchestration and publication-artifact validation |
VeloGraphX currently includes static or dynamic/incremental support for:
- Breadth-first search (BFS) and unweighted shortest paths
- Weighted single-source shortest paths (SSSP)
- Connected components
- PageRank
- Triangle counting
- k-core decomposition
- Common-neighbor and Jaccard-style neighborhood operations
- Adaptive neighbor intersection
The incremental engine uses localized repair where correctness conditions permit and explicit full-recompute fallback where a destructive update cannot be safely or efficiently repaired.
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-failureBuilds are continuously checked on Ubuntu and macOS, with additional ASan/UBSan coverage on Linux.
Python bindings require pybind11; NumPy, SciPy and Apache Arrow interoperability is supported.
cmake -S . -B build-python \
-DCMAKE_BUILD_TYPE=Release \
-DVELOGRAPHX_BUILD_PYTHON=ON
cmake --build build-python -jExample Python usage:
import numpy as np
import velographx as vx
edges = np.array([[0, 1], [1, 2], [2, 0]], dtype=np.uint32)
graph = vx.from_numpy_edges(edges)
bfs = vx.IncrementalBFS(graph, 0)
update = vx.UpdateBatch()
update.add(2, 3)
graph.apply(update)
bfs.apply(update)
print(bfs.distances)At a high level, VeloGraphX combines five layers:
Input / interoperability
edge lists | native binary | NumPy | SciPy CSR | Arrow
|
v
Versioned dynamic graph storage
base adjacency + insertion/deletion deltas + compaction
|
v
Incremental / adaptive algorithms
affected-work estimation + localized repair + full fallback
|
v
CPU execution engine
frontier policies + work stealing + NUMA placement + SIMD kernels
|
v
Research / reproducibility layer
datasets + campaigns + competitors + environment + result artifacts
This separation is intentional: algorithmic work reduction, memory locality, parallel scheduling and instruction-level optimization can be evaluated independently through ablations.
VeloGraphX maintains broad native and interoperability coverage, including:
- static and dynamic graph correctness tests;
- incremental BFS, connected-components, k-core, PageRank, triangle and weighted-SSSP tests;
- deletion and destructive-update fallback cases;
- randomized dynamic mutation campaigns;
- scalar-versus-optimized kernel differential checks;
- NUMA policy, partitioning and scheduler tests;
- work-stealing and concurrency stress coverage;
- compression and codec-policy tests;
- native I/O, partition-cache and async partition-loader tests;
- Python NumPy, SciPy CSR and Apache Arrow interoperability checks;
- Linux ASan/UBSan runs.
CI-scale tests establish engineering correctness and portability for the exercised configurations. They do not substitute for research-scale hardware evaluation.
VeloGraphX includes infrastructure for reproducible experiments rather than embedding unverified headline numbers in the README.
The repository contains:
- checksum-verified dataset preparation;
- public-dataset manifests and readiness contracts;
- competitor adapters for builtin reference, NetworkX, igraph, NetworKit and rustworkx;
- normalized external/native runner contracts for SuiteSparse:GraphBLAS/LAGraph and GAP;
- immutable competitor version-pin readiness checks;
- benchmark-environment capture for OS, CPU, compiler and competitor identities;
- update-fraction, thread-scaling, NUMA, hardware-counter and ablation campaign definitions;
- codec throughput/compression-ratio tooling and codec-policy calibration;
- provenance-rich publication artifact generation and integrity validation.
A hosted-CI engineering campaign exercises core benchmarks, update-fraction measurements, paired ablations, conservative thread checks and normalized BFS adapters. Its result bundle is provenance-captured and integrity-validated and remains explicitly marked research_claim: false.
Hosted CI also now builds immutable pinned native stacks for SuiteSparse:GraphBLAS v10.3.2, LAGraph v1.2.2 and GAP Benchmark Suite v1.5 on the same runner. The workflow executes small 1/2/4-thread BFS engineering measurements, requires GAP verification and an enabled LAGraph BFS self-check, captures machine/build provenance and uploads a machine-readable evidence bundle. These measurements are deliberately marked research_claim: false, publication_grade: false and normalized_cross_engine_claim: false because the upstream LAGraph and GAP harnesses do not yet establish fully identical cross-engine source/output semantics.
The repository also contains public-dataset incremental crossover engineering evidence, including ca-GrQc work, and ongoing work to extend that evidence across additional graph families. These measurements remain engineering evidence unless and until they are repeated under controlled, publication-grade experimental conditions.
Hosted CI validates contracts, correctness and small-scale engineering behavior, not publication-grade superiority or large-scale scalability. Dedicated-hardware benchmark results should only be treated as project claims when dataset identity, environment, version pins, methodology and result artifacts are captured by the documented workflow.
Useful references:
docs/ci-scale-evidence.md— hosted-CI engineering evidence and caveatsdocs/hosted-native-competitors.md— pinned GraphBLAS/LAGraph/GAP hosted build and engineering evidencedocs/benchmark-methodology.md— experimental methodologydocs/prompt-coverage.md— authoritative implemented / partial / unmeasured status matrixdocs/limitations.md— known implementation and validation limitationsdocs/native-competitors.md— LAGraph/GraphBLAS and GAP execution contractbenchmarks/competitor-research-plan.json— competitor version-pin readiness plan
The repository has engineering evidence for correctness, cross-framework adapter normalization, incremental update behavior, optimized intersection paths, compression/decompression behavior, Python interoperability, reproducibility contracts and small hosted-CI execution campaigns.
Hosted CI additionally verifies that pinned GraphBLAS/LAGraph and GAP native stacks build on the same runner and that their exercised BFS harnesses complete with upstream correctness checks across 1/2/4-thread engineering runs. This establishes native build/readiness and small-scale same-runner engineering evidence; it is not yet a normalized cross-engine performance comparison.
Public-dataset incremental crossover work is also underway and already includes ca-GrQc evidence. This is useful evidence for development and hypothesis testing, but it is intentionally not presented as a universal performance result.
VeloGraphX does not currently claim publication-grade superiority over other graph engines.
The following remain unmeasured at publication grade or materially environment-dependent:
- true multi-socket NUMA locality, bandwidth and remote-traffic behavior;
- large 1/2/4/8/16/32+ thread-scaling studies on dedicated hardware;
- 100M+ edge research-scale experiments;
- broad multi-dataset crossover characterization across graph families;
- complete like-for-like competitor comparisons on identical dedicated hardware, including native LAGraph/GraphBLAS and GAP;
- publication-grade hardware-counter and ablation measurements;
- research-scale codec throughput/compression-ratio campaigns;
- calibrated production codec thresholds from representative public-dataset measurements;
- research-scale NVMe /
io_uringthroughput and overlap studies.
The engineering infrastructure for many of these experiments already exists. The remaining gap is controlled execution and evidence; results should not be inferred before those experiments are completed.
Some capabilities are intentionally conservative or environment-dependent:
- localized incremental algorithms may fall back to full recomputation for destructive or difficult updates;
- architecture-specific SIMD paths retain scalar fallback and require representative hardware calibration before broad performance conclusions;
- NUMA execution policies are implemented on Linux, but genuine multi-socket benefits require suitable hardware to measure;
- out-of-core infrastructure supports mmap, async loading, bounded caching, readahead and optional
io_uring, but research-scale NVMe behavior has not yet been established; - adaptive execution and codec-selection thresholds require broader public-dataset calibration;
- hosted native LAGraph/GraphBLAS and GAP builds and upstream-harness correctness checks are available, but fully normalized same-source/output-digest cross-engine comparison and dedicated-hardware publication evidence remain outstanding.
For status decisions, docs/prompt-coverage.md is the authoritative capability matrix.
VeloGraphX is a good fit for exploring workloads such as continuously changing social, communication, transaction, infrastructure, cybersecurity or knowledge graphs where updates are frequent and repeated full recomputation can be expensive.
It is also intended as a research platform for questions around dynamic graph algorithms, incremental computation, CPU graph analytics, SIMD graph kernels, NUMA scheduling, graph compression, temporal graphs, out-of-core graph processing and reproducible graph-system benchmarking.
include/ C++ public headers and core engine components
src/ implementation sources
python/ pybind11 bindings
benchmarks/ benchmark programs, fixtures and research plans
tools/ dataset, competitor, calibration, provenance and experiment tooling
datasets/ dataset manifests and reproducibility fixtures
docs/ architecture, methodology, limitations and research notes
.github/ CI and reproducibility contract workflows
VeloGraphX is under active development. The authoritative status is maintained in docs/prompt-coverage.md, which distinguishes implemented functionality from partial, environment-dependent, unmeasured and future work.
If you are evaluating the repository for research or systems work, start with this README, then review the benchmark methodology, hosted-CI evidence note and prompt-coverage matrix before interpreting benchmark output.
Contributions that improve correctness, dynamic graph algorithms, CPU performance, SIMD/NUMA portability, dataset reproducibility, benchmarking discipline, documentation or interoperability are welcome. Performance-sensitive changes should include reproducible measurements where practical, and optimized execution paths should retain correctness coverage or comparison against a trusted reference.
Apache-2.0. See LICENSE.
Search terms: dynamic graph algorithms · incremental graph analytics · incremental graph processing · CPU graph analytics · C++ graph library · SIMD graph algorithms · AVX2 · AVX-512 · ARM NEON · NUMA graph processing · temporal graphs · out-of-core graph analytics · graph compression · PageRank · BFS · SSSP · connected components · triangle counting · k-core · Python graph analytics · GraphBLAS benchmarking