  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.
