Evaluating Link Prediction Methods

Abstract

Link prediction is a popular research area with important applications in a variety of disciplines, including biology, social science, security, and medicine. The fundamental requirement of link prediction is the accurate and effective prediction of new links in networks. While there are many different methods proposed for link prediction, we argue that the practical performance potential of these methods is often unknown because of challenges in the evaluation of link prediction, which impact the reliability and reproducibility of results. We describe these challenges, provide theoretical proofs and empirical examples demonstrating how current methods lead to questionable conclusions, show how the fallacy of these conclusions is illuminated by methods we propose, and develop recommendations for consistent, standard, and applicable evaluation metrics. We also recommend the use of precision-recall threshold curves and associated areas in lieu of receiver operating characteristic curves due to complications that arise from extreme imbalance in the link prediction classification problem.

References in corpus (11)

• Emergence of scaling in random networks
• Power-law distributions in empirical data
• The structure of scientific collaboration networks
• Link Prediction in Complex Networks: A Survey
• Hierarchical structure and the prediction of missing links in networks
• Evolution of the social network of scientific collaborations
• Clustering and preferential attachment in growing networks
• Popularity versus Similarity in Growing Networks
• Predicting Positive and Negative Links in Online Social Networks
• Supervised Random Walks: Predicting and Recommending Links in Social Networks
• Link Prediction by De-anonymization: How We Won the Kaggle Social Network Challenge

Cited by in corpus (44)

• Foundations and modelling of dynamic networks using Dynamic Graph Neural Networks: A survey
• Progresses and Challenges in Link Prediction
• Common neighbours and the local-community-paradigm for link prediction in bipartite networks
• Detecting drug-drug interactions using artificial neural networks and classic graph similarity measures
• GC-LSTM: Graph Convolution Embedded LSTM for Dynamic Link Prediction
• Reconstructing networks
• Harnessing the Power of Ego Network Layers for Link Prediction in Online Social Networks
• E-LSTM-D: A Deep Learning Framework for Dynamic Network Link Prediction
• Discriminating abilities of threshold-free evaluation metrics in link prediction
• Benchmarking Network Embedding Models for Link Prediction: Are We Making Progress?
• Machine Learning Link Inference of Noisy Delay-coupled Networks with Opto-Electronic Experimental Tests
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• Collaborative Filtering Approach to Link Prediction
• A supervised approach to time scale detection in dynamic networks
• Beyond Pairwise Interactions: Unveiling the Role of Higher-Order Interactions via Stepwise Reduction
• My friends also prefer diverse music: homophily and link prediction with user preferences for mainstream, novelty, and diversity in music
• Time Series Prediction for Graphs in Kernel and Dissimilarity Spaces
• Graphlets versus node2vec and struc2vec in the task of network alignment
• Can Network Analysis Techniques help to Predict Design Dependencies? An Initial Study
• EvalNE: A Framework for Evaluating Network Embeddings on Link Prediction
• Limitations and Alternatives for the Evaluation of Large-scale Link Prediction
• RankMerging: A supervised learning-to-rank framework to predict links in large social network
• Automatic Discovery of Families of Network Generative Processes
• The Atlas for the Aspiring Network Scientist
• Link Prediction via controlling the leading eigenvector
• Joint Subgraph-to-Subgraph Transitions -- Generalizing Triadic Closure for Powerful and Interpretable Graph Modeling
• Synthetic graphs for link prediction benchmarking
• Applications of Multi-view Learning Approaches for Software Comprehension
• Predicting Links on Wikipedia with Anchor Text Information
• Exploring the Performance of Continuous-Time Dynamic Link Prediction Algorithms
• Link Prediction Using Supervised Machine Learning based on Aggregated and Topological Features
• Identification of Device Dependencies Using Link Prediction
• SNE: Signed Network Embedding
• Link Prediction in Bipartite Networks
• Towards Fast Evaluation of Unsupervised Link Prediction by Random Sampling Unobserved Links
• A Fast Parallel Approach for Neighborhood-based Link Prediction by Disregarding Large Hubs
• Evaluating link prediction: New perspectives and recommendations
• Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation
• Mining Temporal Evolution of Knowledge Graph and Genealogical Features for Literature-based Discovery Prediction
• Nondiagonal Mixture of Dirichlet Network Distributions for Analyzing a Stock Ownership Network
• Link Prediction for Temporally Consistent Networks
• Client Network: An Interactive Model for Predicting New Clients
• Personalized Degrees: Effects on Link Formation in Dynamic Networks from an Egocentric Perspective
• Hierarchical Hyperlink Prediction for the WWW