Introduction
A persistent question for machine learning practitioners working with relational data is whether to embed graphs in Euclidean or Hyperbolic space. While hyperbolic space is renowned for its ability to represent hierarchical, tree-like data with near-zero distortion, this representational power comes at a cost. This paper provides a rigorous theoretical foundation for this trade-off, revealing the hidden "tax" paid for hyperbolic geometry in the form of generalization error. By deriving the first complete generalization error bounds for graph embeddings using negative sampling, the authors demonstrate that while hyperbolic spaces fit hierarchical data better (lower bias), they suffer from exponentially higher generalization error (higher variance) compared to linear spaces, particularly when data is noisy or imbalanced.
The Challenge of Real-World Graph Embedding
Graph embedding maps nodes of a graph into a continuous vector space such that structurally "similar" nodes are positioned close together. Recently, Hyperbolic Graph Embedding (HGE) has gained significant traction. Because hyperbolic space grows exponentially as one moves away from the origin, it perfectly matches the branching structure of trees.
However, most existing theoretical validations of HGE assume an ideal, noiseless setting. In practice, graph data is inherently noisy, and training algorithms rely on negative sampling—randomly selecting non-existent edges—to scale computationally. This creates a critical theoretical gap: it remains unclear whether the exponential growth of hyperbolic space makes the model highly susceptible to massive overfitting. Furthermore, the statistical dependencies introduced by negative sampling make standard statistical learning proofs, which assume independent and identically distributed (i.i.d.) data points, difficult to apply.
Methodology: Bounding the Generalization Error
To address this, the authors derive a unified generalization error bound (Theorem 1) applicable to four distinct geometric spaces: Euclidean, Hyperbolic, Spherical, and Inner Product.
Handling the complex dependencies introduced by negative sampling required a methodological innovation. The authors introduce a novel multivariable version of the Ledoux-Talagrand contraction lemma. This mathematical tool allows them to decompose the complex, interdependent loss function into manageable components related to individual sampled edges.
The core of their analysis centers on the embedding space's radius ($R$). By analyzing how the error scales as vectors are allowed to move further from the origin to capture complex relationships, they establish a rigorous comparison between the spaces.
Key Insights and Theoretical Results
The Polynomial vs. Exponential Divide
The most critical finding is the divergence in how generalization error scales with the radius $R$. In linear (Euclidean) space, the generalization error grows polynomially with $R$. In hyperbolic space, however, it grows exponentially. This highlights a fundamental trade-off: the very geometric property that allows HGE to embed trees perfectly also makes it exponentially more sensitive to noise.
The Bias-Variance Trade-off
The authors formally frame the debate between Linear Graph Embedding (LGE) and HGE as a classic bias-variance trade-off. HGE exhibits lower bias because it can represent trees with minimal distortion, but it suffers from higher variance due to its exponentially larger generalization error bound.
The Penalty of Imbalance
The derived bounds also reveal that imbalanced data distributions—which are ubiquitous in real-world graphs featuring "hub" nodes—significantly exacerbate generalization error. For instance, a highly imbalanced "star" graph yields a much worse error bound than a "regular" graph where every node shares the same degree.
The Data Size Threshold
To ground these theoretical bounds, the authors provide an explicit formula (Proposition 2) to determine the volume of data ($M$) required for HGE's low bias to outweigh its high variance. Using a synthetic 5-ary tree of height 4 as a test case, they calculate that HGE would theoretically require a massive amount of training data ($M > 7.735 \times 10^{69}$) to guarantee superiority over LGE in a noisy setting. While this theoretical bound is admittedly conservative, it starkly illustrates the massive "generalization gap" that hyperbolic models must overcome.
Limitations and Future Directions
While this work establishes a crucial theoretical baseline, it presents several avenues for future research:
- The Dimension ($D$) Mystery: Surprisingly, the derived bounds do not explicitly depend on the number of embedding dimensions ($D$). Intuitively, higher dimensions should increase the risk of overfitting, but this is not captured in the current proof—a limitation shared by other recent works in ordinal embedding.
- Tightness of Bounds: The authors acknowledge that their bounds are likely loose. Future work must focus on tightening these inequalities to provide more practical, actionable "rules of thumb" for engineers.
- Non-smooth Losses: The current theoretical framework requires Lipschitz continuous loss functions. Extending these proofs to accommodate non-smooth losses, such as the 0-1 loss, remains an open challenge for the field.
Summary updated