A Bayesian Perspective on Uncertainty Quantification for Estimated Graph Signals

Lennard Rompelberg, Michael T. Schaub

Abstract: We present a Bayesian perspective on quantifying the uncertainty of graph signals estimated or reconstructed from imperfect observations. We show that many conventional methods of graph signal estimation, reconstruction and imputation, can be reinterpreted as finding the mean of a posterior Gaussian distribution, with a covariance matrix shaped by the graph structure. In this perspective, assumptions of signal smoothness as well as bandlimitedness are naturally expressible as the choice of certain prior distributions; noisy, noise-free or partial observations are expressible in terms of certain likelihood models. In addition to providing a point estimate, as most standard estimation strategies do, our probabilistic framework enables us to characterize the shape of the estimated signal distribution around the estimate in terms of the posterior covariance matrix.

Introduction

In Graph Signal Processing (GSP), researchers frequently analyze data residing on the nodes of complex networks, such as temperature readings from sensor arrays or traffic speeds across urban road grids. Real-world observations of these signals are rarely perfect; they are typically corrupted by noise or restricted to a small subset of nodes.

To address these challenges, standard GSP techniques employ estimation and imputation methods that rely on structural assumptions, such as signal smoothness across connected nodes or bandlimitedness in the graph spectral domain. While these methods effectively produce a "best guess" (a point estimate), they generally fail to quantify the confidence of that guess. Furthermore, uncertainty in a graph is not a uniform scalar; it is highly structured and varies based on the graph's topology and the sampling strategy. This work addresses this gap by providing a formal framework for structured uncertainty quantification in GSP.

Methodology: A Bayesian Framework

This research reframes standard graph signal estimation as a Bayesian inference problem. By doing so, we demonstrate that conventional point estimates are mathematically equivalent to the means of posterior Gaussian distributions. This perspective allows for the use of the posterior covariance matrix to quantify structured, directional uncertainty.

Priors and Likelihoods

Standard GSP assumptions are encoded as prior probability distributions:

  • Smoothness: Modeled as a Gaussian prior shaped by the graph Laplacian, effectively treating the signal as a Gaussian Markov Random Field.
  • Bandlimitedness: Modeled as a uniform distribution over a specific signal subspace.

Observations are modeled through likelihood functions. Noisy observations utilize Gaussian likelihoods, while partial observations are handled via a sampling matrix. By combining these components, we derive the posterior Gaussian distribution.

Bayesian estimation of graph signals: The top row shows the true, observed, and estimated signals. The bottom plot illustrates how the prior and likelihood combine to form the posterior distribution for nodes a and b.

To maintain mathematical consistency when dealing with strict constraints—such as perfectly noise-free observations or strict subspace limits—we introduce a limit-based approach (e.g., $\epsilon \to 0$). This ensures that the distributions remain well-defined even when the resulting matrices would otherwise be non-invertible.

Experimental Evaluation

We evaluated this framework using the Minnesota Traffic Network, a standard benchmark in GSP. We generated synthetic signals based on a Laplacian smoothness prior and simulated noisy, partial observations to test the predictive power of our uncertainty quantification.

Comparison of empirical Node-Wise Mean Square Error (left) and theoretical Node-wise Uncertainty (right) on the Minnesota traffic network.

The experiments demonstrated that the theoretical node-wise uncertainty—specifically the diagonal elements of the posterior covariance matrix—closely aligns with the empirical Mean Square Error (MSE) of the estimates. A key finding is the high variance in confidence across the network: two nodes may have identical estimated values but vastly different levels of uncertainty depending on their topological position and proximity to sampled nodes.

Key Insights and Discussion

This Bayesian reinterpretation yields several critical insights for the GSP community:

  1. Optimization as Inference: The common practice of Laplacian Quadratic Regularization (penalizing signal "roughness") is exactly equivalent to finding the posterior mean under a Laplacian-based prior.
  2. Directional Uncertainty: Uncertainty is not merely a scalar value per node but exists in specific "directions" within the signal space, defined by the eigenvectors of the graph Laplacian. For instance, a prior based on smoothness provides no information regarding a global constant shift (the all-ones eigenvector).
  3. Perfect Reconstruction as a Limit Case: The framework shows that "perfect reconstructibility" occurs when the posterior covariance matrix shrinks to zero in all directions, unifying sampling theorems with probabilistic inference.

Conclusion and Future Work

While this work successfully visualizes node-wise uncertainty, the full posterior covariance matrix contains even richer information regarding the correlated uncertainty between connected nodes. Future research should focus on integrating this full covariance structure into downstream machine learning tasks. By accounting for the exact shape of uncertainty, algorithms can avoid overconfidence when processing heavily imputed or noisy graph signals.

Summary updated

BibTeX
@inproceedings{rompelberg2025bayesian,
  author = {Lennard Rompelberg and Michael T. Schaub},
  title = {{A Bayesian Perspective on Uncertainty Quantification for Estimated Graph Signals}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2025},
  doi = {10.1109/icassp49660.2025.10889783},
}
Figure