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(\frac{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 to $R$ and $O(\frac{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 smaller training data
than the existing bound has suggested.

本文提出一种新的图嵌入一般化误差的上限，它作为距离表示的函数集的局部 Rademacher 复杂度的评估。我们的上限是几何半径 $R$ 的多项式，可以最快达到 $O (rac {1}{S})$，其中 $S$ 是训练数据大小。