  Over the last decade, signal processing on graphs has become a very active
area of research. Specifically, the number of applications, for instance in
statistical or deep learning, using frames built from graphs, such as wavelets
on graphs, has increased significantly. We consider in particular the case of
signal denoising on graphs via a data-driven wavelet tight frame methodology.
This adaptive approach is based on a threshold calibrated using Stein's
unbiased risk estimate adapted to a tight-frame representation. We make it
scalable to large graphs using Chebyshev-Jackson polynomial approximations,
which allow fast computation of the wavelet coefficients, without the need to
compute the Laplacian eigendecomposition. However, the overcomplete nature of
the tight-frame, transforms a white noise into a correlated one. As a result,
the covariance of the transformed noise appears in the divergence term of the
SURE, thus requiring the computation and storage of the frame, which leads to
an impractical calculation for large graphs. To estimate such covariance, we
develop and analyze a Monte-Carlo strategy, based on the fast transformation of
zero mean and unit variance random variables. This new data-driven denoising
methodology finds a natural application in differential privacy. A
comprehensive performance analysis is carried out on graphs of varying size,
from real and simulated data.
