图卷积网络增强的非负矩阵分解社区发现方法

doi:10.3778/j.issn.1002-8331.2110-0487

摘要/Abstract

摘要： 非负矩阵分解（nonnegative matrix factorization，NMF）因其有效性和易解释性强被广泛应用于社区发现领域。然而，现有大多数基于NMF的社区发现方法都是线性的，无法有效处理复杂网络的非线性特征，从而导致社区发现性能还有待进一步提高。针对该问题，提出了一种图卷积网络（graph convolutional network，GCN）增强的非线性NMF社区发现方法NMFGCN。NMFGCN包含两个主要模块：GCN和NMF，其中GCN用于学习网络节点表示，NMF将节点表示作为输入获得网络的社区表示。此外，提出一个联合优化方法以训练NMFGCN，不仅使得NMFGCN具有非线性特征表示能力，而且可以使得GCN和NMF相互促进并获得更好的社区划分结果。在人工合成网络和真实网络上进行大量实验，结果表明NMFGCN优于目前基于NMF的社区发现方法，从而证明NMFGCN确实可以提高NMF社区发现方法的性能。此外，NMFGCN还优于DeepWalk和LINE常用图表示学习方法。

关键词: 社区发现, 非负矩阵分解, 图卷积网络, 非线性方法

Abstract: Nonnegative matrix factorization（NMF） has been widely used in community detection due to its effectiveness and better interpretability. However, most existing NMF-based methods are linear, and consequently cannot effectively process the nonlinear characteristics of complex networks. As a result, the performance of community detection needs to be further improved. In view of this, NMFGCN is proposed, which is a nonlinear NMF-based method enhanced by graph convolutional network（GCN）. NMFGCN contains two main modules：GCN and NMF. GCN is applied to obtain the representation of nodes, where NMF takes the representation as input to generate community representation of a given network. In addition, a joint optimization method is proposed to train NMFGCN, which not only allows NMFGCN to possess nonlinear trait, but also enables its two modules to be optimized jointly. Extensive experiments are conducted on synthetic networks and real networks. The results show that NMFGCN is superior to state-of-the-art NMF-based methods, and thereby proves that NMFGCN indeed can boost the performances of NMF-based methods. Moreover, NMFGCN also outperforms some widely-used graph representation based methods, such as LINE and Deepwalk.

Key words: community detection, nonnegative matrix factorization, graph convolutional network, nonlinear method

郑裕龙, 陈启买, 贺超波, 刘海, 张晓雨. 图卷积网络增强的非负矩阵分解社区发现方法[J]. 计算机工程与应用, 2022, 58(11): 73-83.

ZHENG Yulong, CHEN Qimai, HE Chaobo, LIU Hai, ZHANG Xiaoyu. Nonnegative Matrix Factorization Community Detection Method Enhanced by Graph Convolutional Network[J]. Computer Engineering and Applications, 2022, 58(11): 73-83.

参考文献

