Hyperbolic node embedding for temporal networks. (English) Zbl 1483.68263
Summary: Generating general-purpose vector representations of networks allows us to analyze them without the need for extensive feature-engineering. Recent works have shown that the hyperbolic space can naturally represent the structure of networks, and that embedding networks into hyperbolic space is extremely efficient, especially in low dimensions. However, the existing hyperbolic embedding methods apply to static networks and cannot capture the dynamic evolution of the nodes and edges of a temporal network. In this paper, we present an unsupervised framework that uses temporal random walks to obtain training samples with both temporal and structural information to learn hyperbolic embeddings from continuous-time dynamic networks. We also show how the framework extends to attributed and heterogeneous information networks. Through experiments on five publicly available real-world temporal datasets, we show the efficacy of our model in embedding temporal networks in low-dimensional hyperbolic space compared to several other unsupervised baselines. We show that our model obtains state-of-the-art performance in low dimensions, outperforming all baselines, and has competitive performance in higher dimensions, outperforming the baselines in three of the five datasets. Our results show that embedding temporal networks in hyperbolic space is extremely effective when necessitating low dimensions.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 51M09 | Elementary problems in hyperbolic and elliptic geometries |
| 68T05 | Learning and adaptive systems in artificial intelligence |
Keywords:
hyperbolic embedding; network embedding; graph embedding; representation learning; temporal networks; unsupervised learningReferences:
| [1] | Alanis-Lobato, G.; Mier, P.; Andrade-Navarro, MA, Efficient embedding of complex networks to hyperbolic space via their Laplacian, Sci Rep, 6, 30108 (2016) · doi:10.1038/srep30108 |
| [2] | Alanis-Lobato, G.; Mier, P.; Andrade-Navarro, MA, Manifold learning and maximum likelihood estimation for hyperbolic network embedding, Appl Netw Sci, 1, 1, 10 (2016) · doi:10.1007/s41109-016-0013-0 |
| [3] | Atias, N.; Sharan, R., Comparative analysis of protein networks: hard problems, practical solutions, Commun ACM, 55, 5, 88-97 (2012) · doi:10.1145/2160718.2160738 |
| [4] | Cao S, Lu W, Xu Q (2015) Grarep: learning graph representations with global structural information. In: Proceedings of the 24th ACM international conference on information and knowledge management, pp 891-900 |
| [5] | Cao S, Lu W, Xu Q (2016) Deep neural networks for learning graph representations. In: Thirtieth AAAI conference on artificial intelligence |
| [6] | Chamberlain BP, Clough J, Deisenroth MP (2017) Neural embeddings of graphs in hyperbolic space. arXiv preprint arXiv:1705.10359 |
| [7] | Chami I, Ying Z, Ré C, Leskovec J (2019) Hyperbolic graph convolutional neural networks. In: Advances in neural information processing systems, pp 4869-4880 |
| [8] | Cho H, DeMeo B, Peng J, Berger B (2019) Large-margin classification in hyperbolic space. In: The 22nd international conference on artificial intelligence and statistics, pp 1832-1840 |
| [9] | De Sa, C.; Gu, A.; Ré, C.; Sala, F., Representation tradeoffs for hyperbolic embeddings, Proc Mach Learn Res, 80, 4460 (2018) |
| [10] | Ganea OE, Bécigneul G, Hofmann T (2018) Hyperbolic entailment cones for learning hierarchical embeddings. arXiv preprint arXiv:1804.01882 |
| [11] | Ghosh S, Viswanath B, Kooti F, Sharma NK, Korlam G, Benevenuto F, Ganguly N, Gummadi KP (2012) Understanding and combating link farming in the twitter social network. In: Proceedings of the 21st international conference on world wide web, pp 61-70 |
| [12] | Goyal P, Kamra N, He X, Liu Y (2018) DynGEM: Deep embedding method for dynamic graphs. arXiv preprint arXiv:1805.11273 |
| [13] | Grover A, Leskovec J (2016) node2vec: scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp 855-864 |
| [14] | Hawkes, AG, Spectra of some self-exciting and mutually exciting point processes, Biometrika, 58, 1, 83-90 (1971) · Zbl 0219.60029 · doi:10.1093/biomet/58.1.83 |
| [15] | Hummon, NP; Dereian, P., Connectivity in a citation network: the development of DNA theory, Soc Netw, 11, 1, 39-63 (1989) · doi:10.1016/0378-8733(89)90017-8 |
| [16] | Jin D, Heimann M, Rossi RA, Koutra D (2019) Node2bits: compact time-and attribute-aware node representations for user stitching. In: Joint European conference on machine learning and knowledge discovery in databases. Springer, pp 483-506 |
| [17] | Kipf TN, Welling M (2016) Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 |
| [18] | Knyazev B, Augusta C, Taylor GW (2019) Learning temporal attention in dynamic graphs with bilinear interactions. arXiv preprint arXiv:1909.10367 |
| [19] | Krioukov, D.; Papadopoulos, F.; Kitsak, M.; Vahdat, A.; Boguná, M., Hyperbolic geometry of complex networks, Phys Rev E, 82, 3, 036106 (2010) · doi:10.1103/PhysRevE.82.036106 |
| [20] | Li AQ, Ahmed A, Ravi S, Smola AJ (2014) Reducing the sampling complexity of topic models. In: Proceedings of the 20th ACM SIGKDD international conference on knowledge discovery and data mining, pp 891-900 |
| [21] | Li, T.; Zhang, J.; Philip, SY; Zhang, Y.; Yan, Y., Deep dynamic network embedding for link prediction, IEEE Access, 6, 29219-29230 (2018) · doi:10.1109/ACCESS.2018.2839770 |
| [22] | Li, Z.; Zhang, L.; Song, G., Sepne: bringing separability to network embedding, Proc AAAI Conf Artif Intell, 33, 4261-4268 (2019) |
| [23] | Liu Q, Nickel M, Kiela D (2019) Hyperbolic graph neural networks. In: Advances in neural information processing systems, pp 8228-8239 |
| [24] | Lorrain, F.; White, HC, Structural equivalence of individuals in social networks, J Math Sociol, 1, 1, 49-80 (1971) · doi:10.1080/0022250X.1971.9989788 |
| [25] | Lu Y, Wang X, Shi C, Yu PS, Ye Y (2019) Temporal network embedding with micro-and macro-dynamics. In: Proceedings of the 28th ACM international conference on information and knowledge management, pp 469-478 |
| [26] | McDonald D, He S (2019) HEAT: hyperbolic embedding of attributed networks. arXiv preprint arXiv:1903.03036 |
| [27] | Mikolov T, Sutskever I, Chen K, Corrado GS, Dean J (2013) Distributed representations of words and phrases and their compositionality. In: Advances in neural information processing systems, pp 3111-3119 |
| [28] | Muscoloni, A.; Thomas, JM; Ciucci, S.; Bianconi, G.; Cannistraci, CV, Machine learning meets complex networks via coalescent embedding in the hyperbolic space, Nat Commun, 8, 1, 1615 (2017) · doi:10.1038/s41467-017-01825-5 |
| [29] | Nguyen GH, Lee JB, Rossi RA, Ahmed NK, Koh E, Kim S (2018) Continuous-time dynamic network embeddings. In: Companion proceedings of the the web conference |
| [30] | Nickel M, Kiela D (2017) Poincaré embeddings for learning hierarchical representations. In: Advances in neural information processing systems, pp 6338-6347 |
| [31] | Ou M, Cui P, Pei J, Zhang Z, Zhu W (2016) Asymmetric transitivity preserving graph embedding. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp 1105-1114 |
| [32] | Pareja A, Domeniconi G, Chen J, Ma T, Suzumura T, Kanezashi H, Kaler T, Leisersen CE (2019) Evolvegcn: evolving graph convolutional networks for dynamic graphs. arXiv preprint arXiv:1902.10191 |
| [33] | Perozzi B, Al-Rfou R, Skiena S (2014) DeepWalk: online learning of social representations. In: Proceedings of the 20th ACM SIGKDD international conference on knowledge discovery and data mining, pp 701-710 |
| [34] | Rowe R, Creamer G, Hershkop S, Stolfo SJ (2007) Automated social hierarchy detection through email network analysis. In: Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on web mining and social network analysis, pp 109-117 |
| [35] | Sankar A, Wu Y, Gou L, Zhang W, Yang H (2020) DySAT: deep neural representation learning on dynamic graphs via self-attention networks. In: Proceedings of the 13th international conference on web search and data mining, pp 519-527 |
| [36] | Schönemann, PH, A generalized solution of the orthogonal procrustes problem, Psychometrika, 31, 1, 1-10 (1966) · Zbl 0147.19401 · doi:10.1007/BF02289451 |
| [37] | Singer U, Guy I, Radinsky K (2019) Node embedding over temporal graphs. In: Proceedings of the twenty-eighth international joint conference on artificial intelligence, IJCAI-19, pp 4605-4612 |
| [38] | Tang J, Qu M, Wang M, Zhang M, Yan J, Mei Q (2015) LINE: large-scale information network embedding. In: Proceedings of the 24th international conference on world wide web, pp 1067-1077 |
| [39] | Tong Z, Liang Y, Sun C, Li X, Rosenblum D, Lim A (2020a) Digraph inception convolutional networks. Advances in neural information processing systems |
| [40] | Tong Z, Liang Y, Sun C, Rosenblum DS, Lim A (2020b) Directed graph convolutional network. arXiv preprint arXiv:2004.13970 |
| [41] | Trivedi R, Farajtabar M, Biswal P, Zha H (2019) DyRep: learning representations over dynamic graphs. In: International conference on learning representations |
| [42] | Veličković P, Cucurull G, Casanova A, Romero A, Lio P, Bengio Y (2017) Graph attention networks. arXiv preprint arXiv:1710.10903 |
| [43] | Wang D, Cui P, Zhu W (2016) Structural deep network embedding. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pp 1225-1234 |
| [44] | Wang L, Lu Y, Huang C, Vosoughi S (2020) Embedding node structural role identity into hyperbolic space. In: Proceedings of the 29th ACM international conference on information and knowledge management, pp 2253-2256 |
| [45] | Wang L, Gao C, Huang C, Liu R, Ma W, Vosoughi S (2021) Embedding heterogeneous networks into hyperbolic space without meta-path. In: Proceedings of the AAAI conference on artificial intelligence |
| [46] | Wang S, Tang J, Aggarwal C, Chang Y, Liu H (2017) Signed network embedding in social media. In: Proceedings of the 2017 SIAM international conference on data mining |
| [47] | Wang, X.; Zhang, Y.; Shi, C., Hyperbolic heterogeneous information network embedding, Proc AAAI Conf Artif Intell, 33, 5337-5344 (2019) |
| [48] | Wilson B, Leimeister M (2018) Gradient descent in hyperbolic space. arXiv preprint arXiv:1805.08207 |
| [49] | Zhang J, Ackerman MS, Adamic L (2007) Expertise networks in online communities: structure and algorithms. In: Proceedings of the 16th international conference on world wide web, pp 221-230 |
| [50] | Zhang Y, Wang X, Jiang X, Shi C, Ye Y (2019) Hyperbolic graph attention network. arXiv preprint arXiv:1912.03046 |
| [51] | Zhou L, Yang Y, Ren X, Wu F, Zhuang Y (2018) Dynamic network embedding by modeling triadic closure process. In: Thirty-second AAAI conference on artificial intelligence |
| [52] | Zuo Y, Liu G, Lin H, Guo J, Hu X, Wu J (2018) Embedding temporal network via neighborhood formation. In: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery and data mining, pp 2857-2866 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
