# Large Graph Signal Denoising with Application to Differential Privacy

arXiv: https://arxiv.org/abs/2209.02043 · HTML: https://mlsanity.com/paper/2209.02043/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 49 references that are in the map.
- First posted on arXiv 5 Sep 2022.

## Builds on (most cited first, 19 of 19)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [A Review of Relational Machine Learning for Knowledge Graphs](https://mlsanity.com/paper/1503.00759/) (2015)
- [Deep Convolutional Networks on Graph-Structured Data](https://mlsanity.com/paper/1506.05163/) (2015)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks](https://mlsanity.com/paper/1611.01890/) (2016)
- [Graph signal processing for machine learning: A review and new perspectives](https://mlsanity.com/paper/2007.16061/) (2020)
- [Trend Filtering on Graphs](https://mlsanity.com/paper/1410.7690/) (2014)
- [Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison (Extended Cut)](https://mlsanity.com/paper/2006.11220/) (2020)
- [Efficient Implementations of the Generalized Lasso Dual Path Algorithm](https://mlsanity.com/paper/1405.3222/) (2014)
- [Understanding Graph Neural Networks from Graph Signal Denoising Perspectives](https://mlsanity.com/paper/2006.04386/) (2020)
- [Irregularity-Aware Graph Fourier Transforms](https://mlsanity.com/paper/1802.10220/) (2018)
- [Construction of Tight Frames on Graphs and Application to Denoising](https://mlsanity.com/paper/1408.4012/) (2014)
- [Multiresolution Representations for Piecewise-Smooth Signals on Graphs](https://mlsanity.com/paper/1803.02944/) (2018)
- [Data-driven Thresholding in Denoising with Spectral Graph Wavelet Transform](https://mlsanity.com/paper/1906.01882/) (2019)

## Abstract (arXiv)

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.