基于核非负矩阵分解的有向图聚类算法

doi:10.11772/j.issn.1001-9081.2021061129

《计算机应用》唯一官方网站 ›› 2021, Vol. 41 ›› Issue (12): 3447-3454.DOI: 10.11772/j.issn.1001-9081.2021061129

• 第十八届中国机器学习会议(CCML 2021) • 上一篇

基于核非负矩阵分解的有向图聚类算法

陈献¹^,², 胡丽莹¹^,²(), 林晓炜¹^,², 陈黎飞¹^,²^,³

^1.福建师范大学计算机与网络空间安全学院，福州 350117
^2.数字福建环境监测物联网实验室（福建师范大学），福州 350117
^3.福建省应用数学中心（福建师范大学），福州 350117

收稿日期:2021-05-12 修回日期:2021-07-02 接受日期:2021-07-26 发布日期:2021-12-28 出版日期:2021-12-10
通讯作者: 胡丽莹
作者简介:陈献（1997—），男，福建莆田人，硕士研究生，主要研究方向：社区发现、人脸识别
林晓炜（1992—），男，福建龙海人，硕士研究生，主要研究方向：机器学习、复杂网络
陈黎飞（1972—），男，福建长乐人，教授，博士，CCF会员，主要研究方向：统计机器学习、数据挖掘、模式识别。
基金资助:
国家自然科学基金资助项目(U1805263);福建省自然科学基金资助项目(2018J01775)

Directed graph clustering algorithm based on kernel nonnegative matrix factorization

Xian CHEN¹^,², Liying HU¹^,²(), Xiaowei LIN¹^,², Lifei CHEN¹^,²^,³

^1.College of Computer and Cyber Security，Fujian Normal University，Fuzhou Fujian 350117，China
^2.Digit Fujian Internet-of-Things Laboratory of Environmental Monitoring （Fujian Normal University），Fuzhou Fujian 350117，China
^3.Center for Applied Mathematics of Fujian Province （Fujian Normal University），Fuzhou Fujian 350117，China

Received:2021-05-12 Revised:2021-07-02 Accepted:2021-07-26 Online:2021-12-28 Published:2021-12-10
Contact: Liying HU
About author:CHEN Xian， born in 1997， M. S. candidate. His research interests include community detection， face recognition.
LIN Xiaowei， born in 1992， M. S. candidate. His research interests include machine learning， complex network.
CHEN Lifei， born in 1972， Ph. D.， professor. His research interests include statistical machine learning， data mining， pattern recognition.
Supported by:
the National Natural Science Foundation of China(U1805263);the Natural Science Foundation of Fujian Province(2018J01775)

摘要/Abstract

摘要：

现有的有向图聚类算法大多基于向量空间中节点间的近似线性关系假设，忽略了节点间存在的非线性相关性。针对该问题，提出一种基于核非负矩阵分解（KNMF）的有向图聚类算法。首先，引入核学习方法将有向图的邻接矩阵投影到核空间，并通过特定的正则项约束原空间及核空间中节点间的相似性。其次，提出了图正则化核非对称NMF算法的目标函数，并在非负约束条件下通过梯度下降方法推导出一个聚类算法。该算法在考虑节点连边的方向性的同时利用核学习方法建模节点间的非线性关系，从而准确地揭示有向图中潜在的结构信息。最后，在专利-引文网络（PCN）数据集上的实验结果表明，簇的数目为2时，和对比算法相比，所提算法将DB值和DQF值分别提高了约0.25和8%，取得了更好的聚类质量。

关键词: 有向图聚类, 核非负矩阵分解, 核学习方法, 正则化, 节点相似性

Abstract:

Most of the existing directed graph clustering algorithms are based on the assumption of approximate linear relationship between nodes in vector space， ignoring the existence of non-linear correlation between nodes. To address this problem， a directed graph clustering algorithm based on Kernel Nonnegative Matrix Factorization （KNMF） was proposed. First， the adjacency matrix of a directed graph was projected to the kernel space by using a kernel learning method， and the node similarity in both the original and kernel spaces was constrained by a specific regularization term. Second， the objective function of graph regularization kernel asymmetric NMF algorithm was proposed， and a clustering algorithm was derived by gradient descent method under the non-negative constraints. The algorithm accurately reveals the potential structural information in the directed graph by modeling the non-linear relationship between nodes using kernel learning method， as well as considering the directivity of the links of nodes. Finally， experimental results on the Patent Citation Network （PCN） dataset show that compared with the comparison algorithm， when the number of clusters is 2， the proposed algorithm improves the Davies-Bouldin （DB） and Distance-based Quality Function （DQF） by about 0.25 and 8% respectively， achieving better clustering quality.

