Local Search Algorithms For Balanced Graph Edge Partition

In mathmatics,graph partition is the reduction of a graph into some pairwised dis-joint subgraphs.In application,graph partition is a key component to achieve workload balance and reduce job completion time in parallel graph processing systems.Among the various partition strategies,edge partition has demonstrated more promising performance in power-law graphs than vertex partition and thereby has been more widely adopted as the default partition strategy by existing graph systems.It splits the edge set into multiple bal-anced parts with the objective of minimizing the total number of copied vertices.A more balanced edge parition with less copied vertices means a more balanced job allocation and less communication cost.In this paper,we study the problem from a new perspective — instead of propos-ing a new edge partition method,we adopt local search algorithms to further improve the partition results from any existing method.More specifically,we propose two novel data structures,namely adjustable edges and blocks.Based on these two concepts,we first analysis the approximation ratio in a theoretical way and improve this ratio to a large ex-tent? we then develop a greedy heuristic as well as an improved search algorithm utilizing the property of max-flow model.Extensive experiments are conducted on a large number of benchmark datasets from an online database Network Repository and state-of-the-art edge partition strategies.We also adopt our edge partitions on GraphX to test the running time of some graph analytics.The results show that our proposed local search framework can further improve the quality of graph partition by a wide margin.