Network representation learning algorithm incorporated with node profile attribute information

doi:10.11772/j.issn.1001-9081.2018081851

Abstract

Abstract: In order to enhance the network representation learning quality with node profile information, and focus on the problems of semantic information dispersion and incompleteness of node profile attribute information in social network, a network representation learning algorithm incorporated with node profile information was proposed, namely NPA-NRL. Firstly, attribute information were encoded by one-hot encoding, and a data augmentation method of random perturbation was introduced to overcome the incompleteness of node profile attribute information. Then, attribute coding and structure coding were combined as the input of deep neural network to realize mutual complementation of the two types of information. Finally, an attribute similarity measure function based on network homogeneity and a structural similarity measure function based on SkipGram model were designed to mine fused semantic information through joint training. The experimental results on three real network datasets including GPLUS, OKLAHOMA and UNC demonstrate that, compared with the classic DeepWalk, Text-Associated DeepWalk (TADW), User Profile Preserving Social Network Embedding (UPP-SNE) and Social Network Embedding (SNE) algorithms, the proposed NPA-NRL algorithm has a 2.75% improvement in average Area Under Curve of ROC (AUC) value on link prediction task, and a 7.10% improvement in average F1 value on node classification task.

Key words: node profile attribute information, information fusion, network representation learning, deep learning, complex network

摘要： 为融合节点描述信息提升网络表示学习质量，针对社会网络中节点描述属性信息存在的语义信息分散和不完备性问题，提出一种融合节点描述属性的网络表示（NPA-NRL）学习算法。首先，对属性信息进行独热编码，并引入随机扰动的数据集增强策略解决属性信息不完备问题；然后，将属性编码和结构编码拼接作为深度神经网络输入，实现两方面信息的相互补充制约；最后，设计了基于网络同质性的属性相似性度量函数和基于SkipGram模型的结构相似性度量函数，通过联合训练实现融合语义信息挖掘。在GPLUS、OKLAHOMA和UNC三个真实网络数据集上的实验结果表明，和经典的DeepWalk、TADW（Text-Associated DeepWalk）、UPP-SNE（User Profile Preserving Social Network Embedding）和SNE（Social Network Embedding）算法相比，NPA-NRL算法的链路预测AUC（Area Under Curve of ROC）值平均提升2.75%，节点分类F1值平均提升7.10%。

关键词: 节点描述属性信息, 信息融合, 网络表示学习, 深度学习, 复杂网络

CLC Number:

TP391.4

LIU Zhengming, MA Hong, LIU Shuxin, LI Haitao, CHANG Sheng. Network representation learning algorithm incorporated with node profile attribute information[J]. Journal of Computer Applications, 2019, 39(4): 1012-1020.

刘正铭, 马宏, 刘树新, 李海涛, 常圣. 融合节点描述属性信息的网络表示学习算法[J]. 计算机应用, 2019, 39(4): 1012-1020.

References

[1] 丁兆云, 贾焰, 周斌.微博数据挖掘研究综述[J]. 计算机研究与发展, 2014, 51(4):691-706. (DING Z Y, JIA Y, ZHOU B. Survey of data mining for microblogs[J]. Journal of Computer Research and Development, 2014, 51(4):691-706.)
[2] PEROZZI B, AL-RFOU R, SKIENA S. DeepWalk:online learning of social representations[C]//KDD 2014:Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2014:701-710.
[3] TANG J, QU M, WANG M, et al. LINE:large-scale information network embedding[C]//WWW 2015:Proceedings of the 24th International Conference on World Wide Web. Geneva, Switzerland:International World Wide Web Conferences Steering Committee, 2015:1067-1077.
[4] WANG D, CUI P, ZHU W. Structural deep network embedding[C]//KDD 2016:Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2016:1225-1234.
[5] 李志宇, 梁循, 周小平, 等. 一种大规模网络中基于节点结构特征映射的链接预测方法[J]. 计算机学报, 2016, 39(10):1947-1964. (LI Z Y, LIANG X, ZHOU X P, et al. A link prediction method for large-scale networks[J]. Chinese Journal of Computers, 2016, 39(10):1947-1964.)
[6] WANG Z, CHEN C, LI W. Predictive network representation learning for link prediction[C]//SIGIR 2017:Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York:ACM, 2017:969-972.
[7] YANG J, McAULEY J, LESKOVEC J. Community detection in networks with node attributes[C]//ICDM 2013:Proceedings of the 2013 IEEE 13th International Conference on Data Mining. Piscataway, NJ:IEEE, 2013:1151-1156.
[8] McPHERSON M, SMITH-LOVIN L, COOK J M. Birds of a feather:homophily in social networks[J]. Annual Review of Sociology, 2001, 27(1):415-444.
[9] AIELLO L M, BARRAT A, SCHIFANELLA R, et al. Friendship prediction and homophily in social media[J]. ACM Transactions on the Web, 2012, 6(2):1-33.
[10] TRAUD A L, MUCHA P J, PORTER M A. Social structure of Facebook networks[J]. Physica A:Statistical Mechanics and its Applications, 2012, 391(16):4165-4180.
[11] YANG C, LIU Z, ZHAO D, et al. Network representation learning with rich text information[C]//IJCAI 2015:Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Menlo Park, CA:AAAI Press, 2015:2111-2117.
[12] ZHANG D, YIN J, ZHU X, et al. Homophily, structure, and content augmented network representation learning[C]//ICDM 2016:Proceedings of the 16th IEEE International Conference on Data Mining Series. Piscataway, NJ:IEEE, 2016:609-618.
[13] LI H, WANG H, YANG Z, et al. Variation autoencoder based network representation learning for classification[C]//ACL 2017:Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA, USA:ACL, 2017:56-61.
[14] MIKOLOV T, SUTSKEVER I, CHEN K, et al. Distributed representations of words and phrases and their compositionality[C]//NIPS 2013:Proceedings of the Twenty-Seventh Conference on Neural Information Processing Systems. Cambridge, MA:MIT Press, 2013:3111-3119.
[15] ZHANG D, YIN J, ZHU X, et al. User profile preserving social network embedding[C]//IJCAI 2017:Proceedings of the 26th International Joint Conference on Artificial Intelligence. Menlo Park, CA:AAAI Press, 2017:3378-3384.
[16] RAHIMI A, RECHT B. Random features for large-scale kernel machines[C]//NIPS 2008:Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems. Cambridge, MA:MIT Press, 2008:1177-1184.
[17] 温雯, 黄家明, 蔡瑞初, 等. 一种融合节点先验信息的图表示学习方法[J]. 软件学报, 2018, 29(3):786-798. (WEN W, HUANG J M, CAI R C, et al. Graph embedding by incorporating prior knowledge on vertex information[J]. Journal of Software, 2018, 29(3):786-798.)
[18] YANG C, SUN M, LIU Z, et al. Fast network embedding enhancement via high order proximity approximation[C]//IJCAI 2017:Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. Menlo Park, CA:AAAI Press, 2017:19-25.
[19] HUANG X, LI J, HU X. Accelerated attributed network embedding[C]//SDM 2017:Proceedings of the 2017 SIAM International Conference on Data Mining. Philadelphia:SIAM, 2017:633-641.
[20] LeCUN Y, BENGIO Y, HINTON G. Deep learning[J]. Nature, 2015, 521(7553):436-444.
[21] CAO S, LU W, XU Q. Deep neural networks for learning graph representations[C]//AAAI 2016:Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. Menlo Park, CA:AAAI Press, 2016:1145-1152.
[22] LIAO L, HE X, ZHANG H, et al. Attributed social network embedding[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(12):2257-2270.
[23] HAMILTON W L, YING R, LESKOVEC J. Representation learning on graphs:methods and applications[EB/OL].[2018-05-10]. https://arxiv.org/pdf/1709.05584.
[24] SIETSMA J, DOW R J F. Creating artificial neural networks that generalize[J]. Neural Networks, 1991, 4(1):67-79.
[25] HORNIK K, STINCHCOMBE M, WHITE H. Multilayer feedforward networks are universal approximators[J]. Neural Networks, 1989, 2(5):359-366.
[26] GLOROT X, BENGIO Y. Understanding the difficulty of training deep feedforward neural networks[C]//AISTATS 2010:Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics. Cambridge, MA:MIT Press, 2010:249-256.
[27] KINGMA D P, BA J. Adam:a method for stochastic optimization[EB/OL].[2018-05-10]. https://arxiv.org/pdf/1412.6980.
[28] LESKOVEC J, MCAULEY J J. Learning to discover social circles in ego networks[C]//NIPS 2012:Proceedings of the Twenty-sixth Annual Conference on Neural Information Processing Systems. Cambridge, MA:MIT Press, 2012:539-547.
[29] 吕琳媛. 复杂网络链路预测[J]. 电子科技大学学报, 2010, 39(5):651-661. (LYU L Y. Link prediction on complex networks[J]. Journal of University of Electronic Science and Technology of China, 2010, 39(5):651-661.)
[30] FAN R E, CHANG K W, HSIEH C J, et al. LIBLINEAR:a library for large linear classification[J]. Journal of Machine Learning Research, 2008, 9:1871-1874.