动态网络表示学习研究进展

doi:10.3969/j.issn.0372-2112.2020.10.024

摘要/Abstract

摘要： 网络表示学习旨在将网络信息表示为低维稠密的实数向量，解决链接预测、异常检测、推荐系统等任务.近年来，网络表示学习研究取得重大进展，但研究多基于静态网络，而真实世界构成的网络是动态变化的，对动态网络分析的需求日益增加.本文总结了当前动态网络表示学习的方法与研究进展，首先提出网络表示学习的动机，阐述动态网络以及表示学习的发展历史与理论基础；接着，系统概述了大量动态网络嵌入方法，包括基于矩阵分解的动态图嵌入、基于随机游走的动态图嵌入、基于深度学习的动态图嵌入和基于重构概率的动态图嵌入，并分析与比较，给出动态网络表示学习的应用场景；最后，总结未来网络表示学习的研究方向.只有考虑网络的动态性，才能真实反映现实网络的演化，使网络表示学习更具价值.

关键词: 网络表示学习, 图嵌入, 深度学习, 图卷积网络

Abstract: Network representation learning aims to learn the low-dimensional dense real-valued vector of network information, which solves practical tasks such as link prediction, anomaly detection, and recommendation systems. Recently, network representation learning has made great progress. Most existing researches focus on static networks, while real network is dynamic all the time. This survey proposes state of the arts on representation learning of dynamic network. Firstly, it provides historical overview of representation learning in network, followed by the motivation and theoretical basis of dynamic network representation learning. Then comprehensive analysis of dynamic models is proposed, including matrix factorization, random-walk, deep learning, edge reconstruction based dynamic models, and gives the application scenarios of dynamic network embedding. Finally, research directions of representation learning in the future are summarized. Only when considering the temporal dynamics, structure and content can we truly reflect the evolution of the real network and make network representation learning more valuable.

Key words: network representation learning, graph embedding, deep learning, graph convolutional networks

中图分类号:

TP311

曹燕, 董一鸿, 邬少清, 等. 动态网络表示学习研究进展[J]. 电子学报, 2020, 48(10): 2047-2059.

CAO Yan, DONG Yi-hong, WU Shao-qing, et al. Dynamic Network Representation Learning:A Review[J]. Acta Electronica Sinica, 2020, 48(10): 2047-2059.

参考文献

[1] 中国互联网信息中心[EB/OL].http://www.cac.gov.cn/2019-02/28/c_1124175677.htm.201912.
[2] Wasserman S,Faust K.Social Network Analysis:Methods and Applications[M].Cambridge University Press,1994.
[3] 刘华玲,郑建国,孙辞海.基于贪心扰动的社交网络隐私保护研究[J].电子学报,2013,41(8):1586-1591. LIU Hua-ling,ZHENG Jian-guo,SUN Ci-hai.Privacy preserving in social networks based on greedy perturbation[J].Acta Electronica Sinica,2013,41(8):1586-1591.(in Chinese)
[4] Zhang Y,Zhang M,Liu Y,et al.Localized matrix factorization for recommendation based on matrix block diagonal forms[A].Proceedings of the 22nd International Conference on World Wide Web[C].USA:ACM,2013.1511-1520.
[5] Li T,Zhang J,Philip S Y,et al.Deep dynamic network embedding for link prediction[J].IEEE Access,2018,6:29219-29230.
[6] 任开旭,王玉龙,刘同存,等.融合多维语义表示的概率矩阵分解模型[J].电子学报,2019,47(9):1848-1854. REN Kai-xu,WANG Yu-long,LIU Tong-cun,et al.A probabilistic matrix factorization model based on multidimensional semantic representation learning[J].Acta Electronica Sinica,2019,47(9):1848-1854.(in Chinese)
[7] Watkins D S.Fundamentals of Matrix Computations[M].John Wiley & Sons,2004.
[8] Li Y,Tarlow D,Brockschmidt M,et al.Gated graph sequence neural networks[J].arXiv Preprint,2015,arXiv:1511.05493.
[9] Ahmed A,Shervashidze N,Narayanamurthy S,et al.Distributed large-scale natural graph factorization[A].Proceedings of the 22nd International Conference on World Wide Web[C].USA:ACM,2013.37-48.
[10] Bengio Y,Courville A,Vincent P.Representation learning:A review and new perspectives[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(8):1798-1828.
[11] 涂存超,杨成,刘知远,等.网络表示学习综述[J].中国科学:信息科学,2017,47(8):980-996. TU Cunchao,YANG Cheng,LIU Zhiyuan,et al.Network representation learning:an overview[J].Scientia Sinica Informationis,2017,47(8):980-996.(in Chinese)
[12] Hisano R.Semi-supervised graph embedding approach to dynamic link prediction[A].International Workshop on Complex Networks[C].USA:IEEE,2018.109-121.
[13] Nguyen G H,Lee J B,Rossi R A,et al.Continuous-time dynamic network embeddings[A].Companion Proceedings of the the Web Conference[C].France:DBLP,2018.969-976.
[14] Liu W,Li H,Xie B.Real-time graph partition and embedding of large network[A].2018 18th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing (CCGRID)[C].USA:IEEE,2018.432-441.
[15] Du L,Wang Y,Song G,et al.Dynamic network embedding:an extended approach for skip-gram based network embedding[A].Proceedings of the 27th International Joint Conference on Artificial Intelligence[C].Stockholm:IJCAI,2018.2086-2092.
[16] Zhu D,Cui P,Zhang Z,et al.High-order proximity preserved embedding for dynamic networks[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(11):2134-2144.
[17] Zhou L,Yang Y,Ren X,et al.Dynamic network embedding by modeling triadic closure process[A].Thirty-Second AAAI Conference on Artificial Intelligence[C].USA:AAAI,2018.571-578.
[18] Pham D-S,Venkatesh S,Lazarescu M,et al.Anomaly detection in large-scale data stream networks[J].Data Mining and Knowledge Discovery,2014,28(1):145-189.
[19] Yu W,Cheng W,Aggarwal C C,et al.Netwalk:A flexible deep embedding approach for anomaly detection in dynamic networks[A].Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining[C].USA:ACM,2018.2672-2681.
[20] Cao S,Lu W,Xu Q.Grarep:Learning graph representations with global structural information[A].Proceedings of the 24th ACM International on Conference on Information and Knowledge Management[C].USA:ACM,2015,891-900.
[21] Ou M,Cui P,Pei J,et al.Asymmetric transitivity preserving graph embedding[A].Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].USA:ACM,2016.1105-1114.
[22] Perozzi B,Al-Rfou R,Skiena S.Deepwalk:Online learning of social representations[A].Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].USA:ACM,2014.701-710.
[23] Mikolov T,Sutskever I,Chen K,et al.Distributed representations of words and phrases and their compositionality[A].Advances in Neural Information Processing Systems[C].Stockholm:NIPS,2013.3111-3119.
[24] Tang J,Qu M,Wang M,et al.Line:Large-scale information network embedding[A].Proceedings of the 24th International Conference on World Wide Web[C].Florence:DBLP,2015.1067-1077.
[25] Wang D,Cui P,Zhu W.Structural deep network embedding[A].Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].USA:ACM,2016.1225-1234.
[26] Yang C,Liu Z,Zhao D,et al.Network representation learning with rich text information[A].Twenty-Fourth International Joint Conference on Artificial Intelligence[C].San Francisco:IJCAI,2015.1412-1418.
[27] Yao W,Rolia J,Basu S,et al.A Context-Aware framework for patient Navigation and Engagement (CANE)[A].8th International Conference on Collaborative Computing:Networking,Applications and Worksharing (CollaborateCom)[C].USA:IEEE,2012.316-325.
[28] Tu C,Zhang W,Liu Z,et al.Max-margin deepwalk:Discriminative learning of network representation[A].Proceedings of the 25th International Joint Conference on Artificial Intelligence[C].IJCAI,2016.3889-3895.
[29] Watts D J,Strogatz S H.Collective dynamics of ‘small-world’ networks[J].Nature,1998,393(6684):440.
[30] Grover A,Leskovec J.Node2vec:Scalable feature learning for networks[A].Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].USA:ACM,2016.855-864.
[31] Nguyen G H,Lee J B,Rossi R A,et al.Dynamic network embeddings:From random walks to temporal random walks[A].2018 IEEE International Conference on Big Data (Big Data)[C].USA:IEEE,2018.1085-1092.
[32] Goyal P,Chhetri S R,Canedo A.dyngraph2vec:Capturing network dynamics using dynamic graph representation learning[J].Knowledge-Based Systems,2020,187:104816.
[33] Xiong Y,Zhang Y,Fu H,et al.DynGraphGAN:Dynamic graph embedding via generative adversarial networks[A].International Conference on Database Systems for Advanced Applications[C].Chiang Mai:DASFAA,2019.536-552.
[34] Zuo Y,Liu G,Lin H,et al.Embedding temporal network via neighborhood formation[A].Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining[C].USA:ACM,2018.2857-2866.
[35] Zhu L,Guo D,Yin J,et al.Scalable temporal latent space inference for link prediction in dynamic social networks[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(10):2765-2777.
[36] Aiello L M,Barrat A,Schifanella R,et al.Friendship prediction and homophily in social media[J].ACM Transactions on the Web (TWEB),2012,6(2):1-33.
[37] Ahmed N M,Chen L,Wang Y,et al.DeepEye:link prediction in dynamic networks based on non-negative matrix factorization[J].Big Data Mining and Analytics,2018,1(1):19-33.
[38] Katz L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43.
[39] Seyedi S A,Moradi P,Tab F A.A weakly-supervised factorization method with dynamic graph embedding[A].2017 Artificial Intelligence and Signal Processing Conference (AISP)[C].Bangkok:IEEE,2017.213-218.
[40] Trigeorgis G,Bousmalis K,Zafeiriou S,et al.A deep matrix factorization method for learning attribute representations[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2016,39(3):417-429.
[41] Li J,Dani H,Hu X,et al.Attributed network embedding for learning in a dynamic environment[A].Proceedings of the 2017 ACM on Conference on Information and Knowledge Management[C].USA:ACM,2017.387-396.
[42] Ito H,Komamizu T,Amagasa T,et al.Network-word embedding for dynamic text attributed networks[A].2018 IEEE 12th International Conference on Semantic Computing (ICSC)[C].USA:IEEE,2018.334-339.
[43] 李志宇,梁循,徐志明,等.DNPS:基于阻尼采样的大规模动态社会网络结构特征表示学习[J].计算机学报,2017,40(4):805-823. LI Zhi-Yu,LIANG Xun,XU Zhi-Ming,et al.DNPS:Damping based negative-positive sampling of large-scale dynamic social network embedding[J].Chinese Journal of Computers,2017,40(4):805-823.(in Chinese)
[44] Sajjad H P,Docherty A,Tyshetskiy Y.Efficient representation learning using random walks for dynamic graphs[J].arXiv Preprint,2019,arXiv:1901.01346.
[45] Pandhre S,Mittal H,Gupta M,et al.Stwalk:learning trajectory representations in temporal graphs[A].Proceedings of the ACM India Joint International Conference on Data Science and Management of Data[C].USA:ACM,2018.210-219.
[46] Singer U,Guy I,Radinsky K.Node embedding over temporal graphs[J].arXiv Preprint,2019,arXiv:1903.08889.
[47] 张号逵,李映,姜晔楠.深度学习在高光谱图像分类领域的研究现状与展望[J].自动化学报,2018,44(6):961-977. ZHANG Hao-Kui,LI Ying,JIANG Ye-Nan.Deep learning for hyperspectral imagery classification:The state of the art and prospects[J].Acta Automatica Sinica,2018,44(6):961-977.(in Chinese)
[48] Niepert M,Ahmed M,Kutzkov K.Learning convolutional neural networks for graphs[A].International Conference on Machine Learning[C].USA:ICML,2016.2014-2023.
[49] Ma J,Cui P,Zhu W.Depthlgp:Learning embeddings of out-of-sample nodes in dynamic networks[A].Thirty-Second AAAI Conference on Artificial Intelligence[C].AAAI,2018.370-377.
[50] Smola A J,Kondor R.Kernels and regularization on graphs[A].Learning Theory and Kernel Machines[C].Springer,2003.144-158.
[51] Goyal P,Kamra N,He X,et al.Dyngem:Deep embedding method for dynamic graphs[J].arXiv Preprint,2018,arXiv:1805.11273.
[52] Trivedi R,Farajtabar M,Biswal P,et al.Representation learning over dynamic graphs[J].arXiv Preprint,2018,arXiv:1803.04051.
[53] Cho K,Van Merriënboer B,Bahdanau D,et al.On the properties of neural machine translation:Encoder-decoder approaches[J].arXiv Preprint,2014,arXiv:1409.1259.
[54] Fadel S G,Torres R D S.Link prediction in dynamic graphs for recommendation[J].arXiv Preprint,2018,arXiv:1811.07174.
[55] Sankar A,Wu Y,Gou L,et al.Dynamic graph representation learning via self-attention networks[J].arXiv Preprint,2018,arXiv:1812.09430.
[56] Yang C,Liu M,Wang Z,et al.Graph clustering with dynamic embedding[J].arXiv Preprint,2017,arXiv:1712.08249.
[57] Kipf T N,Welling M.Semi-supervised classification with graph convolutional networks[J].arXiv Preprint,2016,arXiv:1609.02907.
[58] Malik O A,Ubaru S,Horesh L,et al.Tensor graph convolutional networks for prediction on dynamic graphs[J].arXiv Preprint,2019,arXiv:1910.07643.
[59] Zheng P,Yuan S,Wu X,et al.One-class adversarial nets for fraud detection[A].Proceedings of the AAAI Conference on Artificial Intelligence[C].AAAI,2019.1286-1293.
[60] Zheng L,Li Z,Li J,et al.Addgraph:anomaly detection in dynamic graph using attention-based temporal GCN[A].Proceedings of the 28th International Joint Conference on Artificial Intelligence[C].USA:ICJAI,2019.4419-4425.
[61] Lemonnier R,Scaman K,Kalogeratos A.Multivariate Hawkes processes for large-scale inference[A].Thirty-First AAAI Conference on Artificial Intelligence[C].AAAI,2017.2168-2174.
[62] Yu Z,Chen J,Quo K,et al.Overlapping community detection based on random walk and seeds extension[A].Proceedings of the 12th Chinese Conference on Computer Supported Cooperative Work and Social Computing[C].China:ICPS,2017.18-24.
[63] 胡小娟,刘磊,邱宁佳.基于主动学习和否定选择的垃圾邮件分类算法[J].电子学报,2017,46(1):203-209. HU Xiao-juan,LIU Lei,QIU Ning-jia.A novel spam categorization algorithm based on active learning method and negative selection algorithm[J].Acta Electronica Sinica,2018,46(1):203-209.(in Chinese)
[64] Tu C,Wang H,Zeng X,et al.Community-enhanced network representation learning for network analysis[J].arXiv Preprint,2016,arXiv:1611.06645.
[65] Tu C,Zhang Z,Liu Z,et al.TransNet:Translation-based network representation learning for social relation extraction[A].Proceedings of the 26th International Joint Conference on Artificial Intelligence[C].Melbourne:IJCAI,2017.2864-2870.
[66] Cao S,Lu W,Xu Q.Deep neural networks for learning graph representations[A].Thirtieth AAAI Conference on Artificial Intelligence[C].AAAI,2016.1145-1152.
[67] Fu T-Y,Lee W-C,Lei Z.Hin2vec:Explore meta-paths in heterogeneous information networks for representation learning[A].Proceedings of the 2017 ACM on Conference on Information and Knowledge Management[C].USA:ACM,2017.1797-1806.
[68] Shi C,Hu B,Zhao W X,et al.Heterogeneous information network embedding for recommendation[J].IEEE Transactions on Knowledge and Data Engineering,2018,31(2):357-370.
[69] Defferrard M,Bresson X,Vandergheynst P.Convolutional neural networks on graphs with fast localized spectral filtering[A].Advances in Neural Information Processing Systems[C].Bracelona:NIPS,2016.3844-3852.
[70] Bruna J,Zaremba W,Szlam A,et al.Spectral networks and locally connected networks on graphs[J].arXiv Preprint,2013,arXiv:1312.6203.
[71] Yang Z,Cohen W W,Salakhutdinov R.Revisiting semi-supervised learning with graph embeddings[J].arXiv Preprint,2016,arXiv:1603.08861.
[72] Xu K,Hu W,Leskovec J,et al.How powerful are graph neural networks[J].arXiv Preprint,2018,arXiv:1810.00826.
[73] Bonner S,Brennan J,Kureshi I,et al.Temporal graph offset reconstruction:Towards temporally robust graph representation learning[A].2018 IEEE International Conference on Big Data (Big Data)[C].USA:IEEE,2018.3737-3746.
[74] Dong Y,Chawla N V,Swami A.metapath2vec:Scalable representation learning for heterogeneous networks[A].Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].USA:ACM,2017.135-144.
[75] Deng D,Shahabi C,Demiryurek U,et al.Latent space model for road networks to predict time-varying traffic[A].Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].USA:ACM,2016.1525-1534.
[76] 国琳,左万利,彭涛.基于隶属度的社会化网络重叠社区发现及动态集群演化分析[J].电子学报,2016,44(3):587-594. GUO Lin,ZUO Wan-li,PENG Tao.Overlapping community detection and dynamic group evolution analysis based on the degree of membership in social network[J].Acta Electronica Sinica,2016,44(3):587-594.(in Chinese)