# Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 67 references that are in the map.
- First posted on arXiv 18 Aug 2022.

## Builds on (most cited first, 25 of 25)

- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Discrete Signal Processing on Graphs: Frequency Analysis](https://mlsanity.com/paper/1307.0468/) (2013)
- [Graph Spectral Image Processing](https://mlsanity.com/paper/1801.04749/) (2018)
- [Discrete Signal Processing on Graphs: Sampling Theory](https://mlsanity.com/paper/1503.05432/) (2015)
- [Signal Recovery on Graphs: Variation Minimization](https://mlsanity.com/paper/1411.7414/) (2014)
- [Graph-Based Blind Image Deblurring From a Single Photograph](https://mlsanity.com/paper/1802.07929/) (2018)
- [Sampling of graph signals with successive local aggregations](https://mlsanity.com/paper/1504.04687/) (2015)
- [DELTACON: A Principled Massive-Graph Similarity Function](https://mlsanity.com/paper/1304.4657/) (2013)
- [Random sampling of bandlimited signals on graphs](https://mlsanity.com/paper/1511.05118/) (2015)
- [Graph Laplacian Regularization for Image Denoising: Analysis in the Continuous Domain](https://mlsanity.com/paper/1604.07948/) (2016)
- [Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2006.08816/) (2020)
- [Random Walk Graph Laplacian based Smoothness Prior for Soft Decoding of JPEG Images](https://mlsanity.com/paper/1607.01895/) (2016)
- [Greedy Sampling of Graph Signals](https://mlsanity.com/paper/1704.01223/) (2017)
- [Eigendecomposition-Free Sampling Set Selection for Graph Signals](https://mlsanity.com/paper/1809.01827/) (2018)
- [Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment](https://mlsanity.com/paper/1907.06179/) (2019)
- [Manifold Graph Signal Restoration using Gradient Graph Laplacian Regularizer](https://mlsanity.com/paper/2206.04245/) (2022)
- [Graph Fourier Transform with Negative Edges for Depth Image Coding](https://mlsanity.com/paper/1702.03105/) (2017)
- [Sampling and Reconstruction of Signals on Product Graphs](https://mlsanity.com/paper/1807.00145/) (2018)
- [Low-complexity Graph Sampling with Noise and Signal Reconstruction via Neumann Series](https://mlsanity.com/paper/1812.02109/) (2018)
- [Fast & Robust Image Interpolation using Gradient Graph Laplacian Regularizer](https://mlsanity.com/paper/2101.09951/) (2021)
- [Structured sampling and fast reconstruction of smooth graph signals](https://mlsanity.com/paper/1705.02202/) (2017)
- [A-Optimal Sampling and Robust Reconstruction for Graph Signals via Truncated Neumann Series](https://mlsanity.com/paper/1803.03353/) (2018)
- [Robust Semi-Supervised Graph Classifier Learning with Negative Edge Weights](https://mlsanity.com/paper/1611.04924/) (2016)
- [Reconstruction-Cognizant Graph Sampling using Gershgorin Disc Alignment](https://mlsanity.com/paper/1811.03206/) (2018)
- [Point Cloud Sampling via Graph Balancing and Gershgorin Disc Alignment](https://mlsanity.com/paper/2103.06153/) (2021)

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

- [Efficient Learning of Balanced Signed Graphs via Iterative Linear Programming](https://mlsanity.com/paper/2409.07794/) (2024)
- [Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming](https://mlsanity.com/paper/2506.01826/) (2025)
- [Lightweight Transformer for EEG Classification via Balanced Signed Graph Algorithm Unrolling](https://mlsanity.com/paper/2510.03027/) (2025)
- [Low-rank Updates in Slowly Time-varying Graphs for Spatial-Temporal Signal Interpolation](https://mlsanity.com/paper/2606.24011/) (2026)

## Abstract (arXiv)

A basic premise in graph signal processing (GSP) is that a graph encoding pairwise (anti-)correlations of the targeted signal as edge weights is exploited for graph filtering. However, existing fast graph sampling schemes are designed and tested only for positive graphs describing positive correlations. In this paper, we show that for datasets with strong inherent anti-correlations, a suitable graph contains both positive and negative edge weights. In response, we propose a linear-time signed graph sampling method centered on the concept of balanced signed graphs. Specifically, given an empirical covariance data matrix barbfC, we first learn a sparse inverse matrix (graph Laplacian) L corresponding to a signed graph G. We define the eigenvectors of Laplacian LB for a balanced signed graph GB -- approximating G via edge weight augmentation -- as graph frequency components. Next, we choose samples to minimize the low-pass filter reconstruction error in two steps. We first align all Gershgorin disc left-ends of Laplacian LB at smallest eigenvalue λmin(LB) via similarity transform Lp = S LB S-1, leveraging a recent linear algebra theorem called Gershgorin disc perfect alignment (GDPA). We then perform sampling on Lp using a previous fast Gershgorin disc alignment sampling (GDAS) scheme. Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on various datasets.