The problem data are a graph with labels on a small subset of the vertices. Many methods to fill in the missing values are based on smoothing via graph Laplacians. We show that those are algebraicly equivalent to kriging with a fixed and somewhat arbitrary covariance. On a social network, the same covariance would be used for age, income and gender. It is more reasonable to tune the covariance based on the observed response values, even if those are relatively few. We see improved performance in hold-out experiments.

This is joint work with Ya Xu and Justin Dyer. It is based largely on Ya Xu's dissertation.