Incremental Graph Calculation

[zhangzq22]

How does graphscope achieve Incremental Graph Calculation？I see that there is an libgrape-lite-based framework（Ingress) for automating incremental graph processing, Is graphscope planning to achieve Incremental Graph Calculation by Ingress?

[welcome[bot]]

Thanks for opening your first issue here! Be sure to follow the issue template! And a maintainer will get back to you shortly!
Please feel free to contact us on DingTalk, WeChat account(graphscope) or Slack. We are happy to answer your questions responsively.

[yecol]

Hi @zhangzq22,
Thanks for your interests in GraphScope!
Yes, we are going to integrate Ingress by April, 2023. Please stay tuned. :)

[dakeleblack]

Ingress增量图计算框架集成至graphscope了吗？如何使用呢？对应的代码是哪块？

[yecol]

Hi @bitao666,

Unfortunately, not yet.
And we made some adjustments, the Ingress will be a standalone project for a while.

Please check out the Ingress code here if you are still interested.
https://github.com/alibaba/libgrape-lite/tree/ingress

[sauravsingla]

Hi everyone,

I’m working on VeloGraphX, a C++20 research engine for exact dynamic graph analytics:

https://github.com/sauravsingla/VeloGraphX

Our current focus is closely related to this discussion: exact localized repair after graph updates, together with runtime selection between incremental execution and full recomputation.

I would be interested in the GraphScope/Ingress community’s perspective on two questions:

1. Which workloads best expose the real crossover between incremental computation and recomputation?
2. Which affected-work or dependency signals have proved most useful in practice for deciding when incremental execution is no longer worthwhile?

We are trying to design the evaluation so that it reflects realistic dynamic-graph behaviour rather than simply selecting workloads favourable to incremental processing.

Any pointers to relevant GraphScope/Ingress experiments or lessons learned would be very helpful.

[sauravsingla]

This is very close to a systems question I’ve been experimenting with: when should a dynamic graph engine incrementally repair an existing result, and when is full recomputation actually cheaper?

I’m developing VeloGraphX, an open-source C++20 engine for exact analytics on evolving graphs.

The current approach does not assume incremental execution always wins. It measures affected work and observed cost, then chooses between localized repair and fresh recomputation.

Some current validation results:

• 2,000,000 graph updates with 0 BFS mismatches and 0 triangle-count mismatches
• Adaptive BFS selector: 108/108 cases exact
• Mean selector overhead: 1.66% relative to the best repair/recompute choice for each tested regime

The engine currently includes dynamic paths for BFS/SSSP, connected components, triangles, k-core and weighted SSSP, with PageRank-related localized maintenance and conservative fallback.

I would be very interested in how the GraphScope/Ingress community thinks about the repair-vs-recompute crossover. In particular, whether an incremental framework should expose an adaptive policy explicitly rather than assuming incrementalization is always beneficial.

The implementation, methodology and reproducible evidence are here:

https://github.com/sauravsingla/VeloGraphX

Any criticism around methodology or comparison with Ingress-style incrementalization would be very useful.