Technical Summary: Hyperbolic Graph Embedders for Link Prediction and Topology Reconstruction

Problem Statement

Complex networks across diverse domains (e.g., protein interactions, citation graphs, communication systems) often exhibit structural properties such as heterogeneous degree distributions, short path lengths, and high clustering coefficients. Hyperbolic geometry provides a natural latent representation for these structures due to its exponential volume growth, which accommodates hierarchical and heterogeneous connectivity patterns. While various methods have been developed to infer hyperbolic coordinates for nodes (hyperbolic network embedding) from different research communities—machine learning, network science, and algorithmics—systematic comparisons of these methods remain rare.

The core problem addressed is the lack of a unified evaluation framework to compare unsupervised hyperbolic embedding methods. Specifically, there is a need to determine which methods best recover missing links (link prediction) and which best capture the generative mechanisms underlying network topology (topology reconstruction). Furthermore, the impact of network incompleteness (missing links) on the inferred geometric parameters, particularly the temperature parameter governing clustering, requires investigation.

Methodology

The authors established a unified, reproducible experimental framework to benchmark 13 representative unsupervised hyperbolic embedding methods. These methods were categorized into four paradigms based on their research origins and optimization objectives:

1. Maximum-Likelihood Embedders (MLEs): Infer coordinates by maximizing the likelihood of the observed network under a hyperbolic random graph model (e.g., Mercator, KVK, BFKL, DHRG, Anneal).
2. Structural/Ordering-Based Embedders (SOEs): Recover layouts using graph-theoretic properties like node similarity, ordering, and community structure (e.g., Coalescent, CLOVE, LPCS, HMCS).
3. Representation-Learning Embedders (RLEs): Optimize task-specific loss functions in hyperbolic space using Riemannian gradient-based optimization (e.g., Poincaré, Lorentz).
4. Hybrid Embedders (HEs): Combine representation learning with model-based likelihood optimization (e.g., Poincaré+DHRG, Lorentz+DHRG).

Evaluation Protocol:
The benchmark evaluated methods on two complementary tasks using both synthetic networks (generated from the $S_1/H_2$ model with varying sizes, temperatures, and average degrees) and 11 empirical networks:

• Link Prediction: A fraction of edges ($q \in \{0.1, 0.5\}$) was removed to create a training set. Methods were evaluated on their ability to rank candidate missing edges by hyperbolic distance using metrics such as global precision, local precision, predictive power, and a vertex-centric metric (VCMPR).
• Topology Reconstruction: Using inferred coordinates and model parameters, synthetic networks were generated. Reconstruction quality was assessed by comparing structural statistics (degree distributions, clustering spectra, degree correlations, spectral gaps, global transitivity, and Jaccard similarity of edge sets) between the generated and original networks.

Handling Incompleteness:
The study specifically adapted MLEs (Mercator, DHRG, Anneal) to account for missing links by optimizing an effective likelihood function that incorporates the missing-link fraction $q$. The authors derived an analytical relationship showing how random link removal biases the inferred temperature ($T$) in unadjusted models, leading to an overestimation of geometric randomness.

Key Results

1. Effect of Incompleteness on Geometry:
The study demonstrated that missing links significantly distort inferred geometric parameters. Standard Mercator infers a progressively larger effective temperature as the missing-link fraction increases, whereas the $q$-adjusted version approximately recovers the input temperature. This suggests that high inferred temperatures in observed networks may reflect incompleteness rather than intrinsically weak geometric organization.

2. Link Prediction Performance:

• Synthetic Networks: KVK (an MLE) achieved the highest probability of ranking in the top percentile across all network parameter settings. Hybrid methods (Poincaré+DHRG, Lorentz+DHRG) also performed strongly. Structural methods (LPCS, HMCS) generally occupied the lowest positions.
• Real Networks: The ranking shifted slightly; Anneal, Poincaré+DHRG, and Lorentz+DHRG occupied the top three positions. KVK's performance on real networks was lower, potentially due to its design restricting the power-law exponent to $\le 3$, whereas many real networks have exponents $>3$.
• Consensus: Different embedders exploit topological information differently, with only fair-to-moderate agreement (Cohen's kappa) between their predictions, except for high agreement between hybrid methods and their base counterparts.

3. Topology Reconstruction Performance:

• Synthetic Networks: Mercator and Lorentz+DHRG performed best in reproducing degree distributions. Mercator, KVK, and DHRG excelled at reproducing global transitivity.
• Edge Overlap vs. Statistics: A critical distinction was observed: methods like Lorentz+DHRG tended to generate edges that overlapped significantly with the reference graph (high Jaccard similarity), whereas Mercator generated synthetic replicas that closely matched aggregate statistics (degree distribution, transitivity) but differed substantially at the individual edge level.
• Real Networks: Mercator and DHRG generally reproduced degree distributions well, while Mercator and Lorentz+DHRG achieved the highest Jaccard similarity.

4. Trade-offs and Paradigms:

• Task Correlation: Performance on link prediction and topology reconstruction was positively correlated but not perfectly predictive. KVK was top for link prediction but ranked sixth for reconstruction; Mercator was top for reconstruction but ranked fifth for prediction.
• Paradigm Dominance: Performance was more strongly associated with the embedding paradigm than the disciplinary origin. Maximum-likelihood (MLE), representation-learning (RLE), and hybrid (HE) approaches generally outperformed structural/ordering-based (SOE) methods. No single method dominated across all tasks and structural regimes.

Significance and Claims

The paper claims to provide the first systematic benchmark of hyperbolic embedders across machine learning, network science, and algorithmic communities under a unified protocol. Its primary contributions are:

1. Identification of Network Regimes: It identifies specific structural regimes (e.g., varying temperature, degree distribution exponents, and incompleteness levels) where different paradigms succeed or fail.
2. Practical Guidance: It offers guidance for method selection in downstream applications, noting that the choice of method should depend on both the intended task (prediction vs. reconstruction) and the specific topology of the network.
3. Insight on Incompleteness: It highlights that observational incompleteness can be confounded with intrinsic geometric randomness, cautioning against interpreting high inferred temperatures as evidence of weak geometry without accounting for missing data.

The authors modestly conclude that while hyperbolic embeddings provide a reusable, unsupervised representation for multiple tasks, there is no universally best embedder. They acknowledge limitations, including the exclusion of computational cost analysis, the reliance on the $S_1/H_2$ model for reconstruction (which does not explicitly model community structure), and the restriction to link prediction and reconstruction tasks, excluding other potential applications like node classification.