# Compressive Recovery of Signals Defined on Perturbed Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 39 references that are in the map.
- First posted on arXiv 12 Feb 2024.

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

- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Network Topology Inference from Spectral Templates](https://mlsanity.com/paper/1608.03008/) (2016)
- [Adaptive Graph-based Total Variation for Tomographic Reconstructions](https://mlsanity.com/paper/1610.00893/) (2016)
- [Sparse linear regression from perturbed data](https://mlsanity.com/paper/2003.14389/) (2020)
- [When is Network Lasso Accurate?](https://mlsanity.com/paper/1704.02107/) (2017)
- [Contact Tracing Enhances the Efficiency of COVID-19 Group Testing](https://mlsanity.com/paper/2011.14186/) (2020)
- [Reducing Basis Mismatch in Harmonic Signal Recovery via Alternating Convex Search](https://mlsanity.com/paper/1406.5231/) (2014)
- [Steerable Discrete Cosine Transform](https://mlsanity.com/paper/1610.09152/) (2016)

## Abstract (arXiv)

Recovery of signals with elements defined on the nodes of a graph, from compressive measurements is an important problem, which can arise in various domains such as sensor networks, image reconstruction and group testing. In some scenarios, the graph may not be accurately known, and there may exist a few edge additions or deletions relative to a ground truth graph. Such perturbations, even if small in number, significantly affect the Graph Fourier Transform (GFT). This impedes recovery of signals which may have sparse representations in the GFT bases of the ground truth graph. We present an algorithm which simultaneously recovers the signal from the compressive measurements and also corrects the graph perturbations. We analyze some important theoretical properties of the algorithm. Our approach to correction for graph perturbations is based on model selection techniques such as cross-validation in compressed sensing. We validate our algorithm on signals which have a sparse representation in the GFT bases of many commonly used graphs in the network science literature. An application to compressive image reconstruction is also presented, where graph perturbations are modeled as undesirable graph edges linking pixels with significant intensity difference. In all experiments, our algorithm clearly outperforms baseline techniques which either ignore the perturbations or use first order approximations to the perturbations in the GFT bases.