We study the problem of matrix completion when infor- mation about row or column proximities is available, in the form of weighted graphs. The problem can be formulated as the optimization of a convex function that can be solved efficiently using the alternating direction multipliers method. Experiments show that our model offers better reconstruction than the standard method that only uses a low rank assumption, especially when few observations are available.