A common way to express algorithms in SGL is in the vertex-centric manner. In this approach, the developer adopts the ‘think like a vertex’ paradigm. This has the advantage to be easy to the user and reason about, as well as expose a large amount of parallelism in the problem. The user writes two operators -- a vertex-operator and a neighbor operator. These operators sufficiently express the graph algorithm -- the vertex operator performs computation of the algorithm on the vertex, producing a result, while the neighbor operator updates the neighboring vertices of this vertex with this result (figure-1). SGL provides multiple paradigms that can use these operators to efficiently process the graph:
- The k-Level Asynchronous (KLA) Paradigm -- unified asynchronous and BSP processing of general graphs.
- Hybrid Out-of-Core Paradigm -- for efficient processing of out-of-core graphs.
- Hierarchical Communication Reduction Paradigm -- for fast processing of Power-Law graphs.
- Hierarchical Graph Paradigm -- for expressing naturally hierarchical algorithms.
Using these, SGL provides 30+ commonly used graph algorithms as standard, using this paradigm, including various traversals, centrality metrics, and a multitude of graph mining and graph analytic algorithms. We will now go over how the computation proceeds to execute the algorithm.
First a computation is applied to an active vertex:
Then, the result of this computation is propagated to the vertex's neighbors (or other specified vertices):
Finally, the neighbors are updated with this information: