电子学报 ›› 2020, Vol. 48 ›› Issue (10): 2047-2059.DOI: 10.3969/j.issn.0372-2112.2020.10.024
曹燕, 董一鸿, 邬少清, 陈华辉, 钱江波, 潘善亮
收稿日期:
2019-07-01
修回日期:
2020-03-02
出版日期:
2020-10-25
通讯作者:
作者简介:
基金资助:
CAO Yan, DONG Yi-hong, WU Shao-qing, CHEN Hua-hui, QIAN Jiang-bo, PAN Shan-liang
Received:
2019-07-01
Revised:
2020-03-02
Online:
2020-10-25
Published:
2020-10-25
Corresponding author:
Supported by:
摘要: 网络表示学习旨在将网络信息表示为低维稠密的实数向量,解决链接预测、异常检测、推荐系统等任务.近年来,网络表示学习研究取得重大进展,但研究多基于静态网络,而真实世界构成的网络是动态变化的,对动态网络分析的需求日益增加.本文总结了当前动态网络表示学习的方法与研究进展,首先提出网络表示学习的动机,阐述动态网络以及表示学习的发展历史与理论基础;接着,系统概述了大量动态网络嵌入方法,包括基于矩阵分解的动态图嵌入、基于随机游走的动态图嵌入、基于深度学习的动态图嵌入和基于重构概率的动态图嵌入,并分析与比较,给出动态网络表示学习的应用场景;最后,总结未来网络表示学习的研究方向.只有考虑网络的动态性,才能真实反映现实网络的演化,使网络表示学习更具价值.
中图分类号:
曹燕, 董一鸿, 邬少清, 等. 动态网络表示学习研究进展[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) |
[1] | 李钦, 刘伟, 牛朝阳, 宝音图, 惠周勃. 低信噪比下基于分裂EfficientNet网络的雷达信号调制方式识别[J]. 电子学报, 2023, 51(3): 675-686. |
[2] | 范兵兵, 何庭建, 张聪炫, 陈震, 黎明. 联合遮挡约束与残差补偿的特征金字塔光流计算方法[J]. 电子学报, 2023, 51(3): 648-657. |
[3] | 许新征, 李杉. 基于特征膨胀卷积模块的轻量化技术研究[J]. 电子学报, 2023, 51(2): 355-364. |
[4] | 张聿远, 闫文君, 张立民. 基于多模态特征融合网络的空时分组码识别算法[J]. 电子学报, 2023, 51(2): 489-498. |
[5] | 吴翼腾, 刘伟, 于溆乔. 基于参数差异假设的图卷积网络对抗性攻击[J]. 电子学报, 2023, 51(2): 330-341. |
[6] | 李滔, 董秀成, 林宏伟. 基于深监督跨尺度注意力网络的深度图像超分辨率重建[J]. 电子学报, 2023, 51(1): 128-138. |
[7] | 郭晓轩, 冯其波, 冀振燕, 郑发家, 杨燕燕. 多线激光光条图像缺陷分割模型研究[J]. 电子学报, 2023, 51(1): 172-179. |
[8] | 贾童瑶, 卓力, 李嘉锋, 张菁. 基于深度学习的单幅图像去雾研究进展[J]. 电子学报, 2023, 51(1): 231-245. |
[9] | 何滢婕, 刘月峰, 边浩东, 郭威, 张小燕. 基于Informer的电池荷电状态估算及其稀疏优化方法[J]. 电子学报, 2023, 51(1): 50-56. |
[10] | 张永梅, 孙捷. 基于动静态特征双输入神经网络的咳嗽声诊断COVID-19算法[J]. 电子学报, 2023, 51(1): 202-212. |
[11] | 袁海英, 成君鹏, 曾智勇, 武延瑞. Mobile_BLNet:基于Big-Little Net的轻量级卷积神经网络优化设计[J]. 电子学报, 2023, 51(1): 180-191. |
[12] | 王神龙, 雍宇, 吴晨睿. 基于伪孪生神经网络的低纹理工业零件6D位姿估计[J]. 电子学报, 2023, 51(1): 192-201. |
[13] | 吴靖, 叶晓晶, 黄峰, 陈丽琼, 王志锋, 刘文犀. 基于深度学习的单帧图像超分辨率重建综述[J]. 电子学报, 2022, 50(9): 2265-2294. |
[14] | 李雪莹, 王田路, 梁鹏, 王翀. 基于系统模型的用户评论中非功能需求的自动分类[J]. 电子学报, 2022, 50(9): 2079-2089. |
[15] | 琚长瑞, 秦晓燕, 袁广林, 李豪, 朱虹. 尺度敏感损失与特征融合的快速小目标检测方法[J]. 电子学报, 2022, 50(9): 2119-2126. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||