TR-2015-03
Understanding Graph Computation Behavior to Enable Robust Benchmarking
Fan Yang; Andrew Chien. 31 March, 2015.
Communicated by Andrew Chien.
Abstract
Graph processing is widely recognized as important for a growing range of applications, including social network analysis, machine learning, data mining, and web search. Recently, many performance assessments and comparative studies of graph computation have been published, all of which employ highly varied ensembles of algorithms and graphs. To explore the robustness of these studies, we characterize how behavior varies across a variety of graph algorithms on a diverse collection of graphs (size and degree distribution). Our results show that graph computation behaviors form a very broad space, and inefficient exploration of this space will possibly lead to an ad-hoc study as well as a narrow understanding of graph processing performance.Hence, we consider constructing an ensemble of experiments, e.g. a benchmark suite, to most effectively explore graph computation behavior space. We study different ensembles of graph computations, and define two metrics, spread and coverage, to quantify how efficiently and completely an ensemble explores the space. Our results show that: (1) an ensemble drawn from a single algorithms or a single graph may unfairly characterize a graph-processing system, (2) an ensemble exploring both algorithm diversity and graph diversity improves the quality significantly, but must be carefully chosen, (3) some algorithms are more useful than others for exploring the space, and (4) it is possible to reduce benchmarking complexity (i.e. number of algorithms, graphs, etc.) while conserving the benchmarking quality.
Original Document
The original document is available in PDF (uploaded 31 March, 2015 by Andrew Chien).