Difference between revisions of "GraphWavelets"

From WikiBiron
m
 
(22 intermediate revisions by one other user not shown)
Line 2: Line 2:
  
 
<p>
 
<p>
−
In this work we propose the construction of two-channel wavelet filterbanks for analyzing functions
+
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
 
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
 
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
 
processing domain, such as Fourier decomposition, signal filtering and downsampling can be extended to
−
graph domain. Especially, we observe a spectral folding phenomenon in bipartite graphs which occurs
+
graph domain.  
−
during downsampling of these graphs and produces aliasing in graph signals. We propose quadrature
 
−
mirror filters on graph (referred to as graph-QMF) for bipartite graph which cancel aliasing and lead
 
−
to perfect reconstruction. For arbitrary graphs we present a bipartite subgraph decomposition which
 
−
produces an edge-disjoint collection of bipartite subgraphs. Graph-QMFs are then constructed on each
 
−
bipartite subgraph leading to multi-dimensional separable wavelet filterbanks on graphs. Our proposed
 
−
filterbanks are critically sampled and we state necessary and sufficient conditions for orthogonality,
 
−
aliasing cancellation and perfect reconstruction. The filterbanks are realized by Chebychev polynomial
 
−
approximations.
 
−
 
 
 
</p>
 
</p>
−
 
 
<p>
 
<p>
−
Assume that a number of power-constrained sensors are spr\-ead over an
+
Graphs provide a very flexible model for representing data in many domains.
−
area, acquiring data, e.g., temperature measurements. An estimate of
+
Many networks such
−
the temperature in each point of that area is to be made available at
+
as biological networks, social networks and sensor networks etc.
−
a central node (sink) based on transmissions from the sensors. Each sensor is capable of transmitting data
+
have a natural interpretation in terms of finite graphs with vertices
−
only over a small distance. Communication is done via data hoping,
+
as data-sources and links established based on connectivity, similarity,  
−
where data from each sensor is forwarded (using other sensors as relay
+
ties etc. The data on these graphs can be visualized as a finite
−
stations) until it reaches the target node. Such a network is referred
+
collection of samples termed as graph-signals.  
−
to as a multihop network.
+
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).  
 
</p>
 
</p>
−
 
 
<p>
 
<p>
−
A simple and naive design would be for each sensor to just transmit a
+
Mostly, the sizes (number of nodes) of
−
quantized version of its own measurement to the central node. However,
+
the graphs in these applications are enormous, which present computational and technical challenges
−
this approach would not be exploiting the fact that measurements
+
for the purpose of storage, analysis etc. In some other applications such as wireless sensor-networks,
−
originated from spatially close sensors are likely to be correlated,
+
the data-exchanges between far-off nodes can be expensive (bandwidth , latency , energy constraints
−
and energy would be wasted with the transmission of redundant data to
+
issues). Therefore, instead of operating on the original graph, it would be desirable to find and operate
−
the central node. As an alternative, since data is correlated, it
+
on smaller graphs with fewer nodes and data representing a smooth approximation of the original data.
−
would be reasonable to use some sort of transform as a means to
+
Moreover, such systems need to employ localized operations which could be computed at each node
−
decorrelate the information from sensors, and, therefore, represent
+
by using data from a small neighborhood of nodes around it. Multi-channel wavelet filterbanks, widely
−
the measurements using fewer bits.
+
used as a signal processing tool for the sparse representation of signals, possess both these features (i.e.
−
</p>
+
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.
  
−
<p>
 
−
Servetto and Gastpar have proposed the
 
−
use of distributed transforms to decorrelate data. A main drawback of
 
−
those algorithms is that in a power constrained sensor network
 
−
scenario, transmission costs account for most (if not all) the energy
 
−
consumption. Distributed algorithms that rely on a potentially large
 
−
number of intersensor communications, or do not take into account
 
−
communication costs as a function of the number of bits and the
 
−
distances over which bits are transmitted, might in the end be elevating power
 
−
consumption to unacceptable levels. For example, in the case of
 
−
distributed wavelet algorithms, the amount of necessary data exchanges
 
−
and the degree of decorrelation achieved are directly related to the
 
−
number of levels of decompositions used. Depending on the network
 
−
properties (data correlation, distances between sensors, etc), a
 
−
specific number of decompositions may perform better.
 
 
</p>
 
</p>
−
 
+
<p> Researchers have recently focused on developing localized transforms specifically for data defined
−
<p>
+
on graphs. Crovella and Kolaczyk designed wavelet like functions on graphs which are localized
−
Distributed implementation of the wavelet transform poses several
+
in space and time. Wang and Ramchandran proposed graph dependent basis functions for sensor
−
challenges. First, if the filters contain anticausal terms,  
+
network graphs, which implement an invertible 2-channel like filter-bank. There exists a natural spectral
−
sensors would be required to transmit data backwards (i.e., away from the
+
interpretation of graph-signals in terms of eigen-functions and eigen-values of graph Laplacian matrix
−
sink instead of towards the sink) or alternatively to send
+
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
−
uncompressed data forward. Second, any data transmitted back and
+
wavelet operators in the graph spectral domain, i.e., the space of eigenfunctions of the graph Laplacian
−
forth over the network has to be quantized, since tramsmissions at
+
matrix L. These basis functions provide a spectral decomposition for data on a graph similar to the Fourier
−
full precision can substantialy increase energy consumption, affecting
+
transform for standard signals. A common drawback of all of these filterbank designs is that they are not
−
the final performance. In this project we develop a distributed wavelet
+
critically sampled as the output of the transform is not downsampled and there is oversampling usually
−
transform algorithm to decorrelate data as it flows through the
+
by a factor of number of channels in the filterbank. Unlike classical wavelet transforms which have
−
network. We eliminate unnecessary transmissions by calculating partial
+
well-understood downsampling/upsampling operations, there is no obvious way in graphs to downsample
−
approximations of the wavelet coefficients based on the available data
+
nodes in a regular manner, since the neighboring nodes vary in number and orientation. Lifting based
−
at each sensor. The coefficients are refined at future nodes, as data
+
wavelet transforms have been proposed in for graphs in Euclidean Space and in our previous work
−
is forwarded to the sink. We also address the impact of data
+
[http://biron.usc.edu/wiki/index.php/Wavelets_on_Trees for trees] and [http://biron.usc.edu/~kumarsun/papers/ICIP10GraphTransform.pdf for general graphs]. These transforms are critically sampled and invertible
−
quantization on the final distortion. We derive an upper bound to the
+
by construction. However the design requires splitting the vertex set of the graph into two disjoint sets
−
resulting extra distortion introduced by quantization in terms of the
+
and transform is computed only on the links between nodes in different sets. Thus links between nodes
−
bits allocated to the partial data, and use it as a tool to design the
+
in same set are not utilized by the transform.
−
quantizers so the extra distortion is within a given threshold.
 
 
</p>
 
</p>
−
 
 
<p>
 
<p>
−
We then address the scenario where energy-constrained sensors in a wireless sensor network can choose among different distributed
+
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
−
coding schemes to encode their data. We propose a framework where the network is described as a graph, with sensors representing
+
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 
−
the nodes, and where communication and processing costs are associated to edge weights and the coding schemes associated to states
+
on all undirected bipartite graphs lead to a spectral decomposition of
−
 
+
the graph-signal where spectral coefficients are reproduced at mirror
−
of operation. After carefully describing data transitions and edge costs, we show that a shor\-test-path algorithm can be used to  
+
graph-frequencies around a central
−
 
+
frequency. This is a phenomenon we term as spectrum folding in graphs as it is analogous to the
−
find the optimum network configuration, i.e., the one that leads to the lowest overall energy.
+
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.  
 
</p>
 
</p>
  
−
<p>
 
−
Our methods discussed above apply when the transform is performed along a single path (ergo, no overlapping paths). Naturally, this breaks down when applying this transform along more general routing trees that have overlapping paths.
 
−
 
−
To address this problem, we propose a wavelet transform that can be computed along an arbitrary routing tree using wavelet lifting.  This eliminates the need for costly heuristics to merge overlapping 1D transforms.  The transform is critically sampled, exploits data correlation across adjacent paths, and is computed in a unidirectional manner to avoid incurring additional costs for backward transmissions found in existing 2D transforms.
 
−
 
−
An optimization technique (analogous to that in our previous work) is then developed for our proposed tree based transform to select the number of levels of decomposition at each node that results in minimum cost.
 
−
 
−
We also propose a method for joint transform and routing optimization using our tree based transform to exploit a trade-off between high inter-node data correlation (for good compression efficiency) and low total distance to route to the sink (for low total routing cost).
 
−
</p>
 
−
 
−
<p>
 
−
More detailed information about this project can be found in the publications below.
 
−
</p>
 
−
 
−
<br><br>
 
−
 
−
<P><B>Distributed compression algorithms for quantizer design, encoding of quantized data and source localization in sensor networks</B></P>
 
−
<p>
 
−
In sensor networks, multiple correlated observations are available
 
−
from many sensors that can sense, compute and communicate. Often
 
−
these sensors are battery-powered and operate under strict
 
−
limitations on wireless communication bandwidth. This motivates
 
−
the use of data compression in the context of various tasks such
 
−
as detection, classification, localization and tracking, which
 
−
require data exchange between sensors.  The basic strategy for
 
−
reducing the overall energy usage in the sensor network would then
 
−
be to decrease the communication cost at the expense of additional
 
−
computation in the sensors. One important sensor collaboration task with broad applications is source localization. Since practical systems will require
 
−
quantization of the observations before transmission, different
 
−
quantizer designs should be compared in terms of localization
 
−
error.
 
−
</p>
 
−
<p>
 
−
In the project, we consider the effect
 
−
of quantization on source localization and provide distributed
 
−
algorithms for quantizer design, encoding of quantized data and
 
−
localization based on them, to achieve good data compression.
 
−
</p>
 
−
 
−
<p>
 
−
More detailed information about this project can be found in the publications below.
 
−
</p>
 
 
<br><br>
 
<br><br>
 
<ul>
 
<ul>
Line 137: Line 90:
 
<li>'''Publications'''
 
<li>'''Publications'''
 
<ul>
 
<ul>
−
 
+
<li>
−
<li> G. Shen and A. Ortega, "Transform-based Distributed Data Gathering". <i>To Appear in IEEE Transactions on Signal Processing</i>.
+
S. K. Narang and Antonio Ortega, "Perfect Reconstruction Two-Channel Wavelet Filter-Banks For Graph Structured Data", <i>To appear in IEEE Transactions on Signal Processing</i>[http://arxiv.org/abs/1106.3693<small><b> PDF format</b></small>]</ul>
−
[http://arxiv.org/abs/0909.5177v3 <small><b>arXiv:0909.5177v3</b></small>]
+
<ul>
−
 
+
<li>S.K. Narang and A. Ortega, "Multi-dimensional separable critically sampled wavelet filterbanks on arbitrary graphs",<i>To appear in IEEE Intl. Conf. on Acoustics, Speech and Signal Processing (ICASSP'12)</i>
−
<li> S.K. Narang, G. Shen and A. Ortega, "Unidirectional Graph-based Wavelet Transforms for Efficient Data Gathering in Sensor Netowkrs". <i>IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP'10),</i> Dallas, April 2010.
+
</ul>
−
 
+
<ul>
−
<li> S. Lee, S. Pattem, M. Sathiamoorthy,B. Krishnamachari, and A. Ortega "Spatially-Localized Compressed Sensing and Routing in Multi-hop Sensor Networks". <i>In Proceedings of Third International Conference on Geosensor Networks (GSN'09),</i> Oxford, July 2009.
+
<li>Woo-Shik Kim, S.K. Narang and A. Ortega, "Graph based transforms for depth video coding",<i>To appear in IEEE Intl. Conf. on Acoustics, Speech and Signal Processing (ICASSP'12)</i>
−
[http://biron.usc.edu/~sungwonl/Papers/GSN09_CS.pdf <small><b>PDF format</b></small>]
+
</ul>
−
 
+
<ul>
−
<li> P. Tarrio, G. Valenzise, G. Shen and A. Ortega, "Distributed Network Configuration for Wavelet-based Compression in Sensor Networks". <i>Third International Conference on Geosensor Networks (GSN'09),</i> Oxford, Jul 2009.
+
<li>S.K. Narang and A. Ortega, "Downsampling Graphs Using Spectral Theory",<i>IEEE Intl. Conf. on Acoustics, Speech and Signal Processing (ICASSP'11),</i>[http://biron.usc.edu/~kumarsun/papers/ICASSP11Downsampling.pdf <small><b> PDF format</b></small>],
−
[http://biron.usc.edu/~godwinsh/Papers/GSN09.pdf <small><b>PDF format</b></small>]
+
[http://biron.usc.edu/~kumarsun/Posters/ICASSPPoster2011.pdf <small><b> Poster</b></small>]
−
 
+
</ul>
−
<li> G. Shen, S. Pattem and A. Ortega, "Energy-efficient Graph-based Wavelets for Distributed Coding in Wireless Sensor Networks". <i> IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP'09),</i> Taipei, Apr 2009.
+
<ul>
−
[http://biron.usc.edu/~godwinsh/Papers/ICASSP09_Broadcast.pdf <small><b>PDF format</b></small>]
+
<li>S.K. Narang and A. Ortega, "Local Two-Channel Critically Sampled Filter-Banks On Graphs",<i>Intl. Conf. on Image Proc. (ICIP'10),</i>[http://biron.usc.edu/~kumarsun/papers/ICIP10GraphTransform.pdf <small><b> PDF format</b></small>],
−
 
+
[http://biron.usc.edu/~kumarsun/Posters/ICIPPoster2010.pdf <small><b> Poster</b></small>]
−
<li> G. Shen, S. Narang and A. Ortega, "Adaptive Distributed Transforms for Irregularly Sampled Wireless Sensor Networks". <i> IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP'09),</i> Taipei, Apr 2009.
+
</ul>
−
[http://biron.usc.edu/~godwinsh/Papers/ICASSP09_Filter_Opt.pdf <small><b>PDF format</b></small>]
+
<ul>
−
 
+
<li> S. K. Narang and A. Ortega, "Lifting Based Wavelet Transforms on Graphs". <i>In Proc. of 2009 APSIPA Annual Summit and Conference (APSIPA ASC 2009)</i> Sapporo, Japan [http://biron.usc.edu/~kumarsun/papers/APSIPA_09_Graph_Lifting.pdf <small><b> PDF format</b></small>]</ul>
−
<li> S. Pattem, G. Shen, Y. Chen, B. Krishnamachari and A. Ortega, "SenZip: An Architecture for Distributed En-route Compression in Wireless Sensor Networks". <i>In Workshop on Sensor Networks for Earth and Space Science Applications (ESSA'09),</i> San Francisco, Apr 2009.
 
−
[http://biron.usc.edu/~godwinsh/Papers/ESSA09.pdf <small><b>PDF format</b></small>]
 
−
 
 
−
<li> G. Shen and A. Ortega, "Joint Routing and 2D Transform Optimization for Irregular Sensor Network Grids Using Wavelet Lifting". <i> International Symposium on Information Processing in Sensor Networks (IPSN'08)</i>, St. Louis, Apr 2008.
 
−
[http://biron.usc.edu/~godwinsh/Papers/IPSN08ShenOrtega.pdf <small><b>PDF format</b></small>]
 
−
 
 
−
<li> G. Shen and A. Ortega, "Optimized Distributed 2D Transforms for Irregularly Sampled Sensor Network Grids Using Wavelet Lifting". <i> IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP'08)</i>, Las Vegas, Apr 2008.
 
−
[http://biron.usc.edu/~godwinsh/Papers/ICASSP08ShenOrtega.pdf <small><b>PDF format</b></small>]
 
−
 
 
−
<li> A. Ciancio and A. Ortega, "Energy Efficient Data-Representation and Routing for
 
−
Wireless Sensor Networks Based on a Distributed
 
−
Wavelet Compression Algorithm". <i> International Symposium on Information Processing in Sensor Networks (IPSN'06)</i>, Nashville, Apr 2006.
 
−
[http://biron.usc.edu/~godwinsh/Papers/IPSN06CiancioOrtega.pdf <small><b>PDF format</b></small>]
 
−
 
 
−
<li> A. Ciancio and A. Ortega, "A Dynamic Programming Approach to Distortion-Energy Optimization
 
−
  for Distributed Wavelet Compression With Applications to
 
−
Data Gathering in Wireless Sensor Networks". <i> IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP'06)</i>, Toulouse, France, May 2006.
 
−
[http://biron.usc.edu/~godwinsh/Papers/ICASSP06CiancioOrtega.pdf <small><b>PDF format</b></small>]
 
−
 
 
−
<li> Y. H. Kim and A. Ortega, "Maximum A Posteriori (MAP)-Based Algorithm for Distributed Source Localization using Quantized Acoustic Sensor Readings". <i> IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP'06)</i>, Toulouse, France, May 2006.
 
−
[http://www-scf.usc.edu/~yhk/ICASSP06_yoon.pdf <small><b>PDF format</b></small>]
 
−
 
 
−
<li> A. Ciancio and A. Ortega, "Energy Consumption Optimization in
 
−
Wireless Sensor Networks Using Dynamic Programming (Work-in-progess)". <i> International Symposium on Information Processing in Sensor Networks (IPSN'05)</i>, Los Angeles, Apr 2005.
 
−
[http://biron.usc.edu/~godwinsh/Papers/IPSN05CiancioOrtega.pdf <small><b>PDF format</b></small>]
 
−
 
 
−
<li> A. Ciancio and A. Ortega,"Distributed Wavelet  
 
−
Compression Algorithm for Wireless Multihop Sensor Networks Based on Lifting". <i> International Conference on Acoustics, Speech and Signal Processing (ICASSP'05)</i>, Philadelphia, Mar 2005.
 
−
[http://biron.usc.edu/~godwinsh/Papers/ICASSP05CiancioOrtega.pdf <small><b>PDF format</b></small>]
 
−
 
 
−
<li> Y. H. Kim and A. Ortega, "Quantizer Design for Source localization in Sensor Networks". <i> IEEE International Conference on Acoustic, Speech and Signal Processing (ICASSP'05)</i>, Philadelphia, March 2005.
 
−
[http://www-scf.usc.edu/~yhk/ICASSP05_yoon.pdf <small><b>PDF format</b></small>]
 
−
 
 
−
<li> Y. H. Kim and A. Ortega, "Quantizer Design and Distributed Encoding Algorithm for Source Localization in Sensor Networks". <i>International Symposium on Information Processing in Sensor Networks (IPSN'05)</i>, Los Angeles, April 2005.
 
−
[http://www-scf.usc.edu/~yhk/IPSN05_yoon.pdf <small><b>PDF format</b></small>]
 
−
 
 
−
<li> A. Ciancio and A. Ortega,"Distributed Wavelet Compression
 
−
Algorithm for Wireless Sensor Networks Based on Lifting", <i> International Conference on Acoustics, Speech and Signal Processing (ICASSP'04)</i>, Montreal, May 2004.
 
−
[http://biron.usc.edu/~godwinsh/Papers/ICASSP04CiancioOrtega.pdf <small><b>PDF format</b></small>]
 
  
 
</ul>
 
</ul>
Line 201: Line 115:
 
<ul>
 
<ul>
 
   <li> [http://sipi.usc.edu/~ortega/ Antonio Ortega]
 
   <li> [http://sipi.usc.edu/~ortega/ Antonio Ortega]
−
  <li> [http://biron.usc.edu/~ciancio/ Alexandre Ciancio]
+
   <li> [http://biron.usc.edu/wiki/index.php/Sunil_Kumar Sunil K Narang]
−
  <li> [http://www-scf.usc.edu/~yhk/ Yoon Hak Kim]
 
−
  <li> [http://biron.usc.edu/~kumarsun/ Sunil Narang]
 
−
   <li> [http://biron.usc.edu/wiki/index.php/Godwin Godwin Shen]
 
 
</ul>
 
</ul>
 
<br>
 
<br>
  
−
 
+
<li>''' Software '''
−
 
 
−
<li>'''Related Links'''
 
 
<ul>
 
<ul>
−
  <li> [http://biron.usc.edu/wiki/index.php/Wavelets_on_Trees Wavelets on Trees]
+
<li> [http://biron.usc.edu/wiki/index.php/Graph_Filterbanks Graph Filterbanks]
−
  <li> [http://anrg.usc.edu/SenZip/ SenZip] (developed jointly with the
 
−
[http://anrg.usc.edu/www/index.php/Main_Page USC Autonomous Networks Research Group, ANRG])
 
−
 
 
 
</ul>
 
</ul>
 
<br>
 
<br>
Line 222: Line 128:
 
<li>'''Acknowledgements'''
 
<li>'''Acknowledgements'''
 
<ul>
 
<ul>
−
   <li> This work was supported in part by NASA under grant AIST-05-0081
+
   <li> This work was supported by NSF under grant CCF-1018977. Any opinions, findings, and conclusions or recommendations expressed
 +
in this material are those of the author(s) and do not necessarily
 +
reflect the views of the National Science Foundation.

Latest revision as of 17:46, 22 July 2015

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 Antonio Ortega, "Perfect Reconstruction Two-Channel Wavelet Filter-Banks For Graph Structured Data", To appear in IEEE Transactions on Signal Processing PDF format
    • S.K. Narang and A. Ortega, "Multi-dimensional separable critically sampled wavelet filterbanks on arbitrary graphs",To appear in IEEE Intl. Conf. on Acoustics, Speech and Signal Processing (ICASSP'12)
    • Woo-Shik Kim, S.K. Narang and A. Ortega, "Graph based transforms for depth video coding",To appear in IEEE Intl. Conf. on Acoustics, Speech and Signal Processing (ICASSP'12)
    • S.K. Narang and A. Ortega, "Downsampling Graphs Using Spectral Theory",IEEE Intl. Conf. on Acoustics, Speech and Signal Processing (ICASSP'11), PDF format, Poster
    • S.K. Narang and A. Ortega, "Local Two-Channel Critically Sampled Filter-Banks On Graphs",Intl. Conf. on Image Proc. (ICIP'10), PDF format, Poster
    • S. K. Narang and A. Ortega, "Lifting Based Wavelet Transforms on Graphs". In Proc. of 2009 APSIPA Annual Summit and Conference (APSIPA ASC 2009) Sapporo, Japan PDF format


  • People


  • Software



  • Acknowledgements
    • This work was supported by NSF under grant CCF-1018977. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
    • Retrieved from "https://biron.usc.edu/wiki/index.php?title=GraphWavelets&oldid=2858"