Key words: directed graph clustering, Kernel Nonnegative Matrix Factorization (KNMF), kernel learning method, regularization, node similarity

中图分类号:

TP135

陈献, 胡丽莹, 林晓炜, 陈黎飞. 基于核非负矩阵分解的有向图聚类算法[J]. 计算机应用, 2021, 41(12): 3447-3454.

Xian CHEN, Liying HU, Xiaowei LIN, Lifei CHEN. Directed graph clustering algorithm based on kernel nonnegative matrix factorization[J]. Journal of Computer Applications, 2021, 41(12): 3447-3454.

图/表 8

表1 有向网络数据集的详细信息

Tab. 1 Details of directed network datasets

数据集		节点数	边数	簇数
PCN		149	215	—
WebKB	Cornel	195	304	5
	Texas	187	328	5
	Washington	230	446	5
	Wisconsin	265	530	5
LFR	LFR1	1 000	15 662	32
	LFR2	1 000	15 164	31
	LFR3	1 000	15 429	33

图1 参数d对DB指标的影响

Fig. 1 Influence of parameter d on DB index

图2 参数d对DQF指标的影响

Fig. 2 Influence of parameter d on DQF index

图3 WebKB数据集上d值对AC指标影响

Fig. 3 Influence of d value on AC index on WebKB dataset

图4 WebKB数据集中λ值对AC指标影响

Fig. 4 Influence of λ value on AC index on WebKB dataset

表2 簇数（r）不同时各算法在PCN上的DB和DQF指标比较

Tab. 2 Comparison of DB and DQF indexes on PCN for each algorithm with different number of clusters （r）

算法	DB						DQF
算法	r=2	r=3	r=4	r=5	r=6	r=10	r=2	r=3	r=4	r=5	r=6	r=10
ANMF Rnd	1.468	1.504	1.196	0.933	0.743	1.113	0.759	0.491	0.392	0.323	0.272	0.185
RANMF Rnd	1.470	1.619	1.194	0.896	0.712	0.420	0.757	0.449	0.343	0.276	0.235	0.170
RKANMF Rnd	1.271	1.424	1.169	0.896	0.741	0.505	0.822	0.541	0.403	0.335	0.297	0.250
DeepWalk	2.465	1.508	1.122	0.896	0.679	0.399	0.492	0.357	0.248	0.211	0.186	0.117
ANMF SVD	1.432	1.128	1.123	0.902	0.735	0.825	0.772	0.499	0.426	0.310	0.268	0.234
RANMF SVD	1.431	1.127	1.151	0.857	0.714	0.437	0.771	0.500	0.423	0.325	0.247	0.171
RKANMF SVD	1.182	0.909	1.102	1.090	0.709	0.394	0.855	0.770	0.434	0.353	0.427	0.376

表3 各算法在WebKB数据集上的结果比较

Tab. 3 Result comparison of different algorithms on WebKB dataset

算法	Cornell			Texas			Washington			Wisconsin
	$\| V \| = 195, \| E \| = 304, r = 5$			$\| V \| = 187, \| E \| = 187, r = 5$			$\| V \| = 230, \| E \| = 446, r = 5$			$\| V \| = 265, \| E \| = 530, r = 5$
	Jaccard	NMI	AC	Jaccard	NMI	AC	Jaccard	NMI	AC	Jaccard	NMI	AC
ANMF Rnd	0.185	0.143	0.369	0.218	0.153	0.375	0.196	0.138	0.357	0.168	0.688	0.323
RANMF Rnd	0.287	0.169	0.459	0.332	0.164	0.518	0.287	0.169	0.477	0.240	0.078	0.459
RKANMF Rnd	0.291	0.189	0.479	0.340	0.166	0.527	0.290	0.164	0.484	0.245	0.079	0.468
DeepWalk	0.178	0.077	0.323	0.258	0.095	0.439	0.178	0.044	0.365	0.171	0.079	0.347
ANMF SVD	0.188	0.097	0.354	0.349	0.225	0.551	0.245	0.103	0.452	0.226	0.076	0.423
RANMF SVD	0.203	0.127	0.379	0.416	0.194	0.594	0.375	0.209	0.543	0.270	0.085	0.502
RKANMF SVD	0.267	0.190	0.462	0.428	0.210	0.615	0.382	0.222	0.604	0.282	0.101	0.536

