# The maximum capability of a topological feature in link prediction

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 83 references that are in the map.
- First posted on arXiv 30 Jun 2022.

## Builds on (most cited first, 18 of 18)

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Simplicial Closure and higher-order link prediction](https://mlsanity.com/paper/1802.06916/) (2018)
- [Scale-free networks are rare](https://mlsanity.com/paper/1801.03400/) (2018)
- [Network Medicine Framework for Identifying Drug Repurposing Opportunities for COVID-19](https://mlsanity.com/paper/2004.07229/) (2020)
- [Stacking Models for Nearly Optimal Link Prediction in Complex Networks](https://mlsanity.com/paper/1909.07578/) (2019)
- [Evaluating Link Prediction Methods](https://mlsanity.com/paper/1505.04094/) (2015)
- [Link Prediction in Social Networks: the State-of-the-Art](https://mlsanity.com/paper/1411.5118/) (2014)
- [Principled approach to the selection of the embedding dimension of networks](https://mlsanity.com/paper/2004.09928/) (2020)
- [Progresses and Challenges in Link Prediction](https://mlsanity.com/paper/2102.11472/) (2021)
- [Representing higher-order dependencies in networks](https://mlsanity.com/paper/1508.03113/) (2015)
- [Quantifying Spatial Homogeneity of Urban Road Networks via Graph Neural Networks](https://mlsanity.com/paper/2101.00307/) (2021)
- [Accurate and scalable social recommendation using mixed-membership stochastic block models](https://mlsanity.com/paper/1604.01170/) (2016)
- [Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms](https://mlsanity.com/paper/1909.00174/) (2019)
- [Benchmarking Network Embedding Models for Link Prediction: Are We Making Progress?](https://mlsanity.com/paper/2002.11522/) (2020)
- [Collaborative Filtering Approach to Link Prediction](https://mlsanity.com/paper/2103.09907/) (2021)
- [Predictability of real temporal networks](https://mlsanity.com/paper/2007.04828/) (2020)

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

- [Significant Ties Graph Neural Networks for Continuous-Time Temporal Networks Modeling](https://mlsanity.com/paper/2211.06590/) (2022)
- [Efficient and Privacy-Preserved Link Prediction via Condensed Graphs](https://mlsanity.com/paper/2503.12156/) (2025)
- [H3: A Healthcare Three-Hop Index for Physician Referral Network Prediction](https://mlsanity.com/paper/2605.02150/) (2026)

## Abstract (arXiv)

Networks offer a powerful approach to modeling complex systems by representing the underlying set of pairwise interactions. Link prediction is the task that predicts links of a network that are not directly visible, with profound applications in biological, social, and other complex systems. Despite intensive utilization of the topological feature in this task, it is unclear to what extent a feature can be leveraged to infer missing links. Here, we aim to unveil the capability of a topological feature in link prediction by identifying its prediction performance upper bound. We introduce a theoretical framework that is compatible with different indexes to gauge the feature, different prediction approaches to utilize the feature, and different metrics to quantify the prediction performance. The maximum capability of a topological feature follows a simple yet theoretically validated expression, which only depends on the extent to which the feature is held in missing and nonexistent links. Because a family of indexes based on the same feature shares the same upper bound, the potential of all others can be estimated from one single index. Furthermore, a feature's capability is lifted in the supervised prediction, which can be mathematically quantified, allowing us to estimate the benefit of applying machine learning algorithms. The universality of the pattern uncovered is empirically verified by 550 structurally diverse networks. The findings have applications in feature and method selection, and shed light on network characteristics that make a topological feature effective in link prediction.