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

doi:10.3778/j.issn.1673-9418.2104116

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (12): 2788-2796.DOI: 10.3778/j.issn.1673-9418.2104116

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

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

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

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

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)

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP391

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

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.

图/表 6

图1 KGCN模型框架

Fig.1 KGCN model framework

表1 数据集详细信息

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

表1 数据集详细信息

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

图2 评价指标随 α变化图

Fig.2 Preformance changing with α

图3 评价指标随 k变化图

Fig.3 Preformance changing with k

表2 不同数据集上各算法结果对比单位：%

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

表3 消融分析实验结果单位：%

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

参考文献 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.

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

Method of K-order Graph Convolution Attribute Network Community Detection

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 27

相关文章 4

编辑推荐

Metrics

[1]	邢长征，赵宏宝，张全贵，郭亚兰. 融合评论文本层级注意力和外积的推荐方法[J]. 计算机科学与探索, 2020, 14(6): 947-957.
[2]	毛宜钰，刘建勋，胡蓉，唐明董，石敏. 采用Sigmoid函数的Web服务协同过滤推荐算法[J]. 计算机科学与探索, 2017, 11(2): 314-322.
[3]	周旸，陈晓云，程建军，刘伟，苗海飞. 基于最优特征向量的谱二分社团检测方法[J]. 计算机科学与探索, 2017, 11(12): 1897-1906.
[4]	王鹏，景丽萍. 改进的单类协同过滤推荐方法[J]. 计算机科学与探索, 2014, 8(10): 1231-1238.