# Discrete Signal Processing on Graphs: Sampling Theory

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

## Key facts

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

## Built on by (most cited first, 30 of 34)

- [ClassEval: A Manually-Crafted Benchmark for Evaluating LLMs on Class-level Code Generation](https://mlsanity.com/paper/2308.01861/) (2023)
- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond](https://mlsanity.com/paper/2101.05510/) (2021)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Spectrally Pruned Gaussian Fields with Neural Compensation](https://mlsanity.com/paper/2405.00676/) (2024)
- [SigMaNet: One Laplacian to Rule Them All](https://mlsanity.com/paper/2205.13459/) (2022)
- [FastMAC: Stochastic Spectral Sampling of Correspondence Graph](https://mlsanity.com/paper/2403.08770/) (2024)
- [Finite Impulse Response Filters for Simplicial Complexes](https://mlsanity.com/paper/2103.12587/) (2021)
- [Untrained Graph Neural Networks for Denoising](https://mlsanity.com/paper/2109.11700/) (2021)
- [Graph Signal Restoration Using Nested Deep Algorithm Unrolling](https://mlsanity.com/paper/2106.15910/) (2021)
- [Gegenbauer Graph Neural Networks for Time-varying Signal Reconstruction](https://mlsanity.com/paper/2403.19800/) (2024)
- [Convolutional Learning on Multigraphs](https://mlsanity.com/paper/2209.11354/) (2022)
- [Recovering Missing Node Features with Local Structure-based Embeddings](https://mlsanity.com/paper/2309.09068/) (2023)
- [Sampling and Uniqueness Sets in Graphon Signal Processing](https://mlsanity.com/paper/2401.06279/) (2024)
- [Graph CNN for Moving Object Detection in Complex Environments from Unseen Videos](https://mlsanity.com/paper/2207.06440/) (2022)
- [Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2208.08726/) (2022)
- [Matched Topological Subspace Detector](https://mlsanity.com/paper/2504.05892/) (2025)
- [Group Downsampling with Equivariant Anti-aliasing](https://mlsanity.com/paper/2504.17258/) (2025)
- [Graph Generative Models for Fast Detector Simulations in High Energy Physics](https://mlsanity.com/paper/2104.01725/) (2021)
- [Recovery of Missing Sensor Data by Reconstructing Time-varying Graph Signals](https://mlsanity.com/paper/2203.00418/) (2022)
- [Learning Decentralized Traffic Signal Controllers with Multi-Agent Graph Reinforcement Learning](https://mlsanity.com/paper/2311.03756/) (2023)
- [Towards joint graph learning and sampling set selection from data](https://mlsanity.com/paper/2412.09753/) (2024)
- [Task-Based Graph Signal Compression](https://mlsanity.com/paper/2110.12387/) (2021)
- [Inhomogeneous graph trend filtering via a l2,0 cardinality penalty](https://mlsanity.com/paper/2304.05223/) (2023)
- [A Poincar'e Inequality and Consistency Results for Signal Sampling on Large Graphs](https://mlsanity.com/paper/2311.10610/) (2023)
- [Dense Air Quality Maps Using Regressive Facility Location Based Drive By Sensing](https://mlsanity.com/paper/2201.09739/) (2022)
- [Graph Unfolding and Sampling for Transitory Video Keyframe Selection via Gershgorin Disc Alignment](https://mlsanity.com/paper/2408.01859/) (2024)
- [Sampling Transferable Graph Neural Networks with Limited Graph Information](https://mlsanity.com/paper/2410.16593/) (2024)
- [Reconstruction of Graph Signals on Complex Manifolds with Kernel Methods](https://mlsanity.com/paper/2505.15202/) (2025)
- [On the Impact of Downstream Tasks on Sampling and Reconstructing Noisy Graph Signals](https://mlsanity.com/paper/2509.10874/) (2025)

## Abstract (arXiv)

We propose a sampling theory for signals that are supported on either directed or undirected graphs. The theory follows the same paradigm as classical sampling theory. We show that perfect recovery is possible for graph signals bandlimited under the graph Fourier transform. The sampled signal coefficients form a new graph signal, whose corresponding graph structure preserves the first-order difference of the original graph signal. For general graphs, an optimal sampling operator based on experimentally designed sampling is proposed to guarantee perfect recovery and robustness to noise; for graphs whose graph Fourier transforms are frames with maximal robustness to erasures as well as for ErdHos-R'enyi graphs, random sampling leads to perfect recovery with high probability. We further establish the connection to the sampling theory of finite discrete-time signal processing and previous work on signal recovery on graphs. To handle full-band graph signals, we propose a graph filter bank based on sampling theory on graphs. Finally, we apply the proposed sampling theory to semi-supervised classification on online blogs and digit images, where we achieve similar or better performance with fewer labeled samples compared to previous work.