  We consider the problem of recovering random graph signals from nonlinear
measurements. For this case, closed-form Bayesian estimators are usually
intractable and even numerical evaluation of these estimators may be hard to
compute for large networks. In this paper, we propose a graph signal processing
(GSP) framework for random graph signal recovery that utilizes the information
of the structure behind the data. First, we develop the GSP-linear minimum
mean-squared-error (GSP-LMMSE) estimator, which minimizes the mean-squared
error (MSE) among estimators that are represented as an output of a graph
filter. The GSP-LMMSE estimator is based on diagonal covariance matrices in the
graph frequency domain, and thus, has reduced complexity compared with the
LMMSE estimator. This property is especially important when using the
sample-mean versions of these estimators that are based on a training dataset.
We then state conditions under which the low-complexity GSP-LMMSE estimator
coincides with the optimal LMMSE estimator. Next, we develop the approximated
parametrization of the GSP-LMMSE estimator by shift-invariant graph filters by
solving a weighted least squared (WLS) problem. We present three
implementations of the parametric GSP-LMMSE estimator for typical graph
filters. Parametric graph filters are more robust to outliers and to network
topology changes. In our simulations, we evaluate the performance of the
proposed GSP-LMMSE estimators for the problem of state estimation in power
systems, which can be interpreted as a graph signal recovery task. We show that
the proposed sample-GSP estimators outperform the sample-LMMSE estimator for a
limited training dataset and that the parametric GSP-LMMSE estimators are more
robust to topology changes in the form of adding/removing vertices/edges.
