Skip to content

VeloGraphX v0.8.0 — Dynamic Storage & Exact Analytics

Choose a tag to compare

View all tags
@sauravsingla sauravsingla released this 03 Sep 09:44
· 9 commits to main since this release
v0.8.0
5714f7a

VeloGraphX v0.8.0

VeloGraphX v0.8.0 is a substantial evolution of the dynamic graph engine, strengthening mutable graph storage, adaptive incremental execution, storage-independent algorithms, correctness validation, and reproducible comparison against established graph systems.

The release continues VeloGraphX's core principle: maintain exact graph analytics as the graph changes, repairing affected work when that is cheaper and falling back to recomputation when it is not.

What's new

Dynamic storage architecture

The mutable graph layer has been substantially redesigned:

  • Replaced the previous compact representation with fixed-size segmented CSR storage.

  • Replaced per-vertex hash-based update overlays with sorted slices in shared packed delta arenas.

  • Added overlay cancellation and fragmentation repacking.

  • Added explicit forward and reverse adjacency maintenance.

  • Added in_neighbors() and compact reverse-neighbor access.

  • Added explicit consolidation back to canonical CSR.

  • Added storage introspection for compact edges, live deltas, and approximate owned storage.

These changes provide a stronger foundation for long-running dynamic workloads and localized analytics.

Adaptive repair vs. recomputation

VeloGraphX now has stronger evidence around its central adaptive-execution design.

The selector evaluates factors including update fraction, affected work, graph scale, root locality, and observed execution cost rather than assuming incremental execution is always faster.

Current validation reports:

  • 108/108 exact adaptive BFS runs.

  • 1.66% mean overhead from the regime-best strategy in the validated hosted campaign.

This captures the intended behavior of VeloGraphX: incremental maintenance when locality makes it worthwhile, full recomputation when it does not.

Exact dynamic analytics

VeloGraphX provides dynamic or maintained paths for:

  • BFS / unweighted SSSP

  • Weighted SSSP

  • Connected components

  • Triangle counting

  • k-core

  • PageRank

The dynamic exactness stress campaign has exercised:

2,000,000 updates · 0 BFS mismatches · 0 triangle mismatches

Correctness remains the primary gate for dynamic benchmark results.

PageRank correctness and validation

PageRank maintenance received substantial correctness and observability improvements:

  • Localized repair now traverses actual predecessors using reverse adjacency.

  • Full PageRank uses tolerance-based convergence.

  • Added explicit dangling-mass redistribution.

  • Added L1 and L∞ convergence residuals.

  • Added quantitative localized-vs-full rank-vector validation.

  • Added conservative full recomputation when updates introduce graph-wide dangling-mass dependencies.

  • Exposed convergence, residual, validation, and fallback information through the optional Python bindings.

Storage-independent algorithms

The graph-access layer has been expanded so algorithm implementations are less tightly coupled to VeloGraphX's native storage.

This release includes work covering:

  • Non-intrusive graph access.

  • Generic BFS over foreign graph representations.

  • Weighted graph access for SSSP.

  • External mutable-storage validation.

  • Pinned Teseo interoperability evidence.

  • Pinned Sortledton same-algorithm BFS/storage portability evidence.

The goal is to separate algorithm behavior from storage behavior, making both easier to evaluate independently.

Reproducible benchmark evidence

v0.8.0 significantly expands the project's benchmark and comparison infrastructure.

VeloGraphX vs GraphBolt/DZiG

For the tested hosted dynamic BFS configurations using deterministic graph/update streams and correctness verification:

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×

GraphBolt/DZiG is pinned to a specific revision and its final answers are independently correctness-verified.

VeloGraphX vs NetworKit vs RisGraph

The three-system dynamic BFS campaign reports:

  • 91/91 exact evaluated VeloGraphX results.

  • VeloGraphX raw-policy wins in 45 / 27 / 19 evaluated regimes across the campaign's compared policy groupings.

  • On web-Google, VeloGraphX dynamic BFS is approximately 1.38× faster than NetworKit in the reported case.

  • On ca-GrQc, NetworKit is approximately 1.35× faster in the reported case.

Both wins and losses are retained intentionally.

Static BFS and SSSP context

On the tested static BFS campaign, VeloGraphX was fastest among the evaluated VeloGraphX/GAPBS/LAGraph cases at both 1 and 4 threads.

The static SSSP results show the opposite outcome: GAPBS was substantially faster in the tested cases.

These results are included to characterize workload-dependent behavior rather than claim universal superiority.

Multicore and storage evidence

Current hosted campaigns also report:

  • BFS: 2.74× scaling at 4 threads.

  • Connected components: 2.50× at 4 threads.

  • Triangle counting: 2.24× at 4 threads.

  • Compression: approximately 3.25×–3.78× smaller representation in the evaluated cases, with a currently documented BFS traversal cost.

  • Public graph scale exercised up to 875,713 vertices / 5,105,039 edges on web-Google.

Reproducibility and research infrastructure

v0.8.0 substantially strengthens the evidence pipeline:

  • Pinned competitor revisions.

  • Deterministic workload generation.

  • Public-dataset provenance and checksum validation.

  • Exact correctness gates.

  • Repeated benchmark statistics and machine-readable artifacts.

  • Multi-root comparison campaigns.

  • Hosted benchmark preflight validation.

  • Canonical publication campaign definitions.

  • Explicit controlled-hardware execution contracts.

  • NUMA, thread-scaling, hardware-counter, and ablation plans.

  • Explicit documentation of negative results and claim boundaries.

Engineering

VeloGraphX currently provides:

  • C++20 implementation.

  • 29 CTest targets.

  • Linux and macOS CI.

  • ASan/UBSan validation.

  • Multicore CPU execution.

  • SIMD-oriented intersection paths.

  • NUMA-aware policies.

  • Compression and partition caching.

  • Asynchronous partition loading.

  • Optional Python bindings.

  • Apache-2.0 licensing.

Evidence boundary

Benchmark numbers included with this release are reproducible engineering evidence from hosted environments, not publication-grade hardware claims.

Shared CI hardware is inherently variable. Controlled-hardware publication campaigns with pinned machines, larger workloads, NUMA placement, hardware counters, and broader thread scaling remain a separate next step.

VeloGraphX also intentionally retains negative results where competing systems perform better.

Project status

VeloGraphX remains an active pre-1.0 research and engineering project.

APIs may evolve before 1.0. For reproducible experiments, pin v0.8.0 or the corresponding commit.

Thank you to everyone exploring, testing, benchmarking, and contributing to VeloGraphX.

Assets 2
Loading