Fast Stochastic Block Partition for Streaming Graphs
Ahsen J. Uppal, H. Howie Huang · 2018
The graph partition problem continues to be challenging, particularly for streaming graph data. Although optimal graph partitioning is NP-hard, stochastic methods can provide approximate solutions in reasonable time. However, such methods are optimized for static, not dynamic graph data. In this paper, we describe a new efficient algorithm we have developed for stochastic block partitioning on time-varying, streaming graph data. Our algorithm is a refinement of the baseline algorithm of the IEEE HPEC Graph Challenge [1]. Our incremental algorithm efficiently updates its previous internal state as new pieces are streamed in, and generates a complete partition at every time step. Compared to the naive baseline which performs a complete partitioning from scratch at every time step, our algorithm offers speedups between 1.96x for N=500 and 3.56x for N=20k overall, for a graph streamed over 10 parts, with similar accuracy. At the margin, the speedup in processing time for additional streaming pieces over the baseline is between 7.1x for N=500 to 25.1x for N=20k.