Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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.  

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

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

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

A few small comments:

- 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?
- Supplementary, Lemma 3 should read "$\mathcal{X}$ is the domain of functions in $\mathcal{F}$
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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. 

It'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.

limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: Strength
The 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). 

Weakness：

Nonetheless, 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.


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

2)	I’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:  
A Vector-Contraction Inequality for Rademacher Complexities. ALT 2016: 3-17

3)	The authors should re-organize the proof to make it easy to follow.

4)	There are many inconsistent/unclaimed symbols making the unnecessary confusion. For example,  
a)	In line 190, $i_{1,m}^-$ should be $i_{1,m}^+$;
b)	In line 195, $r$ is not claimed;
c)	In Eq.(31), $R_M(F)$ is not claimed;
d)	In line 579, $D$ should be $D_k$, etc.
In addition, the symbols should be as concise as possible to make the paper clear and easy to understand.’

5)	The current version of this paper is not easy to understand, and the writing and structure need to be further improved. For example,
a)	In definition 1, (b) should be in another line;
b)	In line 543, “By ... the its…”, ‘the’ should be removed;
c)	In line 569, “Let D is …” should be “Let D be…”;
d)	In theorem 3, reference [41] is not included in the main paper.
e)	Many references have been published in conference such as [21] instead of arXiv. 
limitations_and_societal_impact: 
Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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).
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.

Some questions:
1. 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.
2. 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)$?

Some typos:
1. 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)$.
2. Line 154, are consists of --> consist of.
3. Line 165, $s_m^+$ and $s_m^+$ --> $s_m^+$ and $s_m^-$.
4. Line 308, the balanced --> the more balanced.
5. Eq. (24), the second $(i,j)\in\mathcal{E}$ --> $(i,j)\notin\mathcal{E}$.
6. Line 327, $(i_{k,m}^-,j_{k,m}^-)\in\mathcal{E}$ --> $(i_{k,m}^-,j_{k,m}^-)\notin\mathcal{E}$.
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_title: null

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)