Wavelets on Graphs via Deep Learning

Raif M. Rustamov, Leonidas J. GuibasNeurIPS 2013 · OpenReview

Introduction

This paper introduces a machine learning framework to "learn" graph wavelets tailored to specific classes of signals. By framing the classic "lifting scheme" as a deep auto-encoder, the authors create an unsupervised, linear transform that achieves significantly better sparsity and reconstruction than standard graph wavelets while remaining computationally efficient.

The Challenge of Graph Signals

Signal processing on graphs—such as social networks, sensor grids, or 3D meshes—is challenging because graphs lack the regular, grid-like structure of pixels in an image. While traditional wavelets are designed for regular grids, existing "graph wavelets" are usually fixed; their shape is determined entirely by the graph's topology (the connections between nodes).

The authors argue that this fixed approach is a missed opportunity. If you are processing specific types of data, like temperature readings or facial images, your wavelets should adapt to the underlying patterns in that data, not just the graph's structure. The challenge lies in achieving this adaptability while maintaining essential wavelet properties: efficiency, invertibility, locality, and multi-scale representation.

Bridging Signal Processing and Deep Learning

To solve this, the authors bridge the gap between signal processing and deep learning using the Lifting Scheme.

Lifting Scheme Block Diagram
  1. The Lifting Scheme as an Auto-encoder: The lifting scheme is a modular method for building wavelets using "Predict" ($P$) and "Update" ($U$) steps. The authors observed that these steps are structurally identical to the encoding and decoding layers of an auto-encoder network.
  2. Unsupervised Learning for Sparsity: Instead of training on labeled data, the network is trained to minimize a sparsity surrogate (an $L_1$-like penalty) on the "detail coefficients." In auto-encoder terms, they minimize reconstruction error while forcing that error to be sparse, naturally finding the most efficient basis for the data.
  3. Mathematical Constraints: To ensure the result is a valid wavelet transform, specific constraints are imposed. They tie the weights of the Update and Predict operators ($U \approx P^T$) to preserve the signal's integral (vanishing moments) and restrict the "receptive field" so nodes only predict immediate neighbors (locality).
  4. Greedy Layer-wise Training: The transform is trained one level at a time, from the finest scale to the coarsest, similar to early deep belief networks.

Key Insights and Performance

The framework was evaluated on synthetic data (cycle graphs) and real-world datasets, including the Minnesota road network, US temperature data, and the Extended Yale Face Database B.

  • Superior Sparsity: On the Minnesota road network and US temperature data, the learned wavelets achieved lower reconstruction errors with fewer coefficients compared to standard Haar wavelets.
  • Outperforming Classical Image Wavelets: When applied to facial images (treated as signals on a grid graph), the learned graph wavelets outperformed the industry-standard CDF 9/7 wavelet filterbanks (used in JPEG 2000) in both Peak Signal-to-Noise Ratio (PSNR) and Structural Similarity Index (SSIM).
  • Linearity and Efficiency: Unlike many non-linear deep learning models, this framework produces a linear transform after training. This makes it mathematically predictable and extremely fast to apply, running in linear time and memory ($O(N)$) relative to the graph size.
  • Semi-Supervised Learning: The learned wavelets were successfully used to predict temperatures at unmeasured locations, outperforming Laplacian regularized least squares and harmonic interpolation.

Limitations and Future Directions

A primary limitation of this method is its reliance on a pre-existing hierarchical partitioning of the graph (e.g., via spectral clustering).

Hierarchical Graph Partitioning

The quality of the learned wavelets is somewhat sensitive to how well this initial partitioning is performed. Future work could explore randomizing the graph partitioning or using "bagging" techniques to create more robust, over-complete dictionaries. Additionally, while linearity benefits efficiency, introducing non-linearities could potentially capture even more complex signal patterns, albeit at the cost of the classical wavelet interpretation.

Summary updated

Abstract

An increasing number of applications require processing of signals defined on weighted graphs. While wavelets provide a flexible tool for signal processing in the classical setting of regular domains, the existing graph wavelet constructions are less flexible -- they are guided solely by the structure of the underlying graph and do not take directly into consideration the particular class of signals to be processed. This paper introduces a machine learning framework for constructing graph wavelets that can sparsely represent a given class of signals. Our construction uses the lifting scheme, and is based on the observation that the recurrent nature of the lifting scheme gives rise to a structure resembling a deep auto-encoder network. Particular properties that the resulting wavelets must satisfy determine the training objective and the structure of the involved neural networks. The training is unsupervised, and is conducted similarly to the greedy pre-training of a stack of auto-encoders. After training is completed, we obtain a linear wavelet transform that can be applied to any graph signal in time and memory linear in the size of the graph. Improved sparsity of our wavelet transform for the test signals is confirmed via experiments both on synthetic and real data.
BibTeX
@inproceedings{rustamov2013wavelets,
  author = {Raif M. Rustamov and Leonidas J. Guibas},
  title = {{Wavelets on Graphs via Deep Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=ByNiT_ZdbH},
}
Figure