publication . Report . Preprint . 2017

Compressive Embedding and Visualization using Graphs

Paratte, Johan; Perraudin, Nathanaël; Vandergheynst, Pierre;
Open Access
  • Published: 15 May 2017
  • Publisher: Lausanne, arXiv e-print archive
  • Country: Switzerland
Abstract
Visualizing high-dimensional data has been a focus in data analysis communities for decades, which has led to the design of many algorithms, some of which are now considered references (such as t-SNE for example). In our era of overwhelming data volumes, the scalability of such methods have become more and more important. In this work, we present a method which allows to apply any visualization or embedding algorithm on very large datasets by considering only a fraction of the data as input and then extending the information to all data points using a graph encoding its global similarity. We show that in most cases, using only $\mathcal{O}(\log(N))$ samples is s...
Subjects
free text keywords: Computer Science - Learning, Statistics - Machine Learning
Related Organizations
16 references, page 1 of 2

[7] L. Van Der Maaten, E. Postma, and J. Van den Herik, “Dimensionality reduction: a comparative,” J Mach Learn Res, vol. 10, pp. 66-71, 2009.

[8] L. Van Der Maaten, “Accelerating t-sne using tree-based algorithms.,” Journal of machine learning research, vol. 15, no. 1, pp. 3221-3245, 2014.

[10] F. R. Chung, Spectral graph theory, vol. 92. AMS Bookstore, 1997.

[11] D. I. Shuman, B. Ricaud, and P. Vandergheynst, “Vertex-frequency analysis on graphs,” arXiv preprint arXiv:1307.5708, 2013. [OpenAIRE]

[12] D. K. Hammond, P. Vandergheynst, and R. Gribonval, “Wavelets on graphs via spectral graph theory,” Applied and Computational Harmonic Analysis, vol. 30, no. 2, pp. 129-150, 2011. [OpenAIRE]

[13] A. Susnjara, N. Perraudin, D. Kressner, and P. Vandergheynst, “Accelerated filtering on graphs using lanczos method,” arXiv preprint arXiv:1509.04537, 2015. [OpenAIRE]

[14] D. I. Shuman, B. Ricaud, and P. Vandergheynst, “Vertex-frequency analysis on graphs,” Applied and Computational Harmonic Analysis, vol. 40, no. 2, pp. 260-291, 2016.

[15] G. Puy, N. Tremblay, R. Gribonval, and P. Vandergheynst, “Random sampling of bandlimited signals on graphs,” Applied and Computational Harmonic Analysis, 2016. [OpenAIRE]

[16] B. Nadler, S. Lafon, R. R. Coifman, and I. G. Kevrekidis, “Diffusion maps, spectral clustering and eigenfunctions of fokker-planck operators,” arXiv preprint math/0506090, 2005. [OpenAIRE]

[17] R. R. Coifman and S. Lafon, “Diffusion maps,” Applied and computational harmonic analysis, vol. 21, no. 1, pp. 5-30, 2006.

[18] D. K. Hammond, Y. Gur, and C. R. Johnson, “Graph diffusion distance: A difference measure for weighted graphs based on the graph laplacian exponential kernel,” in Global Conference on Signal and Information Processing (GlobalSIP), 2013 IEEE, pp. 419-422, IEEE, 2013.

[22] J. Cheeger, “A lower bound for the smallest eigenvalue of the laplacian,” 1969.

[23] J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Transactions on pattern analysis and machine intelligence, vol. 22, no. 8, pp. 888-905, 2000.

[24] N. Perraudin, J. Paratte, D. Shuman, L. Martin, V. Kalofolias, P. Vandergheynst, and D. K. Hammond, “GSPBOX: A toolbox for signal processing on graphs,” ArXiv e-prints, Aug. 2014. [OpenAIRE]

[25] J. W. Sammon, “A nonlinear mapping for data structure analysis,” IEEE Transactions on computers, vol. 100, no. 5, pp. 401-409, 1969. [OpenAIRE]

16 references, page 1 of 2
Abstract
Visualizing high-dimensional data has been a focus in data analysis communities for decades, which has led to the design of many algorithms, some of which are now considered references (such as t-SNE for example). In our era of overwhelming data volumes, the scalability of such methods have become more and more important. In this work, we present a method which allows to apply any visualization or embedding algorithm on very large datasets by considering only a fraction of the data as input and then extending the information to all data points using a graph encoding its global similarity. We show that in most cases, using only $\mathcal{O}(\log(N))$ samples is s...
Subjects
free text keywords: Computer Science - Learning, Statistics - Machine Learning
Related Organizations
16 references, page 1 of 2

[7] L. Van Der Maaten, E. Postma, and J. Van den Herik, “Dimensionality reduction: a comparative,” J Mach Learn Res, vol. 10, pp. 66-71, 2009.

[8] L. Van Der Maaten, “Accelerating t-sne using tree-based algorithms.,” Journal of machine learning research, vol. 15, no. 1, pp. 3221-3245, 2014.

[10] F. R. Chung, Spectral graph theory, vol. 92. AMS Bookstore, 1997.

[11] D. I. Shuman, B. Ricaud, and P. Vandergheynst, “Vertex-frequency analysis on graphs,” arXiv preprint arXiv:1307.5708, 2013. [OpenAIRE]

[12] D. K. Hammond, P. Vandergheynst, and R. Gribonval, “Wavelets on graphs via spectral graph theory,” Applied and Computational Harmonic Analysis, vol. 30, no. 2, pp. 129-150, 2011. [OpenAIRE]

[13] A. Susnjara, N. Perraudin, D. Kressner, and P. Vandergheynst, “Accelerated filtering on graphs using lanczos method,” arXiv preprint arXiv:1509.04537, 2015. [OpenAIRE]

[14] D. I. Shuman, B. Ricaud, and P. Vandergheynst, “Vertex-frequency analysis on graphs,” Applied and Computational Harmonic Analysis, vol. 40, no. 2, pp. 260-291, 2016.

[15] G. Puy, N. Tremblay, R. Gribonval, and P. Vandergheynst, “Random sampling of bandlimited signals on graphs,” Applied and Computational Harmonic Analysis, 2016. [OpenAIRE]

[16] B. Nadler, S. Lafon, R. R. Coifman, and I. G. Kevrekidis, “Diffusion maps, spectral clustering and eigenfunctions of fokker-planck operators,” arXiv preprint math/0506090, 2005. [OpenAIRE]

[17] R. R. Coifman and S. Lafon, “Diffusion maps,” Applied and computational harmonic analysis, vol. 21, no. 1, pp. 5-30, 2006.

[18] D. K. Hammond, Y. Gur, and C. R. Johnson, “Graph diffusion distance: A difference measure for weighted graphs based on the graph laplacian exponential kernel,” in Global Conference on Signal and Information Processing (GlobalSIP), 2013 IEEE, pp. 419-422, IEEE, 2013.

[22] J. Cheeger, “A lower bound for the smallest eigenvalue of the laplacian,” 1969.

[23] J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Transactions on pattern analysis and machine intelligence, vol. 22, no. 8, pp. 888-905, 2000.

[24] N. Perraudin, J. Paratte, D. Shuman, L. Martin, V. Kalofolias, P. Vandergheynst, and D. K. Hammond, “GSPBOX: A toolbox for signal processing on graphs,” ArXiv e-prints, Aug. 2014. [OpenAIRE]

[25] J. W. Sammon, “A nonlinear mapping for data structure analysis,” IEEE Transactions on computers, vol. 100, no. 5, pp. 401-409, 1969. [OpenAIRE]

16 references, page 1 of 2
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue