Risk-Aware Low-Pass Importance Sampling for Graph Signals Under Heterogeneous Noise and Model Mismatch

We study sampling of smooth/bandlimited graph signals when (i) sensor noise is heterogeneous across vertices and (ii) the graph used to design the sampler can be mildly mismatched to the true topology. We propose a risk-aware variant of local low-pass importance sampling that scores each vertex via a Hutchinson estimator of the diagonal of a graph heat-kernel operator and reweights the score by the inverse noise variance. The sampler selects without replacement according to these risk-aware scores. Reconstruction is performed with standard decoders (Tikhonov,Bandlimited, and a Chebyshev data-consistent smoother), enabling fair comparisons to prior work. On grid, Erdős–Rényi (ER), and Barabási–Albert (BA) graphs, our approach consistently reduces the normalized root- mean-square error (NRMSE) compared to random sampling; the gain increases with the sampling rate and persists under selection-graph mismatch. The method is simple, eigendecomposition-free, and scales linearly in the number of edges per Hutchinson probe.