Directed graph clustering algorithm based on kernel nonnegative matrix factorization

doi:10.11772/j.issn.1001-9081.2021061129

Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (12): 3447-3454.DOI: 10.11772/j.issn.1001-9081.2021061129

Special Issue: 第十八届中国机器学习会议(CCML 2021)

• The 18th China Conference on Machine Learning • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP135

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.

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

Figures/Tables 8

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

Fig. 1 Influence of parameter d on DB index

Fig. 2 Influence of parameter d on DQF index

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

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

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

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

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

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

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

References 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]	Shuaihua ZHANG, Shufen ZHANG, Mingchuan ZHOU, Chao XU, Xuebin CHEN. Malicious traffic detection model based on semi-supervised federated learning [J]. Journal of Computer Applications, 2024, 44(11): 3487-3494.
[2]	Jie WU, Xuezhong QIAN, Wei SONG. Personalized federated learning based on similarity clustering and regularization [J]. Journal of Computer Applications, 2024, 44(11): 3345-3353.
[3]	Mengjie LAN, Jianping CAI, Lan SUN. Self-regularization optimization methods for Non-IID data in federated learning [J]. Journal of Computer Applications, 2023, 43(7): 2073-2081.
[4]	Lin ZHOU, Yuzhi XIAO, Peng LIU, Youpeng QIN. Community mining algorithm based on multi-relationship of nodes and its application [J]. Journal of Computer Applications, 2023, 43(5): 1489-1496.
[5]	Wenbo LI, Bo LIU, Lingling TAO, Fen LUO, Hang ZHANG. Deep spectral clustering algorithm with L1 regularization [J]. Journal of Computer Applications, 2023, 43(12): 3662-3667.
[6]	Yang LI, Anbiao WU, Ye YUAN, Linlin ZHAO, Guoren WANG. Unsupervised attributed graph embedding model based on node similarity [J]. Journal of Computer Applications, 2022, 42(1): 1-8.
[7]	Yue YANG, Shitong WANG. Four-layer multiple kernel learning method based on random feature mapping [J]. Journal of Computer Applications, 2022, 42(1): 16-25.
[8]	Lili FAN, Guifu LU, Ganyi TANG, Dan YANG. Low-rank representation subspace clustering method based on Hessian regularization and non-negative constraint [J]. Journal of Computer Applications, 2022, 42(1): 115-122.
[9]	LIN Junchao, WAN Yuan. Self-adaptive multi-measure unsupervised feature selection method with structured graph optimization [J]. Journal of Computer Applications, 2021, 41(5): 1282-1289.
[10]	Qian LIU, Hongyuan WANG, Liang CAO, Boyan SUN, Yu XIAO, Ji ZHANG. Cloth-changing person re-identification based on joint loss capsule network [J]. Journal of Computer Applications, 2021, 41(12): 3596-3601.
[11]	Hua LI, Guifu LU, Qinru YU. Manifold regularized nonnegative matrix factorization based on clean data [J]. Journal of Computer Applications, 2021, 41(12): 3492-3498.
[12]	SHEN Marui, LI Jincheng, ZHANG Ya, ZOU Jian. Magnetic resonance image reconstruction algorithm via non-convex total variation regularization [J]. Journal of Computer Applications, 2020, 40(8): 2358-2364.
[13]	WANG Zhiyuan, JIANG Ailian, MUHAMMAD Osman. Unsupervised feature selection method based on regularized mutual representation [J]. Journal of Computer Applications, 2020, 40(7): 1896-1900.
[14]	XIE Qi, XU Xu, CHENG Gengguo, CHEN Heping. Feature selection algorithm based on new forest optimization algorithm [J]. Journal of Computer Applications, 2020, 40(5): 1266-1271.
[15]	GENG Yuanqian, WU Chuansheng, LIU Wen. Mixed non-convex and non-smooth regularization constraint based blind image restoration [J]. Journal of Computer Applications, 2020, 40(4): 1171-1176.

Directed graph clustering algorithm based on kernel nonnegative matrix factorization

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 28

Related Articles 15

Recommended Articles

Metrics