Generalization Bounds for Graph Embedding Using Negative Sampling: Linear vs Hyperbolic
Authors: Atsushi Suzuki
Atsushi Nitanda
jing wang
Linchuan Xu
Kenji Yamanishi
Marc Cavazza
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph embedding
Poincare embedding
hyperbolic space
negative sampling
generalization error
statistical learning theory
Rademacher complexity

Abstract: Graph embedding, which represents real-world entities in a mathematical space, has enabled numerous applications such as analyzing natural languages, social networks, biochemical networks, and knowledge bases.
It has been experimentally shown that graph embedding in hyperbolic space can represent hierarchical tree-like data more effectively than embedding in linear space, owing to hyperbolic space's exponential growth property. 
However, since the theoretical comparison has been limited to ideal noiseless settings, the potential for the hyperbolic space's property to worsen the generalization error for practical data has not been analyzed.
In this paper, we provide a generalization error bound applicable for graph embedding both in linear and hyperbolic spaces under various negative sampling settings that appear in graph embedding. 
Our bound states that error is polynomial and exponential with respect to the embedding space's radius in linear and hyperbolic spaces, respectively, which implies that hyperbolic space's exponential growth property worsens the error.
Using our bound, we clarify the data size condition on which graph embedding in hyperbolic space can represent a tree better than in Euclidean space by discussing the bias-variance trade-off.
Our bound also shows that imbalanced data distribution, which often appears in graph embedding, can worsen the error.


Generalization Error Bounds for Graph Embedding Using Negative Sampling: Linear vs Hyperbolic
Atsushi Suzuki University of Greenwich London, United Kingdom atsushi suzuki rw@gmail........... com com
Atsushi Nitanda
Kyushu Institute of Technology
Fukuoka, Japan
nitanda@ai kyutech. ac.
Jing Wang"
Linchuan Xu
University of Greenwich London, United Kingdom
The Hong Kong Polytechnic University Hong Kong SAR, China
j jing. wangegreenwich ac uk
1 linch. nu@polyu.ede edu. hk
Kenji Yamanishi
Marc Cavazza
The University of Tokyo Tokyo, Japan
National Institute of Informatics
Tokyo, Japan
yamanishi@g. ecc uttkyo..oooo.cc..
marc. www.ccaaazaaammaaccoo
Abstract
Graph embedding. which represents real-world entities in mathematical space, has enabled numerous applications such as analyzing natural languages, social networks, biochemical networks, and knowledge bases. It has been experimentally shown that graph embedding in hyperbolic space can represent hierarchical tree-like data more effectively than embedding in linear space, owing to hyperbolic space's exponential growth property. However, since the thcoretical comparison has been limited to ideal noiseless settings, the potential for the hyperbolic space's property to worsen the generalization еттоr for practical data has not been analyzed. In this paper, we provide generalization error bound applicable for graph embedding both in linear and hyperbolic spaces under various negative sampling settings that appear in graph embedding. Our bound states that error is polynomial and exponential with respect the embedding space's ' radius in linear and hyperbolic spaces, respectively, which implies that hyperbolic space's exponential growth property worsens the error. Using our bound, clarify the data size condition on which graph embedding in hyperbolic space can represent tree better than Euclidean space by discussing the bias-variance trade-off. Our bound also shows that imbalanced data distribution, which often appears graph embedding, can worsen the error.
Introduction
Graphs are fundamental formulation of real-world entities and their relations, such words in natural languages, people in social network, and objects in knowledge bases. Here, the vertices and edges of graph correspond the entities and the relations among them, respectively. Based on the formulation, graph embedding has enabled numerous applications for those data, such as machine translation and sentiment analysis for natural language
and community detection and
"Corresponding author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

