Enhancing Balanced Graph Edge Partition with Effective Local Search
원문 초록
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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
AFANet: Adaptive Frequency-Aware Network for Weakly-Supervised Few-Shot Semantic Segmentation
NeSyCoCo: A Neuro-Symbolic Concept Composer for Compositional Generalization
PersonaMagic: Stage-Regulated High-Fidelity Face Customization with Tandem Equilibrium
Grounding Descriptions in Images informs Zero-Shot Visual Recognition
SAFE: Slow and Fast Parameter-Efficient Tuning for Continual Learning with Pre-Trained Models
Happy: A Debiased Learning Framework for Continual Generalized Category Discovery
토론
이 논문과 연결된 포럼 글이 아직 없습니다.