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: Extracting knowledge by performing computations on graphs is becoming increasingly challenging as graphs grow in size. A standard approach distributes the graph over a cluster of nodes, but performing computations on a distributed graph is expensive if large amount of data have to be moved. Without partitioning the graph, communication quickly becomes a limiting factor in scaling the system up. Existing graph partitioning heuristics incur high computation and communication cost on large graphs, sometimes as high as the future computation itself. Observing that the graph has to be loaded into the cluster, we ask if the partitioning can be done at the same time with a lightweight streaming algorithm. We propose natural, simple heuristics and compare their performance to hashing and METIS, a fast, offline heuristic. We show on a large collection of graph datasets that our heuristics are a significant improvement, with the best obtaining an average gain of 76 . The heuristics are scalable in the size of the graphs and the number of partitions. Using our streaming partitioning methods, we are able to speed up PageRank computations on Spark, a distributed computation system, by 18 to 39 for large social networks.
@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.