Stacking Models for Nearly Optimal Link Prediction in Complex Networks

Abstract

Most real-world networks are incompletely observed. Algorithms that can accurately predict which links are missing can dramatically speedup the collection of network data and improve the validity of network models. Many algorithms now exist for predicting missing links, given a partially observed network, but it has remained unknown whether a single best predictor exists, how link predictability varies across methods and networks from different domains, and how close to optimality current methods are. We answer these questions by systematically evaluating 203 individual link predictor algorithms, representing three popular families of methods, applied to a large corpus of 548 structurally diverse networks from six scientific domains. We first show that individual algorithms exhibit a broad diversity of prediction errors, such that no one predictor or family is best, or worst, across all realistic inputs. We then exploit this diversity via meta-learning to construct a series of "stacked" models that combine predictors into a single algorithm. Applied to a broad range of synthetic networks, for which we may analytically calculate optimal performance, these stacked models achieve optimal or nearly optimal levels of accuracy. Applied to real-world networks, stacked models are also superior, but their accuracy varies strongly by domain, suggesting that link prediction may be fundamentally easier in social networks than in biological or technological networks. These results indicate that the state-of-the-art for link prediction comes from combining individual algorithms, which achieves nearly optimal predictions. We close with a brief discussion of limitations and opportunities for further improvement of these results.

arXiv comment30 pages, 9 figures, 22 tables

References in corpus (12)

• A survey of cross-validation procedures for model selection
• Link Prediction in Complex Networks: A Survey
• Hierarchical structure and the prediction of missing links in networks
• Predicting Missing Links via Local Information
• Missing and spurious interactions and the reconstruction of complex networks
• Using stacking to average Bayesian predictive distributions
• The ground truth about metadata and community detection in networks
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contexts
• Consistencies and inconsistencies between model selection and link prediction in networks
• Link-Prediction Enhanced Consensus Clustering for Complex Networks
• Significant communities in large sparse networks

Cited by in corpus (27)

• Progresses and Challenges in Link Prediction
• Predicting the Future of AI with AI: High-quality link prediction in an exponentially growing knowledge network
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Link prediction with hyperbolic geometry
• Bayesian hierarchical stacking: Some models are (somewhere) useful
• Disentangling homophily, community structure and triadic closure in networks
• Benchmarking Network Embedding Models for Link Prediction: Are We Making Progress?
• Discriminating abilities of threshold-free evaluation metrics in link prediction
• The maximum capability of a topological feature in link prediction
• Generative model for reciprocity and community detection in networks
• Collaborative Filtering Approach to Link Prediction
• Mapping flows on weighted and directed networks with incomplete observations
• Functional structure in production networks
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Inference of Edge Correlations in Multilayer Networks
• A novel similarity measure for mining missing links in long-path networks
• Symmetry-driven network reconstruction through pseudobalanced coloring optimization
• Missing links as a source of seemingly variable constants in complex reaction networks
• Link Prediction Accuracy on Real-World Networks Under Non-Uniform Missing Edge Patterns
• Unexpected advantages of exploitation for target searches in complex networks
• The Atlas for the Aspiring Network Scientist
• Link Prediction via controlling the leading eigenvector
• Node metadata can produce predictability transitions in network inference problems
• Systematic assessment of the quality of fit of the stochastic block model for empirical networks
• The hidden architecture of connections: How do multidimensional identities shape our social networks?
• Domain matters: Towards domain-informed evaluation for link prediction
• A Fast Parallel Approach for Neighborhood-based Link Prediction by Disregarding Large Hubs