Bayesian Design of Sampling Set for Bandlimited Graph Signals

Xuan Xie, Junhao Yu, Hui Feng, Bo Hu

Abstract

The design of sampling sets (DoS) for bandlimited graph signals (GS) is a critical problem in Graph Signal Processing (GSP). While traditional methods often ignore signal priors, this work introduces a Bayesian optimization framework that leverages stochastic prior knowledge. By analyzing the error metric matrix through Gershgorin discs and introducing a novel Bayesian graph coherence metric, we propose a heuristic algorithm that significantly improves reconstruction accuracy and noise robustness compared to non-Bayesian approaches.

Introduction

In many real-world applications, such as sensor networks or urban traffic monitoring, we aim to reconstruct a signal across an entire graph by sampling only a subset of nodes. This is known as the Design of Sampling (DoS) problem. Conventional non-Bayesian methods typically assume only that the signal is bandlimited—meaning it resides in a low-frequency subspace. However, these methods fail to exploit available statistical information, such as historical data or known variances across different spectral components. This paper addresses this gap by integrating a stochastic prior into the sampling strategy.

Bayesian Framework and Heuristic Design

The proposed Bayesian DoS framework defines utility functions based on Mutual Information (MI) and Mean Square Error (MSE) to identify the most informative nodes. A key technical contribution is the introduction of Bayesian Graph Coherence. While standard coherence measures the energy of a node in the signal subspace, the Bayesian version weights this energy by the variance of the signal's spectral components. This ensures that nodes corresponding to highly uncertain or high-variance components are prioritized for sampling.

To avoid the NP-hard complexity of direct optimization, we utilize a heuristic algorithm where nodes are sampled proportionally to their Bayesian graph coherence. This approach is further justified through Gershgorin disc analysis, which visualizes how prior knowledge effectively "shifts" the importance of nodes by altering the eigenvalue bounds of the error metric matrix.

Visual comparison of graph signals and the resulting sampling sets for non-Bayesian vs. Bayesian DoS.

Performance Evaluation

The framework was validated using synthetic simulations on random geometric graphs with 64 vertices. The signals were modeled as bandlimited with coefficients following a joint Gaussian distribution.

Key Results

  • Enhanced Accuracy: The Bayesian approach consistently achieves a lower Normalized Mean Square Error (NMSE) than non-Bayesian methods, particularly when the number of samples is small. The prior knowledge acts as a guide, allowing the system to focus limited sampling resources on the most critical unknowns.
  • Robustness to Noise: As shown in the performance analysis, Bayesian methods maintain stability even as observation noise increases. The stochastic prior serves as a buffer, preventing the estimation error from escalating as rapidly as it does in non-Bayesian relaxation or coherence-based methods.
  • Heuristic Efficiency: The proposed Bayesian coherence heuristic performs nearly as well as computationally expensive convex relaxation methods, making it suitable for large-scale network applications.
NMSE (dB) vs. noise variance, comparing Bayesian and non-Bayesian sampling strategies across different algorithms.

Conclusion and Future Work

By incorporating stochastic priors, the Bayesian Design of Sampling offers a more robust and accurate solution for graph signal reconstruction in noisy environments. While the current framework assumes known priors, future research will focus on estimating these priors directly from data and extending the optimization to specific tasks like node-level prediction rather than general reconstruction.

Summary updated

BibTeX
@inproceedings{xie2019bayesian,
  author = {Xuan Xie and Junhao Yu and Hui Feng and Bo Hu},
  title = {{Bayesian Design of Sampling Set for Bandlimited Graph Signals}},
  booktitle = {GlobalSIP},
  year = {2019},
  url = {https://openreview.net/forum?id=YbLgdOUGaS},
}
Figure