# A Probabilistic Interpretation of Sampling Theory of Graph Signals

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Mar 2015.

## Built on by (most cited first, 4 of 4)

- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [Sparse Graph Learning with Spectrum Prior for Deep Graph Convolutional Networks](https://mlsanity.com/paper/2202.13526/) (2022)
- [Towards joint graph learning and sampling set selection from data](https://mlsanity.com/paper/2412.09753/) (2024)
- [Sampling Method for Generalized Graph Signals with Pre-selected Vertices via DC Optimization](https://mlsanity.com/paper/2509.14836/) (2025)

## Abstract (arXiv)

We give a probabilistic interpretation of sampling theory of graph signals. To do this, we first define a generative model for the data using a pairwise Gaussian random field (GRF) which depends on the graph. We show that, under certain conditions, reconstructing a graph signal from a subset of its samples by least squares is equivalent to performing MAP inference on an approximation of this GRF which has a low rank covariance matrix. We then show that a sampling set of given size with the largest associated cut-off frequency, which is optimal from a sampling theoretic point of view, minimizes the worst case predictive covariance of the MAP estimate on the GRF. This interpretation also gives an intuitive explanation for the superior performance of the sampling theoretic approach to active semi-supervised classification.