  Geometric data analysis relies on graphs that are either given as input or
inferred from data. These graphs are often treated as "correct" when solving
downstream tasks such as graph signal denoising. But real-world graphs are
known to contain missing and spurious links. Similarly, graphs inferred from
noisy data will be perturbed. We thus define and study the problem of graph
denoising, as opposed to graph signal denoising, and propose an approach based
on link-prediction graph neural networks. We focus in particular on
neighborhood graphs over point clouds sampled from low-dimensional manifolds,
such as those arising in imaging inverse problems and exploratory data
analysis. We illustrate our graph denoising framework on regular synthetic
graphs and then apply it to single-particle cryo-EM where the measurements are
corrupted by very high levels of noise. Due to this degradation, the initial
graph is contaminated by noise, leading to missing or spurious edges. We show
that our proposed graph denoising algorithm improves the state-of-the-art
performance of multi-frequency vector diffusion maps.
