Adaptive Graph Normalized Sign Algorithm

Ercan Engin Kuruoglu, PhD Cantab, Prof, Ieee Fellow, Changran Peng, Yi Yan, Ercan E. KuruogluCai 2024 · DOI

TL;DR

This paper introduces the Adaptive Graph Normalized Sign (GNS) algorithm, a novel approach for predicting graph signals corrupted by impulsive noise and missing data. By incorporating spectral normalization into the efficient Graph-Sign algorithm, GNS achieves significantly faster convergence and improved prediction accuracy compared to existing methods, particularly in real-world scenarios like temperature forecasting.

What Problem Does This Paper Address?

Predicting signals that evolve over time on a graph structure (graph signals) is crucial for many applications, such as traffic forecasting or weather prediction. However, these predictions become challenging when the data is noisy, especially with "impulsive" noise (sudden, large spikes) and when some data points are missing. Traditional methods often struggle with these conditions. While existing graph signal processing (GSP) algorithms like Graph Least Mean Squares (GLMS) and its normalized version (GNLMS) exist, they assume Gaussian noise and can become unstable with impulsive noise. Other algorithms like Graph Normalized LMP (GNLMP) and Graph-Sign (G-Sign) address impulsive noise, with G-Sign offering efficiency by avoiding explicit noise distribution assumptions. However, G-Sign lacks a normalization term that has proven beneficial in other algorithms for speeding up convergence. This paper aims to bridge this gap by introducing a normalized version of the G-Sign algorithm.

Methods

The core innovation of this paper is the Adaptive Graph Normalized Sign (GNS) algorithm. It builds upon the Graph-Sign (G-Sign) algorithm, which uses an $\ell_1$-norm optimization to handle impulsive noise efficiently. The GNS algorithm enhances G-Sign by introducing a spectral domain normalization term into the update process. This normalization is derived by approximating the update in the spectral domain (using the Graph Fourier Transform) and then deriving a normalization factor that aims to improve convergence speed and reduce estimation error. The paper uses a fractional lower order moment (FLOM) to model the noise statistics for this approximation. The resulting update equation for GNS incorporates this normalization factor, leading to faster convergence and better prediction performance.

Datasets

The paper evaluates the proposed GNS algorithm using a real-world dataset of 95 hourly temperatures collected from 197 weather stations in the US. This dataset is used to construct an 8-nearest-neighbor graph. The experiments simulate missing data by only allowing signals from 130 nodes to be observed, mimicking realistic scenarios.

Key Insights and Ideas

  • Normalization is Key for Speed: The paper demonstrates that adding a spectral normalization term to the already efficient G-Sign algorithm significantly boosts its convergence speed. This highlights the importance of normalization, even when dealing with non-Gaussian noise.
  • GNS Outperforms G-Sign: The proposed GNS algorithm consistently shows better prediction performance than the original G-Sign algorithm across various noise levels.
  • Robustness to Impulsive Noise: Like G-Sign, GNS is designed to be robust to impulsive noise, outperforming traditional methods like GLMS which struggle in such conditions.
  • Practical Applicability: The successful application to real-world temperature data underscores the practical utility of GNS for time-varying graph signal prediction.

Key Results

  • Faster Convergence: GNS converges approximately twice as fast as G-Sign, requiring about half the number of iterations to reach a steady state.
  • Improved Prediction Accuracy: In terms of spatial Mean Squared Error (MSE), GNS demonstrates better prediction performance than G-Sign under various $\alpha$ settings (representing different levels of noise impulsiveness). For instance, with $\alpha=1.1$, GNS achieves a lower spatial MSE compared to G-Sign.
  • Robustness to Noise: The paper shows that GNS, G-Sign, and GLMP are relatively unaffected by changes in the noise parameter $\alpha$, indicating their robustness to impulsive noise, unlike GLMS which performs poorly.

Limitations and Future Work

  • Computational Cost of Normalization: The paper notes that calculating the normalization term $M[t]$ in each step can introduce extra computational costs. While an approximation is used, this is a potential area for further optimization.
  • Further Exploration of Normalization: The authors suggest that investigating other forms of normalization or adaptive strategies could lead to further improvements.
  • Generalizability: While tested on temperature data, exploring GNS's performance on other types of graph signals and applications would be valuable.

Summary updated

BibTeX
@inproceedings{fellow2024adaptive,
  author = {Ercan Engin Kuruoglu, PhD Cantab, Prof, IEEE Fellow and Changran Peng and Yi Yan and Ercan E. Kuruoglu},
  title = {{Adaptive Graph Normalized Sign Algorithm}},
  booktitle = {Cai},
  year = {2024},
  doi = {10.1109/cai59869.2024.00027},
}
Figure