Towards kernelizing the classifier for hyperbolic data

Abstract

Data hierarchy, as a hidden property of data structure, exists in a wide range of machine learning applications. A common practice to classify such hierarchical data is first to encode the data in the Euclidean space, and then train a Euclidean classifier. However, such a paradigm leads to a performance drop due to distortion of data embedding in the Euclidean space. To relieve this issue, hyperbolic geometry is investigated as an alternative space to encode the hierarchical data for its higher ability to capture the hierarchical structures. Those methods cannot explore the full potential of the hyperbolic geometry, in the sense that such methods define the hyperbolic operations in the tangent plane, causing the distortion of data embeddings. In this paper, we develop two novel kernel formulations in the hyperbolic space, with one being positive definite (PD) and another one being indefinite, to solve the classification tasks in hyperbolic space. The PD one is defined via mapping the hyperbolic data to the Drury-Arveson (DA) space, which is a special reproducing kernel Hilbert space (RKHS). To further increase the discrimination of the classifier, an indefinite kernel is further defined in the Kreĭn spaces. Specifically, we design a 2-layer nested indefinite kernel which first maps hyperbolic data into the DA spaces, followed by a mapping from the DA spaces to the Kreĭn spaces. Extensive experiments on real-world datasets demonstrate the superiority of the proposed kernels.

Graphical abstract

Keywords

data hierarchy / hyperbolic geometry / drury-arveson space / kreĭn space

References

[1] Gong J, Teng Z, Teng Q, Zhang H, Du L, Chen S, Bhuiyan Z A, Li J, Liu M, Ma H . Hierarchical graph transformer-based deep learning model for large-scale multi-label text classification. IEEE Access, 2020, 8: 30885–30896

[2] Wang Q, Mao Z, Wang B, Guo L . Knowledge graph embedding: a survey of approaches and applications. IEEE Transactions on Knowledge and Data Engineering, 2017, 29( 12): 2724–2743

[3] Du X, Xia Y. Natural images enhancement using structure extraction and retinex. In: Proceedings of the 20th International Conference on Advanced Concepts for Intelligent Vision Systems. 2020, 408−420

[4] Kim S, Song C, Jang J, Paik J . Edge-aware image filtering using a structure-guided CNN. IET Image Processing, 2020, 14( 3): 472–479

[5] Long J, Feng X, Zhu X, Zhang J, Gou G . Efficient superpixel-guided interactive image segmentation based on graph theory. Symmetry, 2018, 10( 5): 169

[6] Wang H, Zhang F, Zhang M, Leskovec J, Zhao M, Li W, Wang Z. Knowledge-aware graph neural networks with label smoothness regularization for recommender systems. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019, 968−977

[7] Ying R, He R, Chen K, Eksombatchai P, Hamilton W L, Leskovec J. Graph convolutional neural networks for web-scale recommender systems. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018, 974−983

[8] Lee S, Park S, Kahng M, Lee S G. PathRank: a novel node ranking measure on a heterogeneous graph for recommender systems. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management. 2012, 1637−1641

[9] Ma R, Fang P, Drummond T, Harandi M. Adaptive poincaré point to set distance for few-shot classification. In: Proceedings of the 36th AAAI Conference on Artificial Intelligence. 2022, 1926−1934

[10] Sun J, Xie Y, Zhang H, Faloutsos C. Less is more: compact matrix decomposition for large sparse graphs. In: Proceedings of the 7th SIAM International Conference on Data Mining. 2007, 366−377

[11] Perozzi B, Al-Rfou R, Skiena S. DeepWalk: online learning of social representations. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2014, 701−710

[12] Hajiramezanali E, Hasanzadeh A, Duffield N, Narayanan K, Zhou M, Qian X. Variational graph recurrent neural networks. In: Proceedings of the 33rd International Conference on Neural Information Processing Systems. 2019, 960

[13] Linial N, London E, Rabinovich Y . The geometry of graphs and some of its algorithmic applications. Combinatorica, 1995, 15( 2): 215–245

[14] Krioukov D, Papadopoulos F, Kitsak M, Vahdat A, Boguñá M . Hyperbolic geometry of complex networks. Physical Review E, 2010, 82( 3): 036106

[15] Nickel M, Kiela D. Poincaré embeddings for learning hierarchical representations. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. 2017, 6341−6350

[16] Alanis-Lobato G, Mier P, Andrade-Navarro M A . Efficient embedding of complex networks to hyperbolic space via their Laplacian. Scientific Reports, 2016, 6: 30108

[17] Chamberlain B P, Clough J, Deisenroth M P. Neural embeddings of graphs in hyperbolic space. 2017, arXiv preprint arXiv: 1705.10359

[18] Ganea O E, Bécigneul G, Hofmann T. Hyperbolic entailment cones for learning hierarchical embeddings. In: Proceedings of the 35th International Conference on Machine Learning. 2018, 1632−1641

[19] Nickel M, Kiela D. Learning continuous hierarchies in the Lorentz model of hyperbolic geometry. In: Proceedings of the 35th International Conference on Machine Learning. 2018, 3779−3788

[20] De Sa C, Gu A, Ré C, Sala F. Representation tradeoffs for hyperbolic embeddings. In: Proceedings of Machine Learning Research, 2018, 80: 4460−4469

[21] Suzuki R, Takahama R, Onoda S. Hyperbolic disk embeddings for directed acyclic graphs. In: Proceedings of International Conference on Machine Learning. 2019, 6066−6075

