  In nonparametric regression, it is common for the inputs to fall in a
restricted subset of Euclidean space. Typical kernel-based methods that do not
take into account the intrinsic geometry of the domain across which
observations are collected may produce sub-optimal results. In this article, we
focus on solving this problem in the context of Gaussian process (GP) models,
proposing a new class of Graph Laplacian based GPs (GL-GPs), which learn a
covariance that respects the geometry of the input domain. As the heat kernel
is intractable computationally, we approximate the covariance using
finitely-many eigenpairs of the Graph Laplacian (GL). The GL is constructed
from a kernel which depends only on the Euclidean coordinates of the inputs.
Hence, we can benefit from the full knowledge about the kernel to extend the
covariance structure to newly arriving samples by a Nystr\"{o}m type extension.
We provide substantial theoretical support for the GL-GP methodology, and
illustrate performance gains in various applications.
