  We propose Gaussian processes for signals over graphs (GPG) using the apriori
knowledge that the target vectors lie over a graph. We incorporate this
information using a graph- Laplacian based regularization which enforces the
target vectors to have a specific profile in terms of graph Fourier transform
coeffcients, for example lowpass or bandpass graph signals. We discuss how the
regularization affects the mean and the variance in the prediction output. In
particular, we prove that the predictive variance of the GPG is strictly
smaller than the conventional Gaussian process (GP) for any non-trivial graph.
We validate our concepts by application to various real-world graph signals.
Our experiments show that the performance of the GPG is superior to GP for
small training data sizes and under noisy training.
