# Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jul 2019.

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

- [Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2208.08726/) (2022)
- [Towards joint graph learning and sampling set selection from data](https://mlsanity.com/paper/2412.09753/) (2024)
- [Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment](https://mlsanity.com/paper/2110.11420/) (2021)
- [Graph Unfolding and Sampling for Transitory Video Keyframe Selection via Gershgorin Disc Alignment](https://mlsanity.com/paper/2408.01859/) (2024)
- [On the Impact of Downstream Tasks on Sampling and Reconstructing Noisy Graph Signals](https://mlsanity.com/paper/2509.10874/) (2025)
- [Sampling Method for Generalized Graph Signals with Pre-selected Vertices via DC Optimization](https://mlsanity.com/paper/2509.14836/) (2025)
- [Lightweight Transformer for EEG Classification via Balanced Signed Graph Algorithm Unrolling](https://mlsanity.com/paper/2510.03027/) (2025)
- [Multilevel Graph Wavelet Compressed Sensing with Scale-Aware Neural Recovery](https://mlsanity.com/paper/2607.20857/) (2026)

## Abstract (arXiv)

Graph sampling set selection, where a subset of nodes are chosen to collect samples to reconstruct a smooth graph signal, is a fundamental problem in graph signal processing (GSP). Previous works employ an unbiased least-squares (LS) signal reconstruction scheme and select samples via expensive extreme eigenvector computation. Instead, we assume a biased graph Laplacian regularization (GLR) based scheme that solves a system of linear equations for reconstruction. We then choose samples to minimize the condition number of the coefficient matrix---specifically, maximize the smallest eigenvalue λmin. Circumventing explicit eigenvalue computation, we maximize instead the lower bound of λmin, designated by the smallest left-end of all Gershgorin discs of the matrix. To achieve this efficiently, we first convert the optimization to a dual problem, where we minimize the number of samples needed to align all Gershgorin disc left-ends at a chosen lower-bound target T. Algebraically, the dual problem amounts to optimizing two disc operations: i) shifting of disc centers due to sampling, and ii) scaling of disc radii due to a similarity transformation of the matrix. We further reinterpret the dual as an intuitive disc coverage problem bearing strong resemblance to the famous NP-hard set cover (SC) problem. The reinterpretation enables us to derive a fast approximation scheme from a known SC error-bounded approximation algorithm. We find an appropriate target T efficiently via binary search. Extensive simulation experiments show that our disc-based sampling algorithm runs substantially faster than existing sampling schemes and outperforms other eigen-decomposition-free sampling schemes in reconstruction error.