Method of K-order Graph Convolution Attribute Network Community Detection

doi:10.3778/j.issn.1673-9418.2104116

Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (12): 2788-2796.DOI: 10.3778/j.issn.1673-9418.2104116

• Artificial Intelligence • Previous Articles Next Articles

Method of K-order Graph Convolution Attribute Network Community Detection

CHEN Jie¹, ZHANG Erming¹, WANG Qianqian², ZHAO Shu¹^,⁺(), ZHANG Yanping¹

1. College of Computer Science and Technology, Anhui University, Hefei 230601, China
2. College of International Education, Anhui University, Hefei 230601, China

Received:2021-05-08 Revised:2021-06-25 Online:2022-12-01 Published:2021-06-08
About author:CHEN Jie, born in 1982, Ph.D., lecturer, mem-ber of CCF. Her research interests include in-telligent computing, machine learning, etc.
ZHANG Erming, born in 1995, M.S. candi-date. His research interests include intelligent computing, machine learning, etc.
WANG Qianqian, born in 1982, M.S., lecturer, member of CAAI. Her research interests include granular computing and machine learning.
ZHAO Shu, born in 1979, Ph.D., professor, Ph.D. supervisor, senior member of CCF. Her research interests include granular computing, quotient space theory and machine learning.
ZHANG Yanping, born in 1962, professor, Ph.D. supervisor. Her research interests include in-telligent computing, quotient space, machine lear-ning, intelligent information processing, etc.
Supported by:
National Key Research and Development Program Subtopic of China(2017YFB1401903);National Natural Science Foundation of China(61876001)

K阶图卷积属性网络社团检测方法

陈洁¹, 张二明¹, 王倩倩², 赵姝¹^,⁺(), 张燕平¹

1.安徽大学计算机科学与技术学院，合肥 230601
2.安徽大学国际教育学院，合肥 230601

通讯作者: +E-mail: zhaoshuzs2002@hotmail.com
作者简介:陈洁（1982—），女，安徽巢湖人，博士，讲师，CCF会员，主要研究方向为智能计算、机器学习等。
张二明（1995—），男，安徽淮北人，硕士研究生，主要研究方向为智能计算、机器学习等。
王倩倩（1982—），女，安徽六安人，硕士，讲师，CAAI会员，主要研究方向为粒计算、机器学习。
赵姝（1979—），女，安徽巢湖人，博士，教授，博士生导师，CCF高级会员，主要研究方向为粒计算、商空间理论、机器学习。
张燕平（1962—），女，安徽合肥人，教授，博士生导师，主要研究方向为智能计算、商空间、机器学习、智能信息处理等。
基金资助:
国家重点研发计划子课题(2017YFB1401903);国家自然科学基金(61876001)

Abstract

Abstract:

Mining community structure in attribute network is helpful to further analysis of network nodes, which has important practical significance. Graph convolution neural network can effectively embed the structural information of attribute network and obtain the feature representation of nodes. Based on this, the community structure with good performance can be obtained. However, most of the existing graph convolution methods use fixed low-order graph convolution, only consider the first-order or second-order neighbors of each node, don’t make full use of the node relationship and ignore the diversity of network structure. In addition, the sparsity of the original network structure can’t be overcome, which will reduce the performance of community detection. In order to solve the above problems, this paper proposes a K-order graph convolution community detection method (KGCN) which combines attribute information and structure information. This method can effectively overcome the sparsity of the original network and use the high-order structure of nodes for community detection. Firstly, the original network is reconstructed according to the attribute information of nodes to alleviate the sparsity of the original network. Secondly, considering the high-order structure correlation, the K-order graph convolution encoder is used to encode the nodes to obtain the feature representation of the nodes. Finally, community detection is carried out using spectral clustering algorithm. Experimental results show that the KGCN method achieves better community detection results than the existing algorithms on four real datasets.

Key words: community detection, K-order graph convolution, attribute information, sparsity

摘要：

挖掘属性网络中的社团结构有助于对网络节点进一步分析，具有重要的现实意义。图卷积神经网络能够有效地将属性网络的结构信息进行嵌入，获取节点的特征表示，从而可获得性能良好的社团结构。然而，现有图卷积方法大多使用固定的低阶图卷积，只考虑每个节点一阶或二阶内的邻居，没有充分利用节点关系，忽略了网络结构的多样性。另外原始网络结构的稀疏性无法克服，会降低社团检测的性能。为解决上述问题，提出一种融合属性信息与结构信息的K阶图卷积社团检测方法（KGCN），该方法可以有效地克服原始网络的稀疏性并利用节点的高阶结构进行社团检测。首先根据节点的属性信息对原始网络进行重构，缓解原始网络结构的稀疏性；其次考虑到高阶结构关联，采用K阶图卷积编码器对节点进行编码，获得节点的特征表示；最后使用谱聚类算法进行社团检测。实验结果表明，在四个真实数据集上，相比现有算法，KGCN方法取得更好的社团检测结果。

