Enhancing Balanced Graph Edge Partition with Effective Local Search

Zhenyu Guo, Mingyu Xiao, Yi Zhou, Dongxiang Zhang, Kian-Lee Tan

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.

Introduction

In the era of Big Data, massive graphs such as social networks and web crawls often exceed the capacity of a single machine. To process these efficiently, they must be partitioned across a cluster. While vertex partitioning (splitting nodes) is common, it often fails on "power-law" graphs where a few highly connected nodes create communication bottlenecks. Edge partitioning—splitting the edge set—has become the industry standard for these cases. However, the challenge lies in minimizing the replication factor (the number of vertex copies across machines) while maintaining a balanced workload.

Finding the optimal edge partition is NP-hard. Most existing tools rely on "one-pass" heuristics that build partitions from scratch. This research introduces a local search framework designed to "clean up" and refine these existing partitions, significantly reducing communication overhead in distributed systems.

Methodology: Adjustable Edges and Blocks

The core of the proposed approach is to iteratively move edges between machines to lower the replication factor without violating balance constraints. Two structural concepts are introduced to facilitate this:

  1. Adjustable Edges: Edges that can be moved to a target machine without increasing the replication factor because both endpoints already exist on that machine.
  2. Blocks: Connected components of edges that remain after accounting for adjustable edges. Moving an entire block can potentially eliminate vertex copies entirely.
Illustration of moving a block C between partitions (E1 to E4) to optimize the replication factor.

Based on these concepts, the authors developed two primary algorithms:

  • LS-G (Local Search - Greedy): A fast heuristic that identifies blocks and attempts to move them and their incident adjustable edges to other machines sequentially.
  • LS-F (Local Search - Flow): A sophisticated algorithm using a Max-Flow min-cut model. This allows for the simultaneous movement of multiple blocks while strictly adhering to machine balance constraints, uncovering optimizations that greedy heuristics might overlook.

Experimental Evaluation

The algorithms were tested on a massive suite of 1,872 real-world graphs from the Network Data Repository, spanning domains such as social, biological, and collaboration networks. The graphs ranged from 1,000 to over 17 million edges.

Key Results

  • Quality Improvement: Local search refined existing partitions by an average of 12.07% (LS-G) and 13.20% (LS-F) across all datasets.
  • System Speedup: In practical applications, these refined partitions led to significant performance gains:
  • PageRank saw an average speedup of ~10%.
  • Triangle Counting saw an average speedup of ~8%.
  • Compared to Spark GraphX built-in partitioners, the refined partitions yielded a 30.82% average speedup in total computation time.
  • Theoretical Breakthrough: The paper establishes a new theoretical approximation ratio of $min\{k, \bar{d}\}$ (where $k$ is the number of partitions and $\bar{d}$ is the average degree), a significant improvement over previous bounds.

Conclusion

This research demonstrates that local search is a highly effective tool for refining graph partitions. By focusing on "blocks" rather than individual edges and utilizing Max-Flow models, the proposed framework consistently improves partition quality and system performance. While LS-F provides the highest quality, LS-G offers a fast, viable alternative for production environments. Future work includes integrating these techniques directly into frameworks like Spark or Flink and scaling the Max-Flow approach for graphs with billions of edges.

Summary updated

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.
BibTeX
@inproceedings{guo2021enhancing,
  author = {Zhenyu Guo and Mingyu Xiao and Yi Zhou and Dongxiang Zhang and Kian-Lee Tan},
  title = {{Enhancing Balanced Graph Edge Partition with Effective Local Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=iAfbtqgAyE2},
}
Figure