DisHAP：基于层次亲和聚类的分布式大图划分算法

doi:10.12263/DZXB.20190919

摘要/Abstract

摘要：

平衡图划分是改善并行图计算性能的关键.一个良好的划分算法应保证划分后的子图在负载均衡的前提下，减少子图之间的交互边(切割边)规模，从而减少网络通信.对此，本文设计一种基于层次亲和聚类的分布式大图划分算法(DisHAP).该算法采用亲和聚类的思想，将图初始划分为规模相等的k个子图；再将结果映射成顶点序列，以线性嵌入顺序处理节点，通过局部交换策略优化割边率；最后将DisHAP应用在MapReduce框架中，使用多种真实及理论图数据，与现有的大图划分算法做比较分析.以Twitter图为例，划分2,4,8,16,32个子区，相较于现有的大图划分算法(LDG,BLP,Spinner,Fennel,ParMetis及PSA-MIR算法)，割边率减少1.7%～30.2%，说明了该算法的优越性.同时该算法具有良好的可扩展性，划分的子区数量及图的规模对划分时间具有较低的影响.

关键词: 分布式大图划分, 层次聚类, 局部优化, 分布式图计算, 平衡划分

Abstract:

It is the key to improve the performance of graph calculation by improving the efficiency of the graph partitioning algorithm and reducing the communication edge scale between the subgraphs. Due to the limited memory capacity of single computing node, it is difficult to meet the partitioning requirements of large-scale graphs in terms of partitioning efficiency and partitioning quality. In this paper, a distributed graph partitioning algorithm based on hierarchical affinity clustering for massive scale graphs is designed, called DisHAP. It uses the Boruvka minimum spanning tree algorithm to balance cluster the graph under the constraint condition of the input graph according to the vertex similarity, and partitions the graph into k subgraph (partitions) with equal size. In order to optimize the fractiom of edges cut between these large subgraphs, we map the initial partition results to the vertex sequence and cut into a large number of subsections, randomly select the sub slice pairs in the neighbor subgraph sequence, and migrate the vertices according to the mutual exchange and the single vertex positive profit. Thus, the optimization problem of large data volume is converted to a large number of small problems to solve. The algorithm is applied to the MapReduce framework to effectively improve the efficiency of the algorithm. Finally, we use various actual and theoretical graph data to compare with existing graph partitioning algorithms to verify the effectiveness of the DisHAP algorithm. Taking the graph Twitter as an example, it is partitioned into 2,4,8,16,32 partitions. Compared to LDG, BLP, Spinner, Fennel, ParMetis and PSA-MIR algorithms, the fraction of edges cut is reduced by 30.2%, 29.4%, 10.2%, 7.8%, 1.7%, and 3.3% respectively.

Key words: distributed large-scale graph partitioning, hierarchical clustering, local optimization, distributed graph computation, balanced partitioning

中图分类号:

TP311

柳菁, 李琪. DisHAP：基于层次亲和聚类的分布式大图划分算法[J]. 电子学报, 2021, 49(10): 2002-2011.

Jing LIU, Qi LI. DisHAP: A Distributed Partition Algorithm for Large Scale Graphs Based on Hierarchical Affinity Clustering[J]. Acta Electronica Sinica, 2021, 49(10): 2002-2011.

图/表 8

参考文献 24

1	Basak A, Li S C, Hu X, et al. Analysis and optimization of the memory hierarchy for graph processing workloads[A]. 2019 IEEE International Symposium on High Performance Computer Architecture (HPCA)[C]. Washington, DC, USA: IEEE, 2019. 373－386.
2	Miller G L, Teng S H, Vavasis S A. A unified geometric approach to graph separators[A]. 1991 Proceedings 32nd Annual Symposium of Foundations of Computer Science[C]. San Juan, PR, USA: IEEE, 1991. 538－547.
3	Stanton I, Kliot G. Streaming graph partitioning for large distributed graphs[A]. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD 12[C]. New York, USA: ACM Press, 2012. 1222－1230.
4	Stanton I. Streaming balanced graph partitioning algorithms for random graphs[A]. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms[C]. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2014. 1287－1301.
5	Andreev K, Räcke H. Balanced graph partitioning[A]. Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - SPAA04[C]. New York, USA: ACM Press, 2004: 120－124.
6	Liu N, Li D S, Zhang Y M, et al. Large-scale graph processing systems: A survey[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(3): 384－404.
7	Benlic U, Hao J K. An effective multilevel tabu search approach for balanced graph partitioning[J]. Computers & Operations Research, 2011, 38(7): 1066－1075.
8	Kokosiński Z, Bała M. Solving graph partitioning problems with parallel metaheuristics[A]. Recent Advances in Computational Optimization[C]. Cham, Germany: Springer, 2018. 89－105.
9	Awadelkarim A, Ugander J. Prioritized restreaming algorithms for balanced graph partitioning[A]. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining[C]. New York, NY, USA: ACM, 2020. 1877－1887.
10	Nishimura J, Ugander J. Restreaming graph partitioning: Simple versatile algorithms for advanced balancing[A]. Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C]. New York, NY, USA: ACM, 2013. 1106－1114.
11	Srinuvasu M A. Analysis of large graph partitioning and frequent subgraph mining on graph data[J]. International Journal of Advanced Computer Research, 2015, 6(7): 12.
12	Moon B, Jagadish H V, Faloutsos C, et al. Analysis of the clustering properties of the Hilbert space-filling curve[J]. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(1): 124－141.
13	Tsourakakis C, Gkantsidis C, Radunovic B, et al. FENNEL: streaming graph partitioning for massive scale graphs[A]. Proceedings of the 7th ACM International Conference on Web Search and Data Mining[C]. New York, NY, USA: ACM, 2014. 333－342.
14	Battaglino C, Pienta P, Vuduc R. GraSP: distributed streaming graph partitioning[A]. The 1st High Performance Graph Mining Workshop[C]. Arcelona, SPAIN: Barcelona Supercomputing Center, 2015. DOI:10.5821/hpgm15.3.
15	Martella C, Logothetis D, Loukas A, et al. Spinner: scalable graph partitioning in the cloud[EB/OL]. , 2019.
16	Pope A S, Tauritz D R, Kent A D. Evolving multi-level graph partitioning algorithms[A]. IEEE Symposium Series on Computational Intelligence (SSCI)[C]. Athens, Greece: IEEE, 2016. 1－8.
17	Tsourakakis C E, Kolountzakis M N, Miller G L. Approximate triangle counting[EB/OL]. , 2019.
18	Qian X H. Graph processing and machine learning architectures with emerging memory technologies: A survey[J]. Science China Information Sciences, 2021, 64(6): 1－25.
19	Borůvka, Otakar. O jistém problému minimálním[EB/OL]. , 2019.
20	Han M Y, Daudjee K, Ammar K, et al. An experimental comparison of pregel-like graph processing systems[J]. Proceedings of the VLDB Endowment, 2014, 7(12): 1047－1058.
21	Murtagh F, Contreras P. Algorithms for hierarchical clustering: An overview[J]. WIREs Data Mining and Knowledge Discovery, 2012, 2(1): 86－97.
22	Tang C F, Rao Y, Yu H L, et al. Improving knowledge graph completion using soft rules and adversarial learning[J]. Chinese Journal of Electronics, 2021, 30(4): 623－633.
23	Khayyat Z, Awara K, Alonazi A, et al. Mizan: A system for dynamic load balancing in large-scale graph processing[A]. Proceedings of the 8th ACM European Conference on Computer Systems - EuroSys 13[C]. New York, USA: ACM Press, 2013. 169－182.
24	Fiduccia C M, Mattheyses R M. A linear-time heuristic for improving network partitions[A]. 19th Design Automation Conference[C]. Las Vegas, NV, USA: IEEE, 1982. 175－181.