表3 各算法在WebKB数据集上的结果比较

Tab. 3 Result comparison of different algorithms on WebKB dataset

算法	Cornell			Texas			Washington			Wisconsin
	$\| V \| = 195, \| E \| = 304, r = 5$			$\| V \| = 187, \| E \| = 187, r = 5$			$\| V \| = 230, \| E \| = 446, r = 5$			$\| V \| = 265, \| E \| = 530, r = 5$
	Jaccard	NMI	AC	Jaccard	NMI	AC	Jaccard	NMI	AC	Jaccard	NMI	AC
ANMF Rnd	0.185	0.143	0.369	0.218	0.153	0.375	0.196	0.138	0.357	0.168	0.688	0.323
RANMF Rnd	0.287	0.169	0.459	0.332	0.164	0.518	0.287	0.169	0.477	0.240	0.078	0.459
RKANMF Rnd	0.291	0.189	0.479	0.340	0.166	0.527	0.290	0.164	0.484	0.245	0.079	0.468
DeepWalk	0.178	0.077	0.323	0.258	0.095	0.439	0.178	0.044	0.365	0.171	0.079	0.347
ANMF SVD	0.188	0.097	0.354	0.349	0.225	0.551	0.245	0.103	0.452	0.226	0.076	0.423
RANMF SVD	0.203	0.127	0.379	0.416	0.194	0.594	0.375	0.209	0.543	0.270	0.085	0.502
RKANMF SVD	0.267	0.190	0.462	0.428	0.210	0.615	0.382	0.222	0.604	0.282	0.101	0.536

表4 各算法在LFR网络数据集上的结果比较

Tab. 4 Result comparison of different algorithms on LFR network dataset

算法	LFR1 $(μ = 0.1)$			LFR2 $(μ = 0.3)$			LFR3 $(μ = 0.5)$
算法	Jaccard	NMI	AC	Jaccard	NMI	AC	Jaccard	NMI	AC
ANMF Rnd	0.234	0.629	0.399	0.287	0.660	0.469	0.201	0.570	0.399
RANMF Rnd	0.176	0.570	0.344	0.253	0.620	0.436	0.182	0.540	0.369
RKANMF Rnd	0.163	0.576	0.320	0.272	0.647	0.456	0.159	0.530	0.353
DeepWalk	1.000	1.000	1.000	0.920	0.992	0.956	0.875	0.982	0.925
ANMF SVD	1.000	1.000	1.000	0.925	0.982	0.955	0.843	—	0.912
RANMF SVD	1.000	1.000	1.000	0.925	0.982	0.955	0.837	0.959	0.915
RKANMF SVD	1.000	1.000	1.000	0.926	0.983	0.957	0.877	0.978	0.930

表4 各算法在LFR网络数据集上的结果比较

Tab. 4 Result comparison of different algorithms on LFR network dataset

算法	LFR1 $(μ = 0.1)$			LFR2 $(μ = 0.3)$			LFR3 $(μ = 0.5)$
算法	Jaccard	NMI	AC	Jaccard	NMI	AC	Jaccard	NMI	AC
ANMF Rnd	0.234	0.629	0.399	0.287	0.660	0.469	0.201	0.570	0.399
RANMF Rnd	0.176	0.570	0.344	0.253	0.620	0.436	0.182	0.540	0.369
RKANMF Rnd	0.163	0.576	0.320	0.272	0.647	0.456	0.159	0.530	0.353
DeepWalk	1.000	1.000	1.000	0.920	0.992	0.956	0.875	0.982	0.925
ANMF SVD	1.000	1.000	1.000	0.925	0.982	0.955	0.843	—	0.912
RANMF SVD	1.000	1.000	1.000	0.925	0.982	0.955	0.837	0.959	0.915
RKANMF SVD	1.000	1.000	1.000	0.926	0.983	0.957	0.877	0.978	0.930

参考文献 28

1	NEWMAN M E J. The structure and function of complex networks［J］. SIAM Review， 2003， 45（2）： 167-256. 10.1137/s003614450342480
2	章永来，周耀鉴. 聚类算法综述［J］. 计算机应用， 2019， 39（7）： 1869-1882. 10.11772/j.issn.1001-9081.2019010174
	ZHANG Y L， ZHOU Y J. Review of clustering algorithms［J］. Journal of Computer Applications， 2019， 39（7）： 1869-1882. 10.11772/j.issn.1001-9081.2019010174
