  We study a Bayesian approach to estimating a smooth function in the context
of regression or classification problems on large graphs. We derive theoretical
results that show how asymptotically optimal Bayesian regularization can be
achieved under an asymptotic shape assumption on the underlying graph and a
smoothness condition on the target function, both formulated in terms of the
graph Laplacian. The priors we study are randomly scaled Gaussians with
precision operators involving the Laplacian of the graph.
