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

Area of Science:

• Graph Signal Processing (GSP)
• Machine Learning
• Linear Algebra

Background:

• Graph signal processing typically uses positive graphs for correlations.
• Real-world data often exhibits anti-correlations, requiring signed graph models.
• Existing sampling methods are limited to positive graphs.

Purpose of the Study:

• To develop the first linear-time method for sampling signed graphs.
• To enable effective graph filtering and signal processing on datasets with anti-correlations.
• To improve signal interpolation accuracy from sampled nodes.

Main Methods:

• Learning a sparse inverse covariance matrix as a signed graph Laplacian.
• Approximating the graph with a balanced signed graph in linear time.
• Employing Gershgorin Disc Perfect Alignment (GDPA) and Gershgorin Disc Alignment Sampling (GDAS) for node selection.

Main Results:

• The proposed method achieves linear-time complexity for signed graph sampling.
• The signed graph sampling method demonstrates superior performance over positive graph sampling schemes.
• Experimental results validate the effectiveness on datasets with anti-correlations.

Conclusions:

• The developed method provides a significant advancement for graph signal processing on signed graphs.
• This approach broadens the applicability of GSP to datasets with complex correlation structures.
• The technique offers a more accurate way to sample and interpolate signals from anti-correlated data.