Graph summarization algorithm based on node similarity grouping and graph compression

doi:10.11772/j.issn.1001-9081.2022101535

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (10): 3047-3053.DOI: 10.11772/j.issn.1001-9081.2022101535

• Artificial intelligence • Previous Articles

Graph summarization algorithm based on node similarity grouping and graph compression

Yu HONG¹, Hongchang CHEN², Jianpeng ZHANG²(), Ruiyang HUANG²

^1.Cyberspace Security College，Zhengzhou University，Zhengzhou Henan 450002，China
^2.Institute of Information Technology，Information Engineering University，Zhengzhou Henan 450002，China

Received:2022-10-17 Revised:2023-01-31 Accepted:2023-01-31 Online:2023-04-12 Published:2023-10-10
Contact: Jianpeng ZHANG
About author:HONG Yu， born in 1998， M. S. candidate. His research interests include graph data mining.
CHEN Hongchang， born in 1964， Ph. D.， professor. His research interests include big data analysis， communication and information systems.
HUANG Ruiyang， born in 1986， Ph. D.， associate research fellow. His research interests include knowledge graph， text mining.
Supported by:
National Natural Science Foundation of China(62002384);China Postdoctoral Science Foundation(2020M683760)

基于节点相似性分组与图压缩的图摘要算法

宏宇¹, 陈鸿昶², 张建朋²(), 黄瑞阳²

^1.郑州大学网络空间安全学院，郑州 450002
^2.信息工程大学信息技术研究所，郑州 450002

通讯作者: 张建朋
作者简介:宏宇（1998—），男，河北廊坊人，硕士研究生，主要研究方向：图数据挖掘
陈鸿昶（1964—），男，河南新密人，教授，博士生导师，博士，主要研究方向：大数据分析、通信与信息系统
黄瑞阳（1986—），男，福建漳州人，副研究员，博士，主要研究方向：知识图谱、文本挖掘。
基金资助:
国家自然科学基金资助项目(62002384);中国博士后科学基金资助项目(2020M683760)

Abstract

Abstract:

To solve the problem that the current graph summarization methods have high compression ratios and the graph compression algorithms cannot be directly used in downstream tasks， a fusion algorithm of graph summarization and graph compression was proposed， which called Graph Summarization algorithm based on Node Similarity grouping and graph Compression （GSNSC）. Firstly， the nodes were initialized as super nodes， and the super nodes were grouped according to the similarity. Secondly， the super nodes of each group were merged until the specified number of times or nodes were reached. Thirdly， super edges and corrected edges were added between the super nodes for reconstructing the original graph. Finally， for the graph compression part， the cost of compressing and summarizing the adjacent edges of each super node were judged， and the less expensive one in these two was selected to execute. Experiments of graph compression ratio and graph query were conducted on six datasets such as Web-NotreDame， Web-Google and Web-Berkstan. Experimental results on six datasets show that， the proposed algorithm has the compression ratio reduced by at least 23 percentage points compared with SLUGGER （Scalable Lossless sUmmarization of Graphs with HiERarchy） algorithm， and the compression ratio decreased by at least 13 percentage points compared with SWeG （Summarization of Web-scale Graphs） algorithm. Experimental results on Web-NotreDame dataset show that the degree error of the proposed algorithm is reduced by 41.6% compared with that of SWeG algorithm. The above verifies that the proposed algorithm has better graph compression ratio and graph query accuracy.

Key words: graph summarization, graph compression, graph query, super edge, Minimum Description Length (MDL)

摘要：

针对当前图摘要方法压缩率较高，图压缩算法无法直接被用于下游任务分析的问题，提出一种图摘要与图压缩的融合算法，即基于节点相似性分组与图压缩的图摘要算法（GSNSC）。首先，初始化节点为超节点，并根据相似度对超节点分组；其次，将每个组的超节点合并，直到达到指定次数或指定节点数；再次，在超节点之间添加超边和校正边以恢复原始图；最后，对于图压缩部分，判断对每个超节点的邻接边压缩和摘要的代价，并选择二者中代价较小的执行。在Web-NotreDame、Web-Google和Web-Berkstan等6个数据集上进行了图压缩率和图查询实验。实验结果表明，在6个数据集上，与SLUGGER（Scalable Lossless sUmmarization of Graphs with HiERarchy）算法相比，所提算法的压缩率至少降低了23个百分点；与SWeG（Summarization of Web-scale Graphs）算法相比，所提算法的压缩率至少降低了13个百分点；在Web-NotreDame数据集上，所提算法的度误差比SWeG降低了41.6%。以上验证了所提算法具有更好的图压缩率和图查询准确度。

关键词: 图摘要, 图压缩, 图查询, 超边, 最小描述长度

CLC Number:

TP391

Yu HONG, Hongchang CHEN, Jianpeng ZHANG, Ruiyang HUANG. Graph summarization algorithm based on node similarity grouping and graph compression[J]. Journal of Computer Applications, 2023, 43(10): 3047-3053.

宏宇, 陈鸿昶, 张建朋, 黄瑞阳. 基于节点相似性分组与图压缩的图摘要算法[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3047-3053.

Figures/Tables 7

Fig. 1 Schematic diagram of example

Tab. 1 Symbols and meanings

符号	含义
$C C$	压缩后的校正边集
$u ¯$	超节点u的邻居超节点集合
$C = C +, C -$	校正边集合
T	迭代次数
$θ$	节点的合并阈值
$∏ A B$	超节点A和B之间的全部边的集合
$E A B$	超节点A和B之间实际存在的边的集合

Tab. 1 Symbols and meanings

符号	含义
$C C$	压缩后的校正边集
$u ¯$	超节点u的邻居超节点集合
$C = C +, C -$	校正边集合
T	迭代次数
$θ$	节点的合并阈值
$∏ A B$	超节点A和B之间的全部边的集合
$E A B$	超节点A和B之间实际存在的边的集合

Tab. 2 Dataset description

名称	节点数	边数	描述
DBLP	317 080	1 049 866	Collaboration
Web-NotreDame	325 729	1 497 135	Web
Web-Google	875 713	5 105 039	Web
Web-Berkstan	685 230	7 600 595	Web
Skitter	1 696 415	11 095 298	Internet
Youtube	1 134 890	2 987 624	Social

Tab. 3 Comparison of experimental results of different algorithms on six datasets

算法	θ	DBLP		Web-Berkstan		Web-Google		Web-NotreDame		Skitter		Youtube
算法	θ	压缩率	运行时间/s	压缩率	运行时间/s	压缩率	运行时间/s	压缩率	运行时间/s	压缩率	运行时间/s	压缩率	运行时间/s
DPGS	0.1	0.663 6	68	0.255 4	291	0.407 6	227	0.306 1	72	0.622 9	504	0.670 7	175
	0.2	0.680 1	67	0.268 9	219	0.415 3	206	0.323 2	73	0.647 6	465	0.720 6	154
	0.3	0.712 9	67	0.280 3	226	0.436 1	197	0.349 9	63	0.698 2	445	0.756 6	154
GSNSC	0.1	0.328 1	113	0.083 0	356	0.178 3	248	0.138 6	89	0.209 2	649	0.378 8	232
	0.2	0.347 7	105	0.091 6	305	0.258 1	216	0.130 2	80	0.253 2	598	0.392 8	215
	0.3	0.369 6	96	0.105 9	296	0.196 9	200	0.155 0	72	0.293 3	530	0.413 5	200
SWeG	0.1	0.653 2	78	0.214 2	325	0.371 6	256	0.288 4	89	0.550 6	670	0.643 9	208
	0.2	0.662 0	76	0.223 7	306	0.381 8	229	0.303 6	86	0.578 5	601	0.688 8	169
	0.3	0.695 0	72	0.235 6	286	0.403 9	207	0.333 1	80	0.627 0	563	0.733 7	168
GREEDY	0.1	0.551 6	18 596	0.461 2	OOT	0.531 2	OOT	0.442 6	32 569	0.585 6	OOT	0.601 5	OOT
	0.2	0.625 6	17 569	0.475 6	OOT	0.540 2	OOT	0.453 6	36 895	0.593 6	OOT	0.632 9	OOT
	0.3	0.642 5	15 469	0.491 7	OOT	0.563 9	OOT	0.472 5	40 122	0.654 9	OOT	0.664 5	OOT
GreedyCS	0.1	0.572 6	20 156	0.344 6	OOT	0.432 6	OOT	0.285 9	38 456	0.486 9	OOT	0.523 6	OOT
	0.2	0.581 6	19 756	0.349 8	OOT	0.442 6	OOT	0.295 8	40 123	0.503 8	OOT	0.545 6	OOT
	0.3	0.605 9	17 596	0.365 9	OOT	0.476 8	OOT	0.324 8	45 698	0.523 6	OOT	0.578 9	OOT
SLUGGER		0.676 0	23	0.456 0	103	0.493 0	76	0.385 0	20	0.537 0	209	0.909 0	185

Fig. 2 Relationship between θ and compression ratio on Web-NotreDame dataset

Fig. 3 Relationship between T and compression ratio on Web-NotreDame dataset （θ=0.2）

Tab. 4 Degree error and adjacency error comparison of three algorithms on different datasets

算法	Web-NotreDame		Web-Google
算法	度误差	邻接误差/10⁶	邻接误差/10⁶
GSNSC	0.505	2.412	2.400
DPGS	0.983	3.523	3.550
SWeG	0.864	2.704	2.750

References 24

1	LEE K， JO H， KO J， et al. SSumM： sparse summarization of massive graphs［C］// Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2020： 144-154. 10.1145/3394486.3403057
2	MACCIONI A， ABADI D J. Scalable pattern matching over compressed graphs via dedensification［C］// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2016： 1755-1764. 10.1145/2939672.2939856
3	NAVLAKHA S， RASTOGI R， SHRIVASTAVA N. Graph summarization with bounded error［C］// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2008： 419-432. 10.1145/1376616.1376661
4	SEO H， PARK K， HAN Y， et al. An effective graph summarization and compression technique for a large-scaled graph［J］. The Journal of Supercomputing， 2020， 76（10）： 7906-7920. 10.1007/s11227-018-2245-5
5	SHIN K， GHOTING A， KIM M， et al. SWeG： lossless and lossy summarization of web-scale graphs［C］// Proceedings of the 2019 World Wide Web Conference. Republic and Canton of Geneva： International World Wide Web Conferences Steering Committee， 2019： 1679-1690. 10.1145/3308558.3313402
6	ZHOU H， LIU S， LEE K， et al. DPGS： degree-preserving graph summarization［C］// Proceedings of the 2021 SIAM International Conference on Data Mining. Philadelphia， PA： SIAM， 2021：280-288. 10.1137/1.9781611976700.32
7	ZHU L， GHASEMI-GOL M， SZEKELY P， et al. Unsupervised entity resolution on multi-type graphs［C］// Proceedings of the 2016 International Semantic Web Conference， LNCS 9981. Cham： Springer， 2016： 649-667.
8	TIAN Y， HANKINS R A， PATEL J M. Efficient aggregation for graph summarization［C］// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2008： 567-580. 10.1145/1376616.1376675
9	YONG Q， HAJIABADI M， SRINIVASAN V， et al. Efficient graph summarization using weighted LSH at billion-scale［C］// Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2021： 2357-2365. 10.1145/3448016.3457331
10	UR R S， NAWAZ A， ALI T， et al. g-Sum： a graph summarization approach for a single large social network［J］. EAI Endorsed Transactions on Scalable Information Systems， 2021， 8（32）： No.e2.
11	SACENTI J A P， FILETO R， WILLRICH R. Knowledge graph summarization impacts on movie recommendations［J］. Journal of Intelligent Information Systems， 2022， 58（1）： 43-66. 10.1007/s10844-021-00650-z
12	BOLDI P， SANTINI M， VIGNA S. Permuting web graphs［C］// Proceedings of the 2009 International Workshop on Algorithms and Models for the Web-Graph， LNCS 5427. Berlin： Springer， 2009： 116-126.
13	HERNÁNDEZ C， NAVARRO G. Compressed representations for Web and social graphs［J］. Knowledge and Information Systems， 2014， 40（2）： 279-313. 10.1007/s10115-013-0648-4
14	BRISABOA N R， LADRA S， NAVARRO G. k ²-trees for compact Web graph representation［C］// Proceedings of the 2009 International Symposium on String Processing and Information Retrieval， LNCS 5721. Berlin： Springer， 2009： 18-30.
15	FRANCISCO A P， GAGIE T， KÖPPL D， et al. Graph compression for adjacency-matrix multiplication［J］. SN Computer Science， 2022， 3（3）： No.193. 10.1007/s42979-022-01084-2
16	EMAMZADEH ESMAEILI NEJAD A， JAHROMI M Z， TAHERI M. Graph compression based on transitivity for neighborhood query［J］. Information Sciences， 2021， 576： 312-328. 10.1016/j.ins.2021.06.050
17	YANG S， YANG Z， CHEN X， et al. Distributed aggregation-based attributed graph summarization for summary-based approximate attributed graph queries［J］. Expert Systems with Applications， 2021， 176： No.114921. 10.1016/j.eswa.2021.114921
18	LEE K， KO J， SHIN K. SLUGGER： lossless hierarchical summarization of massive graphs［C］// Proceedings of the IEEE 38th International Conference on Data Engineering. Piscataway： IEEE， 2022： 472-484. 10.1109/icde53745.2022.00040
19	KE X， KHAN A， BONCHI F. Multi-relation graph summarization［J］. ACM Transactions on Knowledge Discovery from Data， 2022， 16（5）： No.82. 10.1145/3494561
20	KANG S， LEE K， SHIN K. Personalized graph summarization： formulation， scalable algorithms， and applications［C］// Proceedings of the IEEE 38th International Conference on Data Engineering. Piscataway： IEEE， 2022： 2319-2332. 10.1109/icde53745.2022.00219
21	董荣胜，张新凯，刘华东，等. 大规模图数据的k ²-MDD表示方法与操作研究［J］. 计算机研究与发展， 2016， 53（12）：2783-2792. 10.7544/issn1000-1239.2016.20160589
	DONG R S， ZHANG X K， LIU H D， et al. Representation and operations research of k ²-MDD in large-scale graph data［J］. Jouanal of Computer Research and Development， 2016， 52（12）：2783-2792. 10.7544/issn1000-1239.2016.20160589
22	RISSANEN J. Modeling by shortest data description［J］. Automatica， 1978， 14（5）： 465-471. 10.1016/0005-1098(78)90005-5
23	BRODER A Z， CHARIKAR M， FRIEZE A M， et al. Min-wise independent permutations［J］. Journal of Computer and System Sciences， 2000， 60（3）： 630-659. 10.1006/jcss.1999.1690
24	LeFEVRE K， TERZI E. GraSS： graph structure summarization［C］// Proceedings of the 2010 SIAM International Conference on Data Mining. Philadelphia， PA： SIAM， 2010： 454-465. 10.1137/1.9781611972801.40

[1]	Danfeng ZHAO, Junchen LIN, Wei SONG, Jian WANG, Dongmei HUANG. Strategy with low redundant computation for reachability query preserving graph compression [J]. Journal of Computer Applications, 2020, 40(2): 510-517.
[2]	SHI Weijie, DONG Yihong, WANG Xiong, PAN Jianfei. Research progress of index-based subgraph query technology [J]. Journal of Computer Applications, 2019, 39(1): 39-45.
[3]	SONG Baoyan, JIA Chunjie, SHAN Xiaohuan, DING Linlin, DING Xingyan. Dynamic Top-K interesting subgraph query on large-scale labeled graph [J]. Journal of Computer Applications, 2018, 38(2): 471-477.
[4]	Xin-gong CHANG Ji-song KOU Ming-qiang LI. Evolutionary substructure discovery algorithm based on individuals with state backtracking [J]. Journal of Computer Applications, 2007, 27(8): 1944-1947.

Graph summarization algorithm based on node similarity grouping and graph compression

基于节点相似性分组与图压缩的图摘要算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 24

Related Articles 4

Recommended Articles

Metrics