Link prediction with hyperbolic geometry

Abstract

Link prediction is a paradigmatic problem in network science with a variety of applications. In latent space network models this problem boils down to ranking pairs of nodes in the order of increasing latent distances between them. The network model with hyperbolic latent spaces has a number of attractive properties suggesting it must be a powerful tool to predict links, but the past work in this direction reported mixed results. Here we perform systematic investigation of the utility of latent hyperbolic geometry for link prediction in networks. We first show that some measures of link prediction accuracy are extremely sensitive with respect to inaccuracies in the inference of latent hyperbolic coordinates of nodes, so that we develop a new coordinate inference method that maximizes the accuracy of such inference. Applying this method to synthetic and real networks, we then find that while there exists a multitude of competitive methods to predict obvious easy-to-predict links, among which hyperbolic link prediction is rarely the best but often competitive, it is the best, often by far, when the task is to predict less obvious missing links that are really hard to predict. These links include missing links in incomplete networks with large fractions of missing links, missing links between nodes that do not have any common neighbors, and missing links between dissimilar nodes at large latent distances. Overall these results suggest that the harder a specific link prediction task is, the more seriously one should consider using hyperbolic geometry.

References in corpus (35)

• Link Prediction in Complex Networks: A Survey
• Predicting Missing Links via Local Information
• How to project a bipartite network?
• Hyperbolic Geometry of Complex Networks
• Recommender Systems
• Missing and spurious interactions and the reconstruction of complex networks
• Popularity versus Similarity in Growing Networks
• Sustaining the Internet with Hyperbolic Mapping
• Class of correlated random networks with hidden variables
• Structure and inference in annotated networks
• Self-similarity of complex networks and hidden metric spaces
• Scalable Link Prediction in Dynamic Networks via Non-Negative Matrix Factorization
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
• Scale-free Networks Well Done
• Network Mapping by Replaying Hyperbolic Growth
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Stacking Models for Nearly Optimal Link Prediction in Complex Networks
• Curvature and temperature of complex networks
• Multiscale unfolding of real networks by geometric renormalization
• Emergence of Soft Communities from Geometric Preferential Attachment
• A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities
• Network Geometry Inference using Common Neighbors
• Clustering implies geometry in networks
• Generalized communities in networks
• Reconstructing networks with unknown and heterogeneous errors
• Deciphering the global organization of clustering in real complex networks
• Consistencies and inconsistencies between model selection and link prediction in networks
• Hyperbolic Graph Generator
• Characterizing the analogy between hyperbolic embedding and community structure of complex networks
• Latent geometry of bipartite networks
• Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
• Minimum curvilinear automata with similarity attachment for network embedding and link prediction in the hyperbolic space

Cited by in corpus (19)

• Network Geometry
• Progresses and Challenges in Link Prediction
• Percolation and Topological Properties of Temporal Higher-order Networks
• Reconstructing networks
• Discriminating abilities of threshold-free evaluation metrics in link prediction
• Finding shortest and nearly shortest path nodes in large substantially incomplete networks
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• Collaborative Filtering Approach to Link Prediction
• Random hyperbolic graphs in $d+1$ dimensions
• Detecting local perturbations of networks in a latent hyperbolic embedding space
• Zoo Guide to Network Embedding
• Information Evolution in Complex Networks
• Random graphs and real networks with weak geometric coupling
• Greedy routing optimisation in hyperbolic networks
• The Atlas for the Aspiring Network Scientist
• Systematic comparison of graph embedding methods in practical tasks
• Geometric representations of brain networks can predict the surgery outcome in temporal lobe epilepsy
• Symmetry-driven embedding of networks in hyperbolic space
• Hyperbolic embedding of brain networks as a tool for epileptic seizures forecasting