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 to minimize 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 the max-flow model. To evaluate the performance of our algorithms, we first provide adequate theoretical analysis in terms of the approximation quality. We significantly improve the previously 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
Processing massive graphs, such as social networks or web crawls, requires distributing the data across multiple machines. Traditional vertex partitioning often fails on "power-law" graphs where a few highly connected nodes create significant bottlenecks. Consequently, edge partitioning—splitting the lines rather than the dots—has become the modern standard. The objective is to divide edges into equal-sized buckets to ensure workload balance while minimizing the Replication Factor (RF), which measures the communication overhead caused by vertex copies across machines.
While many initial partitioners (e.g., METIS, GraphX defaults) exist, they are often suboptimal. This research introduces a local search framework designed to refine these initial partitions, driving down communication costs without violating balance constraints.
The Local Search Framework: Adjustable Edges and Blocks
The core of the proposed refinement strategy lies in two novel structural concepts:
- Adjustable Edges: These are edges that can be moved between partitions without increasing the replication factor because their endpoints already exist in the destination partition.
- Blocks: These are connected components of edges that remain after adjustable edges are removed. Moving an entire block can strictly decrease the replication factor by removing vertex copies from the source partition.
Refinement Algorithms
Building on these concepts, the authors developed two primary algorithms:
- LS-G (Greedy): A fast heuristic that identifies blocks and attempts to move them, along with incident adjustable edges, to other partitions if balance constraints allow.
- LS-F (Max-Flow): A more sophisticated approach that identifies independent sets of blocks and uses a Max-Flow min-cut model. This allows for the simultaneous movement of multiple adjustable edges, finding optimizations that a greedy search would overlook.
Theoretical Contributions
The paper provides a significant theoretical advancement by establishing a new approximation ratio of $\min\{k, \bar{d}\}$, where $k$ is the number of partitions and $\bar{d}$ is the average degree. This is a substantial improvement over previous complex logarithmic bounds, providing a firmer theoretical foundation for the edge partition problem.
Experimental Evaluation
The framework was evaluated using a massive dataset of 1,872 real-world graphs from the Network Data Repository, ranging from social networks to biological systems.
Key Findings
- Replication Factor Reduction: LS-G and LS-F improved partition quality by an average of 12.07% and 13.20%, respectively, across the nearly 2,000 datasets.
- Initial Partitioner Sensitivity: The refinement is particularly effective on partitions generated by METIS, which tends to create numerous small blocks that the local search can easily optimize.
- Downstream Speedups: Refined partitions led to a ~10% speedup in PageRank and an ~8% improvement in triangle counting tasks. Compared to Spark GraphX's built-in partitioners, the framework achieved an average total computation time speedup of 30.82%.
Conclusion
This research demonstrates that "polishing" existing partitions via local search is a highly effective and computationally feasible alternative to building new partitioners from scratch. While the local search adds some initial overhead, the resulting reduction in communication costs significantly accelerates downstream graph processing tasks. Future work may explore relaxing balance constraints to further minimize replication factors or integrating these local search moves directly into the initial partitioning phase of distributed systems.
Summary updated