[22] Balažević I, Allen C, Hospedales T. Multi-relational Poincaré graph embeddings. In: Proceedings of the 33rd International Conference on Neural Information Processing Systems. 2019, 401

[23] Sonthalia R, Gilbert A C. Tree! I am no tree! I am a low dimensional hyperbolic embedding. In: Proceedings of the 34th International Conference on Neural Information Processing Systems. 2020, 72

[24] Weber M, Zaheer M, Rawat A S, Menon A, Kumar S. Robust large-margin learning in hyperbolic space. In: Proceedings of the 34th International Conference on Neural Information Processing Systems. 2020, 1499

[25] Cho H, DeMeo B, Peng J, Berger B. Large-margin classification in hyperbolic space. In: Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics. 2019, 1832−1840

[26] Fang P, Harandi M, Petersson L. Kernel methods in hyperbolic spaces. In: Proceedings of 2021 IEEE/CVF International Conference on Computer Vision (ICCV). 2021, 10665−10674

[27] Rochberg R . Complex hyperbolic geometry and Hilbert spaces with complete pick kernels. Journal of Functional Analysis, 2019, 276( 5): 1622–1679

[28] Cucerzan S. Large-scale named entity disambiguation based on Wikipedia data. In: Proceedings of 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL). 2007, 708−716

[29] Rozemberczki B, Davies R, Sarkar R, Sutton C. GEMSEC: graph embedding with self clustering. In: Proceedings of 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 2019, 65−72

[30] Zhao B, Sen P, Getoor L. Entity and relationship labeling in affiliation networks. In: Proceedings of ICML Workshop on Statistical Network Analysis. 2006

[31] Shchur O, Mumme M, Bojchevski A, Günnemann S. Pitfalls of graph neural network evaluation. 2018, arXiv preprint arXiv: 1811.05868

[32] Bojchevski A, Günnemann S. Deep Gaussian embedding of graphs: unsupervised inductive learning via ranking. In: Proceedings of the 6th International Conference on Learning Representations. 2018

[33] Parker J R. Notes on complex hyperbolic geometry. Preprint, 2003

[34] Ratcliffe J G. Foundations of Hyperbolic Manifolds. New York: Springer, 1994

[35] Goldman W M. Complex Hyperbolic Geometry. Oxford: Oxford University Press, 1999

[36] Kim J, Scott C D . L₂ kernel classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32( 10): 1822–1831

[37] Bordelon B, Canatar A, Pehlevan C. Spectrum dependent learning curves in kernel regression and wide neural networks. In: Proceedings of the 37th International Conference on Machine Learning. 2020, 96

[38] Kang Z, Wen L, Chen W, Xu Z . Low-rank kernel learning for graph-based clustering. Knowledge-Based Systems, 2019, 163: 510–517

[39] Ober S W, Rasmussen C E, van der Wilk M. The promises and pitfalls of deep kernel learning. In: Proceedings of the 37th Conference on Uncertainty in Artificial Intelligence. 2021, 1206−1216

[40] Fang P, Zhou J, Roy S K, Ji P, Petersson L, Harandi M . Attention in attention networks for person retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, 44( 9): 4626–4641

[41] Ong C S, Mary X, Canu S, Smola A J. Learning with non-positive kernels. In: Proceedings of the 21st International Conference on Machine Learning. 2004

[42] Ungar A A . The hyperbolic Pythagorean theorem in the Poincaré disc model of hyperbolic geometry. The American Mathematical Monthly, 1999, 106( 8): 759–763

[43] Shalit O, Shalit O. Operator theory and function theory in Drury–Arveson space and its quotients. In: Alpay D, ed. Operator Theory. Basel: Springer, 2014, 1−50

[44] Arcozzi N, Rochberg R, Sawyer E, Wick B D. Distance functions for reproducing kernel Hilbert spaces. Contemp., 2011, 547: 25−53

[45] Ungar A A . From Pythagoras to Einstein: the hyperbolic Pythagorean theorem. Foundations of Physics, 1998, 28( 8): 1283–1321

[46] Birman G S, Ungar A A . The hyperbolic derivative in the Poincaré ball model of hyperbolic geometry. Journal of Mathematical Analysis and Applications, 2001, 254( 1): 321–333

[47] Dray T. The Geometry of Special Relativity. Boca Raton: CRC Press, 2012

[48] 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

[49] Xu H M, Xue H, Chen X H, Wang Y Y. Solving indefinite kernel support vector machine with difference of convex functions programming. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence. 2017, 2782−2788

[50] Oglic D, Gärtner T. Learning in reproducing kernel Krein spaces. In: Proceedings of the International Conference on Machine Learning. 2018, 3856−3864

[51] McAuley J, Targett C, Shi Q, van den Hengel A. Image-based recommendations on styles and substitutes. In: Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2015, 43−52

[52] McCallum A K, Nigam K, Rennie J, Seymore K . Automating the construction of internet portals with machine learning. Information Retrieval, 2000, 3( 2): 127–163

[53] Deshmukh A A. Kernel approximation. Stats 608, 2015, 1–3

[54] Platt J . Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in Large Margin Classifiers, 1999, 10( 3): 61–74

[55] Schölkopf B, Smola A J. Learning with Kernels: support vector machines, regularization, optimization, and beyond. MIT Press, 2002

[56] Chang C C, Lin C J . LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2011, 2( 3): 27

RIGHTS & PERMISSIONS

Higher Education Press