Evaluation of Graph Analytics Frameworks Using the GAP Benchmark Suite
Authors:
- 1 October 2020
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 216-227
Abstract
Graphs play a key role in data analytics. Graphs and the software systems used to work with them are highly diverse. Algorithms interact with hardware in different ways and which graph solution works best on a given platform changes with the structure of the graph. This makes it difficult to decide which graph programming framework is the best for a given situation. In this paper, we try to make sense of this diverse landscape. We evaluate five different frameworks for graph analytics: SuiteS-parse GraphBLAS, Galois, the NWGraph library, the Graph Kernel Collection, and GraphIt. We use the GAP Benchmark Suite to evaluate each framework. GAP consists of 30 tests: six graph algorithms (breadth-first search, single-source shortest path, PageRank, betweenness centrality, connected components, and triangle counting) on five graphs. The GAP Benchmark Suite includes high-performance reference implementations to provide a performance baseline for comparison. Our results show the relative strengths of each framework, but also serve as a case study for the challenges of establishing objective measures for comparing graph frameworks.Keywords
Funding Information
- National Science Foundation (1835499,1618425,1705092,1725322)
- DARPA (26-3511-51,HR0011-18-3-0007)
- Department of Defense (FA8702-15-D-0002)
This publication has 38 references indexed in Scilit:
- Faster set intersection with SIMD instructions by reducing branch mispredictionsProceedings of the VLDB Endowment, 2014
- OpenTuner2014
- A lightweight infrastructure for graph analytics2013
- GraphX2013
- Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication2005
- The webgraph framework I2004
- Δ-stepping: a parallelizable shortest path algorithmJournal of Algorithms, 2003
- A faster algorithm for betweenness centrality*The Journal of Mathematical Sociology, 2001
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular GraphsSIAM Journal on Scientific Computing, 1998
- An O(logn) parallel connectivity algorithmJournal of Algorithms, 1982