  In the graph signal processing (GSP) literature, it has been shown that
signal-dependent graph Laplacian regularizer (GLR) can efficiently promote
piecewise constant (PWC) signal reconstruction for various image restoration
tasks. However, for planar image patches, like total variation (TV), GLR may
suffer from the well-known "staircase" effect. To remedy this problem, we
generalize GLR to gradient graph Laplacian regularizer (GGLR) that provably
promotes piecewise planar (PWP) signal reconstruction for the image
interpolation problem -- a 2D grid with random missing pixels that requires
completion. Specifically, we first construct two higher-order gradient graphs
to connect local horizontal and vertical gradients. Each local gradient is
estimated using structure tensor, which is robust using known pixels in a small
neighborhood, mitigating the problem of larger noise variance when computing
gradient of gradients. Moreover, unlike total generalized variation (TGV), GGLR
retains the quadratic form of GLR, leading to an unconstrained quadratic
programming (QP) problem per iteration that can be solved quickly using
conjugate gradient (CG). We derive the means-square-error minimizing weight
parameter for GGLR, trading off bias and variance of the signal estimate.
Experiments show that GGLR outperformed competing schemes in interpolation
quality for severely damaged images at a reduced complexity.
