  Graph-based data structures have drawn great attention in recent years. The
large and rapidly growing trend on developing graph processing systems focus
mostly on improving the performance by preprocessing the input graph and
modifying its layout. These systems usually take several hours to days to
complete processing a single graph on high-end machines, let alone the overhead
of pre-processing which most of the time can be dominant. Yet for most of graph
applications the exact answer is not always crucial, and providing a rough
estimate of the final result is adequate. Approximate computing is introduced
to trade off accuracy of results for computation or energy savings that could
not be achieved by conventional techniques alone. Although various computing
platforms and application domains benefit from approximate computing, it has
not been thoroughly explored yet in the context of graph processing systems.
  In this work, we design, implement and evaluate GraphGuess, inspired from the
domain of approximate graph theory and extend it to a general, practical graph
processing system. GraphGuess is essentially an approximate graph processing
technique with adaptive correction, which can be implemented on top of any
graph processing system. We build a vertex-centric processing system based on
GraphGuess, where it allows the user to trade off accuracy for better
performance. Our experimental studies show that using GraphGuess can
significantly reduce the processing time for large scale graphs while
maintaining high accuracy.
