Generalization Error Bounds for Graph Embedding Using Negative Sampling: Linear vs Hyperbolic

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.

heading: 1 Introduction
text: Graphs are a fundamental formulation of real-world entities and their relations, such as words in natural languages, people in social network, and objects in knowledge bases. Here, the vertices and edges of a graph correspond to 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 [1, 2, 3, 4], and community detection and
∗Corresponding author
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
link prediction for social network data [5, 6, 7, 8, 9], pathway prediction of biochemical network [10, 11], and link prediction and triplet classification for knowledge base [12, 13, 14, 15, 16, 17]. Graph embedding produces representations of a graph’s vertices in a space equipped with a function that defines the dissimilarity between two points. In this paper, we call a function that defines the dissimilarity a 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 a positive pair, a pair of vertices connected by an edge, and a large value for a 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 [1]. In this strategy, we sample a positive pair for each iteration, followed by sampling negative pairs around the positive pair.
As a dissimilarity space, many graph embedding methods have used linear space equipped with an inner product function [1, 2, 3, 5, 6, 7, 8, 9], which we call linear graph embedding (LGE). However, linear space has limitations in representing data with a hierarchical tree-like structure [18, 19, 20, 21]. These limitations are due to linear space’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) requires, which is exponential [21]. To overcome this limitation, graph embedding in hyperbolic space has recently attracted much attention [20, 22, 23, 24, 25, 26, 4, 27], 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 ball in hyperbolic space grows exponentially with respect to its radius [18, 19, 20, 21]. As a result, hyperbolic space is almost tree-like in that it 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 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 [21], 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 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 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 a 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 generalization error bound. Since the data distribution depends on the graph structure and positive sampling affects the distribution of negative sampling in the negative sampling structure, we cannot apply the i.i.d.-uniform-distribution-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-Talagrand contraction lemma
[36]. By our approach, we can upper-bound the Rademacher complexity of a graph embedding loss function by the sum of the Rademacher complexities [31, 32, 33] of linear prediction models, which have been calculated in [30, 21]. As a 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-sampling-based graph embedding. 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 a polynomial and exponential error with respect to the embedding space’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.

heading: 2 Preliminary
text: 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,Z>0,R,R≥0 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 ∈ Z>0. We denote by ,RD the set of D-dimensional real vectors. For a matrixA ∈ RD,V , we denote by [A]d,v the element in the d-row and the v-th column. For a vector x ∈ RD, we denote by ‖x‖2 the 2-norm of x, defined by ‖x‖2 = √ x>x, and for a matrixA ∈ RD,V , we denote by ‖A‖op,2, the operator norm ofA with respect to the 2-norm, defined by ‖A‖op,2 := supx∈V,x 6=0 ‖Ax‖2 ‖x‖2 . By (an) N n=1, we denote a sequence (a1, a2, . . . , aN ).

