  We propose a kernel regression method to predict a target signal lying over a
graph when an input observation is given. The input and the output could be two
different physical quantities. In particular, the input may not be a graph
signal at all or it could be agnostic to an underlying graph. We use a training
dataset to learn the proposed regression model by formulating it as a convex
optimization problem, where we use a graph-Laplacian based regularization to
enforce that the predicted target is a graph signal. Once the model is learnt,
it can be directly used on a large number of test data points one-by-one
independently to predict the corresponding targets. Our approach employs
kernels between the various input observations, and as a result the kernels are
not restricted to be functions of the graph adjacency/Laplacian matrix. We show
that the proposed kernel regression exhibits a smoothing effect, while
simultaneously achieving noise-reduction and graph-smoothness. We then extend
our method to the case when the underlying graph may not be known apriori, by
simultaneously learning an underlying graph and the regression coefficients.
Using extensive experiments, we show that our method provides a good prediction
performance in adverse conditions, particularly when the training data is
limited in size and is noisy. In graph signal reconstruction experiments, our
method is shown to provide a good performance even for a highly
under-determined subsampling.
