GSDet

One of the first steps required for data exploration is often to reduce the size of the data of interest so that exploration algorithms can be run within a reasonable amount of time. To this end, the data is generally sampled. Whether through periodic sampling or using random linear combinations, as in compressed sensing, knowledge of the data’s specific structure allows for the design of appropriate sampling schemes that are efficient (effectively encoding the information) and robust to noise. In the current context, where data are increasingly measured over networks, it is necessary to provide efficient sampling schemes for signals defined on such irregular structures.

Abstract

Graphs are an essential tool for modeling networked data. Depending on the application, the nodes in a graph can represent individuals in social networks, brain regions in neural networks… in short, any system composed of interconnected subsystems. 

Data from a graph, known as graph signals—such as individual leisure activities or blood flow in brain regions—can be represented by a scalar value per node.Graph sampling involves measuring an a priori smooth graph signal on a reduced set of nodes carefully chosen to enable a stable reconstruction. In previous work, we have shown that this problem is closely related to leverage scores, a key concept in dimension reduction efforts such as low-rank approximation of large matrices. To improve upon existing results regarding the number of nodes required for sampling, the robustness of the recovery process to noise, and/or the computational complexity of sampling algorithms, we propose to closely examine deterministic processes. Building on recent results linking deterministic processes and random-root spanning trees on graphs, we will study how specific random walks on graphs can reveal optimal sampling sets. The results of this study could have a significant impact not only on graph signal processing, but more generally on machine learning and data mining, where data dimensionality reduction is often a necessary step.

Expected results

We draw on recent results regarding deterministic processes to improve the latest graph sampling algorithms. The results of this research could have an impact in the field of GSPs, and more generally in all fields where dimension reduction via lever scores is important.

Carrier

Nicolas Tremblay (Gipsa-lab)

References

Illustrations

[1] An illustration of the social network Facebook; integrated into the world map.

[2] (Left) representation of a neural network; (right) representation of a wavelet on the graph modeling this network.

[3] A map of the Internet, OPTE project.

[4] An unofficial map of Tokyo's commuter rail and subway network.

[5] The U.S. power grid.

Publications

