We discuss a version of matrix completion problem in which the goal is to estimate a symmetric kernel defined on the vertex set of a weighted graph based on i.i.d. noisy observations of the kernel at randomly picked couples of vertices of the graph. The underlying assumption is that the kernel is low rank and, at the same time, "smooth" on the graph. The smoothness is characterized by discrete Sobolev type norms defined in terms of graph Laplacian. We derive minimax lower bounds on estimation error and develop estimation methods for which such bounds are attained up to log factors.