GraphBolt Thesis：《GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs》
Previously through the articleThe Dissertation Graph: Awesome-Graphs Takes a Sample with 200 Graph Systems Dissertations.Introduced Awesome-Graphs, a thesis graphing project, to the group and shared Google'sPregeland OSDI'12PowerGraphSOSP'13X-Streamcap (a poem)Naiad. This time, we share with you a streaming graph processing system paper, GraphBolt, to see how incremental graph computation can be implemented in a computational history-based way and ensure consistency with the semantics of full graph computation.
Students interested in graph computing technology can learn more about it, and you are very welcome to follow and participate in the open source project of Thesis Mapping:
- Awesome-Graphs：/TuGraph-family/Awesome-Graphs
- OSGraph：/TuGraph-family/OSGraph
Thanks in advance to those of you who gave the project a Star, and let's get right into the meat of it!
summaries
GraphBolt implements dependency-driven incremental computation by capturing intermediate value dependencies during computation and guarantees BSP semantics.
1. Introduction
The core of streaming graph processing is dynamic graphs, and the stream of graph updates modifies the graph structure frequently, and the incremental graph algorithm responds to changes in the graph structure in a timely manner to generate the final result of the latest graph snapshot. Therefore, the core goal of incremental graph algorithms is to minimize repeated computations. Typical systems such as GraphIn, KickStarter, and Differential Dataflow.
GraphBolt minimizes repetitive computation from graph changes through dependency-driven streaming graph processing techniques.
- Describe and track the dependencies of the intermediate values generated during the iteration process.
- When the graph structure is changed, the final result is produced iteration by iteration based on the dependencies.
Key Optimization:
- The scale of dependency information is reduced from O(E) to O(V) by utilizing graph structure information as well as in the form of aggregated values at points.
- Supports dynamic switching between dependency-driven optimization strategies and traditional incremental computation for cases where dependency information is not available due to pruning.
- Provides a generic incremental programming model to support the disassembly of complex aggregations into merged incremental values.
2. Background and motivation
2.1 Flowchart Processing
The streaming graph G is always modified by the ΔG update stream, which contains insertions/deletions of points/edges, and the algorithm S iteratively computes the final result on the latest snapshot of the graph. To ensure consistency, updates during iterative computation are written to ΔG in batches and merged into G before the start of the next iteration.
synchronous processing
The BSP model divides the computation into multiple iterations, with the current iteration relying only on the results of the last iteration's computation. This makes the development of graph algorithms simpler and allows clear derivation of convergence information as well as accuracy verification. Therefore, the synchronous processing model is the preferred choice for large-scale graph computing systems.
Calculation of increments
- I: Point initial value.
- k: number of iterations.
- Si(G, I): the i-th iteration of algorithm S on graph G with I as input.
- S*(G, I): the last iteration of the algorithm on graph G with I as input.
- RGi: the result of the ith iteration of the graph G.
- RG: Iteration results for graph G.
- GT：G+ΔG。
- Zs: the conversion function that\(R_{G^T}^k = Z^s(R_G^k)\)。
2.2 Problem: incorrect results
How to minimize duplicate computations in the incremental computation of graph-change oriented flow graphs while guaranteeing the semantics of synchronous processing?
2.3 Technology overview
Challenges for dependency-driven incremental computing:
- Online tracking relies on high information cost and complexity |E｜.
- The complexity is reduced to |V｜ based on point aggregated values.
- Reality maps are generally sparsely skewed and can be conservatively pruned for dependent information.
- Difficulty in handling complex aggregation calculations.
- The development of a generic incremental programming model decomposes complex aggregations into incremental value changes.
- Simple aggregations such as SUM and COUNT can be expressed directly without going through the decomposition process.
- Computationally aware hybrid execution capabilities.
- Supports dynamic switching between dependency-driven optimization strategies and traditional incremental computation.
3. Dependency perception processing
3.1 Synchronization Semantics
Define value dependencies based on graph structure:
- (u, v): compute any edge in the graph.
- ut: the value of point u at the tth iteration.
- ->: a dependency relationship, where the latter depends on the former.
3.2 Tracking value dependencies
Suppose that after the Lth iteration, the graph G is modified to GT, and CL corresponds to the set of point values at the end of the iteration L. In order to ensure the accuracy of the results, it is necessary to keep track of information about all point values that contribute to CL during the computation.
honorific title\(\mathcal{D}_G=(\mathcal{V}_D,\mathcal{E}_D)\)Then there is:
At each iteration, DG adds |V| points and |E| and edge information. The space complexity O(|E|-t).
Tracking point dependencies based on point aggregation values
The general point value calculation is divided into two steps.
- \(\bigoplus\): Aggregate the values of the neighbor points from the last iteration.
- \(\oint\): Calculate point values based on aggregated values.
honorific title\(g_i(v)=\bigoplus_{\forall e=(u,v)\in E}(c_{i-1}(u))\)，\(\mathcal{A}_G=(\mathcal{V}_\mathcal{A},\mathcal{E}_\mathcal{A})\)Then there is:
The space complexity is reduced to O(|V|-t) by keeping track of the aggregated values at the points instead of the individual point values.
Trim value aggregation information
The real graph is generally skewed, so most of the point values will change at the very beginning of the algorithm, but the number of updated points will diminish as the iteration progresses.
When the point values are stable, the aggregated values at the points also tend to be stable, which provides an optimization opportunity for tracking information about the dependence of the aggregated values.
- Horizontal cropping: stops tracking aggregated values when a defined iteration is reached, corresponding to the red line in the figure above.
- Vertical cropping: the aggregated values will no longer be tracked for point values that have stabilized, corresponding to the white area on the red line in the figure above.
3.3 Dependency-driven value optimization
Let Ea denote the added edge and Ed denote the deleted edge, then we have\(G^T=G \cup E_a \backslash E_d\)For dependency graphs\(\mathcal{A}_G\), how to convert CL to CLT.
Optimize for what?
There are two types of optimization actions for each iteration:
- The endpoints of the edges in Ea, Ed, and the corresponding point values are affected by edge modifications.
- Neighbors of the endpoints, and the neighbor point values will be optimized in the next iteration.
For example, when adding the new edge 1->2, the aggregated values are updated as shown above. Where the solid line indicates the propagation of values and the dashed line indicates the change in values.
The whole process depends on the diagram\(\mathcal{A}_G\), the change in aggregation values comes from the modification of the edges. The optimization process involves much less computation than recomputation on the original graph.
How to optimize?
For simple aggregation operations, such as sum and product, the contribution of changes can be calculated directly. But for complex aggregation operations, such as vector operations, it is more difficult to represent them directly.
complex aggregation
For MLDM algorithms, such as BP and ALS, it is more difficult to increment the point values. Converting complex aggregation to an incremental approach can be done in two steps.
Static disassembly into simple subaggregates
Complex aggregations can be broken down into multiple simple subaggregations such as the ALS algorithm.
The aggregation value can be expressed as:
Dynamic valuation of independent contributions
The calculation of point values by sub-aggregation occurs before sum, which introduces double counting. Therefore it is necessary to calculate each part independently and then calculate the aggregated difference value.
Aggregate Properties and Extensions
Characterization of the three incremental aggregation operators (+, -, Δ):
- The operators are exchangeable and combinable.
- The definitional domain of the operator contains the aggregated values on the points as well as the associated values on the edges.
- The operator can incrementally handle the effects from a single input.
Such operators are decomposable, e.g. sum, count.
The relative ones are indecomposable operators such as max, min. The + operation can be incrementable for +, but not for - and ∆.
Thus the aggregated values degenerate into a collection of input point values, implemented by dynamically pulling the values of the input edges.
4. GraphBolt processing engine
4.1 Flowcharts and Dependency Layouts
Points/edges are added/removed in the following two ways:
- Single point/edge changes.
- Batch point/edge changes.
Changes trigger value optimization as soon as they take effect, and changes made during optimization are cached and continue to be processed in the next optimization step.
Aggregate values are maintained in an array corresponding to the points, holding value data across iterations. As the computation progresses, the aggregated value information is updated and grows dynamically.
4.2 Dependency-driven processing model
The BP algorithm uses restract+propagate to simulate update.
The PangeRank algorithm defines propagate_delta directly to implement update.
selective scheduling
GraphBolt will only recalculate point values after neighbor values have been updated and allows the user to specify logic for selective scheduling, such as comparing tolerance ranges for value changes to determine whether to initiate a recalculation.
Computationally aware hybrid execution
Horizontal cropping causes that after more than the specified iterations, the aggregated values will no longer be valid and GraphBolt will dynamically switch to incremental computation mode without value optimization.
4.3 Guaranteed Synchronization Semantics
Theorem: Using a dependency-driven value optimization approach, computing giT(v) based on ci-1T(u) can satisfy the dependencies defined by ET.
5 Related work
- Flowchart Processing Framework
- Tornado: forking execution of user queries during graph updates.
- KickStarter: Incrementally correcting monotone graph algorithms using dependency trees.
- GraphIn: provides a 5-stage processing model using fixed-size batch dynamic graphs.
- Kineograph: an incremental computation for graph mining based on the pull/push model.
- STINGER: Proposing dynamic graph data structures and developing algorithms for specific problems.
- Batch processing of graph snapshots
- Chronos: implements computation across snapshots using an incremental approach.
- GraphTau: maintains a history of values on snapshots and enables data correction through value fallback.
- Static graph processing system: processing discrete graph snapshots.
- Universal Stream Processing
- Generalized stream processing systems: manipulating unstructured data streams without boundaries.
- Differential Dataflow: extends Timely Dataflow for incremental computation, which strongly relies on differential operators.
- incremental algorithm
- Incremental PageRank
- Triangle Counting
- IVM algorithm