GraphWavelets

Wavelet Filterbanks for Graph based Data

In this work we propose the construction of wavelet filterbanks for analyzing functions defined on the vertices of any arbitrary finite weighted undirected graph. These graph based functions are referred to as graph-signals as we build a framework in which many concepts from the classical signal processing domain, such as Fourier decomposition, signal filtering and downsampling can be extended to graph domain.

Graphs provide a very flexible model for representing data in many domains. Many networks such as biological networks, social networks and sensor networks etc. have a natural interpretation in terms of finite graphs with vertices as data-sources and links established based on connectivity, similarity, ties etc. The data on these graphs can be visualized as a finite collection of samples termed as graph-signals. For example, graphical models can be used to represent irregularly sampled datasets in Euclidean spaces or missing samples in regular grids. In many machine learning applications multi-dimensional datasets can be represented as point-clouds of vectors and links are established between data sources based on the distance between their feature-vectors. In computer vision, meshes are polygon graphs in 2D/3D space and the attributes of the sampled points (coordinates, intensity etc) constitute the graph-signals. The graph-signal formulation can also be used to solve systems of partial differential equations using finite element analysis (grid based solution).

Mostly, the sizes (number of nodes) of the graphs in these applications are enormous, which present computational and technical challenges for the purpose of storage, analysis etc. In some other applications such as wireless sensor-networks, the data-exchanges between far-off nodes can be expensive (bandwidth , latency , energy constraints issues). Therefore, instead of operating on the original graph, it would be desirable to find and operate on smaller graphs with fewer nodes and data representing a smooth approximation of the original data. Moreover, such systems need to employ localized operations which could be computed at each node by using data from a small neighborhood of nodes around it. Multi-channel wavelet filterbanks, widely used as a signal processing tool for the sparse representation of signals, possess both these features (i.e. smooth approximations and localized operations). For example, a two channel wavelet transform splits the sample space into an approximation subspace which contains a smoother (coarser) version of the original signal and a detail subspace containing additional details required to perfectly reconstruct the original signal. While wavelet transform-based techniques would seem well suited to provide efficient local analysis, a major obstacle to their application to graphs is that these, unlike images, are not regularly structured. For graphs traditional notions of dimensions along which to filter the data do not hold.

Researchers have recently focused on developing localized transforms specifically for data defined on graphs. Crovella and Kolaczyk designed wavelet like functions on graphs which are localized in space and time. Wang and Ramchandran proposed graph dependent basis functions for sensor network graphs, which implement an invertible 2-channel like filter-bank. There exists a natural spectral interpretation of graph-signals in terms of eigen-functions and eigen-values of graph Laplacian matrix L. Maggioni and Coifman introduced “diffusion wavelets” as the localized basis functions of the eigenspaces of the dyadic powers of a diffusion operator. Hammond et. al. construct a class of wavelet operators in the graph spectral domain, i.e., the space of eigenfunctions of the graph Laplacian matrix L. These basis functions provide a spectral decomposition for data on a graph similar to the Fourier transform for standard signals. A common drawback of all of these filterbank designs is that they are not critically sampled as the output of the transform is not downsampled and there is oversampling usually by a factor of number of channels in the filterbank. Unlike classical wavelet transforms which have well-understood downsampling/upsampling operations, there is no obvious way in graphs to downsample nodes in a regular manner, since the neighboring nodes vary in number and orientation. Lifting based wavelet transforms have been proposed in for graphs in Euclidean Space and in our previous work for trees and for general graphs. These transforms are critically sampled and invertible by construction. However the design requires splitting the vertex set of the graph into two disjoint sets and transform is computed only on the links between nodes in different sets. Thus links between nodes in same set are not utilized by the transform.

Our prime contribution in this work is to introduce the theory behind sampling operations on graphs, which leads us to the design of critically-sampled wavelet-filterbanks on graphs. We describe a downsample then upsample(DU) operation on graphs in which a set of nodes in the graph are first downsampled (removed) and then upsampled (replaced) by inserting zeros. We show that the DU operations on all undirected bipartite graphs lead to a spectral decomposition of the graph-signal where spectral coefficients are reproduced at mirror graph-frequencies around a central frequency. This is a phenomenon we term as spectrum folding in graphs as it is analogous to the frequency-folding or “aliasing” effect in regular signal processing domain. Based on this property we propose critically sampled two-channel filterbanks for bipartite graphs and provide necessary and sufficient conditions for aliasing cancellation, perfect-reconstruction and orthogonality in these filterbanks. As a practical solution we propose a graph quadrature mirror filterbank (referred to as graph-QMF) design for bipartite graphs which has all the above mentioned properties. However, the exact realizations of the graph-QMF filters do not have well-localized support on the graph and therefore we implement polynomial approximations of these filters which are locally supported around each node (at the cost of small reconstruction error and loss of orthogonality). For arbitrary graphs, we formulate a bipartite subgraph decomposition problem well known to the graph theory community. The decomposition provides us a disjoint collection of bipartite subgraphs whose union is the original graph. Each of these subgraphs is then used as a separate dimension to filter and downsample leading to a multi-dimensional separable wavelet filterbank design.

• Publications
  • S.K. Narang and A. Ortega, "Downsampling Graphs Using Spectral Theory",IEEE Intl. Conf. on Acoustics, Speech and Signal Processing (ICASSP'11), PDF format

People

• Antonio Ortega
• Alexandre Ciancio
• Yoon Hak Kim
• Sunil Narang
• Godwin Shen

Related Links

• Wavelets on Trees
• SenZip (developed jointly with the USC Autonomous Networks Research Group, ANRG)

Acknowledgements

• This work was supported in part by NASA under grant AIST-05-0081