# Inherent Limits on Topology-Based Link Prediction

arXiv: https://arxiv.org/abs/2301.08792 · HTML: https://mlsanity.com/paper/2301.08792/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jan 2023.

## Built on by (most cited first, 1 of 1)

- [Graph Neural Networks Based Analog Circuit Link Prediction](https://mlsanity.com/paper/2504.10240/) (2025)

## Abstract (arXiv)

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.