Efficient Filtering of Graph Based Data Using Graph Partitioning

Authors: Nileshkumar Vaishnav, Aditya Tatu

Abstract:

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.

Keywords: Graph signal processing, graph partitioning, inverse filtering on graphs, algebraic signal processing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1129854

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.