[1] A. Agaskar and Y. Lu. A Spectral Graph Uncertainty Principle. Information Theory, IEEE Transactions on, 59(7):4338{4356, July 2013.

[2] A. Anis, A. Gadde, and A. Ortega. “Towards a sampling theorem for signals on arbitrary graphs.” In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2014, pp. 3864–3868, May 2014.

[3] A. Anis, A. Gadde, and A. Ortega. Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies. IEEE Transactions on Signal Processing, 64(14):3775{3789, July 2016.

[4] L. Avena and A. Gaudilli. "On some random forests with determinantal roots." arXiv preprint arXiv:1310.1723, 2013.

[5] F. A. Azevedo, L. R. Carvalho, L. T. Grinberg, J. M. Farfel, R. E. Ferretti, R. E. Leite, R. Lent, S. Herculano-Houzel, and others. Equal numbers of neuronal and nonneuronal cells make the human brain an isometrically scaled-up primate brain. Journal of Comparative Neurology, 513(5):532{541, 2009.

[6] J. J. Benedetto. Irregular sampling and frames. wavelets: A Tutorial in Theory and Applications, 2:445{507, 1992.

[7] E. J. Candes et al. Compressive sampling. In Proceedings of the International Congress of Mathematicians, vol. 3, pp. 1433–1452. Madrid, Spain, 2006.

[8] S. Chen, A. Sandryhaila, and J. Kovacevic. Sampling theory for graph signals. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2015, pp. 3392–3396, Apr. 2015.

[9] S. Chen, R. Varma, A. Sandryhaila, and J. Kovacevic. Discrete Signal Processing on Graphs: Sampling Theory. CoRR, abs/1503.05432, 2015.

[10] F. Chung. Spectral Graph Theory. No. 92. American Mathematical Society, 1997.

[11] R. R. Coifman and M. Maggioni. Diffusion wavelets. Applied and Computational Harmonic Analysis, 21(1):53{94, July 2006.

[12] D. A. Drachman. Do we have brain to spare? Neurology, 64(12):2004{2005, 2005.

[13] P. Drineas, M. Magdon-Ismail, M. W. Mahoney, and D. P. Woodruff. Fast approximation of matrix coherence and statistical leverage. The Journal of Machine Learning Research, 13(1):3475{3506, 2012.

[14] J. A. Dunne, R. J. Williams, and N. D. Martinez. Network structure and robustness of marine food webs. Marine Ecology Progress Series, 273:291{302, 2004.

[15] P. Gai and S. Kapadia. Contagion in financial networks. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 2010.

[16] B. Girault, P. Goncalves, and E. Fleury. Translation on Graphs: An Isometric Shift Operator. Signal Processing Letters, IEEE, 22(12):2416{2420, Dec. 2015.

[17] K. Grochenig. Reconstruction algorithms in irregular sampling. Mathematics of Computation, 59(199):181{194, 1992.

[18] D. Hammond, P. Vandergheynst, and R. Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129{150, 2011.

[19] P. Holme, B. J. Kim, C. N. Yoon, and S. K. Han. "Attack vulnerability of complex networks." Physical Review E, 65(5):056109, 2002.

[20] C. J. Honey, J.-P. Thivierge, and O. Sporns. Can structure predict function in the human brain? Neuroimage, 52(3):766{776, 2010.

[21] H. Jeong, S. P. Mason, A.-L. Barabasi, and Z. N. Oltvai. Lethality and centrality in protein networks. Nature, 411(6833):41{42, 2001.

[22] A. Kulesza and B. Taskar. Determinantal Point Processes for Machine Learning. Foundations and TrendsR
in Machine Learning, 5(2{3):123{286, 2012.

[23] M. W. Mahoney. Randomized Algorithms for Matrices and Data. Foundations and TrendsR
in Machine Learning, 3(2):123{224, 2011.

[24] J. D. McEwen and Y. Wiaux. A Novel Sampling Theorem on the Sphere. IEEE Transactions on Signal Processing, 59(12), 2011.

[25] S. Narang and A. Ortega. Perfect Reconstruction Two-Channel Wavelet Filter Banks for Graph Structured Data. Signal Processing, IEEE Transactions on, 60(6):2786{2799, June 2012.

[26] S. Narang and A. Ortega. Compact Support Biorthogonal Wavelet Filterbanks for Arbitrary Undirected Graphs. Signal Processing, IEEE Transactions on, 61(19):4673{4685, Oct. 2013.

[27] B. Pasdeloup, R. Alami, V. Gripon, and M. Rabbat. “Toward an uncertainty principle for weighted graphs.” In Proceedings of the 23rd European Signal Processing Conference (EUSIPCO), pp. 1496–1500, Aug. 2015.

[28] N. Perraudin and P. Vandergheynst. Stationary signal processing on graphs. arXiv preprint arXiv:1601.02522, 2016.

[29] I. Pesenson. Sampling in Paley-Wiener spaces on combinatorial graphs. Transactions of the American Mathematical Society, 360(10):5603{5627, 2008.

[30] I. Z. Pesenson and M. Z. Pesenson. Sampling, Filtering and Sparse Approximations on Combinatorial Graphs. J. Fourier Anal. Appl., 16(6):921{942, 2010.

[31] G. Puy, N. Tremblay, R. Gribonval, and P. Vandergheynst. "Random sampling of bandlimited signals on graphs." *Applied and Computational Harmonic Analysis*, pp. {, 2016.

[32] A. Sakiyama and Y. Tanaka. Oversampled Graph Laplacian Matrix for Graph Filter Banks. Signal Processing, IEEE Transactions on, 62(24):6425{6437, Dec. 2014.

[33] A. Sandryhaila and J. Moura. Discrete signal processing on graphs: Graph fourier transform. In Acoustics, Speech and Signal Processing (ICASSP), 2013 IEEE International Conference on, pages 6167{6170, May 2013.

[34] A. Sandryhaila and J. Moura. Big Data Analysis with Signal Processing on Graphs: Representation and processing of massive data sets with irregular structure. Signal Processing Magazine, IEEE, 31(5):80{90, Sept. 2014.

[35] C. Shannon. Communication in the Presence of Noise. Proceedings of the IRE, 37(1):10{21, Jan. 1949.

[36] D. Shuman, S. Narang, P. Frossard, A. Ortega, and P. Vandergheynst. The emerging field of signal processing on graphs: Extending highdimensional data analysis to networks and other irregular domains. Signal Processing Magazine, IEEE, 30(3):83{98, May 2013.

[37] D. I. Shuman, B. Ricaud, and P. Vandergheynst. Vertex-frequency analysis on graphs. Applied and Computational Harmonic Analysis, 40(2):260{291, Mar. 2016. in press.

[38] N. Tremblay and P. Borgnat. Subgraph-Based Filterbanks for Graph Signals. IEEE Transactions on Signal Processing, 64(15):3827{3840, Aug. 2016.

[39] N. Tremblay, G. Puy, R. Gribonval, and P. Vandergheynst. Compressive spectral clustering. In Proceedings of the 33 rd International Conference on Machine Learning (ICML), volume 48, pages 1002{1011. JMLR: W&CP, 2016.

[40] C. Wilks and P. Meara. Untangling word webs: graph theory and the notion of density in second language word association networks. Second Language Research, 18(4):303{324, 2002.