Graph signal processing in the presence of topology uncertainties

The goal of this paper is to expand graph signal processing tools to deal with cases where the graph topology is not perfectly known. Assuming that the uncertainty affects only a limited number of edges, we make use of small perturbation analysis to derive closed form expressions instrumental to formulate signal processing algorithms that are resilient to imperfect knowledge of the graph topology. Then, we formulate a Bayesian approach to estimate the presence/absence of uncertain edges based only on the observed data and on the statistics of the data. Finally, we exploit our perturbation analysis to analyze clustering and semi-supervised learning algorithms. Numerical tests confirm the benefits of our perturbation-aware methods.