Hyperbolic Positive Definite Kernels Based on Möbius Gyrovector Space
YANG Meimei1,2, FANG Pengfei1,2, ZHU Shipeng1,2, XUE Hui1,2
1. School of Computer Science and Engineering, Southeast University, Nanjing 211189; 2. Key Laboratory of New Generation Artificial Intelligence Technology and Its Interdisciplinary Applications of Ministry of Education, Southeast University, Nanjing 211189
Abstract:Hierarchical data is widely present in various machine learning scenarios and the data can be encoded in hyperbolic spaces with very low distortion. Kernel methods are introduced to further enhance the representation capability of hyperbolic space. However, the existing hyperbolic kernels still have the drawbacks of low adaptive capacity or data distortion. To address these issues, hyperbolic positive definite kernels based on Möbius gyrovector space is proposed in this paper. By leveraging the relationship between the Möbius gyrovector space and the Poincaré model, a class of hyperbolic kernel functions, the Möbius radial basis kernels, are constructed. Specifically, the Möbius gyrodistance is employed in place of the Euclidean distance to construct the Möbius Gaussian kernel and the Möbius Laplacian kernel, with the positive definiteness of the kernel functions further demonstrated. Moreover, kernel functions are transformed from complex space to real space, and thus they are more suitable for most machine learning tasks. Experiments on several real-world social network datasets validate the effectiveness of the proposed method.
[1] 戴筠. 基于双曲空间图嵌入的科研热点预测.大数据, 2022, 8(6): 94-104. (DAI J.Emerging Scientific Topic Prediction Based on Poincare Graph Embedding. Big Data Research, 2022, 8(6): 94-104.) [2] 王强,江昊,羿舒文,等.复杂网络的双曲空间表征学习方法.软件学报, 2021, 32(1): 93-117. (WANG Q, JIANG H, YI S W, et al. Hyperbolic Representation Learning for Complex Networks. Journal of Software, 2021, 32(1): 93-117. [3] LINIAL N, LONDON E, RABINOVICH Y.The Geometry of Gra-phs and Some of Its Algorithmic Applications // Proc of the 35th Annual Symposium on Foundations of Computer Science. Washington, USA: IEEE, 1994: 577-591. [4] VINH TRAN L, TAY Y, ZHANG S, et al. HyperML: A Boosting Metric Learning Approach in Hyperbolic Space for Recommender Systems // Proc of the 13th International Conference on Web Search And Data Mining. New York, USA: ACM, 2020: 609-617. [5] BALAŽEVIĆ I, ALLEN C, HOSPEDALES T. Multi-relational Poin-caré Graph Embeddings // Proc of the 33rd International Conference on Neural Information Processing Systems. Cambridge, USA: MIT Press, 2019: 4463-4473. [6] GANEA O, BÉCIGNEUL G, HOFMANN T. Hyperbolic Entailment Cones for Learning Hierarchical Embeddings[C/OL].[2023-07-12]. https://arxiv.org/pdf/1804.01882.pdf. [7] PENG W, VARANKA T, MOSTAFA A, et al. Hyperbolic Deep Neu-ral Networks: A Survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021, 44(12): 10023-10044. [8] KHRULKOV V, MIRVAKHABOVA L, USTINOVA E, et al. Hyperbolic Image Embeddings // Proc of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. Washington, USA: IEEE, 2020: 6417-6427. [9] CHAMI I, YING Z, RÉ C, et al.Hyperbolic Graph Convolutional Neural Networks // Proc of the 33rd International Conference on Neural Information Processing Systems. Cambridge, USA: MIT Press, 2019: 4868-4879. [10] HSU J, GU J, WU G H, et al. Capturing Implicit Hierarchical Structure in 3D Biomedical Images with Self-Supervised Hyperbolic Representations[C/OL].[2023-07-12]. https://arxiv.org/pdf/2012.01644.pdf. [11] NICKEL M, KIELA D.Poincaré Embeddings for Learning Hierarchical Representations // Proc of the 31st International Conference on Neural Information Processing Systems. Cambridge, USA: MIT Press, 2017: 6341-6350. [12] NICKEL M, KIELA D.Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry[C/OL]. [2023-07-12].https://arxiv.org/pdf/1806.03417.pdf. [13] GANEA O, BÉCIGNEUL G, HOFMANN T. Hyperbolic Neural Networks[C/OL].[2023-07-12]. https://arxiv.org/pdf/1805.09112.pdf. [14] GULCEHRE C, DENIL M, MALINOWSKI M, et al. Hyperbolic Attention Networks[C/OL].[2023-07-12]. https://arxiv.org/pdf/1805.09786.pdf. [15] SHIMIZU R, MUKUTA Y, HARADA T.Hyperbolic Neural Networks++[C/OL]. [2023-07-12].https://arxiv.org/pdf/2006.08210.pdf. [16] LIU Q, NICKEL M, KIELA D.Hyperbolic Graph Neural Networks // Proc of the 33rd International Conference on Neural Information Processing Systems. Cambridge, USA: MIT Press, 2019: 8230-8241. [17] KIM J, SCOTT C D.L2 Kernel Classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(10): 1822-1831. [18] BORDELON B, CANATAR A, PEHLEVAN C.Spectrum Depen-dent Learning Curves in Kernel Regression and Wide Neural Networks // Proc of the 37th International Conference on Machine Learning. San Diego, USA: JMLR, 2020: 1024-1034. [19] KANG Z, WEN L J, CHEN W Y, et al. Low-Rank Kernel Lear-ning for Graph-Based Clustering. Knowledge-Based Systems, 2019, 163: 510-517. [20] OBER S W, RASMUSSEN C E, VAN DER WILK M. The Pro-mises and Pitfalls of Deep Kernel Learning[C/OL].[2023-07-12]. https://arxiv.org/pdf/2102.12108v1.pdf. [21] FANG P F, ZHOU J M, ROY S K, et al. Attention in Attention Networks for Person Retrieval. IEEE Transactions on Pattern Ana-lysis and Machine Intelligence, 2022, 44(9): 4626-4641. [22] CHO H, DEMEO B, PENG J, et al. Large-Margin Classification in Hyperbolic Space. Proceedings of Machine Learning Research, 2019, 89: 1832-1840. [23] FANG P F, HARANDI M, PETERSSON L.Kernel Methods in Hyperbolic Spaces // Proc of the IEEE/CVF International Confe-rence on Computer Vision. Washington, USA: IEEE, 2021: 10645-10654. [24] CANNON J W, FLOYD W J, KENYON R, et al. Hyperbolic Geometry. Flavors of Geometry, 1997, 31: 59-115. [25] UNGAR A A.From Pythagoras to Einstein: The Hyperbolic Pythagorean Theorem. Foundations of Physics, 1998, 28: 1283-1321. [26] UNGAR A A.Analytic Hyperbolic Geometry and Albert Einstein's Special Theory of Relativity. London, UK: World Scientific, 2008. [27] UNGAR A A.Extension of the Unit Disk Gyrogroup into the Unit Ball of Any Real Inner Product Space. Journal of Mathematical Analysis and Applications, 1996, 202: 1040-1057. [28] YANG M M, FANG P F, XUE H.Expanding the Hyperbolic Kernels: A Curvature-Aware Isometric Embedding View // Proc of the 32nd International Conference on Artificial Intelligence. San Francisco, USA: IJCAI, 2023: 4469-4477. [29] BISHOP C M, NASRABADI N M.Pattern Recognition and Machine Learning. Berlin, Germany: Springer, 2006. [30] BERG C, CHRISTENSEN J P R, RESSEL P.Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions. Berlin, Germany: Springer, 1984. [31] ARCOZZI N, ROCHBERG R, SAWYER E. The Diameter Space, A Restriction of the Drury-Arveson-Hardy Space[C/OL]. [2023-07-12].https://www.researchgate.net/publication/241115968_The_Diameter_Space_A_Restriction_of_the_Drury-Arveson-Hardy_Space. [32] ROZEMBERCZKI B, DAVIES R, SARKAR R, et al. GEMSEC: Graph Embedding with Self Clustering // Proc of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. Washington, USA: IEEE, 2019: 65-72. [33] ZHAO B, SEN P, GETOOR L. Entity and Relationship Labeling in Affiliation Networks[C/OL]. [2023-07-12]. http://www.cs.cmu.edu/~eairoldi/nets/icml_sna/paper7_final.pdf. [34] CUCERZAN S.Large-Scale Named Entity Disambiguation Based on Wikipedia Data // Proc of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. Stroudsburg, USA: ACL, 2007: 708-716. [35] SHCHUR O, MUMME M, BOJCHEVSKI A, et al. Pitfalls of Graph Neural Network Evaluation[C/OL].[2023-07-12]. https://arxiv.org/abs/1811.05868. [36] BOJCHEVSKI A, GÜNNEMANN S. Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking[C/OL].[2023-07-12]. https://arxiv.org/pdf/1707.03815.pdf. [37] MCAULEY J, TARGETT C, SHI Q F, et al. Image-Based Reco-mmendations on Styles and Substitutes // Proc of the 38th International ACM SIGIR Conference on Research and Development in In-formation Retrieval. New York, USA: ACM, 2015: 43-52. [38] MCCALLUM A K, NIGAM K, RENNIE J, et al. Automating the Construction of Internet Portals with Machine Learning. Information Retrieval, 2000, 3: 127-163. [39] PEROZZI B, AL-RFOU R, SKIENA S.DeepWalk: Online Lear-ning of Social Representations // Proc of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2014: 701-710. [40] 周志华.机器学习.北京:清华大学出版社, 2016. (ZHOU Z H. Machine Learning. Beijing,China: Tsinghua University Press, 2016.) [41] SHAWE-TAYLOR J, CRISTIANINI N.Kernel Methods for Pattern Analysis. Cambridge, UK: Cambridge University Press, 2004. [42] LOOSLI G, CANU S, ONG C S.Learning SVM in Kreǐn Spaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016, 38(6): 1204-1216.