Name	Number of vertices	Number of edges	Type
hugebubble-10	18.3M	27.5M	Mesh
channel	4.8M	42.6M	Mesh
nlpkkt240	27.9M	373M	Mesh
uk-2002	18.5M	262M	Social
de126	67.1M	201M	Mesh
rgg26	67.1M	575M	Mesh
arabic-2005	22.7M	553M	Social
Friendster	66M	1.8B	Social
Twitter	40M	1.5B	Social
LiveJournal	4.8M	1.3B	Social
world-roads	5.6M	1.1B	road
PLG18	630K	35M	synthetic
PLG20	2.8M	135M	synthetic
PLG22	9.1M	518M	synthetic
PLG24	29.7M	1.9B	synthetic
PLG26	115M	7.9B	synthetic

Name	Number of vertices	Number of edges	Type
hugebubble-10	18.3M	27.5M	Mesh
channel	4.8M	42.6M	Mesh
nlpkkt240	27.9M	373M	Mesh
uk-2002	18.5M	262M	Social
de126	67.1M	201M	Mesh
rgg26	67.1M	575M	Mesh
arabic-2005	22.7M	553M	Social
Friendster	66M	1.8B	Social
Twitter	40M	1.5B	Social
LiveJournal	4.8M	1.3B	Social
world-roads	5.6M	1.1B	road
PLG18	630K	35M	synthetic
PLG20	2.8M	135M	synthetic
PLG22	9.1M	518M	synthetic
PLG24	29.7M	1.9B	synthetic
PLG26	115M	7.9B	synthetic

k	LDG （ε=1.1）	BLP （ε=1.0）	Spinner （ε=1.05）	Fennel （ε=1.09）	ParMetis （ε=1.03）	PSA-MIR （ε=1.0）	DisHAP （ε=1.03）
2	0.31	0.34	0.15	0.07	0.12	0.15	0.10
4	0.49	0.55	0.31	0.29	0.24	0.21	0.19
8	0.69	0.66	0.49	0.48	0.35	0.40	0.38
16	0.80	0.76	0.61	0.59	0.52	N/A	0.49
32	0.86	0.80	0.69	0.67	N/A	N/A	0.58

k	LDG （ε=1.1）	BLP （ε=1.0）	Spinner （ε=1.05）	Fennel （ε=1.09）	ParMetis （ε=1.03）	PSA-MIR （ε=1.0）	DisHAP （ε=1.03）
2	0.31	0.34	0.15	0.07	0.12	0.15	0.10
4	0.49	0.55	0.31	0.29	0.24	0.21	0.19
8	0.69	0.66	0.49	0.48	0.35	0.40	0.38
16	0.80	0.76	0.61	0.59	0.52	N/A	0.49
32	0.86	0.80	0.69	0.67	N/A	N/A	0.58

Graph	ParMetis			DisHAP
Graph	Avg. cut	Best cut	t/s	Avg. cut	Best cut	t/s
hugebubble-10	1922	1854	4.66	1910	1857	8.20
channel	48798	47776	1.55	56912	55959	2.71
de126	18086	17609	23.74	17002	16703	31.02
rgg26	44747	42739	23.37	38371	37676	19.91
nlpkkt240	1178988	1152935	32.97	1241950	1228086	25.06
uk-2002	787391	697767	128.71	439227	390182	96.62
arabic-2005	1078415	968871	1245.57	561778	481141	1092.45