# Link Prediction via Matrix Completion

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2016.

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

- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Generative Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2301.00169/) (2022)
- [Discrete Aware Matrix Completion via Convexized ℓ0-Norm Approximation](https://mlsanity.com/paper/2405.02101/) (2024)
- [Topic Modeling and Link-Prediction for Material Property Discovery](https://mlsanity.com/paper/2507.06139/) (2025)

## Abstract (arXiv)

Inspired by practical importance of social networks, economic networks, biological networks and so on, studies on large and complex networks have attracted a surge of attentions in the recent years. Link prediction is a fundamental issue to understand the mechanisms by which new links are added to the networks. We introduce the method of robust principal component analysis (robust PCA) into link prediction, and estimate the missing entries of the adjacency matrix. On one hand, our algorithm is based on the sparsity and low rank property of the matrix, on the other hand, it also performs very well when the network is dense. This is because a relatively dense real network is also sparse in comparison to the complete graph. According to extensive experiments on real networks from disparate fields, when the target network is connected and sufficiently dense, whatever it is weighted or unweighted, our method is demonstrated to be very effective and with prediction accuracy being considerably improved comparing with many state-of-the-art algorithms.