Two-Dimensional Balanced Partitioning and Efficient Caching for Distributed Graph Analysis
Lists
Only you see this
Abstract
Distributed graph analysis usually partitions a large graph into multiple small-sized subgraphs and distributes them into a cluster of machines for computing. Therefore, graph partitioning plays a crucial role in distributed graph analysis. However, the widely used existing graph partitioning schemes balance only in one dimension (number of edges or vertices) or incur a large number of edge cuts, so they degrade the performance of distributed graph analysis. In this article, we propose a novel graph partition scheme BPart and two enhanced algorithms BPart-C and BPart-S to achieve a balanced partition for both vertices and edges, and also reduce the number of edge cuts. Besides, we also propose a neighbor-aware caching scheme to further reduce the number of edge cuts so as to improve the efficiency of distributed graph analysis. Our experimental results show that BPart-C and BPart-S can achieve a better balance in both dimensions (the number of vertices and edges), and meanwhile reducing the number of edge cuts, compared to multiple existing graph partitioning algorithms, i.e., Chunk-V, Chunk-E, Fennel, and Hash. We also integrate these partitioning algorithms into two popular distributed graph systems, KnightKing and Gemini, to validate their impact on graph analysis efficiency. Results show that both BPart-C and BPart-S can significantly reduce the total running time of various graph applications by up to 60% and 70%, respectively. In addition, the neighbor-aware caching scheme can further improve the performance by up to 24%.
BibTeX
@article{lin2025two,
author = {Shuai Lin and Rui Wang and Yongkun Li and Yinlong Xu and John C. S. Lui},
title = {{Two-Dimensional Balanced Partitioning and Efficient Caching for Distributed Graph Analysis}},
journal = {IEEE Trans. Parallel Distributed Syst.},
year = {2025},
doi = {10.1109/tpds.2024.3501292},
}Loading related content...