3	NEWMAN M E J， GIRVAN M. Finding and evaluating community structure in networks［J］. Physical Review. E， Statistical， Nonlinear， and Soft Matter Physics， 2004， 69（2）： No.026113. 10.1103/physreve.69.026113
4	BLONDEL V D， GUILLAUME J L， LAMBIOTTE R， et al. Fast unfolding of communities in large networks［J］. Journal of Statistical Mechanics： Theory and Experiment， 2008， 2008（10）： No.P10008. 10.1088/1742-5468/2008/10/p10008
5	蔡晓妍，戴冠中，杨黎斌. 谱聚类算法综述［J］. 计算机科学， 2008， 35（7）： 14-18. 10.3969/j.issn.1002-137X.2008.07.004
	CAI X Y， DAI G Z， YANG L B. Survey on spectral clustering algorithms［J］. Computer Science， 2008， 35（7）： 14-18. 10.3969/j.issn.1002-137X.2008.07.004
6	SATULURI V， PARTHASARATHY S. Symmetrizations for clustering directed graphs［C］// Proceedings of the 14th International Conference on Extending Database Technology. New York： ACM， 2011： 343-354. 10.1145/1951365.1951407
7	LUXBURG U VON. A tutorial on spectral clustering［J］. Statistics and Computing， 2007， 17（4）： 395-416. 10.1007/s11222-007-9033-z
8	NASCIMENTO M C V， DE CARVALHO A C P L F. Spectral methods for graph clustering — a survey［J］. European Journal of Operational Research， 2011， 211（2）： 221-231. 10.1016/j.ejor.2010.08.012
9	ZHOU D Y， HUANG J Y， SCHÖLKOPF B. Learning from labeled and unlabeled data on a directed graph［C］// Proceedings of the 22nd International Conference on Machine Learning. New York： ACM， 2005： 1036-1043. 10.1145/1102351.1102482
10	LEE D D， SEUNG H S. Learning the parts of objects by non-negative matrix factorization［J］. Nature， 1999， 401（6755）： 788-791. 10.1038/44565
11	WANG F， LI T， WANG X， et al. Community discovery using nonnegative matrix factorization［J］. Data Mining and Knowledge Discovery， 2011， 22（3）： 493-521. 10.1007/s10618-010-0181-y
12	TOSYALI A， KIM J， CHOI J， et al. Regularized asymmetric nonnegative matrix factorization for clustering in directed networks［J］. Pattern Recognition Letters， 2019， 125： 750-757. 10.1016/j.patrec.2019.07.005
13	PEROZZI B， AL-RFOU R， SKIENA S. DeepWalk： online learning of social representations［C］// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2014： 701-710. 10.1145/2623330.2623732
14	WANG Y X， ZHANG Y J. Nonnegative matrix factorization： a comprehensive review［J］. IEEE Transactions on Knowledge and Data Engineering， 2013， 25（6）： 1336-1353. 10.1109/tkde.2012.51
15	ZHAO X M， ZHANG S Q. Facial expression recognition using kernel locality preserving projections［M］// JIN D， LIN S. Advances in Electron Engineering， Communication and Management Vol.2， LNEE140. Berlin： Springer， 2012： 713-718.
16	ZAFEIRIOU S， PETROU M. Nonlinear non-negative component analysis algorithms［J］. IEEE Transactions on Image Processing， 2010， 19（4）： 1050-1066. 10.1109/tip.2009.2038816
17	BUCIU I， NIKOLAIDIS N， PITAS I. Nonnegative matrix factorization in polynomial feature space［J］. IEEE Transactions on Neural Networks， 2008， 19（6）： 1090-1100. 10.1109/tnn.2008.2000162
18	ZHU F， HONEINE P， KALLAS M. Kernel nonnegative matrix factorization without the pre-image problem［C］// Proceedings of the 2014 IEEE International Workshop on Machine Learning for Signal Processing. Piscataway： IEEE， 2014： 1-6. 10.1109/mlsp.2014.6958910
19	NEWMAN M E J. Networks： An Introduction［M］. Oxford： Oxford University Press， 2010： 172-175， 212-214.
20	XU W， LIU X， GONG Y H. Document clustering based on non-negative matrix factorization［C］// Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2003： 267-273. 10.1145/860435.860485
21	CHEN W S， LIU J M， PAN B B， et al. Face recognition using nonnegative matrix factorization with fractional power inner product kernel［J］. Neurocomputing， 2019， 348： 40-53. 10.1016/j.neucom.2018.06.083
22	LEE D D， SEUNG H S. Algorithms for non-negative matrix factorization［C］// Proceedings of the 13th International Conference on Neural Information Processing Systems. Cambridge： MIT Press， 2000： 534-541.
23	ROSVALL M， BERGSTROM C T. Maps of random walks on complex networks reveal community structure［J］. Proceedings of the National Academy of Sciences of the United States of America， 2018， 105（4）： 1118-1123. 10.1371/journal.pone.0018209
24	GHANI R， JONES R， McCALLUM A， et al. CMU World Wide Knowledge Base （Web->KB） project［DS/OL］. （2001-01）［2020-10-14］..
25	LANCICHINETTI A， FORTUNATO S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities［J］. Physical Review. E， Statistical， Nonlinear， and Soft Matter Physics， 2009， 80（1）： No.016118. 10.1103/physreve.80.016118
26	DAVIES D L， BOULDIN D W. A clusters separation measure［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1979， PAMI-1（2）： 224-227. 10.1109/tpami.1979.4766909
27	KEHAGIAS A， PITSOULIS L. Bad communities with high modularity［J］. The European Physical Journal B， 2013， 86（7）： No.330. 10.1140/epjb/e2013-40169-1
28	DANON L， DÍAZ-GUILERA A， DUCH J， et al. Comparing community structure identification［J］. Journal of Statistical Mechanics： Theory and Experiment， 2005， 2005（9）： No.P09008. 10.1088/1742-5468/2005/09/p09008

