Navigating the maze of graph analytics frameworks using massive graph datasets

By Nadathur Rajagopalan Satish, Narayanan Sundaram, Md. Mostofa Ali Patwary, Jiwon Seo, Jongsoo Park, M. Hassaan, Shubho Sengupta, Zhaoming Yin, Pradeep K. Dubey. 2014

202 citations recorded by the source corpus.

Graph algorithms are becoming increasingly important for analyzing large datasets in many fields. Real-world graph data follows a pattern of sparsity, that is not uniform but highly skewed towards a few items. Implementing graph traversal, statistics and machine learning algorithms on such data in a scalable manner is quite challenging. As a result, several graph analytics frameworks (GraphLab, CombBLAS, Giraph, SociaLite and Galois among others) have been developed, each offering a solution with different programming models and targeted at different users. Unfortunately, the "Ninja performance gap" between optimized code and most of these frameworks is very large (2-30X for most frameworks and up to 560X for Giraph) for common graph algorithms, and moreover varies widely with algorithms. This makes the end-users' choice of graph framework dependent not only on ease of use but also on performance. In this work, we offer a quantitative roadmap for improving the performance of all these frameworks and bridging the "ninja gap". We first present hand-optimized baselines that get performance close to hardware limits and higher than any published performance figure for these graph algorithms. We characterize the performance of both this native implementation as well as popular graph frameworks on a variety of algorithms. This study helps end-users delineate bottlenecks arising from the algorithms themselves vs. programming model abstractions vs. the framework implementations. Further, by analyzing the system-level behavior of these frameworks, we obtain bottlenecks that are agnostic to specific algorithms. We recommend changes to alleviate these bottlenecks (and implement some of them) and reduce the performance gap with respect to native code. These changes will enable end-users to choose frameworks based mostly on ease of use.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Information Systems

How researchers see this paper

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

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Information Systems

Citations in the corpus

A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications (2017, background): “, graph analytics [8] and representation learning [9].”
EmptyHeaded: A Relational Engine for Graph Processing (2015, methodology): “ance set intersections in-depth in Section 4 and EmptyHeaded’s triangle counting numbers are comparable to Intel’s hand-coded numbers which are slightly (10-20%) faster than the Galois implementation [30]. We provide a comparison to Galois on SSSP and PageRank in Section 5.2.2. 5.2.2 Graph Analytics”
Graphicionado: A high-performance and energy-efficient accelerator for graph analytics (2016, methodology): “For synthetic graphs, the Graph500 RMAT data generator [1] is used to generate the RMAT graph [10] and a bipartite graph generator described in [43] is used to generate a SB graph which has similar edge distributions with the realworld Netflix graph but at a different scale.”
GraphMat: High performance graph analytics made productive (2015, background): “However, a recent study has shown [28] that the performance of most frameworks is off by an order of magnitude when compared to native, hand- This work is licensed under the Creative Commons AttributionNonCommercial-NoDerivs 3.0 Unported License.”
OuterSPACE: An Outer Product Based Sparse Matrix Multiplication Accelerator (2018, methodology): “19) used for Graph500 to generate undirected power-law graphs, which is also employed in recent work in graph analytics [51] [58].”