  Graph Partitioning is widely used in many real-world applications such as
fraud detection and social network analysis, in order to enable the distributed
graph computing on large graphs. However, existing works fail to balance the
computation cost and communication cost on machines with different power
(including computing capability, network bandwidth and memory size), as they
only consider replication factor and neglect the difference of machines in
realistic data centers. In this paper, we propose a general graph partitioning
algorithm WindGP, which can support fast and high-quality edge partitioning on
heterogeneous machines. WindGP designs novel preprocessing techniques to
simplify the metric and balance the computation cost according to the
characteristics of graphs and machines. Also, best-first search is proposed
instead of BFS and DFS, in order to generate clusters with high cohesion.
Furthermore, WindGP adaptively tunes the partition results by sophisticated
local search methods. Extensive experiments show that WindGP outperforms all
state-of-the-art partition methods by 1.35 - 27 times on both dense and sparse
distributed graph algorithms, and has good scalability with graph size and
machine number.
