  Novel Monte Carlo estimators are proposed to solve both the Tikhonov
regularization (TR) and the interpolation problems on graphs. These estimators
are based on random spanning forests (RSF), the theoretical properties of which
enable to analyze the estimators' theoretical mean and variance. We also show
how to perform hyperparameter tuning for these RSF-based estimators. TR is a
component in many well-known algorithms, and we show how the proposed
estimators can be easily adapted to avoid expensive intermediate steps in
generalized semi-supervised learning, label propagation, Newton's method and
iteratively reweighted least squares. In the experiments, we illustrate the
proposed methods on several problems and provide observations on their run
time.
