Partitioning an input graph over a set of workers is a complex operation. Objectives are twofold: split the work evenly, so that every worker gets an equal share, and minimize edge cut to achieve a good work locality (i.e. workers can work independently). Partitioning a graph accessible from memory is a notorious NP-complete problem. Motivated by the regain of interest for the stream processing paradigm (where nodes and edges arrive as a flow to the datacenter), we propose in this paper a stream-enabled graph partitioning system that constantly seeks an optimum between those two objectives. We first expose the hardness of partitioning using classic and static methods; we then exhibit the cut versus load balancing tradeoff, from an application point of view. With this tradeoff in mind, our approach translates the online partitioning problem into a standard optimization problem. A greedy algorithm handles the stream of incoming graph updates while optimizations are triggered on demand to improve upon the greedy decisions. Using simulations, we show that this approach is very efficient, turning a basic optimization strategy such as hill climbing into an online partitioning solution that compares favorably to literature's recent stream partitioning solutions.
@cite_8 are the first to consider a stream of nodes to be placed onto partitions on the fly. Many heuristics are proposed and tested, from intuitive ones (considering balance) to more advanced ones (considering clustering coefficient); we re-implement the best performing one in this paper to compare it to our proposal. All approaches are one pass; a placed vertex is never moved afterward. Their paper assumes a full knowledge model, where the graph to be streamed has to be present on one machine prior to the execution of the proposed heuristics.
@cite_8
2006023152
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 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 81 2 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.