  Low-rank matrix completion has achieved great success in many real-world data
applications. A matrix factorization model that learns latent features is
usually employed and, to improve prediction performance, the similarities
between latent variables can be exploited by pairwise learning using the graph
regularized matrix factorization (GRMF) method. However, existing GRMF
approaches often use the squared loss to measure the pairwise differences,
which may be overly influenced by dissimilar pairs and lead to inferior
prediction. To fully empower pairwise learning for matrix completion, we
propose a general optimization framework that allows a rich class of
(non-)convex pairwise penalty functions. A new and efficient algorithm is
developed to solve the proposed optimization problem, with a theoretical
convergence guarantee under mild assumptions. In an important situation where
the latent variables form a small number of subgroups, its statistical
guarantee is also fully considered. In particular, we theoretically
characterize the performance of the complexity-regularized maximum likelihood
estimator, as a special case of our framework, which is shown to have smaller
errors when compared to the standard matrix completion framework without
pairwise penalties. We conduct extensive experiments on both synthetic and real
datasets to demonstrate the superior performance of this general framework.
