Distributed Power-law Graph Computing: Theoretical and Empirical Analysis
With the emergence of big graphs in a variety of real applications like social networks, machine learning based on distributed graph-computing (DGC) frameworks has attracted much attention from big data machine learning community. In DGC frameworks, the graph partitioning (GP) strategy plays a key role to affect the performance, including the workload balance and communication cost. Typically, the degree distributions of natural graphs from real applications follow skewed power laws, which makes GP a challenging task. Recently, many methods have been proposed to solve the GP problem. However, the existing GP methods cannot achieve satisfactory performance for applications with power-law graphs. In this paper, we propose a novel vertex-cut method, called degree-based hashing (DBH), for GP. DBH makes effective use of the skewed degree distributions for GP. We theoretically prove that DBH can achieve lower communication cost than existing methods and can simultaneously guarantee good workload balance. Furthermore, empirical results on several large power-law graphs also show that DBH can outperform the state of the art.
1. The authors suggest a method for vertex-cut-based graph partitioning for distributed computation. Targeting good performance on naturally occurring power-law graphs, they introduce a hash-based method that works (in its simplest form) as follows:Every edge e is uniquely assigned to a machine by selecting the incident vertex with the smallest degree and hashing that vertex's id. This intuitively leads to a balanced partitioning. The authors further provide analysis showing that their method performs at least as good as currently used graph partitioning schemes. Finally, experimental evaluation shows that for the task of PageRank, their method actually outperforms the state of the art.Pros:The idea is simple and clear. The solution is intuitive and apparently effective. The figures contribute to readability. Simple analysis guarantees that the method is definitely not a bad idea and the experiments show strict improvement over the state of the art.The authors have performed a number of experiments, however sticking to PageRank exclusively.The suggest GP method pertains to the very timely topic of graph-computation, it is very easy to implement and it is reasonable to assume that it will have impact on the community.Cons:The biggest issue with the paper is organization and readability. While there are crisp ideas in the material, the presentation is lacking. Ideas do not flow well and there are some grammatical errors. Should the paper be accepted it would need a lot of editing.The idea itself is not the big contribution; it feels like a very reasonable approach. It’s the experimental evaluation and, secondarily the analysis, that give this paper merit.