# Graph sampling with determinantal processes

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

## Key facts

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

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

- [Sampling and Uniqueness Sets in Graphon Signal Processing](https://mlsanity.com/paper/2401.06279/) (2024)
- [Bypassing orthogonalization in the quantum DPP sampler](https://mlsanity.com/paper/2503.05906/) (2025)
- [On the Impact of Downstream Tasks on Sampling and Reconstructing Noisy Graph Signals](https://mlsanity.com/paper/2509.10874/) (2025)
- [Multilevel Graph Wavelet Compressed Sensing with Scale-Aware Neural Recovery](https://mlsanity.com/paper/2607.20857/) (2026)

## Abstract (arXiv)

We present a new random sampling strategy for k-bandlimited signals defined on graphs, based on determinantal point processes (DPP). For small graphs, ie, in cases where the spectrum of the graph is accessible, we exhibit a DPP sampling scheme that enables perfect recovery of bandlimited signals. For large graphs, ie, in cases where the graph's spectrum is not accessible, we investigate, both theoretically and empirically, a sub-optimal but much faster DPP based on loop-erased random walks on the graph. Preliminary experiments show promising results especially in cases where the number of measurements should stay as small as possible and for graphs that have a strong community structure. Our sampling scheme is efficient and can be applied to graphs with up to 106 nodes.