Covariance functions and Bayes errors for GP regression on random graphs

We consider GP learning of functions defined on the nodes of a random graph. Covariance functions proposed for this scenario, based on diffusion processes on the graph, are shown to have some counter-