link prediction for social network data [ 6 7 8 91, pathway prediction of biochemical network
[TO] [T]. and link prediction and triplet classification for knowledge base [12 13
14
15
16
[7].
Graph embedding produces representations of a graph's 's vertices in a space equipped with function that defines the dissimilarity between two points. In this paper, we call a function that defines the dissimilarity dissimilarity function and a space equipped with a dissimilarity function a dissimilarity space. For example, we can consider the squared distance as a dissimilarity function. Graph embedding aims to obtain representations such that the dissimilarity function reflects the relations defined by the edges, Specifically, we expect that the dissimilarity function returns a small value for the representations of positive pair, pair of vertices connected by an edge, and a large value for negative pair, a pair not connected. Here, to reduce the computational cost, obtaining training data by the negative sampling strategy has been known to be effective M.. In this strategy, we sample positive pair for each iteration, followed by sampling negative pairs around the positive pair.
As dissimilarity space, many graph embedding methods have used linear space equipped with an inner product function T2
3 S 6 9. which we call linear graph embedding (LGE). However, linear space has limitations in representing data with hierarchical tree-like structure [18
19 20 21
These limitations are due to linear space's 's polynomial growth property, which means that the volume or surface of a ball in linear space grows polynomially with respect to its radius. This linear space's growth speed is significantly slower than embedding hierarchical data such as an r-ary tree (r 2 2) requires, which is exponential (2I). To overcome this limitation, graph embedding in hyperbolic 25 26 [2]. which we call hyperbolic graph embedding (HGE) in this paper. In contrast to linear space's polynomial growth property, hyperbolic space has the exponential growth property, that is, the volume of any hall in hyperbolic
space has recently attracted much attention [20 22 23
24
space grows exponentially with respect to its radius [18] 19 20 2T]. As a result, hyperbolic space is almost tree-like in that can be well approximated by a tree [28). and we can embed any tree in hyperbolic space with arbitrarily low distortion [29). Existing HGE papers have experimentally shown HGE's ability to effectively represent hierarchical tree-like data such as taxonomies and social networks. However, the theoretical guarantee of HGE's performance is limited to ideal noiseless settings [28 29 23), and the comparison between LGE and HGE's generalization performance in noisy settings has not been discussed, although HGE could have a much worse generalization error than LGE in compensation for hyperbolic space's 's exponential growth property and cause overfitting for real data, which are often noisy.
In this paper, we derive a generalization bound for graph embedding using the negative sampling strategy under noisy settings. To the best of our knowledge, this is the first work that derives a complete generalization error bound for both LGE and HGE. As discussed in (2I), since the generalization error of a learning model reflects the volume of its hypothesis space, we can conjecture that the generalization errors of LGE and HGE are polynomial and exponential with respect to the embedding space's 's radius, reflecting inner product space and hyperbolic space's polynomial and exponential growth property. Also, an imbalanced data distribution, which often appears in graph embedding reflecting the graph structure's 's imbalance, may worsen the error. In this paper, we formally prove that the above conjectures are true, as well as clarify the dependency of the error bound on the number of entities and the size of training data. Based on the derived generalization error bounds, we also clarify the data size condition on which HGE outperforms LGE in embedding a tree, by discussing the bias-variance trade-off.
To derive a generalization error bound in embedding problem, existing papers (30 21 deriving ordinal embedding's bounds have converted the problem into linear prediction problem to calculate its Rademacher complexity (31.
32 33 Also, for hyperbolic embedding, the decomposition of the Lorentz Gramian matrix [34 has been combined with the above technique (21). For graph embedding using negative sampling, however, we cannot straightforwardly apply these techniques, which have been effective for deriving ordinal embedding's 's generalization error bound. Since the data distribution depends on the graph structure and positive sampling affects the distribution of negative sampling the negative sampling structure, we cannot apply the Li.dd-uniform--e -iniffrrm-istiitutionnn based discussions in (30] 21) to graph embedding using the negative sampling strategy. Although a recent unpublished paper 35) has attempted to derive a generalization error bound only for LGE, which is incomplete in that the bound still has an unevaluated part and cannot be applied for noisy settings, this dependency between the distributions has been ignored. We solve this problem by decomposing the loss function into functions of each edge sampled by the negative sampling strategy. We achieved this decomposition by our novel multivariable version of the Ledoux- -aalagrad contraction lemma
2

---

36J. By our approach, we can upper-bound bound the Rademacher complexity of graph embedding loss function by the sum of the Rademacher complexities [3 32 33] of linear prediction models. which have been calculated in [30 21 As result, our generalization bound is valid for various negative sampling settings where the distribution of positive and negative edges are dependent.
Our contributions are threefold:
We have derived the generalization error bound for negative-samae sampling- baasedd graph embed- ding. Our theorem is applicable to various settings regarding the embedding space, data distribution and loss function, such as LGE and HGE, the dependency between the positive pairs and negative pairs' distribution, and sigmoid loss functions. Our upper bound shows that LGE and HGE cause polynomial and exponential error with respect the embedding space's s radius, respectively. Our bound also shows that imbalanced data distribution can worsen the error.
We have derived specific error bounds for practical negative sampling strategies.
We have derived an explicit training data size condition on which HGE can represent a tree better than LGE.
2 Preliminary
Notation In this paper, the symbol == is used to state that its left hand side is defined by its right hand side. We denote by Z. E,,, IR, IRzo the set of integers, the set of positive integers, the set of real numbers, and the set of non-negative real numbers, respectively. Suppose that D, V. E Z We denote by _D the set of D-dimensional real vectors. For a matrix A DDV we denote by [A],, the element in the d-row and the e-th column. For a vector æ E RD,, we denote by ||0||| the 2-norm of defined by ||ж||| V T and for matrix A RDV we denote by || A the operator | norm of A with respect to the 2-norm, defined by ||Al sup aV | By (an)a= we
denote sequence (a1, a2....,,ay. ).).
2.1 Graph Embedding
In this section, we first formulate the general embedding problem, before we specialize it into graph embedding. Consider an entity set V and the true fussimilarittfunnciinn function V x V + R defined on the entity set For i,j E V, we call 8* (i. the true dissimilarity between i and j. and a small 8 (i. value implies that entity i and are similar or closely related to each other, and large (i.j)) value implies converse. In this paper, we identify V with the integer set {1, 2, ..... ... 1V... Embedding zV of the entity set V in a space (Z, 82) equipped with 2 > RR. of 2 so that the representations are consistent to the true
aims to get representations 21, 22, dissimilarity function áz dissimilarity among the entities in that if 8 (i, j) is small, then 8(2;, 2ÿ) is also small, and vice versa. We call Z the embedding space. Specifically, we aim to satisfy
8 (i.i) S 0r + 82 2,) Oz.
as frequent possible with respect some distribution regarding (i, which discuss in the next subsection. Here, 0*, Oz E IRz are fixed thresholds regarding the true dissimilarity 8* and the dissimilarity 8z in the embedding space.
As a dissimilarity function of the embedding space Z, we mainly consider the square distance x Z + Rzo. and the negative inner product (2,, 2z) if Z is equipped with an inner product (,, Z
[Az(z;, 2; 2 if 2 is equipped with a distance function Az Z
Z R. In this paper, deal
with the following four dissimilarity spaces.
Definition 1. (Dissimilarity spaces)
(a) The D-dimensional Euclidean space (R., Ago) consists of the set of D-dimensional real vectors
and the distance function ARD R x RDD + Rzo defined by AR x') = || 2/112- The
dissimilarity function is given by pR (z, x') = Agn (2,(2)))))

---

(b) The D-dimensional hyperbolic space (L", ALD) consists of the D-dimensional hyperboloid D C DR and the distance function A defined by
L. far R+11
(ar, a/M
=
(1, x²) arcosh(- (ar, x.) xx):
(2)
where (M RDD x RD
R is the Minkowski inner prodct defined by
211 ... d'Dl = -2-200 + zaz' The dissimilarity function is given by (z, (2, = (z, (z,,'))²
(1Ro 21 ... zpl 13'0
M
(c) The D-dimensional sphere (SD, Ago) consists of the subset S C R D+1 and the distance function Ag defined by
SD = =
x ====1], (g, x') = arccos( [xx).
(3)
The dissimilarity function given by (2, z') = |Ago ( 21)²²
(d) The canonical D-dimensional inner product space (I", 61D) dissimilarity space consists of the set _1 RD of D-dimensional real vectors and the dissimilarity function dip 1 1 R defined by the negative canonical inner product 6yp (2, x') == -2 z'.
Our main focus this paper is R.D and L.,. although our bound is also applicable to S' and I.P
Remark 1. There are multiple models to represent the above spaces. For example, we can use the Poincaré ball model, upper half space model, Klein ball model to represent hyperbolic space, other than the hyperboloid model used in Definition [ While these isometric to each other, we used the models in Definition | because we can formulate the dissimilarity function as a simple function of linear combination of inner products = 2', and x' z'. or (xx x') which makes it easy to apply techniques in [30 21].
Graph Embedding Consider graph EV,E), where V is the vertex set and & V V is the edge set. Here, we only consider undirected graphs, and thus assume that if (i:j) E & then (j.i) E holds. Graph embedding for a graph (V, is special case of embedding problem defined above, where the vertices V are the entities, the true dissimilarity between two entities i, is given by the graph distance defined by
8 (i.j) = min {K] 3(v1, U2..... ,e.......k.)) VK (i. 01), (21, (0 (4)
and 6* Then, the objective defined by (1) is equivalent to
(i.j) E & <> 02(21, S 0z. We say that a pair (i is truly positive if (i,j) E E and truly negative otherwise.
(5)
In the following, denote by deg (i) the degree of E V, defined by deg (i) (51(1,)) E).
2.2 Data distribution
In this paper, we consider Srrative-sampling based training data and loss functions. Training data consist of M positive-negative pair sequences. The m-th positive-negative pair sequence 8m
(s si)) consists of K+ positive pairs st = (i,) (Vx V)K! and K negative pairs sm = (15,m (15, J2.m).......) ..... K .m mm-J-- .m
(it mk
k
mm
(V V) Here, for m 1,2, M, we expect that i and jitm are similar to each other, that is, 8* (itmm Ji.m. S 8* is valid for + 1.2..... K+ and conversely, tT.m and jī.m are dissimilar to each other, that is, 8" (k..
0 valid for A 1,2,..., although these rules do not always hold owing to noise or the sampling strategy aiming to save the computational cost. To derive a meaningful generalization error bound, an assumption on the distribution of the training data needed. We consider the following weak assumption.
Assumption 1. 81, ..,..., , SM are independently and identically distributed.

---

Remark 2. Assumption 1 does NOT imply the independence and identity of the distribution of pairs in ith and sm For example, the distribution of (f m m Jw. may depend on Jk.m-J..mm This weakness assumption allows to discuss practical negative sampling settings where negative pairs' distributions depend on positive pairs.
We give some training data distribution examples, which may be noisy. In the follow- ( and P ('k.m::.mm denote the probability of edge (sim= and ing, I
(iamn being generated as the k-th positive and negative pairs, respectively, and (1 (fw Jir.) denotes the probability of edge (J Jh.m) being generated as the k-th negative pair given (* (R Jk
being generated as the k'-th positive pair.
Example 1. (Data Distribution)
(a) (Simple positive-negative sampling) First, we consider the simplest case. Regarding the positive pair generation, suppose that all the pairs (i, in the edge & have the same probability of being generated as a positive pair, as a simple case. Also, suppose that all the pairs (i.j) not in the edge set have a possibly non-zero probability that is lower than that for the positive pairs, which means the existence of noise. Here, we assume that each pair not in the edge set have the same probability, that is, the following holds:
p+
if (
EE,
PP ( Fim)
rtpp
if i hmmm: if it k. 3b.m
& E and km. + Jk.m
where x+ E [0. 1] indicates the noise intensity. If pairs appear, and if = 1, then all edges appears in the same probability. Here, since Et.....it... (( J.m) 1, we have that p (1-rt) PRRV---T For negative pair sampling, consider the following simple distribution.
O, then only truly positive
p-
if (i..m
$ E and km.m + Jk
P
( (omm Ji.m
p
if k Jh.m
E
0
if km J8.m
where r- E [0, 1] indicates the noise intensity. Also, p given by p (1--))(((
(b) (Skipgram [ type negative sampling) some applications, it is not easy sample truly negative pairs effectively. In this case, more effective but inaccurate methods are often used. In the following, we explain a negative sampling strategy in [1]. representative on such methods. Let K+ 1, and consider the positive pair sampling strategy again (6). Based on this simple setting, we consider the negative sampling strategy [1]. Here, one vertex of a negative pair fr,m is always the same as that of the positive pair ii..: and the other entity of the negative pair is generated according to the distribution whose probability mass function proportional to a value T (Ji,..)). where |>00 + R2o is a function and U ()īī,)) is the frequency of the vertex Ji,m appearing in a positive pair. In summary, the conditional distribution is given by
IP| (1..m:Jmm) (it.
) (itmm-)t.m))
gm (U(T,)
if kmm i1m otherwise.
(8)
Here, since Enim. Ev p ( (it.mo (ittm
we have q Ej x (U.mm)))
If
P(( (imm) is given by (6). (JT,m) is given by U (ITm)) = (1-r+) deg (fi.m -rrt (1V -1)
the
(1-pt) el+r
following, we set (2) for simplicity. Then we have P (i Fr.m (it.m Ftm)) U (.T....
The above setting is an example of the negative pair's distribution depending the positive pair.
Note that the above setting does not guarantee that truly negative pairs appear negative pair more frequently than truly positive pairs.
5

---

We remark that this paper's discussion is not limited to the above examples, and Assumption 1 is the only assumption for our main theorem.
2.3 Loss function
To quantify the consistency of the true dissimilarities of entities defined by O and those of rep- resentations defined by óz, we consider loss function I RR Rzo- The loss on positive-negative pair sequence 8m given by 1(8th m. 5m), where
8 = [ii 8ig mim
8,
for = - + and dz,y is given by di,5 == 62(21, 2j) for i,j j E V. Here, we expect that / is increasing with respect to each element of 6 the dissimilarity between a positive pair, and decreasing with respect to each element of 8 the dissimilarity between a negative pair.
Assumption 2. The loss function is Lipschitz continuous for each variable.
We denote the Lipschitz constant of I with respect to 6.t and 6 by I and T respectively, Note that the assumption regarding the loss function's 's Lipschitz continuity is common to derive generalization bound using statistical learning theory (e.g., (33). The following examples show that the above framework is general enough to include the existing applications settings. In the following, IR an increasing function that converts the dissimilarity.
Example 2. (Loss functions)
(a) (Sigmoid- base loss) Define by
166
mm)
In (-[M 6,-- kt -i-
-10) -
Σ In ==
K
(1 t- -I- m00)
#+=1
(10)
where a is sigmoid shape function. For example, we can use the standard sigmoid function defined by (x)) T+exp( (m>) the hinge loss function Ohinge (z) max (0, x + 1} or the ramp loss
La if Oadd function Tramp min {1, Ohinge (x)]. is Lipsschti Then L = L
K+ and k- = 1,2,, K- and - = - Ln a Ohinge or = Oramps for + = 2, K
The above loss function (10) with the standard sigmoid function a corresponds to the negative- sampling-bass based loss function [T] (h(x)) x and 0) and the loss function in (20) for network embedding (h(x)= _ and 0 where are fixed constants defined in the paper).
(b) (Softmax-like loss) Let K+ = 1 and define / by
K 16tt. 5m) = -h (1 sitm + In Σ
exp -hs 6,-
(II)
k
Suppose that h is Li, LipLichchi Then L+ 4T-- = Ln, for k+ = 1,2,..., K+ and k- = 1...... K- The loss function (11) corresponds to the loss function for embedding taxonomy in 20 with h(x) Vir although this h gives non-LLipschiz-cooiimuuss loss function. In this paper, since non-smooth loss function often loses generalization guarantee, we only consider the case
where l and are Lipschitz continuous, in (33.
2.4
Generalization error
The core discussion of this paper is the generalization error, which is the difference between the empirical risk and expected risk. We define the empirical risk function R² (sm) (Z) + R20 on
training data s = (s) ) and the expected risk function R² (2)) - R>o as follows:
M 8m)) R² R² ((zn) Es... 1(5 8m)
Σ 1(8 RS (zx) = M m==1
(12)

---

Let B C Z be the space which we search for optimal representations 21. .2...., VI- As we discuss in the next section, B may be bounded set rather than the whole space 21v1, We define the empirical risk minimizer (2.) [i and expected risk minimizer (xg) [ by
(2.) argmin R2 ((zu) (z)) (=
argmin R² (L) (B
(13)
Our interest the excess risk given by R² (2.) alization error of embedding. We derive the upper bound of the excess risk in the next section.
R² (<=))=² which indicates the gener-
Remark 3. In the remainder of this paper, we compare the generalization error among multiple dissimilarity spaces. Since the loss itself depends on the embedding space's 's dissimilarity function 2, the comparison is not always completely fair. Nevertheless, the comparison can be meaningful. For
example, consider the 0-1 loss defined by 10 with (xx) (x) = [1 if x 2 0,
RRegaddeess
( if -.
of the choice of embedding space 2, the risk function on the 0-1 loss indicates the error rate of classifying a pair (i into "similar (8* (i. < 8")" or "dissimilar (i. > 8*)." Thus, it is fair to compare this 0-1-loss-based risk between different embedding spaces. Although the 0-1 loss itself since the hinge loss and ramp loss dominates the 0- 1 loss in that (0-1(x)) S (ramp(#) (1) S hinge (z)), deriving and comparing bounds for these loss indirectly enables comparison between the 0-1-loss-ber basssd risks of different embedding spaces. In this sense, comparing the risks of different embedding spaces based Lipschitz continuous loss is of interest.
does not satisfy Assumption 2
Generalization Bounds for Graph Embedding
3.1 Assumptions on Embedding Space's Radius
As also discussed in 21 for ordinal embedding, to derive a finite generalization bound, in general, is necessary to restrict parameters (in embedding cases, representations) to bounded domain (e.g., linear prediction models [37 38) neural networks (37 39).. In this section, we discuss our restriction on embedding space. For the derived generalization bound to practical, the restriction should be simple and geometrically intuitive. Following [2I]. we put the following simple restrictions
on embedding space's ' radius. Specifically, we discuss the case where we search for representations in B = BR defined by
Bn { (1)) Yo EV: Ag(20 2x) s R).
(14)
where 2p is [0
0] E R for Z = IR,I"" and ] 0 ...0 R for 2 Z= and
Apo is defined by (z, bound for empirical risk minimizer in R
2 z||2- In the next section, we provide the generalization error
3.2 Main Result: Finite Sample Upper Bounds for the Generalization Error
In this section, we first give our main theorem, which gives an upper bound for the generalization error, followed by remarks about intuitive interpretation of the bound and simplified versions.
Theorem 1. Let Z = RD, L",S" or I", and (2.) | and (zi), VI be empirical and expected risk minimizers defined by 13p. b. Under Assumptions and 2 probability 1 - d:
the following inequality holds with
R (B.))MM R² R²((2(( ((x))))))))
2wz (R)
Σ
Σ
12M2z In |V]
Rz In (1)
T((B) (15)
In oh
M
3
M
where wz defined by weo (R) Wip (R) = (2R)², who (R) = =oshi² R sinh R and
wgo (R) = arccos (1-00s 2R)
-ocos 20 211 2)) 161 = KBD = Knp = 2 and KRD = 2. and vt =
7

---

1B (f mm
E 50
E
for =1,2..... K and +,- -. Here, Eig is
2,
op.
defined by
2 dlag 2 off
(i = (1',
E vi
if j = or i' = j = j and (i.j) + (i',j"),
(16)
otherwise.
2. where d'iag 1. ouf
adiag
= 1/2 adiay
adiag
a = 2. and anf = oof
= g
=
off
10
= 0. 1(BB) is
the range of defined by
(BB max {1(8t.07 .8)) mm E (2, E =B] min (((8t.0% .0) 5m E (z, B}.
(17)
where S = (V x
V) D)*** x (V*V)**
Remark 4. wz RR) corresponds to the embedding space's volume. Similar to ordinal embedding that the larger the embedding space is, the larger the generalization eлror is. Since the volume of a ball is polynomial and exponential with respect to its radius in an inner product space and hyperbolic space, respectively, the generalization error also behaves correspondingly. V indicates the imbalance in the training data's distribution. Theorem suggests that an imbalanced distribution causes large generalization error. This is intuitive because training data's 's imbalance makes it difficult to understand the big picture of the data. We will explore this in Example 3 and Remark 8
cases in (2T). Theorem[Jargul
Remark 5. If 2 R_ or 11 multiplying a constant a to R and a² to Lipschitz constant Lt. imply the same relaxation of the condition, since these two are equivalent by scaling representations. Hence, the bound in Theorem [ for 2 = RR or Il includes term R Lg. which indicates the essential size of the embedding space. This discussion is not true of Z = D and SP, because balls with different sizes are not similar to each other in these spaces.
Remark 6. Owing to Assumption I S (2R)² 2 Σ.=t.- EK= L always holds.
Remark 7. For any distribution on 8, by Jensen's inequality, we have that 1/ S
E (It... ....)) 2 L., SD and I".
EZ Jt E
op.2 = cz holds, where cz = 4 for 2 = RR. and cz = 4 for
The proof is based on evaluating the Rademacher complexity 3I 32 33
but technically nontrivial
due to the dependency among the data. We have overcome this difficulty by our novel decomposition of the Rademacher complexity. See the supplementary materials for the complete proof of Theorem In the following, discuss examples of specific negative sampling strategies.
Example 3 (Calculation of vt). Consider the setting in Example [ Proposition 1.
Then the following holds.
(a) Suppose that the data distribution is given by 6 and 7
Then we have that
1 (1-rt) maxte deg (i) + r (1) 1)
1
e deg (i)
(18)
2 [11 - +1]1 + V 1)]
2
[
1 (1-r=)((1) 1) min.ey deg (i) + +r + (1V) -1) 1)
(IVI - 1) minsey deg (1)
12,2
[(1 - r --->] 1) 81] + DI( 1)]
2
DV(VI| - 1) [8]
(19)
for 2 L, S...P..P5500 SD, and for Z RDD we have that
2[ - --++r+) +r+((2 max deg (i)} + r +i]
maxiev deg (i)
1 V
<4
(20)
+ r D7 2| 1)
[3]
1 ((V) 1) (1-r r minkey deg (i)
1 ((V) 1) mineey deg (i)
"T 54
(21)
VV
1)
M
(IV) -
E
M
M
(b) If the conditional distribution of negative pairs is given by (8) then we have that
(1 1--r- r maxiev deg (i) +r (IV) 1)
S maxjey deg (i)
V =
(22)
[11 (1-r-) + VK 1 1)]
3
8

---

for 3 = SP, and
KR = (1 e deg (1) +r-
(D) -1)
m deg (i)
+ 3
+1
(23)
) + r [V([]
E
See the supplementary materials for the proof of Proposition !
Remark 8. We can interpret the evaluations of vi" and 1/x in Example 3 as follows. In the following. we take 18 and 22 as examples, but similar discussion holds for all settings discussed in Example First, we consider r = 0, which implies no noise setting. In this case, Vi= = 1/ is valid. Here, the right hand side indicates the edge distribution's 's imbalance. For example, the right hand side takes the minimum 2/V] if the graph is regular, where the distribution of edges are completely balanced, and takes the maximum 1/ if the graph is star, where all edges connected to one vertex, which is most imbalanced case. Hence, the equation regarding 2i and V4. implies that the more balanced the edge distribution is, the smaller generalization eπror it has. This relation is consistent to what we have emphasized in Remark [ Second, we consider the relation between r and the generalization error. The bound is decreasing with respect to r, the noise intensity. This is because training data is balanced between truly positive and negative pairs if the noise intensive. Note that does not imply that larger noise is better, because large noise worsens the optimal expected loss, even though it has small generalization error, which may lead to large loss of learned representations.
maxiey deg [8]
4 Comparison between LGE and HGE
Theorem T implies that HGE has a larger generalization error than LGE; in other words, HGE has higher variance than I.G.. Conversely, hyperbolic space's ability to obtain low-distortion representations for a complete noiseless tree has been shown (29 40 21): in other words, HGE has a lower bias than LGE. To evaluate the performance of learning models, discussing the bias-variance trade-off is essential. In this section, by combining the above bias and variance discussions, we derive an explicit condition on which HGE outperforms LGE in obtaining representations for tree.
For fair discussion, suppose that the loss function I is given by (10) with the ramp loss function Gramp- which dominates the 0-1 loss function as discussed in Remark 3] and the data distribution is given by the setting in Example (a) with K+ = stronger than (5):
1. Consider the following conditions
(i,j) E 62(21, S 0z
& ( 82(2,,)) 22 +1,
(24)
and define R' as the expected risk given by representations that satisfy the above conditions. Under the conditions, the loss is zero if truly positive pairs appear as positive pair ((*tmm: E E) or
truly negative pairs appear negative pair (1 JT.m E E). Then R is the achievable minimum expected risk.
Let !R and V1.² 'min denote the minimum V attainable by LGE using F² and HGE using LL2 respec- tively. Assume that the true dissimilarity 8 is the graph distance of tree. Regarding min and min the following lemmata hold [29 40 21 (See the supplementary materials for the proofs).
tree and 8* : V x V + R20 is given by its graph distance. Then, there exist R E Rzo, representations (21, 22,...;
Lemma 1. Suppose that (V,E)
: zv) E BR in IL? and threshold Oz E IR that satisfy (24) for all i E V. In particular, R² z ((+)[[)
R*
Lemma 2. Let (V,E) be a graph and define W and p by W = DI(D -1 and E = [8] I
W.
Define = min {ut, , where put == W (I-Ft]otre W (I-P- ((-))=--)++- and 1A" W (1-r-00-ptt W (1- In LGE, the expected risk of the expected risk minimizers satisfies R (z)))²) 2 Rd +RR2, Here, VE? min is not smaller than the number of disjoint 6-star subgraphs in the graph for the 2-dimensional LGE.
By Theorem I conclude as follows:

---

Proposition 2. Suppose that (V.8) is tree and 8* : V x V- - Rso is given by its graph distance,
and take given Lemma Let V1L0 = (Vuieo + + "(10)=
3w1 ( (R) 1eV
M>
+
(25)
2 (VV8V,,L2 in |V| + /nn
min
then HGE's R.2 (zx)) is smaller than LGE's.
See the supplementary materials for the proof of Proposition 2
Remark 9. Proposition 2 jimlies Dimmliess that if the true dissimilarity is given by the graph distance of tree, then HGE is better than LGE even if the data is not complete and noisy, if M is larger than the right hand side of (25).
Example 4. We consider the complete balanced X-ary tree with height h. Suppose À 5 and h 4,
and the positive and negative pair distributions are given by Example 1
(a) with r = =10
Then, HGE's R² (2)) with R 39.50... is smaller than LGE's if M > 7.735 1099 with probability d, where 10-1
See the supplementary materials for the proof of Example Example the first specific calculation result that theoretically guarantees the superiority of HGE LGE. Nevertheless, tightening the right hand side or deriving necessary condition could be future work.
5 Conclusion
We have shown that LGE and HGE cause a polynomial and exponential error with respect to the embedding space's radius, respectively, and that imbalanced data distribution worsen the error. Our bias- varianeee trade-off discussion implies that even though HGE has larger generalization error than LGE, HGE with sufficiently large number of data represent hierarchical data more effectively. This discussion provides a guide for embedding space selection in real applications.
One limitation of our result is that it does not clarify the error's dependency on the dimension D. Our bound does not depend on D, which is not consistent to our intuition that using low-dimensional space should give low generalization error. This problem is essentially the same as that pointed out [2T), which partially used similar techniques to ours. Deriving a tighter bound in terms of the dimension for general ordinal embedding could be future work.
Acknowledgments and Disclosure of Funding
This work was partially supported by JST KAKENHI 191400000190, 19K20337, and JST-AIP 19U4, Daiwa Foundation Award (Ref: 13849/14682), and JST-PRESTO.
References
[1] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean, "Distributed representations words and phrases and their compositionalityy Neural Information Processing Systems, pp. 3111-3119, 2013.
Proceedings of the 27th Conference on
[2] J. Pennington, R. Socher, and D. Manning, "Glove: Global vectors for word representation." in Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing.
pp. 1532 1543, 2014.
[3] P. Bojanowski, E. Grave, A. Joulin, and T. Mikolov, "Enriching word vectors with subword information," Transactions of the Association for Computational Linguistics, vol. 5, pp. 135-
146, 2017.
[4] A. Tifrea, G. Bécigneul, and O.-F. Ganea, "Poincaré GloVe: Hyperbolic word embeddings." in Proceedings of the 7th International Conference on Learning Representations, 2019.
10

---

[5] P. D. Hoff, A. E. Raftery, and M. S. Handcock, "Latent space approaches to social network analysis." " Journal of the american Statistical association, vol. 97, no. 460, pp. 1098. 2002.
[6] B. Perozzi, R. AI-Rfou, and S. Skiena, "DeepWalk: Online learning of social representations." "
in Proceedings of The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 14, New York, NY, USA August 24 27, 2014, pp. 701-710, 2014.
[7] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, "L.NN: large-scale information network embedding." in Proceedings of Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy, May 18-22, 2015, pp. 1067-1077, 2015.
[8] J. Tang. M. Qu, and Q. Mei, "PTE: predictive text embedding through large-scale heteroge- neous text networks," in Proceedings of Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015, pp. 1 174, 2015.
[9] A. Grover and J. Leskovee, "Node2vec: Scalable feature learning for networks," in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 855-864, 2016.
[10] J. M. Dale, I.. Popescu, and P. D. Karp, "Machine learning methods for metabolic pathway prediction," " BMC bioinformatics, vol. 11, no. pp. 1-14, 2010.
[11] A. R. MA Basher and S. J. Hallam, "Leveraging heterogeneous network embedding for metabolic pathway prediction," Bioinformatics, vol. 37, no. 6, pp. 822-829, 2021.
[12] M. Nickel, V. Tresp, and H.-P. Kriegel, "A three-way model for collective learning on multi- relational data," in Proceedings of the 28th International Conference on Machine Learning.
pp. 809-816, 2011.
[13] A. Bordes, N. Usunier, A. Gareía-Durde J. Weston, and O Yakhnenko, "Translating embed- dings for modeling multi-relational data," " in Proceedings of Advances Neural Information Processing Systems 26: 27th Annual Conference Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pp. 2787-2795, 2013.
[14] S. Riedel, L. Yao, A. McCallum, and B. M. Marlin, "Relation extraction with matrix factoriza- tion and universal schemas," in Proceedings of Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings, June 9-14, 2013, Westin Peachtree Plaza Hotel, Atlanta, Georgia, USA, pp. 74-84, 2013.
[15] M. Nickel, L. Rosasco, and T. A. Poggio. "Holographic embeddings of knowledge graphs," in Proceedings of Proceedings of the Thirtieth AAAI Conference Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pp. 1955-1961, 2016.
[16] T. Trouillon, J. Welbl, S. Riedel, É. Gaussier, and G. Bouchard, "Complex embeddings for simple link prediction," in Proceedings of Proceedings of the 33nd International Conference Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, vol. 48,
pp. 2071-2088 2016.
[17] T. Ebisu and R. Ichise, "TorusE: Knowledge graph embedding on a Lie group." in Proceedings of Proceedings of the Thhrry-Seconde AAAI Conference Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp. 1819-1826, 2018
[18) J. Lamping and R. Rao, "Laying out and visualizing large trees using a hyperbolic space," in Proceedings of the 7th ACM Symposium on User Interface Software and Technology, pp. 13- 14. 1994.
[19] H. Ritter, "Self-organizing maps on non-cuclidean spaces," in Kohonen maps, Elsevier, 1999, pp. 97-109.
[20] M. Nickel and D. Kiela, "Poincaré embeddings for learning hierarchical representations." in Proceedings of the 31st Conference on Neural Information Processing Systems, pp. 6338-
6347,200 2017.
[21] A. Suzuki, A. Nitanda, J. Wang, L. Xu, Yamanishi, and M. Cavazza, "Generalization error bound for hyperbolic ordinal embedding." arXiv preprint arXiv:2 2021.
[22] O.-E. Ganea, G. Bécigneul, and T. Hofmann, "Hyperbolic entailment cones for learning hierarchical embeddings." " in Proceedings of the 35th International Conference on Machine Learning, vol. 80, pp. 1632-1641, 2018.
11

---

[23] F. Sala, D. Sa, A. Gu, and C. Ré. "Representation tradeoffs for hyperbolic embeddings." in Proceedings of the 35th International Conference on Machine Learning. vol. 80, pp. 4457- 4466, 2018.
[24] O.-E. Ganea, G. Bécigneul, and T. Hofmann, "Hyperbolic neural networks," in Proceedings of the 32nd Conference on Neural Information Processing Systems, pp. 5350-5360, 2018.
[25] 1. Chami, Z. Ying, C. Ré, and J. Leskovec, "Hyperbolic graph convolutional neural networks," in Proceedings of the 33rd Conference Neural Information Processing Systems, pp. 4869- 4880, 2019.
[26] Ç. Gülçehre et al., "Hyperbolic attention networks." in Proceedings of 7th International Conference on Learning Representations, 2019.
[27] I. Balazevic, C. Allen, and T. M. Hospedales, "Multi-relational poincaré graph embeddings." in Proceedings of the 33rd Conference on Neural Information Processing Systems, pp. 4465- 4475, 2019.
[28] M. Gromov, "Hyperbolic groups," in Essays in group theory, Springer, 1987, pp. 75-263.
[29] R. Sarkar, "Low distortion delaunay embedding of trees in hyperbolic plane." in Proceedings
of the 19th International Symposium on Graph Drawing, vol. 7034, pp. 355-366, 2011.
[30] L. Jain, K. G. Jamieson, and D. Nowak, "Finite sample prediction and recovery bounds for ordinal embedding." in Proceedings of the 30th Conference on Neural Information Processing Systems, vol. 29, pp. 2703-2711, 2016.
[31] V. Koltchinskii, "Rademacher penalties and structural risk minimization," JEEE Transactions Information Theory, vol. 47, no. 5, pp. 1902-19141 2001.
[32] V. Koltchinskii and D. Panchenko, "Rademacher processes and bounding the risk of function learning," in High dimensional probability II, Springer, 2000, pp. 443-457.
[33] P. L. Bartlett, S. Boucheron, and G. Lugosi, "Model selection and error estimation," Machine Learning. vol. 48, no. 1-3. pp. 85-113, 2002.
[34] P. Tabaghi and I. Dokmanic, "Hyperbolic distance matrices," in Proceedings of the 26th ACM Knowledge Discovery and Data Mining, pp. 1728-1738, 2020.
SIGKDD Conference
[35] Y. Gao, C. Zhang. J. Peng. and A. Parameswaran, "The importance of norm regularization in linear graph embedding: Theoretical analysis and empirical demonstration," arXiv preprint arXiv::802.. 1802003560, 2018
[36] M. Ledoux and M. Talagrand, "Probability in banach spaces: Isoperimetry and processes,"
1991.
[37] P. I.. Bartlett and S. Mendelson, "Rademacher and gaussian complexities: Risk bounds and structural results," Journal of Machine Learning Research, vol. 3, pp. 463-482, 2002.
[38] S. M. Kakade, K. Sridharan, and A. Tewari, "On the complexity of linear prediction: Risk bounds, margin bounds, and regularization." in Proceedings of the 22nd Conference on Neural Information Processing Systems, pp. 793-800, 2008
[39] J. Schmidt-Hicber et al., "Nonparametric regression using deep neural networks with relu activation function," " Annals of Statistics, vol. 48, no. 4, pp. 1875-1897, 2020.
[40] A. Suzuki, Wang, Tian, A. Nitanda, and Yamanishi. "Hyperbolic ordinal embedding." in Proceedings of the 11th Asian Conference on Machine Learning, vol. 101, pp. 1065-1080, 2019.
[41] J. A. Tropp, "An introduction to matrix concentration inequalities," Foundations and Trends in Machine Learning, vol. 8, no. 1-2, pp. 1-230, 2015.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
12

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof' of all theoretical results? [Yes] See the supplementary
materials
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi-
mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releusing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "pDG-4IYs4qv", "reviewer": "Reviewer_WFTn", "summary": "Graph embedding has already been a common and effective technique in many applications, while the corresponding theoretical analysis is limited to ideal noiseless settings. This work intends to derive the unified generalization error bound for negative-sampling-based graph embedding regarding the existence of noise. However, the assumption made in this work to drive the theoretical analysis is somewhat impractical making the derived bound a little bit vacuous.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength\nThe motivation of this paper is reasonable. This paper derives the generalization error bound for negative-sampling-based graph embedding which is applicable to various settings (say different embedding spaces, data distributions, and loss functions). \n\nWeakness：\n\nNonetheless, some technical details are based on very strong assumptions and the risk defined in the paper cannot reflect the true embedding ability of a model. This too suggests that bounding the excess risk therein cannot guarantee a good generalization performance.\n\n\n1)\tThe assumption that all positive-negative pair sequences are i.i.d is too strong, which is not applicable for practical applications. This is because each sequence has $K^+$ positive pairs and $K^-$ negative pairs, and thus it is difficult to ensure that these pairs have no interactions and are independent of each other. Therefore, the generalization error bound is limited and may not make sense.\n\n2)\tI’m wondering that if tighten result could be derived if the telescoping-based Lemma 3 is replaced by the Vector-Contraction Inequality proposed in the following paper:  \nA Vector-Contraction Inequality for Rademacher Complexities. ALT 2016: 3-17\n\n3)\tThe authors should re-organize the proof to make it easy to follow.\n\n4)\tThere are many inconsistent/unclaimed symbols making the unnecessary confusion. For example,  \na)\tIn line 190, $i_{1,m}^-$ should be $i_{1,m}^+$;\nb)\tIn line 195, $r$ is not claimed;\nc)\tIn Eq.(31), $R_M(F)$ is not claimed;\nd)\tIn line 579, $D$ should be $D_k$, etc.\nIn addition, the symbols should be as concise as possible to make the paper clear and easy to understand.’\n\n5)\tThe current version of this paper is not easy to understand, and the writing and structure need to be further improved. For example,\na)\tIn definition 1, (b) should be in another line;\nb)\tIn line 543, “By ... the its…”, ‘the’ should be removed;\nc)\tIn line 569, “Let D is …” should be “Let D be…”;\nd)\tIn theorem 3, reference [41] is not included in the main paper.\ne)\tMany references have been published in conference such as [21] instead of arXiv. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\nYes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6h"}, "extra_text": {}}, {"review_id": "HXDdS0MSywU", "reviewer": "Reviewer_ixpa", "summary": "This paper studies the question of the generalization error incurred when embedding graphs in linear vs. hyperbolic space. Recent literature (e.g. work of Nickel and Kiela, ref. [20]) has shown that graph data with hierarchical structure is often better embedded in hyperbolic space--due to its higher representation capacity--than in linear space (for which it becomes necessary to increase the dimensionality of the embedding). However, this choice may come with a tradeoff in terms of generalization error, and the current paper studies this phenomenon in the context of embeddings obtained via negative sampling. Specifically, the authors show that the generalization errors of such embedding into linear and hyperbolic space incur polynomial and exponential growth, respectively, and are also affected by imbalance in how edges are distributed (i.e. regular graphs are balanced, graphs with hubs are more imbalanced). Some of the difficulty of this problem arises due to dependency in the negative sampling procedure, such that iid assumptions and related results cannot be applied. Towards the end, the authors also show that for the special case of tree data, their theory suggests that the generalization error incurred by a hyperbolic embedding is better than that of a linear embedding. Finally, the authors discuss the limitation that their bound does not depend on the embedding dimension, so is likely not tight. The authors explain their setup through numerous examples of negative sampling strategies, notably the Skip-gram model (ref. [1]), as well as detailed explanations of the different terms appearing in their main result.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**: This paper presents a generalization error bound with interesting consequences and interpretations. Moreover, the proof introduces neat ideas that are of independent interest. Notably, Lemma 3 in the supplementary material gives a nice calculation of the Rademacher complexity of a class of functions defined on data that does not satisfy an iid assumption. The rest of the proof follows a structure similar to that of the main result in ref. [21] (now an ICML paper, so the authors would want to update the reference), so it is nice to compare and contrast the different requirements imposed by the non-iid assumption of the current work.  \n\n**Quality**: Continuing from the comments above, I think the paper is quite technically robust. The claims are transparent, and their theoretical justification feels appropriate. The authors use well-placed and judicious remarks to clarify the portions where their approach may fail (e.g. Remark 3 and the Conclusion). The proofs in the supplementary material provide sufficient background, and while I did not verify the details of each inequality, I was able to understand the proof structure at a high level. \n\n**Clarity**: Considering that this is a theory paper, I found the writing quality to be quite nice overall. Once again, the various remarks scattered throughout the text were helpful in guiding the reader.\n\n**Significance:** Given the rapidly growing interest in embedding graph-structured data into hyperbolic space, the results of this paper seem to provide timely guidance in understanding the pros and cons of choosing hyperbolic vs linear space embeddings.\n\nA few small comments:\n\n- Remark 9: \"as long as $M$ is large enough\" -- could the authors work through a concrete example that practitioners can use in determining the amount of data needed for generalizable hyperbolic embeddings?\n- Supplementary, Lemma 3 should read \"$\\mathcal{X}$ is the domain of functions in $\\mathcal{F}$", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have been quite transparent in describing an important limitation of their work (the lack of dependence on embedding dimension). The potentially negative societal impact has not been discussed. I would suggest that the authors change some wording to remove the short, straggling lines throughout the text, thus freeing up space for such a discussion.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "GKaTpb5p0fe", "reviewer": "Reviewer_ywBH", "summary": "The paper presents a generalization error bound for graph embeddings in the defined dissimilarity space, including the linear space and the hyperbolic space. The main conclusion is that error is polynomial and exponential with respect to the embedding space's radius in linear and hyperbolic spaces respectively. However, hyperbolic graph embeddings (HGE) with sufficiently larger number of data represents hierarchical data more effectively than linear graph embeddings (LGE).", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper has solid theoretical contributions. The assumptions and preliminaries are presented very clearly and detailedly. The derivation of the generalization error bound is also clear. The discussion on the bias-variance trade-off of HGE and LGE is interesting and insightful.\n\nSome questions:\n1. The generalization bounds rely on the assumptions on embedding spaces's radius. However, the hyperbolic embeddings of the hyperboloid model (which is the hyperbolic model analyzed in the paper) may have very large norms in practical experiments, especially when the input graph is a very large tree, then the leaves of the tree will be embedded into the points much far away from the origin. The assumptions on the embedding space's radius do not seem practical in such case.\n2. In Remark 5, why is the bound in Theorem 1 for $\\mathcal{Z}=\\mathbb{R}^D$ or $\\mathbb{I}^D$ includes a term $R^2L_k^\\cdot$? The term in Eq. (15) is $\\omega_{\\mathcal{Z}}(R)L_k^\\cdot$, which should be $RL_k^\\cdot$ since $\\omega_{\\mathbb{R}^D}=\\omega_\\mathbb{I}^D=(2R)$?\n\nSome typos:\n1. Eq. (4), $(i\\cdot v_1),(v_1\\cdot v_2),\\dots,(v_{K-1}\\cdot j))$ --> $(i,v_1),(v_1,v_2),\\dots,(v_{K-1},j)$.\n2. Line 154, are consists of --> consist of.\n3. Line 165, $s_m^+$ and $s_m^+$ --> $s_m^+$ and $s_m^-$.\n4. Line 308, the balanced --> the more balanced.\n5. Eq. (24), the second $(i,j)\\in\\mathcal{E}$ --> $(i,j)\\notin\\mathcal{E}$.\n6. Line 327, $(i_{k,m}^-,j_{k,m}^-)\\in\\mathcal{E}$ --> $(i_{k,m}^-,j_{k,m}^-)\\notin\\mathcal{E}$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors addressed the limitations of the work. The potential negative societal impact is not addressed, but I think there is no such concerns of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "5pTfbJaaCgD", "reviewer": "Reviewer_WZeR", "summary": "This paper presents a generalization error bound for graph embedding with negative sampling. The theoretical results are general and can be applied to various settings, e.g., the embedding space, data distribution, and loss function. The theoretical results show the radius of embedding space plays a key role in graph embedding error, and show the imbalanced data distribution can worsen the error. This paper provides specific error bounds for many negative sampling strategies.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studies a very interesting problem that is overlooked in many works. The proposed error bound for negative sampling-baed graph embedding is practical in real-world applications. The theoretical results are impressive and can benefit researchers to choose embedding space for one specific graph embedding task. \n\nIt's not clear why the theorem is applicable for the inner product space. the dissimilarity function of inner product space is different from the one in Euclidean space, so that loss function and the expected risk are also different.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers generalization error incurred when embedding graphs in linear versus hyperbolic space, in particular in the context of embeddings obtained via negative sampling, and presenting results where linear/hyperbolic space incurs polynomial/exponential growth, respectively, and well as on edge heterogeneity.  One low reviewer raised his/her score in the discussion phase, and
still has the good suggestion to incorporate comments to improve readability.
Decision: Accept (Poster)