Enhancing Balanced Graph Edge Partition with Effective Local Search

Authors

  • Zhenyu Guo University of Electronic Science and Technology of China
  • Mingyu Xiao University of Electronic Science and Technology of China
  • Yi Zhou University of Electronic Science and Technology of China
  • Dongxiang Zhang Zhejiang University
  • Kian-Lee Tan National University of Singapore

Keywords:

Local Search, Heuristic Search

Abstract

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. The graph edge partition problem, which is to split the edge set into multiple balanced parts with the objective of minimizing the total number of copied vertices, has been widely studied from the view of optimization and algorithms. In this paper, we study local search algorithms for this problem to further improve the partition results from existing methods. More specifically, we propose two novel concepts, namely adjustable edges and blocks. Based on these, we develop a greedy heuristic as well as an improved search algorithm utilizing the property of max-flow model. To evaluate the performance of our algorithms, we first provide adequate theoretical analysis in terms of approximation quality. We significantly improve the previous known approximation ratio for this problem. Then we conduct extensive experiments on a large number of benchmark datasets and state-of-the-art edge partition strategies. The results show that our proposed local search framework can further improve the quality of graph partition by a wide margin.

Downloads

Published

2021-05-18

How to Cite

Guo, Z., Xiao, M., Zhou, Y., Zhang, D., & Tan, K.-L. (2021). Enhancing Balanced Graph Edge Partition with Effective Local Search. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12336-12343. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17464

Issue

Section

AAAI Technical Track on Search and Optimization