Suzuki, Atsushi, Nitanda, Atsushi, Suzuki, Taiji, Wang, Jing, Tian, Feng and Yamanishi, Kenji (2023) Tight and fast generalization error bound of graph embedding in metric space. In: Proceedings of the 40th International Conference on Machine Learning. Volume 202: International Conference on Machine Learning, 23rd - 29th July 2023, Honolulu, Hawaii, USA. Proceedings of Machine Learning Research (PMLR) Press - Journal of Machine Learning Research (JMLR), Cambridge MA, USA, pp. 33268-33284. ISSN 1938-7228 (Print), 2640-3498 (Online)

Preview

PDF (Conference paper) 48650 WANG_Tight_And_Fast_Generalization_Error_Bound_Of_Graph_Embedding_In_Metric_Space_(OA)_2023.pdf - Published Version Available under License Creative Commons Attribution. Download (472kB) | Preview

Abstract

Recent studies have experimentally shown that we can achieve in non-Euclidean metric space effective and efficient graph embedding, which aims to obtain the vertices’ representations reflecting the graph’s structure in the metric space. Specifically, graph embedding in hyperbolic space has experimentally succeeded in embedding graphs with hierarchical-tree structure, e.g., data in natural languages, social networks, and knowledge bases. However, recent theoretical analyses have shown a much higher upper bound on non-Euclidean graph embedding’s generalization error than Euclidean one’s, where a high generalization error indicates that the incompleteness and noise in the data can significantly damage learning performance. It implies that the existing bound cannot guarantee the success of graph embedding in non-Euclidean metric space in a practical training data size, which can prevent non-Euclidean graph embedding’s application in real problems. This paper provides a novel upper bound of graph embedding’s generalization error by evaluating the local Rademacher complexity of the model as a function set of the distances of representation couples. Our bound clarifies that the performance of graph embedding in non-Euclidean metric space, including hyperbolic space, is better than the existing upper bounds suggest. Specifically, our new upper bound is polynomial in the metric space’s geometric radius R and can be O(1/S) at the fastest, where S is the training data size. Our bound is significantly tighter and faster than the existing one, which can be exponential in R and O(1/\sqrt_S) at the fastest. Specific calculations on example cases show that graph embedding in non-Euclidean metric space can outperform that in Euclidean space with much maller training data than the existing bound has suggested.

Item Type:	Conference Proceedings
Title of Proceedings:	Proceedings of the 40th International Conference on Machine Learning. Volume 202: International Conference on Machine Learning, 23rd - 29th July 2023, Honolulu, Hawaii, USA
Uncontrolled Keywords:	hyperbolic, representation learning, machine learning
Subjects:	Q Science > Q Science (General) Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Faculty / School / Research Centre / Research Group:	Faculty of Engineering & Science Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS)
Related URLs:	Publisher
Last Modified:	19 Nov 2024 16:22
URI:	http://gala.gre.ac.uk/id/eprint/48650

Actions (login required)

View Item

Downloads