# Optimal link prediction with matrix logistic regression

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2018.

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

- [Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning](https://mlsanity.com/paper/2201.01825/) (2022)

## Abstract (arXiv)

We consider the problem of link prediction, based on partial observation of a large network, and on side information associated to its vertices. The generative model is formulated as a matrix logistic regression. The performance of the model is analysed in a high-dimensional regime under a structural assumption. The minimax rate for the Frobenius-norm risk is established and a combinatorial estimator based on the penalised maximum likelihood approach is shown to achieve it. Furthermore, it is shown that this rate cannot be attained by any (randomised) algorithm computable in polynomial time under a computational complexity assumption.