heading: 2.1 Graph Embedding
text: In this section, we first formulate the general embedding problem, before we specialize it into a graph embedding. Consider an entity set V and the true dissimilarity function V × V → R defined on the entity set V . For i, j ∈ V , we call δ∗(i, j) the true dissimilarity between i and j, and a small δ∗(i, j) value implies that entity i and j are similar or closely related to each other, and large δ∗(i, j) value implies its converse. In this paper, we identify V with the integer set {1, 2, . . . , |V|}. Embedding aims to get representations z1, z2, . . . , zV of the entity set V in a space (Z, δZ) equipped with a dissimilarity function δZ : Z × Z → R of Z so that the representations are consistent to the true dissimilarity among the entities in that if δ∗(i, j) is small, then δ(zi, zj) is also small, and vice versa. We call Z the embedding space. Specifically, we aim to satisfy
δ∗(i, j) Q θ∗ ⇔ δZ(zi, zj) Q θZ , (1)
as frequent as possible with respect to some distribution regarding (i, j), which we discuss in the next subsection. Here, θ∗, θZ ∈ RZ are fixed thresholds regarding the true dissimilarity δ∗ and the dissimilarity δZ in the embedding space.
As a dissimilarity function of the embedding space Z , we mainly consider the square distance [∆Z(zi, zj)]
2 if Z is equipped with a distance function ∆Z : Z × Z → R≥0, and the negative inner product −〈zi, zj〉 if Z is equipped with an inner product 〈·, ·〉 : Z ×Z → R. In this paper, we deal with the following four dissimilarity spaces.
Definition 1. (Dissimilarity spaces) (a) The D-dimensional Euclidean space ( RD,∆RD ) consists of the set of D-dimensional real vectors and the distance function ∆RD : RD × RD → R≥0 defined by ∆RD (z, z′) := ‖z − z′‖ 2 2. The dissimilarity function is given by δRD (z, z′) := [∆RD (z, z′)] 2.
(b) The D-dimensional hyperbolic space ( LD,∆LD ) consists of the D-dimensional hyperboloid LD ⊂ RD+1 and the distance function ∆LD defined by
LD := { x ∈ RD+1 ∣∣ 〈x,x〉M = −1} , ∆LD (x,x′) := arcosh(−〈x,x′〉M), (2) where 〈·, ·〉M : RD × RD → R is the Minkowski inner prodct defined by〈
[z0 z1 · · · zD]>, [z′0 z′1 · · · z′D]> 〉
M := −z0z′0 +
∑D d=1 zdz ′ d. The dissimilarity
function is given by δLD (z, z′) := [∆LD (z, z′)] 2. (c) The D-dimensional sphere ( SD,∆SD ) consists of the subset SD ⊂ RD+1 and the distance function ∆LD defined by
SD := { x ∈ RD+1 ∣∣ x>x = 1} , ∆SD (x,x′) := arccos(x>x′). (3) The dissimilarity function is given by δSD (z, z′) := [∆SD (z, z′)] 2.
(d) The canonical D-dimensional inner product space ( ID, δID ) as a dissimilarity space consists of the set ID = RD of D-dimensional real vectors and the dissimilarity function δID : ID × ID → R defined by the negative canonical inner product δID (z, z′) := −z>z′.
Our main focus in this paper is RD and LD, although our bound is also applicable to SD and ID. 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 1. While these are isometric to each other, we used the models in Definition 1 because we can formulate the dissimilarity function as a simple function of a linear combination of inner products z>z, z>z′, and z′>z′, or 〈x,x′〉M, which makes it easy to apply techniques in [30, 21].
Graph Embedding Consider a graph (V, E), where V is the vertex set and E ∈ 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, E) is a special case of embedding problem defined above, where the vertices V are the entities, the true dissimilarity between two entities i, j is given by the graph distance defined by
δ∗(i, j) := min { K ∣∣ ∃(v1, v2, . . . , vK−1) ∈ VK−1, (i, v1), (v1, v2), . . . , (vK−1, j) ∈ E .} , (4)
and θ∗ = 1. Then, the objective defined by (1) is equivalent to
(i, j) ∈ E ⇔ δZ(zi, zj) ≤ θz. (5)
We say that a pair (i, j) is truly positive if (i, j) ∈ E and truly negative otherwise. In the following, we denote by deg (i) the degree of i ∈ V , defined by deg (i) := {j|(i, j) ∈ E}.