[1] FORTUNATO S，HRIC D.Community detection in networks：a user guide[J].Physics Reports，2016，659：1-44.
[2] 龚卫华，沈松.基于社区发现的兴趣点推荐[J].计算机科学，2019，46（12）：63-68.
GONG W H，SHEN S.Community detection based point-of-interest recommendation[J].Computer Science，2019，46（12）：63-68.
[3] ANTONIO P R，CARLOS O G，FéLIX M A.Detecting，identifying and visualizing research groups in co-authorship networks[J].Scientometrics，2010，82：307-319.
[4] SIMON H，TENG S H.How good is recursive bisection[J].SIAM Journal on Scientic Computing，1997，18（5）：1436-1445.
[5] KERNIGAN B，LIN S.An efficient heuristic procedure for partitioning graphs[J].The Bell System Technical Journal，1970，29（2）：291-307.
[6] CHEN W F，FENG G C.Spectral clustering：a semi-supervised approach[J].Neurocomputing，2012，77（1）：229-242.
[7] NEWMAN M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Science，2006，103（23）：8577-8582.
[8] NEWMAN M E J.Equivalence between modularity optimization and maximum likelihood methods for community detection[J].Physical Review E，2016，94：052315.
[9] GARZA S E，SCHAEFFER S E.Community detection with the label propagation algorithm：a survey[J].Physica A：Statistical Mechanics and Its Applications，2019，534：122058.
[10] 张霄宏，史爱静，贾慧娟，等.一种优化的标签传播方法[J].小型微型计算机系统，2021，42（1）：137-141.
ZHANG X H，SHI A J，JIA H J，et al.Optimized label propagation solution[J].Journal of Chinese Computer Systems，2021，42（1）：137-141.
[11] LIU F Z，XUE S，WU J，et al.Deep learning for community detection：progress，challenges and opportunities[C]//Proceedings of 29th International Joint Conference on Artificial Intelligence，2020：4981-4987.
[12] HE C B，FEI X.CHENG Q W，et al.A survey of community detection in complex networks using nonnegative matrix factorization[J].IEEE Transactions on Computational Social Systems，2021，9（2）：440-457.
[13] ZHANG S H，WANG R S，ZHANG X S.Uncovering fuzzy community structure in complex networks[J].Physical Review E，2007，76：046103.
[14] KUANG D，DING C，PARK H.Symmetric nonnegative matrix factorization for graph clustering[C]//Proceedings of the 2012 SIAM International Conference on Data Mining（SDM），2012：106-117.
[15] MA X K，GAO L，YONG X R，et al.Semi-supervised clustering algorithm for community structure detection in complex networks[J].Physica A：Statistical Mechanics and Its Applications，2010，389（1）：187-197.
[16] WANG X，CUI P，WANG J，et al.Community preserving network embedding[C]//Proceedings of the 31st AAAI Conference on Artificial Intelligence，2017：203-209.
[17] 周飞燕，金林鹏，董军.卷积神经网络研究综述[J].计算机学报，2017，40（6）：1229-1251.
ZHOU F Y，JIN L P，DONG J.Review of convolutional neural network[J].Chinese Journal of Computers，2017，40（6）：1229-1251.
[18] WU Z H，PAN S，CHEN F W，et al.A comprehensive survey on graph neural networks[J].IEEE Transactions on Neural Networks and Learning Systems，2021，32（1）：4-24.
[19] KIPF T N，WELLING M.Semi-supervised classification with graph convolutional networks[C]//Proceedings of the 5th International Conference on Learning Representations，2017：1-14.
[20] 徐冰冰，岑科延，黄俊杰，等.图卷积神经网络综述[J].计算机学报，2020，43（5）：755-780.
XU B B，CEN K Y，HUANG J J，et al.A survey on graph convolutional neural network[J].Chinese Journal of Computers，2020，43（5）：755-780.
[21] PERIZZI B，AL-ROU R，SKIENA S.DeepWalk：online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2014：701-710.
[22] TANG J，QU M，WANG M，et al.LINE：large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web，2015：1067-1077.
[23] LEE D D，SEUNG H S.Learning the parts of objects by non-negative matrix factorization[J].Nature，1999，401：788-791.
[24] DING C，HE X，SIMON H D.On the equivalence of nonnegative matrix factorization and spectral clustering[C]//Proceedings of the 5th SIAM International Conference on Data Mining，2005：606-610.
[25] 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.
[26] MA X K，DONG D，WANG Q.Community detection in multi-layer networks using joint nonnegative matrix factorization[J].IEEE Transactions on Knowledge and Data Engineering，2019，31（2）：273-286.
[27] HE C B，LIU H，TANG Y，et al.Similarity preserving overlapping community detection in signed networks[J].Future Generation Computer Systems，2021，116：275-290.
[28] 陈丽敏，张岩，杨柳.半监督元路径的异构信息网络社区发现算法[J].小型微型计算机系统，2020，41（6）：1152-1155.
CHEN L M，ZHANG Y，YANG L.Semi-supervised meta-path-based algorithm for community detection in heterogeneous information networks[J].Journal of Chinese Computer Systems，2020，41（6）：1152-1155.
[29] YE F H，CHEN C，ZHENG Z B.Deep autoencoder-like nonnegative matrix factorization for community detection[C]//Proceedings of 27th ACM International Conference on Information and Knowledge Management，2018：1393-1402.
[30] BRUNA J，ZAREMBA W，SZLAM A，et al.Spectral networks and locally connected networks on graphs[C]//Proceedings of 3rd International Conference on Learning Representations，2014.
[31] SHUMAN D I，NARANG S K，FROSSARD P，et al.The emerging field of signal processing on graphs：extending high-dimensional data analysis to networks and other irregular domains[J].IEEE Signal Process Magazine，2013，30（3）：83-98.
[32] LEVIE R，MONTI F，BRESSON X，et al.Cayleynets：graph convolutional neural networks with complex rational spectral filters[J].IEEE Transactions on Signal Processing，2017，67（1）：97-109.
[33] KIPF T N，WELLING M.Variational graph auto-encoders[C]//NIPS Workshop on Bayesian Deep Learning，2016：1-3.
[34] DING C，LI T，PENG W，et al.Orthogonal nonnegative matrix factorizations for clustering[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2006：126-135.
[35] YE F H，CHEN C，WEN Z Y，et al.Homophily preserving community detection[J].IEEE Transactions on Neural Networks and Learning Systems，2020，31（8）：2903-2915.
[36] SUN B J，SHEN H W，GAO J H，et al.A non-negative symmetric encoder-decoder approach for community detection[C]//Proceedings of the 26th ACM Conference on Information and Knowledge Management，2017：597-606.
[37] LANCICHINETTI A，FORTUNATO S，RADICCHI F.Benchmark graphs for testing community detection algorithms[J].Physical Review E，2007，78（2）：046110.
[38] SEN P，NAMATA G，BILGIC M，et al.Collective classification in network data[J].AI Magazine，2018，29（3）：93.
[39] CHAKRABORTY T，DALMIA A，MUKHERJEE A.Metrics for community analysis：a survey[J].ACM Computing Surveys，2017，50（4）：54.
[40] MAATEN L V D，HINTON G.Visualizing data using t-SNE[J].Journal of Machine Learning Research，2008，9：2579-2605.
[41] HAMILTON W，YING Z，LESKOVEC J.Inductive representation learning on large graphs[C]//Proceedings of 21st Conference on Neural Information Processing Systems，2017：1024-1034.