  Let (V,A) be a weighted graph with a finite vertex set V, with a symmetric
matrix of nonnegative weights A and with Laplacian $\Delta$. Let $S_*:V\times
V\mapsto{\mathbb{R}}$ be a symmetric kernel defined on the vertex set V.
Consider n i.i.d. observations $(X_j,X_j',Y_j),j=1,\ldots,n$, where $X_j,X_j'$
are independent random vertices sampled from the uniform distribution in V and
$Y_j\in{\mathbb{R}}$ is a real valued response variable such that
${\mathbb{E}}(Y_j|X_j,X_j')=S_*(X_j,X_j'),j=1,\ldots,n$. The goal is to
estimate the kernel $S_*$ based on the data
$(X_1,X_1',Y_1),\ldots,(X_n,X_n',Y_n)$ and under the assumption that $S_*$ is
low rank and, at the same time, smooth on the graph (the smoothness being
characterized by discrete Sobolev norms defined in terms of the graph
Laplacian). We obtain several results for such problems including minimax lower
bounds on the $L_2$-error and upper bounds for penalized least squares
estimators both with nonconvex and with convex penalties.
