Feedback on VeloGraphX dynamic graph architecture and benchmark design

[sauravsingla]

Hi Boost.Graph community,

I’m working on VeloGraphX, an open-source C++20 research engine for exact analytics on dynamically changing graphs:

https://github.com/sauravsingla/VeloGraphX

The system combines mutable graph storage, exact localized repair, multicore CPU execution, and runtime selection between incremental execution and full recomputation.

Given the Boost.Graph community’s experience with graph data structures, algorithms and C++ library design, I would greatly value technical feedback on:

• graph-storage and API design,
• algorithm/data-structure separation,
• multicore execution methodology,
• benchmark fairness,
• and which experiments would be necessary to make the system evaluation convincing.

The goal is not to claim novelty for established BFS/SSSP/etc. algorithms, but to evaluate the architecture and the conditions under which exact incremental repair is preferable to recomputation.

Critical feedback is particularly welcome.

Thank you.

[Becheler]

Hi @sauravsingla and welcome to Boost.Graph! 😄

Thanks for posting, and for asking for critical feedback. I can not verify details of your projects, but the main point BGL community would be looking for is the decoupling between algorithms and storage/graph representations.

Currently your algorithms are tied to concrete storage types: IncrementalBFS, IncrementalComponents, IncrementalKCore, IncrementalPageRank and IncrementalTriangleCount all hold a DynamicGraph&. Plenty of libraries do this, but I think it costs you more than most.

You've already paid for it once. IncrementalSSSP and IncrementalWeightedSSSP are the same Dijkstra with the same lazy deletion priority queue, differing only in d + 1 versus d + weight, written twice because the weight lives in the container instead of being passed in. That's what a BGL property map parameter is for.

More importantly, it blocks the experiments you need to sell your project. You want to show two things: that your storage design is good, and when incremental repair beats recomputation. Both are comparisons, and both need to swap the storage while keeping the algorithm constant:

• your storage against a plain CSR, against Teseo or Sortledton to show yours is better
• and your recomputation baseline against recomputation on a read optimised layout.
  Today every swap means rewriting every algorithm, so what you measure describes your specific storage rather than the general architecture.

In contrast, BGL never defines an algorithm in terms of a concrete graph type:

template <class Graph>
void my_algorithm(Graph& g) {
  using Vertex = typename boost::graph_traits<Graph>::vertex_descriptor;
  for (auto [it, end] = vertices(g); it != end; ++it) {
    for (auto [e, e_end] = out_edges(*it, g); e != e_end; ++e) {
      Vertex v = target(*e, g); /* ... */
} } }

(structured bindings are C++17, so this exact form won't compile against BGL, which is C++14; there's a Boost equivalent)

This is what allows us to keep algorithms constant but swap storage, which is convenient for benchmarks (all BGL stuff in legend test the same algorithm, simply called with different graph representations and storage):

Two mechanisms do the work:

• graph_traits<Graph> supplies the associated types, and vertices, out_edges, target are free functions found by ADL.
• A type opts in by specialising the traits and defining those functions, with no inheritance and no modification of the type itself.
  That's how the LEDA and Stanford GraphBase adaptors work, over foreign C and C++ structures BGL never touches. You have C++20, so you could constrain on concepts for readable errors; we use Boost's C++14 concept checks.

So in BGL parlance we would recommend this:

• template the incremental algorithms on the graph type and express their access as free functions.
• CSR vs segmented, and segmented vs Teseo, become configuration rather than rewrites.

Practically, BGL abstractions can be complex to develop/maintain, so there is a judgement call to make here, but it's not ours to make 😉

PS: one thing to fix maybe: neighbors() returns a std::vector by value, so you allocate on every vertex visit. You already have compact_neighbors() returning a span: make that the main interface ?

[sauravsingla]

Hi Arnaud,

Thank you again for the detailed and constructive feedback. Your comments directly influenced a significant architectural refactoring of VeloGraphX, so I wanted to share what has now been implemented.

Based on your feedback:

• the incremental algorithms are now BasicIncremental* templates rather than being tied directly to DynamicGraph&;
• we introduced a non-intrusive C++20 graph/property-access abstraction using free functions, concepts and ADL customization hooks;
• the same algorithm implementation can now operate over the native dynamic representation, CSR and external graph representations;
• Teseo is integrated not only for recomputation/storage swapping but also for actual mixed insertion/deletion incremental updates;
• Boost.Graph adjacency_list has been added as a second independent external mutable backend to validate that the abstraction is genuinely storage-independent;
• weighted SSSP is now generalized as BasicIncrementalWeightedSSSP, with weighted and unweighted SSSP sharing the common Dijkstra machinery; and
• hot algorithm traversal no longer depends on the allocating neighbors() interface, using callback/range-style access instead.

Most importantly, your observation that a storage comparison is difficult to interpret when changing storage also requires changing the algorithm led us to explicitly separate storage-swap experiments from incremental-repair-versus-recomputation experiments.

I deliberately avoided claiming a Sortledton integration until its exact upstream revision and build environment can be pinned and independently validated.

Thank you for explaining the BGL design rationale behind your suggestions. Your feedback resulted in concrete architectural changes rather than simply changes to the documentation or benchmark presentation.

[Becheler]

Happy to have been useful 🤗