TY - GEN

T1 - Diffusion maps, spectral clustering and eigenfunctions of Fokker-Planck operators

AU - Nadler, Boaz

AU - Lafon, Stéphane

AU - Coifman, Ronald R.

AU - Kevrekidis, Ioannis G.

PY - 2005

Y1 - 2005

N2 - This paper presents a diffusion based probabilistic interpretation of spectral clustering and dimensionality reduction algorithms that use the eigenvectors of the normalized graph Laplacian. Given the pairwise adjacencymatrix of all points, we define a diffusion distance between any two data points and show that the low dimensional representation of the data by the first few eigenvectors of the corresponding Markov matrix is optimal under a certain mean squared error criterion. Furthermore, assuming that data points are random samples from a density p(x) = e -U(x) we identify these eigenvectors as discrete approximations of eigenfunctions of a Fokker-Planck operator in a potential 2U(x) with reflecting boundary conditions. Finally, applying known results regarding the eigenvalues and eigenfunctions of the continuous Fokker-Planck operator, we provide a mathematical justification for the success of spectral clustering and dimensional reduction algorithms based on these first few eigenvectors. This analysis elucidates, in terms of the characteristics of diffusion processes, many empirical findings regarding spectral clustering algorithms.

AB - This paper presents a diffusion based probabilistic interpretation of spectral clustering and dimensionality reduction algorithms that use the eigenvectors of the normalized graph Laplacian. Given the pairwise adjacencymatrix of all points, we define a diffusion distance between any two data points and show that the low dimensional representation of the data by the first few eigenvectors of the corresponding Markov matrix is optimal under a certain mean squared error criterion. Furthermore, assuming that data points are random samples from a density p(x) = e -U(x) we identify these eigenvectors as discrete approximations of eigenfunctions of a Fokker-Planck operator in a potential 2U(x) with reflecting boundary conditions. Finally, applying known results regarding the eigenvalues and eigenfunctions of the continuous Fokker-Planck operator, we provide a mathematical justification for the success of spectral clustering and dimensional reduction algorithms based on these first few eigenvectors. This analysis elucidates, in terms of the characteristics of diffusion processes, many empirical findings regarding spectral clustering algorithms.

KW - Algorithms and architectures

KW - Learning theory

UR - http://www.scopus.com/inward/record.url?scp=84864071145&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84864071145&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84864071145

SN - 9780262232531

T3 - Advances in Neural Information Processing Systems

SP - 955

EP - 962

BT - Advances in Neural Information Processing Systems 18 - Proceedings of the 2005 Conference

T2 - 2005 Annual Conference on Neural Information Processing Systems, NIPS 2005

Y2 - 5 December 2005 through 8 December 2005

ER -