Graph Unrolling Networks: Interpretable Neural Networks for Graph Signal Denoising

Siheng Chen, Yonina C. Eldar, Lingxiao Zhao

TL;DR

This paper introduces "graph unrolling networks," a novel interpretable neural network framework for denoising graph signals. By "unrolling" traditional signal processing algorithms into neural network layers and employing a new "edge-weight-sharing graph convolution," these networks achieve superior denoising performance while offering better interpretability than existing methods.

What Problem Does This Paper Address?

Graph-structured data is ubiquitous, from social networks to biological systems. Processing this data often involves denoising noisy graph signals. Traditional methods rely on hand-crafted priors (like smoothness or sparsity) or pre-designed graph dictionaries, which may not be optimal or are difficult to define for complex real-world signals. While Graph Neural Networks (GNNs) offer powerful learning capabilities, they often lack interpretability and can be designed through trial-and-error. This paper bridges this gap by proposing a framework that combines the interpretability of signal processing algorithms with the learning power of neural networks for graph signal denoising.

Methods

The core innovation is graph unrolling networks. This approach takes an iterative graph signal denoising algorithm and "unrolls" each iteration into a single layer of a neural network. This creates a deep network where each layer corresponds to a step in the original algorithm, providing interpretability.

A key component is the edge-weight-sharing graph convolution. Unlike standard graph convolutions, this operation parameterizes edge weights using a trainable kernel function. Crucially, the parameters of this kernel are shared across all edges, making it efficient and allowing it to adapt flexibly to different graph structures and signals. This convolution is also designed to be permutation-equivariant, meaning the order of vertices doesn't affect the outcome.

The authors then propose two specific architectures:

  • Graph Unrolling Sparse Coding (GUSC): Unrolls the sparse coding denoising approach.
  • Graph Unrolling Trend Filtering (GUTF): Unrolls the trend filtering denoising approach.

These networks are trained in an unsupervised manner, using the noisy graph signals themselves as supervision.

Datasets

The paper evaluates its methods on both simulated and real-world datasets:

  • Simulated Datasets:
    • Smooth graph signals
    • Piecewise-constant graph signals
    • Piecewise-smooth graph signals
  • Real-world Datasets:
    • U.S. temperature data from weather stations.
  • NYC taxi-pickup data from the Manhattan street network.
  • Cora citation network dataset.

The paper does not introduce new benchmark datasets but uses existing ones to compare against established methods.

Key Insights and Ideas

  • Algorithm Unrolling for Interpretability: By mapping iterative denoising algorithms to neural network layers, the authors achieve a level of interpretability rarely seen in deep learning models for graph data. This allows understanding why the network makes certain denoising decisions.
  • Adaptive Priors through Learning: Instead of relying on fixed, hand-crafted priors, the edge-weight-sharing graph convolution learns appropriate priors directly from the data, making the denoising process more flexible and effective.
  • Efficiency via Weight Sharing: The edge-weight-sharing mechanism significantly reduces the number of trainable parameters compared to methods that learn each edge weight independently, making the approach scalable.
  • Robustness to Limited Data: The proposed methods show strong performance even when trained with a single noisy graph signal, highlighting the effectiveness of the learned implicit regularization.

Key Results

  • Superior Denoising Performance: Graph unrolling networks (GUSC and GUTF) consistently outperform conventional denoising algorithms (like Graph Laplacian Denoising and Graph Trend Filtering) and state-of-the-art GNNs across various simulated and real-world datasets and noise models.
  • Significant Error Reduction: For denoising a single smooth graph signal, the Normalized Mean Square Error (NMSE) of the proposed networks was 40-60% lower than Graph Laplacian Denoising and Graph Wavelets, respectively.
  • Adaptability to Noise: The methods maintain strong performance across different noise levels.
  • Limited Impact of Network Depth: The number of unrolling layers had a relatively small impact on denoising performance, suggesting that the core unrolling and convolution design is more critical.

Limitations and Future Work

  • Bernoulli Noise: While the proposed network performs surprisingly well on Bernoulli noise (typically used for binary classification), it's not explicitly designed for this noise model. The authors mention changing the loss function to accommodate this.
  • Computational Cost: While more efficient than some alternatives due to weight sharing, training these networks can still be computationally intensive, especially for very large graphs.
  • Hyperparameter Tuning: While the proposed methods are robust, some hyperparameters (like the threshold $\alpha$ in GUSC and GUTF) still require careful tuning, though the paper shows that a fixed threshold can be effective.

Future work could explore unrolling other iterative denoising algorithms, extending the framework to other graph signal processing tasks beyond denoising, and investigating more advanced kernel designs for the edge-weight-sharing convolution.

Summary updated

Abstract

We propose an interpretable graph neural network framework to denoise single or multiple noisy graph signals. The proposed graph unrolling networks expand algorithm unrolling to the graph domain and provide an interpretation of the architecture design from a signal processing perspective. We unroll an iterative denoising algorithm by mapping each iteration into a single network layer where the feed-forward process is equivalent to iteratively denoising graph signals. We train the graph unrolling networks through unsupervised learning, where the input noisy graph signals are used to supervise the networks. By leveraging the learning ability of neural networks, we adaptively capture appropriate priors from input noisy graph signals. A core component of graph unrolling networks is the edge-weight-sharing graph convolution operation, which parameterizes each edge weight by a trainable kernel function whose trainable parameters are shared by all the edges. The proposed convolution is permutation-equivariant and can flexibly adjust the edge weights to various graph signals. We further consider two special cases of this class of networks, graph unrolling sparse coding (GUSC) and graph unrolling trend filtering (GUTF), by unrolling sparse coding and trend filtering, respectively. To validate the proposed methods, we conduct extensive experiments on both real-world datasets and simulated datasets, and demonstrate that our methods have smaller denoising errors than conventional denoising algorithms and state-of-the-art graph neural networks. For denoising a single smooth graph signal, the normalized mean square error of the proposed networks is around 40% and 60% lower than that of graph Laplacian denoising and graph wavelets, respectively.
BibTeX
@article{chen2021graph,
  author = {Siheng Chen and Yonina C. Eldar and Lingxiao Zhao},
  title = {{Graph Unrolling Networks: Interpretable Neural Networks for Graph Signal Denoising}},
  journal = {IEEE Trans. Signal Process.},
  year = {2021},
  url = {https://openreview.net/forum?id=4474zkJgj92},
}
Figure