Large Graph Signal Denoising with Application to Differential Privacy
- URL: http://arxiv.org/abs/2209.02043v1
- Date: Mon, 5 Sep 2022 16:32:54 GMT
- Title: Large Graph Signal Denoising with Application to Differential Privacy
- Authors: Elie Chedemail, Basile de Loynes, Fabien Navarro, Baptiste Olivier
- Abstract summary: We consider the case of signal denoising on graphs via a data-driven wavelet tight frame methodology.
We make it scalable to large graphs using Chebyshev-Jackson approximations.
A comprehensive performance analysis is carried out on graphs of varying size, from real and simulated data.
- Score: 2.867517731896504
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Graph Laplacian Learning with Exponential Family Noise [8.594140167290098]
We propose a versatile graph inference framework for learning from graph signals corrupted by exponential family noise.
Our framework generalizes previous methods from continuous smooth graph signals to various data types.
arXiv Detail & Related papers (2023-06-14T02:09:52Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing.
The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph.
For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
arXiv Detail & Related papers (2023-02-08T08:17:43Z) - Scaling Structured Inference with Randomization [64.18063627155128]
We propose a family of dynamic programming (RDP) randomized for scaling structured models to tens of thousands of latent states.
Our method is widely applicable to classical DP-based inference.
It is also compatible with automatic differentiation so can be integrated with neural networks seamlessly.
arXiv Detail & Related papers (2021-12-07T11:26:41Z) - Adaptive Gaussian Processes on Graphs via Spectral Graph Wavelets [3.2498534294827044]
We propose a process model using spectral graph wavelets, which can aggregate information at different scales.
We achieve scalability to larger graphs by using a spectrum-adaptive approximation of the filter function, which is designed to yield a low approximation error in dense areas of the graph spectrum.
arXiv Detail & Related papers (2021-10-25T09:25:04Z) - Predicting traffic signals on transportation networks using
spatio-temporal correlations on graphs [56.48498624951417]
This paper proposes a traffic propagation model that merges multiple heat diffusion kernels into a data-driven prediction model to forecast traffic signals.
We optimize the model parameters using Bayesian inference to minimize the prediction errors and, consequently, determine the mixing ratio of the two approaches.
The proposed model demonstrates prediction accuracy comparable to that of the state-of-the-art deep neural networks with lower computational effort.
arXiv Detail & Related papers (2021-04-27T18:17:42Z) - Learning Optical Flow from a Few Matches [67.83633948984954]
We show that the dense correlation volume representation is redundant and accurate flow estimation can be achieved with only a fraction of elements in it.
Experiments show that our method can reduce computational cost and memory use significantly, while maintaining high accuracy.
arXiv Detail & Related papers (2021-04-05T21:44:00Z) - Denoising Score Matching with Random Fourier Features [11.60130641443281]
We derive analytical expression for the Denoising Score matching using the Kernel Exponential Family as a model distribution.
The obtained expression explicitly depends on the noise variance, so the validation loss can be straightforwardly used to tune the noise level.
arXiv Detail & Related papers (2021-01-13T18:02:39Z) - Learning non-Gaussian graphical models via Hessian scores and triangular
transport [6.308539010172309]
We propose an algorithm for learning the Markov structure of continuous and non-Gaussian distributions.
Our algorithm SING estimates the density using a deterministic coupling, induced by a triangular transport map, and iteratively exploits sparse structure in the map to reveal sparsity in the graph.
arXiv Detail & Related papers (2021-01-08T16:42:42Z) - Multilayer Clustered Graph Learning [66.94201299553336]
We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph.
Experiments show that our method leads to a clustered clusters w.r.t.
We learn a clustering algorithm for solving clustering problems.
arXiv Detail & Related papers (2020-10-29T09:58:02Z) - Unrolling of Deep Graph Total Variation for Image Denoising [106.93258903150702]
In this paper, we combine classical graph signal filtering with deep feature learning into a competitive hybrid design.
We employ interpretable analytical low-pass graph filters and employ 80% fewer network parameters than state-of-the-art DL denoising scheme DnCNN.
arXiv Detail & Related papers (2020-10-21T20:04:22Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.