复杂网络的双曲空间表征学习方法
作者:
作者简介:

王强(1995-),男,博士生,主要研究领域为复杂网络,机器学习.
江昊(1976-),男,博士,教授,博士生导师,主要研究领域为复杂网络,数据挖掘,机器学习.
羿舒文(1992-),男,博士生,主要研究领域为复杂网络,人工智能.
杨林涛(1982-),男,博士,副教授,主要研究领域为复杂网络,人工智能.
奈何(1992-),男,博士生,主要研究领域为数据挖掘,机器学习.
聂琦(1992-),男,博士生,主要研究领域为复杂网络,数据挖掘与分析,出行行为复杂性.

通讯作者:

江昊,E-mail:jh@whu.edu.cn

基金项目:

国家自然科学基金(U19B2004);中山市高端科研机构创新专项(181129112748101);广东省“大专项+任务清单”项目(2019sdr002)


Hyperbolic Representation Learning for Complex Networks
Author:
Fund Project:

National Natural Science Foundation of China (U19B2004); Zhongshan City High-end Research Institution Innovation Project (181129112748101); Guangdong Province "Major Project and Task List" Project (2019sdr002)

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [88]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    复杂网络在现实场景中无处不在,高效的复杂网络分析技术具有广泛的应用价值,比如社区检测、链路预测等.然而,很多复杂网络分析方法在处理大规模网络时需要较高的时间、空间复杂度.网络表征学习是一种解决该问题的有效方法,该类方法将高维稀疏的网络信息转化为低维稠密的实值向量,可以作为机器学习算法的输入,便于后续应用的高效计算.传统的网络表征学习方法将实体对象嵌入到低维欧氏向量空间中,但复杂网络是一类具有近似树状层次结构、幂率度分布、强聚类特性的网络,该结构更适合用具有负曲率的双曲空间来描述.针对复杂网络的双曲空间表征学习方法进行系统性的介绍和总结.

    Abstract:

    Complex networks naturally exist in a wide diversity of real-world scenarios. Efficient complex network analysis technology has wide applications, such as community detection, link prediction, etc. However, most complex network analytics methods suffer high computation and space cost dealing with large-scale networks. Network representation learning is one of the most efficient methods to solve this problem. It converts high-dimensional sparse network information into low-dimensional dense real-valued vectors which can be easily exploited by machine learning algorithms. Simultaneously, it facilitates efficient computation for subsequent applications. The traditional network representation embeds the entity objects in the low dimensional Euclidean vector space, but recent work has shown that the appropriate isometric space for embedding complex networks with hierarchical or tree-like structures, power-law degree distributions and high clustering is the negatively curved hyperbolic space. This survey conducts a systematic introduction and review of the literature in hyperbolic representation learning for complex networks.

    参考文献
    [1] Cai HY, Zheng VW, Chang KCC. A comprehensive survey of graph embedding:Problems, techniques, and applications. IEEE Trans. on Knowledge and Data Engineering, 2018,30(9):1616-1637.[doi:10.1109/tkde.2018.2807452]
    [2] Cui P, Wang X, Pei J, Zhu W. A survey on network embedding. IEEE Trans. on Knowledge and Data Engineering, 2018,31(5):833-852.[doi:10.1109/tkde.2018.2849727]
    [3] Chen H, Perozzi B, Al-Rfou R, Skiena S. A tutorial on network embeddings. arXiv Preprint arXiv:1808.02590, 2018. https://arxiv.org/abs/1808.02590
    [4] Goyal P, Ferrara E. Graph embedding techniques, applications, and performance:A survey. Knowledge-based Systems, 2018,151:78-94.[doi:10.1016/j.knosys.2018.03.022]
    [5] Zhang D, Yin J, Zhu X, Zhang C. Network representation learning:A survey. IEEE Trans. on Big Data, 2018, 1.[doi:10.1109/tbdata.2018.2850013]
    [6] Hamilton WL, Rex Y, Jure L. Representation learning on graphs:Methods and applications. IEEE Data (Base) Engineering Bulletin, 2017,40:52-74. https://arxiv.org/abs/1709.05584
    [7] Kipf TN, Welling M. Semi-supervised classification with graph convolutional networks. arXiv Preprint arXiv:1609.02907, 2016. https://arxiv.org/abs/1609.02907
    [8] Chamberlain BP, Clough J, Deisenroth MP. Neural embeddings of graphs in hyperbolic space. arXiv Preprint arXiv:1705.10359, 2017. https://arxiv.org/abs/1705.10359
    [9] Tu CC, Yang C, Liu ZY, Sun MS. Network representation learning:An overview. SCIENTIA SINICA Informationis, 2017(8):32-48(in Chinese with English abstract).[doi:10.1360/N112017-00145]
    [10] Wen W, Huang JM, Cai RC, Hao ZF, Wang LJ. Graph embedding by incorporating prior knowledge on vertex information. Ruan Jian Xue Bao/Journal of Software, 2018,29(3):786-798(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5437.htm[doi:10.13328/j.cnki.jos.005437]
    [11] Qi JS, Liang X, Li ZY, Chen YF, Xu Y. Representation learning of large-scale complex information network:Concepts, methods and challenge. Chinese Journal of Computers, 2018,41(10):222-248(in Chinese with English abstract).[doi:10.11897/SP.J.1016.2018.02394]
    [12] Chen WZ, Zhang Y, Li XM. Network representation learning. Big Data Research, 2015,1(3):8-22(in Chinese with English abstract).[doi:10.11959/j.issn.2096-0271.2015025]
    [13] Hofmann T, Buhmann J. Multidimensional scaling and data clustering. In:Advances in Neural Information Processing Systems. 1995.459-466. https://papers.nips.cc/paper/1008-multidimensional-scaling-and-data-clustering.pdf
    [14] Balasubramanian M, Schwartz EL. The isomap algorithm and topological stability. Science, 2002,295(5552):7.[doi:10.1126/science.295.5552.9r]
    [15] Belkin M, Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering. In:Advances in Neural Information Processing Systems. 2002.585-591. https://papers.nips.cc/paper/1961-laplacian-eigenmaps-and-spectral-techniques-for-embedding-and-clustering.pdf
    [16] Shaw B, Jebara T. Structure preserving embedding. In:Proc. of the ACM Int'l Conf. on Machine Learning. 2009.937-944.[doi:10.1145/1553374.1553494]
    [17] Roweis ST, Saul LK. Nonlinear dimensionality reduction by locally linear embedding. Science, 2000,290(5500):2323-2326.[doi:10.1126/science.290.5500.2323]
    [18] Cao S, Lu W, Xu Q. Grarep:Learning graph representations with global structural information. In:Proc. of the ACM Int'l Conf. on Information and Knowledge Management. 2015.891-900.[doi:10.1145/2806416.2806512]
    [19] Perozzi B, Al-Rfou R, Skiena S. Deepwalk:Online learning of social representations. In:Proc. of the ACM Int'l Conf. on Knowledge Discovery and Data Mining. 2014.701-710.[doi:10.1145/2623330.2623732]
    [20] Grover A, Leskovec J. node2vec:Scalable feature learning for networks. In:Proc. of the ACM Int'l Conf. on Knowledge Discovery and Data Mining. 2016.855-864.[doi:10.1145/2939672.2939754]
    [21] Chen H, Perozzi B, Hu Y, Skiena S. Harp:Hierarchical representation learning for networks. In:Proc. of the 32nd AAAI Conf. on Artificial Intelligence. 2018.2127-2134. https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16273
    [22] Perozzi B, Kulkarni V, Chen H, Skiena S. Don't walk, skip! Online learning of multi-scale network embeddings. In:Proc. of the ACM Int'l Conf. on Advances in Social Networks Analysis and Mining. 2017.258-265.[doi:10.1145/3110025.3110086]
    [23] Dong Y, Chawla NV, Swami A. metapath2vec:Scalable representation learning for heterogeneous networks. In:Proc. of the ACM Int'l Conf. on Knowledge Discovery and Data Mining. 2017.135-144.[doi:10.1145/3097983.3098036]
    [24] Wang D, Cui P, Zhu W. Structural deep network embedding. In:Proc. of the ACM Int'l Conf. on Knowledge Discovery and Data Mining. 2016.1225-1234.[doi:10.1145/2939672.2939753]
    [25] Cao S, Lu W, Xu Q. Deep neural networks for learning graph representations. In:Proc. of the 30th AAAI Conf. on Artificial Intelligence. 2016. https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12423
    [26] Tian F, Gao B, Cui Q, Chen E, Liu TY. Learning deep representations for graph clustering. In:Proc. of the 28th AAAI Conf. on Artificial Intelligence. 2014. https://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8527
    [27] Bruna J, Zaremba W, Szlam A, LeCun Y. Spectral networks and locally connected networks on graphs. In:Proc. of the Int'l Conf. on Learning Representations. 2014. https://arxiv.org/abs/1312.6203
    [28] Scarselli F, Gori M, Tsoi AC, Monfardini G. The graph neural network model. IEEE Trans. on Neural Networks, 2008,20(1):61-80.[doi:10.1109/tnn.2008.2005605]
    [29] Ganea O, Bécigneul G, Hofmann T. Hyperbolic neural networks. In:Advances in Neural Information Processing Systems. 2018.5345-5355. http://papers.nips.cc/paper/7780-hyperbolic-neural-networks
    [30] Krioukov D, Papadopoulos F, Vahdat A, Boguñá M. Curvature and temperature of complex networks. Physical Review E, 2009, 80(3):035101.[doi:10.1103/physreve.80.035101]
    [31] Krioukov D, Papadopoulos F, Kitsak M, Vahdat A. Hyperbolic geometry of complex networks. Physical Review E, 2010,82(3):036106.[doi:10.1103/physreve.82.036106]
    [32] Papadopoulos F, Kitsak M, Serrano MÁ, Boguñá M. Popularity versus similarity in growing networks. Nature, 2012,489(7417):537.[doi:10.1038/nature11459]
    [33] Sarkar R. Low distortion Delaunay embedding of trees in hyperbolic plane. In:Proc. of the Int'l Symp. on Graph Drawing. Berlin, Heidelberg:Springer-Verlag, 2011.355-366.[doi:10.1007/978-3-642-25878-7_34]
    [34] De Sa C, Gu A, Ré C, Sala F. Representation tradeoffs for hyperbolic embeddings. Proc. of Machine Learning Research, 2018,80:4460. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6534139/
    [35] Erdös P, Rényi A. On random graphs I. Publicationes Mathematicae Debrecen, 1959,6:290-297.
    [36] Watts DJ, Strogatz SH. Collective dynamics of ‘small-world’ networks. Nature, 1998,393(6684):440-442.[doi:10.1038/30918]
    [37] Barabási AL, Albert R. Emergence of scaling in random networks. Science, 1999,286(5439):509-512.[doi:10.1126/science.286.5439.509]
    [38] Aldecoa R, Orsini C, Krioukov D. Hyperbolic graph generator. Computer Physics Communications, 2015,196:492-496.[doi:10.1016/j.cpc.2015.05.028]
    [39] García-Pérez G, Allard A, Serrano M, Boguñá M. Mercator:Uncovering faithful hyperbolic embeddings of complex networks. arXiv Preprint arXiv:1904.10814, 2019. https://arxiv.org/abs/1904.10814
    [40] Serrano MÁ, Krioukov D, Boguñá M. Self-similarity of complex networks and hidden metric spaces. Physical Review Letters, 2008,100(7):078701.[doi:10.1103/physrevlett.100.078701]
    [41] Zuev K, Boguñá M, Bianconi G, Krioukov D. Emergence of soft communities from geometric preferential attachment. Scientific Reports, 2015,5:9421.[doi:10.1038/srep09421]
    [42] Muscoloni A, Cannistraci CV. A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities. New Journal of Physics, 2018,20(5):052002.[doi:10.1088/1367-2630/aac06f]
    [43] Papadopoulos F, Psomas C, Krioukov D. Network mapping by replaying hyperbolic growth. IEEE/ACM Trans. on Networking, 2015,23(1):198-211.[doi:10.1109/tnet.2013.2294052]
    [44] Papadopoulos F, Aldecoa R, Krioukov D. Network geometry inference using common neighbors. Physical Review E, 2015,92(2):022807.[doi:10.1103/physreve.92.022807]
    [45] Bläsius T, Friedrich T, Krohmer A, Laue S. Efficient embedding of scale-free graphs in the hyperbolic plane. IEEE/ACM Trans. on Networking, 2018,26(2):920-933.[doi:10.1109/tnet.2018.2810186]
    [46] Alanis-Lobato G, Mier P, Andrade-Navarro MA. Efficient embedding of complex networks to hyperbolic space via their Laplacian. Scientific Reports, 2016,6:30108.[doi:10.1038/srep30108]
    [47] Muscoloni A, Thomas JM, Ciucci S, Bianconi G. Machine learning meets complex networks via coalescent embedding in the hyperbolic space. Nature Communications, 2017,8(1):1615.[doi:10.1038/s41467-017-01825-5]
    [48] Alanis-Lobato G, Mier P, Andrade-Navarro MA. Manifold learning and maximum likelihood estimation for hyperbolic network embedding. Applied Network Science, 2016,1(1):10.[doi:10.1007/s41109-016-0013-0]
    [49] Hébert-Dufresne L, Grochow JA, Allard A. Multi-scale structure and topological anomaly detection via a new network statistic:The onion decomposition. Scientific Reports, 2016,6:31708.[doi:10.1038/srep31708]
    [50] Wang Z, Wu Y, Li Q, Jin F, Xiong W. Link prediction based on hyperbolic mapping with community structure for complex networks. Physica A:Statistical Mechanics and Its Applications, 2016,450:609-623.[doi:10.1016/j.physa.2016.01.010]
    [51] Wang Z, Li Q, Jin F, Xiong W, Wu Y. Hyperbolic mapping of complex networks based on community information. Physica A:Statistical Mechanics and Its Applications, 2016,455:104-119.[doi:10.1016/j.physa.2016.02.015]
    [52] Muscoloni A, Cannistraci CV. Minimum curvilinear automata with similarity attachment for network embedding and link prediction in the hyperbolic space. arXiv Preprint arXiv:1802.01183, 2018. https://arxiv.org/abs/1802.01183
    [53] Bronstein MM, Bruna J, LeCun Y, Szlam A, Vandergheynst P. Geometric deep learning:Going beyond euclidean data. IEEE Signal Processing Magazine, 2017,34(4):18-42.[doi:10.1109/MSP.2017.2693418]
    [54] Cvetkovski A, Crovella M. Hyperbolic embedding and routing for dynamic graphs. In:Proc. of the IEEE Conf. on Computer Communications. 2009.1647-1655.[doi:10.1109/infcom.2009.5062083]
    [55] Wilson RC, Hancock ER, Pekalska E, Duin RPW. Spherical and hyperbolic embeddings of data. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2014,36(11):2255-2269.[doi:10.1109/TPAMI.2014.2316836]
    [56] Nickel M, Kiela D. Poincaré embeddings for learning hierarchical representations. In:Advances in Neural Information Processing Systems. 2017.6338-6347. http://papers.nips.cc/paper/7213-poincare-embeddings-for-learning-hie
    [57] Nickel M, Kiela D. Learning continuous hierarchies in the Lorentz model of hyperbolic geometry. arXiv Preprint arXiv:1806.03417, 2018. https://arxiv.org/abs/1806.03417
    [58] Tay Y, Tuan LA, Hui SC. Hyperbolic representation learning for fast and efficient neural question answering. In:Proc. of the ACM Int'l Conf. on Web Search and Data Mining. 2018.583-591.[doi:10.1145/3159652.3159664]
    [59] Gulcehre C, Denil M, Malinowski M, Razavi A, Pascanu R, Hermann KM, Battaglia P, Bapst V, Raposo D, Santoro A, Freitas N. Hyperbolic attention networks. arXiv Preprint arXiv:1805.09786, 2018. https://arxiv.org/abs/1805.09786
    [60] Friedrich T, Krohmer A. Cliques in hyperbolic random graphs. In:Proc. of the IEEE Conf. on Computer Communications. 2015.1544-1552.[doi:10.1109/infocom.2015.7218533]
    [61] Dhingra B, Shallue CJ, Norouzi M, Dai AM, Dahl GE. Embedding text in hyperbolic spaces. arXiv Preprint arXiv:1806.04313, 2018. https://arxiv.org/abs/1806.04313
    [62] Boguñá M, Papadopoulos F, Krioukov D. Sustaining the internet with hyperbolic mapping. Nature Communications, 2010,1:62.[doi:10.1038/ncomms1063]
    [63] Serrano MÁ, Boguñá M, Sagués F. Uncovering the hidden geometry behind metabolic networks. Molecular BioSystems, 2012,8(3):843-850.[doi:10.1039/c2mb05306c]
    [64] García-Pérez G, Boguñá M, Allard A, Serrano MÁ. The hidden hyperbolic geometry of international trade:World trade atlas 1870-2013. Scientific Reports, 2016,6:33441.[doi:10.1038/srep33441]
    [65] Newman MEJ, Girvan M. Finding and evaluating community structure in networks. Physical Review E, 2004,69(2):026113.[doi:10.1103/physreve.69.026113]
    [66] Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D. Defining and identifying communities in networks. Proc. of the National Academy of Sciences of the United States of America, 2004,101(9):2658-2663.[doi:10.1073/pnas.0400054101]
    [67] Kleineberg KK, Boguñá M, Serrano MÁ, et al. Hidden geometric correlations in real multiplex networks. Nature Physics, 2016, 12(11):1076.[doi:10.1038/nphys3812]
    [68] García-Pérez G, Serrano MÁ, Boguñá M. Soft communities in similarity space. Journal of Statistical Physics, 2018,173(3-4):775-782.[doi:10.1007/s10955-018-2084-z]
    [69] Faqeeh A, Osat S, Radicchi F. Characterizing the analogy between hyperbolic embedding and community structure of complex networks. Physical Review Letters, 2018,121(9):098301.[doi:10.1103/physrevlett.121.098301]
    [70] Hajri H, Zaatiti H, Hebrail G. Learning graph-structured data using Poincaré embeddings and Riemannian K-means algorithms. arXiv Preprint arXiv:1907.01662, 2019. https://arxiv.org/abs/1907.01662
    [71] Krioukov D, Papadopoulos F, Boguñá M, Vahdat A. Efficient navigation in scale-free networks embedded in hyperbolic metric spaces. arXiv cond-mat.stat-mech/0805.1266, 2008. http://www.caida.org/publications/papers/2008/efficient_navigation_scale_free/
    [72] Ortiz E, Starnini M, Serrano MÁ. Navigability of temporal networks in hyperbolic space. Scientific Reports, 2017,7(1):15054.[doi:10.1038/s41598-017-15041-0]
    [73] Stai E, Karyotis V, Papavassiliou S. A hyperbolic space analytics framework for big network data and their applications. IEEE Network, 2016,30(1):11-17.[doi:10.1109/mnet.2016.7389825]
    [74] Karyotis V, Stai E, Papavassiliou S. Evolutionary Dynamics of Complex Communications Networks. CRC Press, 2013.[doi:10.1201/b15505]
    [75] Stai E, Sotiropoulos K, Karyotis V, Papavassiliou S. Hyperbolic traffic load centrality for large-scale complex communications networks. In:Proc. of the IEEE Int'l Conf. on Telecommunications. 2016.1-5.[doi:10.1109/ICT.2016.7500371]
    [76] Kitsak M, Voitalov I, Krioukov D. Link prediction with hyperbolic geometry. arXiv Preprint arXiv:1903.08810, 2019. https://arxiv. org/abs/1903.08810
    [77] Kleineberg KK, Buzna L, Papadopoulos F, Boguñá M, Serrano MÁ. Geometric correlations mitigate the extreme vulnerability of multiplex networks against targeted attacks. Physical Review Letters, 2017,118(21):218301.[doi:10.1103/physrevlett.118.218301]
    [78] Radicchi F, Ramasco JJ, Barrat A, Fortunato S. Complex networks renormalization:Flows and fixed points. Physical Review Letters, 2008,101(14):148701.[doi:10.1103/physrevlett.101.148701]
    [79] Song C, Havlin S, Makse HA. Self-similarity of complex networks. Nature, 2005,433(7024):392-395.[doi:10.1017/cbo9780511780356.007]
    [80] García-Pérez G, Boguñá M, Serrano MÁ. Multiscale unfolding of real networks by geometric renormalization. Nature Physics, 2018,14(6):583.[doi:10.1038/s41567-018-0072-5]
    [81] Cho H, DeMeo B, Peng J, Berger B. Large-margin classification in hyperbolic space. arXiv Preprint arXiv:1806.00437, 2018. https://arxiv.org/abs/1806.00437
    [82] Chami I, Ying Z, Ré C, Leskovec J. Hyperbolic graph convolutional neural networks. In:Advances in Neural Information Processing Systems. 2019.4869-4880. http://papers.nips.cc/paper/8733-hyperbolic-graph-convolutional-neural-networks
    [83] Koblenz network collection. http://konect.uni-koblenz.de/
    附中文参考文献:
    [9] 涂存超,杨成,刘知远,孙茂松.网络表示学习综述.中国科学:信息科学,2017(8):32-48.[doi:10.1360/N112017-00145]
    [10] 温雯,黄家明,蔡瑞初,郝志峰,王丽娟.一种融合节点先验信息的图表示学习方法.软件学报,2018,29(3):786-798. http://www.jos.org.cn/1000-9825/5437.htm[doi:10.13328/j.cnki.jos.005437]
    [11] 齐金山,梁循,李志宇,陈燕方,许媛.大规模复杂信息网络表示学习:概念、方法与挑战.计算机学报,2018,41(10):222-248.[doi:10.11897/SP.J.1016.2018.02394]
    [12] 陈维政,张岩,李晓明.网络表示学习.大数据,2015,1(3):8-22.[doi:10.11959/j.issn.2096-0271.2015025]
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

王强,江昊,羿舒文,杨林涛,奈何,聂琦.复杂网络的双曲空间表征学习方法.软件学报,2021,32(1):93-117

复制
分享
文章指标
  • 点击次数:4872
  • 下载次数: 10068
  • HTML阅读次数: 4883
  • 引用次数: 0
历史
  • 收稿日期:2019-09-09
  • 最后修改日期:2020-04-12
  • 在线发布日期: 2020-07-27
  • 出版日期: 2021-01-06
文章二维码
您是第19785967位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号