heading: 2.2 Data distribution
text: In this paper, we consider negative-sampling-based training data and loss functions. Training data consist of M positive-negative pair sequences. The m-th positive-negative pair sequence sm = (s+m, s − m) consists of K + positive pairs s+m := (( i+1,m, j + 1,m ) , ( i+2,m, j + 2,m ) , . . . , ( i+K+,m, j + K+,m )) ∈ (V × V)K + and K− negative pairs s−m := (( i−1,m, j − 1,m ) , ( i−2,m, j − 2,m ) , . . . , ( i−K−,m, j − K−,m )) ∈ (V × V)K −
. Here, for m = 1, 2, . . . ,M , we expect that i+k,m and j + k,m are similar to each other, that is, δ∗ ( i+k,m, j + k,m ) ≤ θ∗ is valid for k+ = 1, 2, . . . ,K+, and conversely, i−k,m and j − k,m are dissimilar
to each other, that is, δ∗ ( i−k,m, j − k,m ) > θ∗ is valid for k− = 1, 2, . . . ,K−, 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 is needed. We consider the following weak assumption. Assumption 1. s1, s2, . . . , sM are independently and identically distributed.
Remark 2. Assumption 1 does NOT imply the independence and identity of the distribution of pairs in s+m and s − m. For example, the distribution of ( i−k′,m, j − k′,m ) may depend on ( i−k,m, j − k,m ) . This weakness assumption allows us 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 following, P [( i+k,m, j + k,m )] and P [( i−k,m, j − k,m )] denote the probability of edge ( i+k,m, j + k,m ) and(
i−k,m, j − k,m
) being generated as the k-th positive and negative pairs, respectively, and
P [( i−k,m, j − k,m )∣∣∣(i+k′,m, j+k′,m)] denotes the probability of edge (i−k,m, j−k,m) being generated as the k-th negative pair given ( i+k′,m, j + k′,m ) 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, j) in the edge set E 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 [( i+k,m, j + 1,m )] =  p+ if ( i+k,m, j + k,m ) ∈ E , r+p+ if ( i+k,m, j + k,m ) /∈ E and i+k,m 6= j + k,m,
0 if i+k,m = j + k,m,
(6)
where r+ ∈ [0, 1] indicates the noise intensity. If r = 0, then only truly positive pairs appear, and if r = 1, then all edges appears in the same probability. Here, since∑
(i+1,m,j + 1,m)∈V×V
P [( i+1,m, j + 1,m )] = 1, we have that p+ = 1(1−r+)|E|+r+|V|(|V|−1) . For negative
pair sampling, we consider the following simple distribution.
P [( i−k,m, j − 1,m )] =  p− if ( i−k,m, j − k,m ) /∈ E and i−k,m 6= j − k,m, r−p− if ( i−k,m, j − k,m ) ∈ E ,
0 if i−k,m = j − k,m,
(7)
where r− ∈ [0, 1] indicates the noise intensity. Also, p− is given by p− = 1(1−r−)|V|(|V|−1)+r−|E| .
(b) (Skipgram [1] type negative sampling) In some applications, it is not easy to 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], a representative on in 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 in [1]. Here, one vertex of a negative pair i−k,m is always the same as that of the positive pair i+1,m, and the other entity of the negative pair is generated according to the distribution whose probability mass function is proportional to a value π ( U ( j−1,m )) , where
π : R≥0 → R≥0 is a function and U ( j−1,m ) is the frequency of the vertex j−1,m appearing in a positive pair. In summary, the conditional distribution is given by
P [( i−k,m, j − k,m )∣∣∣(i+1,m, j+1,m)] = { qπ ( U ( j−1,m )) if i−k,m = i + 1,m,
0 otherwise. (8)
Here, since ∑ j−k,m∈V P [( i−k,m, j − k,m )∣∣∣(i+1,m, j+1,m)] = 1, we have q = 1∑ j − k,m ∈V π(U(j−1,m)) . If
P [( i+1,m, j + 1,m )] is given by (6), U ( j−1,m ) is given by U ( j−1,m ) = (1−r+) deg (j−1,m)+r +(|V|−1) (1−r+)|E|+r+|V|(|V|−1) . In the
following, we set π(x) = x for simplicity. Then we have P [( i−k,m, j − k,m )∣∣∣(i+1,m, j+1,m)] = U(j−1,m). The above setting is an example of the negative pair’s distribution depending on the positive pair. Note that the above setting does not guarantee that truly negative pairs appear as a negative pair more frequently than truly positive pairs.
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.

heading: 2.3 Loss function
text: To quantify the consistency of the true dissimilarities of entities defined by δ∗ and those of representations defined by δZ , we consider loss function l : RK
+ × RK− → R≥0. The loss on a positive-negative pair sequence sm is given by l ( δ+m, δ − m ) , where
δ•m := [ δi•1,m,j•1,m δi•2,m,j•2,m · · · δi•K•,m,j•K•,m ]> , (9)
for • = −,+ and δi,j is given by δi,j := δZ(zi, zj) for i, j ∈ V . Here, we expect that l is increasing with respect to each element of δ+m, the dissimilarity between a positive pair, and decreasing with respect to each element of δ−m, the dissimilarity between a negative pair.
Assumption 2. The loss function l is Lipschitz continuous for each variable.
We denote the Lipschitz constant of l with respect to δi+k ,j+k and δi−k ,j−k by L + k and L − k , respectively. Note that the assumption regarding the loss function’s Lipschitz continuity is common to derive a 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, h : R→ R is an increasing function that converts the dissimilarity. Example 2. (Loss functions)
(a) (Sigmoid-base loss) Define l by l ( δ+m, δ − m ) :=
K+∑ k+=1 lnσ ( − [ h ( δi+ k+,m ,j+ k+,m ) − h(θ) ]) + K−∑ k−=1 lnσ ( h ( δi− k−,m ,j− k−,m ) − h(θ) ) ,
(10) where σ is a sigmoid shape function. For example, we can use the standard sigmoid function defined by σstd(x) = 11+exp(−x) , the hinge loss function σhinge(x) = max {0, x+ 1} or the ramp loss function σramp(x) = min {1, σhinge(x)}. h is Lh-Lipschitz. Then L+k+ = L − k− = Lh 4 if σ = σstd and L+k+ = L − k− = Lh if σ = σhinge or σ = σramp, for k
+ = 1, 2, . . . ,K+ and k− = 1, 2, . . . ,K−. The above loss function (10) with the standard sigmoid function σ corresponds to the negativesampling-based loss function in [1] (h(x) = x and θ = 0) and the loss function in [20] for network embedding (h(x) = xt and θ = r, where r, t are fixed constants defined in the paper).
(b) (Softmax-like loss) Let K+ = 1 and define l by
l ( δ+m, δ − m ) := −h ( δi+1,m,j + 1,m ) + ln K−∑ k−=1 exp ( −h ( δi− k−,m ,j− k−,m )) . (11)
Suppose that h is Lh-Lipschitz. Then L+k+ = L − k− = Lh, for k + = 1, 2, . . . ,K+ and k− = 1, 2, . . . ,K−. The loss function (11) corresponds to the loss function for embedding taxonomy in [20] with h(x) = √ x, although this h gives a non-Lipschitz-continuous loss function. In this paper, since a non-smooth loss function often loses a generalization guarantee, we only consider the case where h and l are Lipschitz continuous, as in [33].

heading: 2.4 Generalization error
text: 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̂Z
(sm) M m=1
: (Z)V → R≥0 on
training data s = (s)Mm=1 and the expected risk functionRZ : (Z) V → R≥0 as follows:
R̂Zs ( (zv) V v=1 ) := 1
M M∑ m=1 l ( δ+m, δ − m ) , RZ ( (zv) V v=1 ) := Esm l ( δ+m, δ − m ) . (12)
Let B ⊂ Z |V| be the space which we search for optimal representations z1, z2, . . . , z|V|. As we discuss in the next section, B may be a bounded set rather than the whole space Z |V|. We define the empirical risk minimizer (ẑv) |V| v=1 and expected risk minimizer (z ∗ v) |V| v=1 by
(ẑv) |V| v=1 := argmin
(zv) |V| v=1∈B
R̂Zs ( (zv) |V| v=1 ) , (z∗v) |V| v=1 := argmin
(zv) |V| v=1∈B
RZ (
(zv) |V| v=1 ) . (13)
Our interest is the excess risk given byRZ (
(ẑv) |V| v=1
) −RZ ( (z∗v) |V| v=1 ) , which indicates the gener-
alization error of embedding. We derive the upper bound of the excess risk in the next section.
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 dissimilarity function Z , the comparison is not always completely fair. Nevertheless, the comparison can be meaningful. For
example, consider the 0-1 loss defined by (10) with σ(x) = σ0−1(x) := {
1 if x ≥ 0, 0 if x < 0. . Regardless
of the choice of embedding space Z , the risk function on the 0-1 loss indicates the error rate of classifying a pair (i, j) into “similar (δ∗(i, j) ≤ θ∗)” or “dissimilar (δ∗(i, j) > θ∗).” Thus, it is fair to compare this 0-1-loss-based risk between different embedding spaces. Although the 0-1 loss itself does not satisfy Assumption 2, since the hinge loss and ramp loss dominates the 0-1 loss in that σ0−1(x) ≤ σramp(x) ≤ σhinge(x), deriving and comparing bounds for these loss indirectly enables comparison between the 0-1-loss-based risks of different embedding spaces. In this sense, comparing the risks of different embedding spaces based on a Lipschitz continuous loss is of interest.

heading: 3 Generalization Bounds for Graph Embedding

heading: 3.1 Assumptions on Embedding Space’s Radius
text: As also discussed in [21] for ordinal embedding, to derive a finite generalization bound, in general, it is necessary to restrict parameters (in embedding cases, representations) to a 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 be practical, the restriction should be simple and geometrically intuitive. Following [21], 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
BR := { (zv) |V| v=1 ∣∣∣∀v ∈ V : ∆Z(z0, zv) ≤ R}, (14) where z0 is [0 0 . . . 0] ∈ RD for Z = RD, ID and [1 0 . . . 0] ∈ RD+1 for Z = LD,SD, and ∆ID is defined by ∆ID (z, z′) = ‖z′ − z‖2. In the next section, we provide the generalization error bound for empirical risk minimizer in BR.

heading: 3.2 Main Result: Finite Sample Upper Bounds for the Generalization Error
text: 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,LD,SD or ID, and (ẑv)|V|v=1 and (z∗v) |V| v=1 be empirical and expected risk minimizers defined by (13). Under Assumptions 1 and 2, the following inequality holds with probability 1− d: RZ (
(ẑv) |V| v=1
) −RZ ( (z∗v) |V| v=1 ) ≤ 2ωZ(R)
M
∑ •=+,− K•∑ k=1 L•k (√ 2Mν•kZ ln |V|+ κZ 3 ln |V| ) + Il(B) √ ln 2d M ,
(15)
where ωZ is defined by ωRD (R) = ωID (R) := (2R) 2, ωLD (R) := cosh 2R + sinh2R and ωSD (R) :=
2 arccos (1−cos 2R)√ −cos 2R(cos 2R−2) , κLD = κSD = κID = 12 and κRD = 2, and ν • k :=
∥∥∥E(i•k,m,j•k,m)EZi•k,m,j•k,m>EZi•k,m,j•k,m∥∥∥op,2 for k = 1, 2, . . . ,K• and • = +,−. Here, EZi,j is defined by [
EZi,j ] i′,j′ :=  aZdiag if (i, j) = (i ′, j′), aZoff if i ′ = j′ = i or i′ = j′ = j and (i, j) 6= (i′, j′′),
0 otherwise, (16)
where aR D diag = 1, a RD off = −1, aL D diag = − 12 , a SD diag = a ID diag = 1 2 , and a LD off = a SD off = a ID off = 0. Il(B) is the range of l defined by
Il(B) := max { l ( δ+, δ− ) ∣∣∣ sm ∈ S, (zv)Vv=1 ∈ B}−min{l(δ+, δ−) ∣∣∣ sm ∈ S, (zv)Vv=1 ∈ B} , (17) where S := (V × V)K + × (V × V)K −
. Remark 4. ωZ(R) corresponds to the embedding space’s volume. Similar to ordinal embedding cases in [21], Theorem 1 argues that the larger the embedding space is, the larger the generalization error 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. ν•k indicates the imbalance in the training data’s distribution. Theorem 1 suggests that an imbalanced distribution causes large generalization error. This is intuitive because training data’s imbalance makes it difficult to understand the big picture of the data. We will explore this in Example 3 and Remark 8. Remark 5. If Z = RD or ID, multiplying a constant α to R and α2 to Lipschitz constant L•k imply the same relaxation of the condition, since these two are equivalent by scaling representations. Hence, the bound in Theorem 1 for Z = RD or ID includes a term R2L•k, which indicates the essential size of the embedding space. This discussion is not true of Z = LD and SD, because balls with different sizes are not similar to each other in these spaces.
Remark 6. Owing to Assumption 2, Il ≤ (2R)2 ∑ •=+,− ∑K• k=1 L • k always holds. Remark 7. For any distribution on s, by Jensen’s inequality, we have that ν•k ≤ E(i•k,m,j•k,m)
∥∥∥EZi•k,m,j•k,m>EZi•k,m,j•k,m∥∥∥op,2 = cZ holds, where cZ = 4 for Z = RD and cZ = 14 for Z = LD,SD, and ID.
The proof is based on evaluating the Rademacher complexity [31, 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 1. In the following, we discuss examples of specific negative sampling strategies. Example 3 (Calculation of ν•k). Consider the setting in Example 1. Then the following holds. Proposition 1.
(a) Suppose that the data distribution is given by (6) and (7). Then we have that
ν+k,Z= 1 2 · (1− r +) maxi∈V deg (i) + r +(|V| − 1) [(1− r+)|E|+ r+|V|(|V| − 1)] ≤ 1 2 · maxi∈V deg (i) |E| , (18)
ν−k,Z= 1 2 · (1− r −)[(|V| − 1)−mini∈V deg (i)] + r−(|V| − 1) [(1− r−)[|V|(|V| − 1)− |E|] + r−|V|(|V| − 1)] ≤ 1 2 · (|V| − 1)−mini∈V deg (i) |V|(|V| − 1)− |E| ,
(19)
for Z = LD, ID,SD, and for Z = RD we have that
ν+ k,RD≤ 2[(1− r+){2 maxi∈V deg (i)}+ r+|V|] (1− r+)|E|+ r+|V|(|V| − 1) ≤4 · maxi∈V deg (i) |E| , (20)
ν− k,RD≤4
1 |V| (|V| − 1)− (1− r−) mini∈V deg (i) (|V| − 1)− (1− r−) |E||V| ≤4 · 1 |V| (|V| − 1)−mini∈V deg (i) (|V| − 1)− |E||V| . (21)
(b) If the conditional distribution of negative pairs is given by (8), then we have that
ν−k,Z = 1 2 · (1− r −) maxi∈V deg (i) + r −(|V| − 1) [(1− r−)|E|+ r−|V|(|V| − 1)] ≤ 1 2 · maxi∈V deg (i) |E| , (22)
for Z = LD, ID,SD, and
ν− k,RD = 2
[ (1− r−) maxi∈V deg (i) + r−(|V| − 1)
(1− r−)|E|+ r−|V|(|V| − 1) + 1
] ≤ 2 [ maxi∈V deg (i)
|E| + 1
] . (23)
See the supplementary materials for the proof of Proposition 1.
Remark 8. We can interpret the evaluations of ν+1 and ν − k 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 3. First, we consider r = 0, which implies no noise setting. In this case, ν+1 = ν − k = 1 2 · maxi∈V deg (i) |E| is valid. Here, the right hand side indicates the edge distribution’s imbalance. For example, the right hand side takes the minimum 12|V| if the graph is regular, where the distribution of edges are completely balanced, and takes the maximum 12 if the graph is a star, where all edges are connected to one vertex, which is most imbalanced case. Hence, the equation regarding ν+1 and ν − k implies that the more balanced the edge distribution is, the smaller generalization error it has. This relation is consistent to what we have emphasized in Remark 4. 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 is intensive. Note that it 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 a large loss of learned representations.

heading: 4 Comparison between LGE and HGE
text: Theorem 1 implies that HGE has a larger generalization error than LGE; in other words, HGE has a higher variance than LGE. 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 a tree.
For fair discussion, suppose that the loss function l is given by (10) with the ramp loss function σ = σramp, which dominates the 0-1 loss function as discussed in Remark 3, and the data distribution is given by the setting in Example 1 (a) with K+ = K− = 1. Consider the following conditions stronger than (5):
(i, j) ∈ E ⇒ δZ(zi, zj) ≤ θZ − 1, (i, j) /∈ E ⇒ δZ(zi, zj) ≥ θZ + 1, (24)
and defineR∗ 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 (( i+k,m, j + k,m ) ∈ E ) or
truly negative pairs appear as negative pair (( i−k,m, j − k,m ) ∈ E )
. ThenR∗ is the achievable minimum expected risk.
Let V R 2 min and V L2 min denote the minimum V attainable by LGE using R2 and HGE using L2, respectively. Assume that the true dissimilarity δ∗ is the graph distance of a tree. Regarding V R 2
min and V L2 min,
the following lemmata hold [29, 40, 21] (See the supplementary materials for the proofs).
Lemma 1. Suppose that (V, E) is a tree and δ∗ : V × V → R≥0 is given by its graph distance. Then, there exist R ∈ R≥0, representations (z1, z2, . . . ,zV ) ∈ BR in L2, and threshold θZ ∈ R that satisfy (24) for all i, j ∈ V . In particular,RZ ( (z∗v) |V| v=1 ) = R∗.
Lemma 2. Let (V, E) be a graph and define W and ρ by W := |V|(|V| − 1) and E := |E|W . Define µ := min {µ+, µ−}, where µ+ := 1W 1 (1−r+)ρ+r+ − 1 W r− (1−r−)(1−ρ)+r− and µ − :=
1 W 1 (1−r−)(1−ρ)+r− − 1 W
r+
(1−r+)ρ+r+ . In LGE, the expected risk of the expected risk minimizers satisfiesRZ (
(z∗v) |V| v=1 ) ≥ R∗ + V R2minµ. Here, V R 2
min is not smaller than the number of disjoint 6-star subgraphs in the graph for the 2-dimensional LGE.
By Theorem 1, we can conclude as follows:
Proposition 2. Suppose that (V, E) is a tree and δ∗ : V × V → R≥0 is given by its graph distance, and take R given in Lemma 1. Let ν1,LD := (√ ν+ 1,LD + √ ν− 1,LD )2 . If
M >  3ωLD (R) 4|V|µV R2min (√ 8ν1,LD ln |V|+ √ ln 2 d ) +
1 2 (√ 8ν1,LD ln |V|+ √ ln 2d
)  2 , (25)
then HGE’sRZ (
(ẑv) |V| v=1
) is smaller than LGE’s.
See the supplementary materials for the proof of Proposition 2. Remark 9. Proposition 2 implies that if the true dissimilarity is given by the graph distance of a 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 λ-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+ = r− = 10−4. Then, HGE’s RZ ( (ẑv) |V| v=1 ) with R = 39.50... is smaller than LGE’s if M > 7.735 × 1069 with probability 1 - d, where d = 10−1.
See the supplementary materials for the proof of Example 4. Example 4 is the first specific calculation result that theoretically guarantees the superiority of HGE to LGE. Nevertheless, tightening the right hand side or deriving a necessary condition could be future work.

heading: 5 Conclusion
text: 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 can worsen the error. Our bias-variance trade-off discussion implies that even though HGE has larger generalization error than LGE, HGE with sufficiently large number of data can 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 in [21], 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 JPMJCR19U4, Daiwa Foundation Award (Ref: 13849/14682), and JST-PRESTO.

Review summaries:
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.

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.

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.

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).