Linear-Time Sampling on Signed Graphs Via Gershgorin Disc Perfect Alignment
Lists
Only you see this
Abstract
In graph signal processing (GSP), an appropriate underlying graph encodes pairwise (anti-)correlations of targeted discrete signals as edge weights. However, existing fast graph sampling schemes are designed and tested for positive graphs describing only positive correlations. In this paper, we show that for datasets with inherent strong anti-correlations, a suitable graph structure is instead a signed graph with both positive and negative edge weights, and in response, we propose a linear-time signed graph sampling method. Specifically, given an empirical covariance data matrix ${\mathbf{\bar C}}$, we first employ graphical lasso to learn a sparse inverse matrix $\mathcal{L}$, interpreted as a generalized graph Laplacian for signed graph $\mathcal{G}$. We then propose a fast signed graph sampling scheme containing three steps: i) augment $\mathcal{G}$ to a balanced graph ${\mathcal{G}_B}$, ii) align all Gershgorin disc left-ends of corresponding Laplacian ${\mathcal{L}_B}$ at smallest eigenvalue ${\lambda _{\min }}\left( {{\mathcal{L}_B}} \right)$ via similarity transform ${\mathcal{L}_p} = {\mathbf{S}}{\mathcal{L}_B}{{\mathbf{S}}^{ - 1}}$, leveraging a recent linear algebra theorem called Gershgorin disc perfect alignment (GDPA), and iii) perform sampling on ${\mathcal{L}_p}$ using a previous fast Gershgorin disc alignment sampling scheme (GDAS). Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on two political voting datasets.
BibTeX
@inproceedings{dinesh2022linear,
author = {Chinthaka Dinesh and Saghar Bagheri and Gene Cheung and Ivan V. Bajic},
title = {{Linear-Time Sampling on Signed Graphs Via Gershgorin Disc Perfect Alignment}},
booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
year = {2022},
doi = {10.1109/icassp43922.2022.9746424},
}Loading related content...