Wavelets on Graphs via Deep Learning
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.
Summary: The authors present a method for constructing 
      wavelets on weighted graphs that can adapt to a class of signals. The 
      approach uses the lifting scheme and by connecting this scheme to a deep 
      auto-encoder network, the authors are able to perform unsupervised 
      training similar to the pre-training of a stack of auto-encoders. The 
      approach is linear in the size of the graph. The authors explore the 
      performance of the wavelet construction approach through application to 
      several data sets. Quality: The authors provide an elegant 
      approach for taking into account the class of signals when forming 
      wavelets on a graph. Most constructions are based solely on the graph 
      structure, and those few methods that do allow adaptivity based on the 
      signals [19,21] have significant limitations. The technical 
      development is clearly described, novel, and leads to an efficient 
      algorithm that produces wavelets with desirable properties. The 
      partitioning approach is described very briefly and there is almost no 
      discussion of how sensitive the approach is to the partitioning method. 
      The spectral clustering algorithm of [20] has some limitations 
      (performance being poor for some kinds of graphs) and it would be nice to 
      see more information about how sensitive the overall wavelet construct is 
      to the partitioning scheme. For their results on irregular graphs, 
      where I think the construction is of most interest, the authors do not 
      make a comparison to compression or reconstruction using any other type of 
      graph wavelet. Instead, the comparison is to (somewhat dated) learning 
      techniques that are suited to manifold analysis. This constitutes one 
      significant weakness of the paper. Clarity: The paper is very well 
      written and the development is easy to follow. As discussed above, more 
      detail on some of the Originality: The authors provide a new 
      method for constructing wavelets on graphs that has the important ability 
      to adapt to the class of functions that the wavelets will be used to 
      represent. The method is highly original. Significance: The paper 
      represents a useful contribution in the field of wavelets and 
      multiresolution analysis on graphs, a field of growing interest due to the 
      numerous potential applications. I consider that the signal adaptivity, 
      while preserving linearity and efficiency of construction, represents a 
      significant advance.