Scholarlink

<p>Graph partitioning is the basis of many graph computations. A good graph partitioning algorithm is related to the partition balance and the communication overhead between nodes after partitioning. This paper measures the former by the relative standard deviation (RSD). At the same time, the latter is often related to the number of replicated vertices or edge cuts. In order to balance the above two goals, the greedy strategy is adopted to improve, which is a graph edge partitioning algorithm that transforms the graph so that the vertex partitioning methods can be applied to the transformed graph. A novel graph edge partitioning algorithm named G-SPAC is proposed. Firstly, to reduce the number of duplicated vertices, the method of degree-and-spatial-locality priority is designed so that adjacent vertices are more accessible to divide into the same subgraph. Secondly, to improve the division balance, the judgment-aware folding method is designed to carry out the graph division from a more granular perspective. Experiments are conducted on eighteen graph data sets. The results show that for most of the graphs, the RSD for the number of edges of each subgraph partitioned by the G-SPAC algorithm is below 3%. In terms of the number of vertex copies, G-SPAC’s performance is not inferior to the SPAC algorithm, and it can even reduce the number of copies by an order of magnitude on some graphs.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

G-SPAC: a more granular greedy graph partition algorithm with spatial locality and judgment-aware edge folding

  • 期刊论文

  • 发表日期：

    2025年6月27日

查看全文
  • Yuedan Chen,
  • Zhijie Li,
  • Guoqing Xiao,
  • Peixin Xu,
  • Xiaofei Zhang,
  • Kenli Li

摘要

Graph partitioning is the basis of many graph computations. A good graph partitioning algorithm is related to the partition balance and the communication overhead between nodes after partitioning. This paper measures the former by the relative standard deviation (RSD). At the same time, the latter is often related to the number of replicated vertices or edge cuts. In order to balance the above two goals, the greedy strategy is adopted to improve, which is a graph edge partitioning algorithm that transforms the graph so that the vertex partitioning methods can be applied to the transformed graph. A novel graph edge partitioning algorithm named G-SPAC is proposed. Firstly, to reduce the number of duplicated vertices, the method of degree-and-spatial-locality priority is designed so that adjacent vertices are more accessible to divide into the same subgraph. Secondly, to improve the division balance, the judgment-aware folding method is designed to carry out the graph division from a more granular perspective. Experiments are conducted on eighteen graph data sets. The results show that for most of the graphs, the RSD for the number of edges of each subgraph partitioned by the G-SPAC algorithm is below 3%. In terms of the number of vertex copies, G-SPAC’s performance is not inferior to the SPAC algorithm, and it can even reduce the number of copies by an order of magnitude on some graphs.