Optimal link prediction with matrix logistic regression
This work addresses link prediction for network analysis, providing theoretical limits and computational barriers, but it is incremental as it builds on existing matrix logistic regression and minimax frameworks.
The paper tackles link prediction in partially observed networks with vertex side information using a matrix logistic regression model, establishing the minimax rate for Frobenius-norm risk and showing a combinatorial estimator achieves it, but proving this rate is unattainable by polynomial-time algorithms under computational complexity assumptions.
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.