PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs

By Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, Carlos Guestrin. USENIX Symposium on Operating Systems Design and Implementation, 2012

2,018 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/0ad8e89091eed09217e66adc98136126addc2619

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

A lightweight infrastructure for graph analytics (2013, background): “PowerGraph [11] is a distributed-memory programming model for topology or data-driven computations with autonomous or coordinated scheduling, but it is restricted to gather-apply-scatter (GAS) programs, which are a subset of vertex programs.”
Gunrock: a high-performance graph processing library on the GPU (2015, methodology): “ performance with four CPU graph libraries: the Boost Graph Library (BGL) [33], one of the highest-performing CPU single-threaded graph libraries [21]; PowerGraph, a popular distributed graph library [13]; and Ligra [32] and Galois [26, 28], two of the highest-performing multi-core shared-memory gra”
DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs (2020, methodology): “PowerGraph [8] adopts vertex cut for graph partitioning and gather-and-scatter interface for computation.”
EmptyHeaded: A Relational Engine for Graph Processing (2015, methodology): “We omit a description of the uint layout as it is just an array of 32-bit unsigned integers.”
GraphSC: Parallel Secure Computation Made Easy (2015, methodology): “This also resulted in several implementations, including GraphLab [9], [12] and Giraph [59].”
AWB-GCN: A Graph Convolutional Network Accelerator with Runtime Workload Rebalancing (2019, background): “Most of these graphs have a tremendously large numbers of nodes; moreover, the node degree generally varies dramatically, often following a power law distribution [11]–[17].”
DStress: Efficient Differentially Private Computations on Distributed Data (2017, background): “In the age of “big data”, it is well known that many interesting things can be learned by collecting and analyzing large graphs, and a number of tools – including GraphLab [47], PowerGraph [35], and GraphX [36] – have been developed to make such analyses fast and convenient.”
NeuGraph: Parallel Deep Neural Network Computation on Large Graphs (2019, methodology): “With the vertex-program abstraction and graph-specific optimizations, existing graph processing systems [10, 15, 26, 28, 47] can naturally express iterative graph algorithms like PageRank and community detection, and scale them to graphs with billions of vertices and edges.”
Mizan: a system for dynamic load balancing in large-scale graph processing (2013, background): “Nonetheless, PowerGraph s replication approach is complementary to Mizan s dynamic load balancing techniques.”
AliGraph: A Comprehensive Graph Neural Network Platform (2019, methodology): “, PowerGraph [16]) that usually takes several hours).”
A Berkeley View of Systems Challenges for AI (2017, background): “en came a plethora of systems [46, 55, 60, 67, 114], that aimed to”
GASGD: stochastic gradient descent for distributed asynchronous matrix completion via graph partitioning. (2014, methodology): “It has been shown [6] that the vertex-cut approach performs better than edge-cut in these scenarios.”
Naiad: a timely dataflow system (2013, methodology): “Asynchronous computation Several recent systems have abandoned synchronous execution in favor of a model that asynchronously updates a distributed shared data structure, in order to achieve low-latency incremental updates [10, 36] and ﬁne-grained computational dependencies [16, 26].”
Addressing the straggler problem for iterative convergent parallel ML (2016, methodology): “However, GraphLab requires the application programmer to know and specify the communication pattern.”
SNAP: A General Purpose Network Analysis and Graph Mining Library (2016, methodology): “In particular, research on graph processing in large-scale distributed environments [Gonzalez et al. 2012; Malewicz et al. 2010; Kang et al. 2009; Salihoglu and Widom 2013; Xin et al. 2013] provides efficient frameworks, but these frameworks implement only a handful of most common graph algorithms, ”
NOMAD: Nonlocking, stOchastic Multi-machine algorithm for Asynchronous and Decentralized matrix completion (2013, methodology): “PowerGraph [13], upon which the latest version of the GraphLab toolkit is based, is also essentially based on the idea of a parameter server.”
PowerLyra: Differentiated Graph Computation and Partitioning on Skewed Graphs (2019, methodology): “In practice, applying the greedy heuristic to all edges (i.e., Coordinated [24]) incurs a significant penalty during graph partitioning [29], mainly caused by exchanging vertex information among machines.”
GraphChi: Large-Scale Graph Computation on Just a PC (2012, unknown): “PowerGraph is a distributed version of GraphLab [29], which employs a novel vertex-partitioning model and a new Gather-Apply-Scatter (GAS) programming model allowing it to compute on graphs with power-law degree distribution extremely efﬁciently.”