[1]	林筠超, 万源. 基于图结构优化的自适应多度量非监督特征选择方法[J]. 计算机应用, 2021, 41(5): 1282-1289.
[2]	贺杰安, 吴晓红, 何小海, 胡建蓉, 卿粼波. 结合图像增强和卷积神经网络的小麦不完善粒识别[J]. 计算机应用, 2021, 41(3): 911-916.
[3]	汪志远, 降爱莲, 奥斯曼·穆罕默德. 基于正则互表示的无监督特征选择方法[J]. 计算机应用, 2020, 40(7): 1896-1900.
[4]	谢琪, 徐旭, 程耕国, 陈和平. 基于新的森林优化算法的特征选择算法[J]. 计算机应用, 2020, 40(5): 1266-1271.
[5]	耿源谦, 吴传生, 刘文. 混合非凸非光滑正则化约束的模糊图像盲复原[J]. 计算机应用, 2020, 40(4): 1171-1176.
[6]	曾梦, 宁彬, 蔡之华, 谷琼. 使用深度对抗子空间聚类实现高光谱波段选择[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 381-385.
[7]	张斌, 罗晓清, 张战成. 基于TV-L¹结构纹理分解的图像融合质量评价算法[J]. 计算机应用, 2019, 39(9): 2701-2706.
[8]	任珍文, 吴明娜. 基于熵自加权联合正则化最近点的图像集分类算法[J]. 计算机应用, 2019, 39(9): 2547-2551.
[9]	程俊华, 曾国辉, 鲁敦科, 黄勃. 基于Dropout的改进卷积神经网络模型平均方法[J]. 计算机应用, 2019, 39(6): 1601-1606.
[10]	李登刚, 陈香香, 李华丽, 王忠美. 基于超像素的流形正则化稀疏约束NMF混合像元分解算法[J]. 计算机应用, 2019, 39(10): 3100-3106.
[11]	冯明皓, 张天伦, 王林辉, 陈荣, 连少静. 改进的弹性网模型在深度神经网络中的应用[J]. 计算机应用, 2019, 39(10): 2809-2814.
[12]	文凯, 朱传亮. 融合社交网络和兴趣的正则化矩阵分解推荐模型[J]. 计算机应用, 2018, 38(9): 2523-2528.
[13]	代刚, 张鸿. 基于语义相关性与拓扑关系的跨媒体检索算法[J]. 计算机应用, 2018, 38(9): 2529-2534.
[14]	向文, 张灵, 陈云华, 姬秋敏. 结合结构自相似性和卷积网络的单幅图像超分辨率[J]. 计算机应用, 2018, 38(3): 854-858.
[15]	孙圣姿, 万源, 曾成. 自适应嵌入的半监督多视角特征降维方法[J]. 计算机应用, 2018, 38(12): 3391-3398.

基于核非负矩阵分解的有向图聚类算法

Directed graph clustering algorithm based on kernel nonnegative matrix factorization

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 28

相关文章 15

编辑推荐

Metrics