关键词: 社团检测, K阶图卷积, 属性信息, 稀疏性

CLC Number:

TP391

CHEN Jie, ZHANG Erming, WANG Qianqian, ZHAO Shu, ZHANG Yanping. Method of K-order Graph Convolution Attribute Network Community Detection[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(12): 2788-2796.

陈洁, 张二明, 王倩倩, 赵姝, 张燕平. K阶图卷积属性网络社团检测方法[J]. 计算机科学与探索, 2022, 16(12): 2788-2796.

Figures/Tables 6

Fig.1 KGCN model framework

Table 1 Dataset details

数据集	节点数	边缘数	属性长度	社团标签
$C o r a$	2 708	5 429	1 433	7
$C i t e S e e r$	3 327	4 732	3 703	6
$P u b m e d$	19 717	44 338	500	3
$W i k i$	2 405	17 981	4 973	17

Table 1 Dataset details

数据集	节点数	边缘数	属性长度	社团标签
$C o r a$	2 708	5 429	1 433	7
$C i t e S e e r$	3 327	4 732	3 703	6
$P u b m e d$	19 717	44 338	500	3
$W i k i$	2 405	17 981	4 973	17

Fig.2 Preformance changing with α

Fig.3 Preformance changing with k

Table 2 Comparison of algorithm results on different datasets

Methods	Input	Cora			CiteSeer			Pubmed			Wiki
Methods	Input	Acc	NMI	F1	Acc	NMI	F1	Acc	NMI	F1	Acc	NMI	F1
K-means	Feature	34.65	16.73	25.42	38.49	17.02	30.47	57.32	29.12	57.35	33.37	30.20	24.51
Spectral-f	Feature	36.26	15.09	25.64	46.23	21.19	33.70	59.91	32.55	58.61	41.28	43.99	25.20
Spectral-g	Graph	34.19	19.49	30.17	25.91	11.84	29.48	39.74	3.46	51.97	23.58	19.28	17.21
DeepWalk	Graph	46.74	31.75	38.06	36.15	9.66	26.70	61.86	16.71	47.06	38.46	32.38	25.74
DNGR	Graph	49.24	37.29	37.29	32.59	18.02	44.19	45.35	15.38	17.09	37.58	35.85	25.38
GAE	Both	53.25	40.69	41.97	41.26	18.34	29.13	64.08	22.97	49.26	17.33	11.93	15.35
VGAE	Both	55.95	38.45	41.50	44.38	22.71	31.88	65.48	25.09	50.95	28.67	30.28	20.49
MGAE	Both	63.43	45.57	38.01	63.56	39.75	39.49	43.88	8.16	41.98	50.14	47.97	39.20
ARGE	Both	64.00	44.90	61.90	57.30	35.00	54.60	59.12	23.17	58.41	41.40	39.50	38.27
ARVGE	Both	63.80	45.00	62.70	54.40	26.10	52.90	58.22	20.62	23.04	41.55	40.01	37.80
AGC	Both	68.92	53.68	65.61	67.00	41.13	62.48	69.78	31.59	68.72	47.65	45.28	40.36
KGCN	Both	71.21	53.02	67.19	68.14	42.14	63.45	69.79	32.09	68.82	60.85	61.88	55.70

Table 3 Results of ablation analysis

Methods	Cora			CiteSeer			Pubmed			Wiki
Methods	Acc	NMI	F1	Acc	NMI	F1	Acc	NMI	F1	Acc	NMI	F1
Ori_1	46.51	27.84	45.54	60.76	33.95	57.45	60.75	30.61	59.47	44.50	47.86	39.40
Ori_k	68.31	42.33	63.68	67.14	41.14	62.45	69.08	31.09	67.14	44.88	46.33	39.95
Re_k	71.21	53.02	67.19	68.14	42.14	63.45	69.79	32.09	68.82	60.85	61.88	55.70

References 27

[1]	ZHOU Y, CHENG H, YU J X. Clustering large attributed graphs: an efficient incremental approach[C]// Proceedings of the 10th IEEE International Conference on Data Mining, Sydney, Dec 14-17, 2010. Washington: IEEE Computer So-ciety, 2010: 689-698.
[2]	PEEL L, LARREMORE D B, CLAUSET A. The ground truth about metadata and community detection in networks[J]. arXiv:1608.05878, 2016.
[3]	BERGENTHUM R, LORENZ R, MAUSER S. Faster unfol-ding of general petri nets based on token flows[C]// LNCS 5062: Proceedings of the 29th International Conference on Applications and Theory of Petri Nets, Xi’an, Jun 23-27, 2008. Berlin, Heidelberg: Springer, 2008: 13-32.
[4]	CHANG J, BLEI D M. Hierarchical relational models for document networks[J]. The Annals of Applied Statistics, 2010, 48(3): 269-281.
[5]	XIA R K, PAN Y, DU L, et al. Robust multi-view spectral clustering via low-rank and sparse decomposition[C]// Pro-ceedings of the 28th AAAI Conference on Artificial Intel-ligence, Québec City, Jul 27-31, 2014. Menlo Park: AAAI, 2014: 2149-2155.
[6]	YANG C, LIU Z Y, ZHAO D L, et al. Network represen-tation learning with rich text information[C]// Proceedings of the 24th International Joint Conference on Artificial In-telligence, Buenos Aires, Jul 25-31, 2015. Menlo Park: AAAI, 2015: 2111-2117.
[7]	BIAN Y C, LUO D S, YAN Y W, et al. Correction to: memory-based random walk for multi-query local community detec-tion[J]. Knowledge and Information Systems, 2020, 62(5): 2103-2104. DOI URL
[8]	JIN D, ZHANG B B, SONG Y, et al. ModMRF: a modularity-based Markov random field method for community detec-tion[J]. Neurocomputing, 2020, 405: 218-228. DOI URL
[9]	JIN D, LIU Z Y, LI W H, et al. Graph convolutional net-works meet Markov random fields: semi-supervised com-munity detection in attribute networks[C]// Proceedings of the 33rd AAAI Conference on Artificial Intelligence, the 31st Innovative Applications of Artificial Intelligence Con-ference, the 9th AAAI Symposium on Educational Advan-ces in Artificial Intelligence, Honolulu, Jan 27-Feb 1, 2019. Menlo Park: AAAI, 2019: 152-159.
[10]	WANG X, JIN D, CAO X C, et al. Semantic community identification in large attribute networks[C]// Proceedings of the 30th AAAI Conference on Artificial Intelligence, Phoenix, Feb 12-17, 2016. Menlo Park: AAAI, 2016: 265-271.
[11]	KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks[C]// Proceedings of the 5th International Conference on Learning Representations, Tou-lon, Apr 24-26, 2017: 1-14.
[12]	KIPF T N, WELLING M. Variational graph auto-encoders[J]. arXiv:1611.07308, 2016.
[13]	PAN S R, HU R Q, LONG G D, et al. Adversarially regula-rized graph autoencoder for graph embedding[C]// Procee-dings of the 27th International Joint Conference on Artifi-cial Intelligence, Stockholm, Jul 13-19, 2018: 2609-2615.
[14]	WANG C, PAN S R, LONG G D, et al. MGAE: margina-lized graph autoencoder for graph clustering[C]// Procee-dings of the 2017 ACM on Conference on Information and Knowledge Management, Singapore, Nov 6-10, 2017. New York: ACM, 2017: 889-898.
[15]	CHUNAEV P. Community detection in node-attributed so-cial networks: a survey[J]. Computer Science Review, 2020, 37: 100286. DOI URL
[16]	ZHU X, GHAHRAMANI Z. Learning from labels and unla-beled data with label propagation: Tech Report CMU-CALD-02-107[R]. 2002: 1-8.
[17]	YAMAGUCHI Y, HAYASHI K. When does label propa-gation fail? A view from a network generative model[C]// Proceedings of the 26th International Joint Conference on Artificial Intelligence, Melbourne, Aug 19-25, 2017: 3224-3230.
[18]	JIN D, YOU X X, LI W H, et al. Incorporating network em-bedding into Markov random field for better community detection[C]// Proceedings of the 33rd AAAI Conference on Artificial Intelligence, the 31st Innovative Applications of Artificial Intelligence Conference, the 9th AAAI Sympo-sium on Educational Advances in Artificial Intelligence, Honolulu, Jan 27-Feb 1, 2019. Menlo Park: AAAI, 2019: 160-167.
[19]	CAI X, NIE F P, HUANG H. Multi-view K-means cluste-ring on big data[C]// Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, Aug 3-9, 2013. Menlo Park: AAAI, 2013: 2598-2604.
[20]	SHEN X B, LIU W W, TSANG I W, et al. Compressed K-means for large-scale clustering[C]// Proceedings of the 31st AAAI Conference on Artificial Intelligence, San Francisco, Feb 4-9, 2017. Menlo Park: AAAI, 2017: 2527-2533.
[21]	ZHOU Y, CHENG H, YU J F. Graph clustering based on structural/attribute similarities[J]. Proceedings of the VLDB Endowment, 2009, 2(1): 718-729. DOI URL
[22]	WANG X, SONG J L, LU K, et al. Community detection in attributed networks based on heterogeneous vertex interac-tions[J]. Applied Intelligence, 2017, 47(4): 1270-1281. DOI URL
[23]	RUAN Y Y, FUHRY D, PARTHASARATHY S. Efficient community detection in large networks using content and links[C]// Proceedings of the 22nd International World Wide Web Conference, Rio de Janeiro, May 13-17, 2013. New York: ACM, 2013: 1089-1098.
[24]	DANG T, VIENNET E. Community detection based on structural and attribute similarities[C]// Proceedings of the 6th International Conference on Digital Society, Valencia, Jan 30-Feb 4, 2012: 548-553.
[25]	ZHANG X T, LIU H, LI Q M, et al. Attributed graph clus-tering via adaptive graph convolution[C]// Proceedings of the 28th International Joint Conference on Artificial Intel-ligence, Macao, China, Aug 10-16, 2019: 4327-4333.
[26]	VON LUXBURG U. A tutorial on spectral clustering[J]. Sta-tistics and Computing, 2007, 17(4): 395-416.
[27]	AGGARWAL C C, REDDY C K. Data clustering: algori-thms and applications[M]. Boca Raton: CRC Press, 2014.

Method of K-order Graph Convolution Attribute Network Community Detection

K阶图卷积属性网络社团检测方法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 27

Related Articles 15

Recommended Articles

Metrics

[1]	ZHAN Tianming, SONG Bo, SUN Le, WAN Minghua, YANG Guowei. Hyperspectral Change Detection Using Collaborative Sparsity and Nonlocal Low-Rank Tensor [J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(2): 448-457.
[2]	DUAN Xiangyu, YUAN Guan, MENG Fanrong. Dynamic Community Detection: A Survey [J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(4): 612-630.
[3]	XING Changzheng, ZHAO Hongbao, ZHANG Quangui, GUO Yalan. Review Text Hierarchical Attention and Outer Product for Recommendation Method [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(6): 947-957.
[4]	FENG Yong, ZHANG Bingru, XU Hongyan, WANG Rongbing, ZHANG Yonggang. Community Detection Algorithms Combining Improved Differential Evolution and Modularity Density [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(6): 1070-1080.
[5]	CHEN Kejia, CHEN Liming, WU Tong. Survey on Community Detection in Multi-layer Networks [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(11): 1801-1812.
[6]	REN Hao, LIU Baisong, SUN Jinyang. Advances and Perspectives on Knowledge Transfer Based Cross-Domain Recom-mendation [J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(11): 1813-1827.
[7]	JIANG Miaomiao, SUN Gengxin, BIN Sheng. Community Detection Algorithm in Multiple Relationships Online Social Network [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(7): 1134-1144.
[8]	XU Yi, LI Beibei, SONG Wei. Research on Improved Deep Belief Network Classification Algorithm [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(4): 596-607.
[9]	FENG Lizhou, QIN Yue, YANG Guijun. Community Detection Algorithm with Difference of Node-Local Fiedler Vector Centrality [J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(12): 2029-2042.
[10]	LI Chunying, TANG Zhikang, TANG Yong, ZHAO Jiandong, HUANG Yonghang. Community Detection Algorithm with Local-First Approach in Social Networks [J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(8): 1263-1277.
[11]	WANG Hongjie, TENG Fei, LI Tianrui. Incremental Learning Algorithm of Community Detection under Guidance of Modularity [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(4): 556-564.
[12]	SHEN Guilan, JIA Caiyan, YU Jian, YANG Xiaoping. Semantic Community Detection Algorithm for Large Scale Information Network [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(4): 565-576.
[13]	MAO Yiyu, LIU Jianxun, HU Rong, TANG Mingdong, SHI Min. Sigmoid Function-Based Web Service Collaborative Filtering Recommendation Algorithm [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(2): 314-322.
[14]	ZHOU Yang, CHEN Xiaoyun, CHENG Jianjun, LIU Wei, MIAO Haifei. Bisection Spectral Community-Detection Methods Using Optimal Eigenvectors [J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(12): 1897-1906.
[15]	LI Yafang, JIA Caiyan, YU Jian. Survey on Community Detection Algorithms Using Nonnegative Matrix Factorization Model [J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(1): 1-13.