Balanced graph partitioning in the streaming setting is a key problem to enable scalable and efficient computations on massive graph data such as web graphs, knowledge graphs, and graphs arising in the context of online social networks. Two families of heuristics for graph partitioning in the streaming setting are in wide use: place the newly arrived vertex in the cluster with the largest number of neighbors or in the cluster with the least number of non-neighbors.

In this work, we introduce a framework which unifies the two seemingly orthogonal heuristics and allows us to quantify the interpolation between them. More generally, the framework enables a well principled design of scalable, streaming graph partitioning algorithms that are amenable to distributed implementations. We derive a novel one-pass, streaming graph partitioning algorithm and show that it yields significant performance improvements over previous approaches using an extensive set of real-world and synthetic graphs.

Surprisingly, despite the fact that our algorithm is a one-pass streaming
algorithm, we found its performance to be in many cases comparable to the it
de-facto standard offline software METIS and in some cases even superiror. For
instance, for the Twitter graph with more than 1.4 billion of edges, our method
partitions the graph in about 40 minutes achieving a balanced partition that cuts
as few as 6.8{\%} of edges, whereas it took more than 8*tfrac 12* hours by
METIS to produce a balanced partition that cuts 11.98{\%} of edges. We also
demonstrate the performance gains by using our graph partitioner while solving
standard PageRank computation in a graph processing platform with respect to the
communication cost and runtime.