LINEAR-TIME SAMPLING ON SIGNED GRAPHS VIA GERSHGORIN DISC PERFECT ALIGNMENT

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 C, we first employ graphical lasso to learn a sparse inverse matrix L, interpreted as generalized graph Laplacian for signed graph G. We then propose a fast signed graph sampling scheme containing three steps: i) augment G to a balanced graph G_B, ii) align all Gershgorin disc left-ends of corresponding Laplacian L_B at smallest eigenvalue via similarity transform L_p = S*L_B* S^{-1} leveraging a recent linear algebra theory called Gershgorin disc perfect alignment (GDPA), and iii) perform sampling on L_p using a previous fast Gershgorin disc alignment (GDA) sampling scheme. Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on two political voting datasets.