Inherent Limits on Topology-Based Link Prediction

2023/01/20 by Justus I. Hibshman, Tim Weninger, Hibshman, Justus I. +1 · 1 citation
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #Graph Theory and Algorithms #Social and Information Networks (cs.SI)

paper · pdf · doi:10.48550/arxiv.2301.08792

openalex publication_date 2023/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Link prediction systems (e.g. recommender systems) typically use graph topology as one of their main sources of information. However, automorphisms and related properties of graphs beget inherent limits in predictability. We calculate hard upper bounds on how well graph topology alone enables link prediction for a wide variety of real-world graphs. We find that in the sparsest of these graphs the upper bounds are surprisingly low, thereby demonstrating that prediction systems on sparse graph data are inherently limited and require information in addition to the graph topology.

Cited by

• Graph Neural Networks Based Analog Circuit Link Prediction

Related

• The maximum capability of a topological feature in link prediction
• On the effect of the average clustering coefficient on topology-based link prediction in featureless graphs
• Link Prediction without Graph Neural Networks
• Synthetic graphs for link prediction benchmarking
• Link Prediction via Higher-Order Motif Features