Robust graph signal processing in the presence of uncertainties on graph topology

In this paper we address the problem of analyzing signals defined over graphs whose topology is known only with some uncertainty about the presence/absence of some edges. This situation arises in all cases where edges are associated to a set of elements (vertices), but the association rule may be affected by errors. Building on a small perturbation analysis of the graph Laplacian matrix and assuming a simple probabilistic model for the addition/deletion of edges, we derive an analytical model to deal with the perturbation that this uncertainty induces on the observed signal. Using this model, we propose different strategies to recover the underlying signal exploiting statistical knowledge about the probability of the presence/absence of the edges1.