  In the graph signal processing (GSP) literature, graph Laplacian regularizer
(GLR) was used for signal restoration to promote piecewise smooth / constant
reconstruction with respect to an underlying graph. However, for signals slowly
varying across graph kernels, GLR suffers from an undesirable "staircase"
effect. In this paper, focusing on manifold graphs -- collections of uniform
discrete samples on low-dimensional continuous manifolds -- we generalize GLR
to gradient graph Laplacian regularizer (GGLR) that promotes planar / piecewise
planar (PWP) signal reconstruction. Specifically, for a graph endowed with
sampling coordinates (e.g., 2D images, 3D point clouds), we first define a
gradient operator, using which we construct a gradient graph for nodes'
gradients in sampling manifold space. This maps to a gradient-induced nodal
graph (GNG) and a positive semi-definite (PSD) Laplacian matrix with planar
signals as the 0 frequencies. For manifold graphs without explicit sampling
coordinates, we propose a graph embedding method to obtain node coordinates via
fast eigenvector computation. We derive the means-square-error minimizing
weight parameter for GGLR efficiently, trading off bias and variance of the
signal estimate. Experimental results show that GGLR outperformed previous
graph signal priors like GLR and graph total variation (GTV) in a range of
graph signal restoration tasks.
