Synthetic graphs for link prediction benchmarking

Abstract

Predicting missing links in complex networks requires algorithms that are able to explore statistical regularities in the existing data. Here we investigate the interplay between algorithm efficiency and network structures through the introduction of suitably-designed synthetic graphs. We propose a family of random graphs that incorporates both micro-scale motifs and meso-scale communities, two ubiquitous structures in complex networks. A key contribution is the derivation of theoretical upper bounds for link prediction performance in our synthetic graphs, allowing us to estimate the predictability of the task and obtain an improved assessment of the performance of any method. Our results on the performance of classical methods (e.g., Stochastic Block Models, Node2Vec,GraphSage) show that the performance of all methods correlate with the theoretical predictability, that no single method is universally superior, and that each of the methods exploit different characteristics known to exist in large classes of networks. Our findings underline the need for careful consideration of graph structure when selecting a link prediction method and emphasize the value of comparing performance against synthetic benchmarks. We provide open-source code for generating these synthetic graphs, enabling further research on link prediction methods.

15 pages, 8 figures; code available at: https://github.com/avlaskin/synthetic-graphs-for-lp

References in corpus (11)

• A Comprehensive Survey on Graph Neural Networks
• Benchmark graphs for testing community detection algorithms
• 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
• The ground truth about metadata and community detection in networks
• Evaluating Link Prediction Methods
• A network approach to topic models
• Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms
• Consistencies and inconsistencies between model selection and link prediction in networks
• Synthetic graphs for link prediction benchmarking

Cited by in corpus (1)

• Synthetic graphs for link prediction benchmarking