Efficient Filtering of Graph Based Data Using Graph Partitioning

An algebraic framework for processing graph signals
axiomatically designates the graph adjacency matrix as the shift
operator. In this setup, we often encounter a problem wherein we
know the filtered output and the filter coefficients, and need to
find out the input graph signal. Solution to this problem using
direct approach requires O(N3) operations, where N is the number
of vertices in graph. In this paper, we adapt the spectral graph
partitioning method for partitioning of graphs and use it to reduce
the computational cost of the filtering problem. We use the example
of denoising of the temperature data to illustrate the efficacy of the
approach.

Authors:

• Nileshkumar Vaishnav
• Aditya Tatu

Keywords:

• Graph signal processing
• graph partitioning
• inverse filtering on graphs
• algebraic signal processing.

References:

[1] Pascal Frossard Antonio Ortega David I Shuman, Sunil K. Narang and
Pierre Vandergheynst, “The emerging field of signal processing on
graphs,” IEEE Signal Processing Magazine, pp. 83–98, May 2013.
[2] Jose M. F. Moura Aliaksei Sandryhaila, “Discrete signal processing
on graphs,” IEEE Transactions on Signal Processing, vol. 61, pp.
1644–1656, 2013.
[3] F. R. K. Chung, Spectral Graph Theory, AMS, 1996.
[4] P. Vandergheynst D. K. Hammond and R. Gribonval, “Wavelets on
graphs via spectral graph theory,” J. Appl. Comp. Harm. Anal, vol. 30,
no. 2, pp. 129150, 2011.
[5] Markus P¨uschel and Jos´e M. F. Moura, “Algebraic signal processing
theory: Foundation and 1-D time,” IEEE Transactions on Signal
Processing, vol. 56, no. 8, pp. 3572–3585, 2008.
[6] Markus P¨uschel and Jos´e M. F. Moura, “Algebraic signal processing
theory: 1-D space,” IEEE Transactions on Signal Processing, vol. 56,
no. 8, pp. 3586–3599, 2008.
[7] A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on
graphs: Graph fourier transform,” in IEEE International Conference
on Acoustics, Speech, and Signal Processing (ICASSP), pp. 6167-6170,
2013.
[8] J. M. F. Moura A. Sandryhaila, “Discrete signal processing on graphs:
Graph filters,” in IEEE International Conference on Acoustics, Speech,
and Signal Processing (ICASSP), pp. 6163-6166, 2013.
[9] J. M. F. Moura A. Sandryhaila, “Discrete signal processing on graphs:
Frequency analysis,” IEEE Transactions on Signal Processing, vol. 62,
no. 12, pp. 3042–3054, 2014.
[10] P. Lancaster and M. Tismenetsky, The Theory of Matrices, Academic
Press, 2nd edition, 1985.
[11] Jose M. F. Moura Jelena Kovacevic Siheng Chen, Aliaksei Sandryhaila,
“Signal denoising on graphs via graph filtering,” in IEEE Global
Conference on Signal and Information Processing (GlobalSIP),,
December 2014.
[12] Kang-Pu Paul Liu Alex Pothen, Horst D. Simon, “Partitioning sparse
matrices with eigenvectors of graphs,” Report, NAS Systems Division,
NASA Ames Research Center, 1989.