Graph Signal Restoration Using Nested Deep Algorithm Unrolling

Masatoshi Nagahama, Koki Yamada, Yuichi Tanaka, Stanley H. Chan, Yonina C. Eldar

TL;DR

This paper introduces "Graph Signal Restoration Using Nested Deep Algorithm Unrolling," a novel approach to cleaning up corrupted graph signals. By "unrolling" iterative optimization algorithms into deep neural networks, they achieve interpretable and efficient restoration with fewer trainable parameters than traditional graph neural networks, outperforming existing methods on denoising and interpolation tasks.

What Problem Does This Paper Address?

Graph signals, which represent data distributed across networks (like sensor networks, social connections, or brain activity), are often corrupted by noise or missing values during collection. Restoring these signals is crucial for accurate analysis. Existing methods fall into two camps: model-based approaches that rely on fixed, manually tuned parameters (limiting performance) and neural network-based methods that require vast datasets and can lack interpretability. This paper aims to bridge this gap by creating a restoration method that is both performant and interpretable, leveraging the strengths of both optimization and deep learning.

Methods

The core innovation lies in Deep Algorithm Unrolling (DAU). Instead of training a black-box neural network, the authors "unroll" the iterative steps of established optimization algorithms into distinct layers of a neural network. This makes the network's internal workings resemble the original optimization process, enhancing interpretability.

Two main methods are proposed:

  1. GraphDAU: This is a graph signal denoiser built by unrolling the Alternating Direction Method of Multipliers (ADMM). It specifically targets denoising and uses a combination of graph total variation and graph Laplacian regularization. Crucially, only graph-independent regularization parameters are made trainable, keeping the parameter count low.
  2. NestDAU: This is a more general restoration method for linear degradations. It builds upon GraphDAU by unrolling the Plug-and-Play ADMM (PnP-ADMM) algorithm. The key idea here is a "nested" structure: the GraphDAU denoiser is used as a submodule within each iteration (layer) of the unrolled PnP-ADMM. This allows for flexible handling of various degradation matrices (like those in interpolation) while maintaining interpretability.

Both methods benefit from acceleration techniques like precomputing eigendecompositions or using Chebyshev polynomial approximations to speed up computations.

Datasets

The paper uses a variety of datasets for training and evaluation:

  • Synthetic Data:
    • Community graphs with three clusters (for denoising and interpolation).
  • Random sensor graphs (for denoising).
  • Piecewise constant, piecewise smooth, and globally smooth signals are synthesized on these graphs.
  • Real-World Data:
    • U.S. temperature data from weather stations (for denoising and interpolation).
  • RGB color attributes from 3D point clouds (for denoising).

The datasets are split into training, validation, and testing sets. The authors emphasize that their methods require a small number of training data due to the limited number of trainable parameters.

Key Insights and Ideas

  • Algorithm Unrolling for Interpretability: By unrolling optimization algorithms, the authors create deep learning models that retain the interpretability of their underlying mathematical principles, unlike standard black-box neural networks.
  • Graph-Independent Parameters are Key: Making only graph-independent regularization parameters trainable significantly reduces the model's complexity and the amount of training data needed. This is a major advantage for graph-based tasks where graph structures can vary.
  • Nested Structure for Generalization: The NestDAU's hierarchical design, where a denoiser (GraphDAU) is embedded within a general restoration framework (PnP-ADMM), allows it to handle a wider range of restoration problems beyond simple denoising.
  • Transferability: The learned graph-independent parameters can be directly transferred to graphs of different sizes, a significant practical advantage.

Key Results

  • Superior Performance: Both GraphDAU and NestDAU consistently outperform existing methods (including spectral filters, ADMM, PnP-ADMM, GCNs, GUTF, and GUSC) in terms of Root Mean Squared Error (RMSE) for both denoising and interpolation tasks across various synthetic and real-world datasets.
  • Parameter Efficiency: The proposed methods have a significantly smaller number of trainable parameters compared to deep learning-based approaches like GCNs, making them easier and faster to train.
  • Robustness: The methods demonstrate robustness to small perturbations in graph structures.
  • Parameter Transferability: Experiments show that parameters trained on graphs of one size can be effectively applied to graphs of larger sizes, demonstrating the utility of graph-independent parameter learning.
  • Nested Structure Advantage: NestDAU, by incorporating GraphDAU, generally achieves better performance than GraphDAU alone, highlighting the effectiveness of the nested unrolling approach.

Limitations and Future Work

  • Unsupervised Learning: The current methods are trained in a supervised setting. Extending them to an unsupervised setting is suggested as future work.
  • Generalization to Other Tasks: While demonstrated for denoising and interpolation, the authors note that NestDAU is applicable to other restoration tasks like deblurring and point cloud super-resolution, suggesting further exploration in these areas.
  • Computational Complexity: While optimized, methods involving eigendecomposition can still have a high computational cost for very large graphs (O(N³)). Chebyshev polynomial approximation offers a more scalable alternative in such cases.

Summary updated

Abstract

Graph signal processing is a ubiquitous task in many applications such as sensor, social, transportation and brain networks, point cloud processing, and graph neural networks. Often, graph signals are corrupted in the sensing process, thus requiring restoration. In this paper, we propose two graph signal restoration methods based on deep algorithm unrolling (DAU). First, we present a graph signal denoiser by unrolling iterations of the alternating direction method of multiplier (ADMM). We then suggest a general restoration method for linear degradation by unrolling iterations of Plug-and-Play ADMM (PnP-ADMM). In the second approach, the unrolled ADMM-based denoiser is incorporated as a submodule, leading to a nested DAU structure. The parameters in the proposed denoising/restoration methods are trainable in an end-to-end manner. Our approach is interpretable and keeps the number of parameters small since we only tune graph-independent regularization parameters. We overcome two main challenges in existing graph signal restoration methods: 1) limited performance of convex optimization algorithms due to fixed parameters which are often determined manually. 2) large number of parameters of graph neural networks that result in difficulty of training. Several experiments for graph signal denoising and interpolation are performed on synthetic and real-world data. The proposed methods show performance improvements over several existing techniques in terms of root mean squared error in both tasks.
BibTeX
@article{nagahama2022graph,
  author = {Masatoshi Nagahama and Koki Yamada and Yuichi Tanaka and Stanley H. Chan and Yonina C. Eldar},
  title = {{Graph Signal Restoration Using Nested Deep Algorithm Unrolling}},
  journal = {IEEE Trans. Signal Process.},
  year = {2022},
  url = {https://openreview.net/forum?id=V4T5_tP95g7},
}
Figure