{"title":"Efficient Filtering of Graph Based Data Using Graph Partitioning","authors":"Nileshkumar Vaishnav, Aditya Tatu","volume":123,"journal":"International Journal of Information and Communication Engineering","pagesStart":399,"pagesEnd":403,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/10006802","abstract":"An algebraic framework for processing graph signals<br \/>\r\naxiomatically designates the graph adjacency matrix as the shift<br \/>\r\noperator. In this setup, we often encounter a problem wherein we<br \/>\r\nknow the filtered output and the filter coefficients, and need to<br \/>\r\nfind out the input graph signal. Solution to this problem using<br \/>\r\ndirect approach requires O(N3) operations, where N is the number<br \/>\r\nof vertices in graph. In this paper, we adapt the spectral graph<br \/>\r\npartitioning method for partitioning of graphs and use it to reduce<br \/>\r\nthe computational cost of the filtering problem. We use the example<br \/>\r\nof denoising of the temperature data to illustrate the efficacy of the<br \/>\r\napproach.","references":"[1] Pascal Frossard Antonio Ortega David I Shuman, Sunil K. Narang and\r\nPierre Vandergheynst, \u201cThe emerging field of signal processing on\r\ngraphs,\u201d IEEE Signal Processing Magazine, pp. 83\u201398, May 2013.\r\n[2] Jose M. F. Moura Aliaksei Sandryhaila, \u201cDiscrete signal processing\r\non graphs,\u201d IEEE Transactions on Signal Processing, vol. 61, pp.\r\n1644\u20131656, 2013.\r\n[3] F. R. K. Chung, Spectral Graph Theory, AMS, 1996.\r\n[4] P. Vandergheynst D. K. Hammond and R. Gribonval, \u201cWavelets on\r\ngraphs via spectral graph theory,\u201d J. Appl. Comp. Harm. Anal, vol. 30,\r\nno. 2, pp. 129150, 2011.\r\n[5] Markus P\u00a8uschel and Jos\u00b4e M. F. Moura, \u201cAlgebraic signal processing\r\ntheory: Foundation and 1-D time,\u201d IEEE Transactions on Signal\r\nProcessing, vol. 56, no. 8, pp. 3572\u20133585, 2008.\r\n[6] Markus P\u00a8uschel and Jos\u00b4e M. F. Moura, \u201cAlgebraic signal processing\r\ntheory: 1-D space,\u201d IEEE Transactions on Signal Processing, vol. 56,\r\nno. 8, pp. 3586\u20133599, 2008.\r\n[7] A. Sandryhaila and J. M. F. Moura, \u201cDiscrete signal processing on\r\ngraphs: Graph fourier transform,\u201d in IEEE International Conference\r\non Acoustics, Speech, and Signal Processing (ICASSP), pp. 6167-6170,\r\n2013.\r\n[8] J. M. F. Moura A. Sandryhaila, \u201cDiscrete signal processing on graphs:\r\nGraph filters,\u201d in IEEE International Conference on Acoustics, Speech,\r\nand Signal Processing (ICASSP), pp. 6163-6166, 2013.\r\n[9] J. M. F. Moura A. Sandryhaila, \u201cDiscrete signal processing on graphs:\r\nFrequency analysis,\u201d IEEE Transactions on Signal Processing, vol. 62,\r\nno. 12, pp. 3042\u20133054, 2014.\r\n[10] P. Lancaster and M. Tismenetsky, The Theory of Matrices, Academic\r\nPress, 2nd edition, 1985.\r\n[11] Jose M. F. Moura Jelena Kovacevic Siheng Chen, Aliaksei Sandryhaila,\r\n\u201cSignal denoising on graphs via graph filtering,\u201d in IEEE Global\r\nConference on Signal and Information Processing (GlobalSIP),,\r\nDecember 2014.\r\n[12] Kang-Pu Paul Liu Alex Pothen, Horst D. Simon, \u201cPartitioning sparse\r\nmatrices with eigenvectors of graphs,\u201d Report, NAS Systems Division,\r\nNASA Ames Research Center, 1989.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 123, 2017"}