Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering

Drawing on the correspondence between the graph Laplacian the Laplace Beltrami operator on a manifold and the connections to the heat equation we propose a geometrically motivated algorithm for constructing a representation for data sampled from a low di mensional manifold embedded in a higher dimensional space The algorithm provides a computationally e cient approach to non linear dimensionality reduction that has locality preserving prop erties and a natural connection to clustering Several applications are considered In many areas of arti cial intelligence information retrieval and data mining one is often confronted with intrinsically low dimensional data lying in a very high di mensional space For example gray scale n n images of a xed object taken with a moving camera yield data points in R However the intrinsic dimensionality of the space of all images of the same object is the number of degrees of freedom of the camera in fact the space has the natural structure of a manifold embedded in R n While there is a large body of work on dimensionality reduction in general most existing approaches do not explicitly take into account the structure of the manifold on which the data may possibly reside Recently there has been some interest Tenenbaum et al Roweis and Saul in the problem of devel oping low dimensional representations of data in this particular context In this paper we present a new algorithm and an accompanying framework of analysis for geometrically motivated dimensionality reduction The core algorithm is very simple has a few local computations and one sparse eigenvalue problem The solution re ects the intrinsic geometric structure of the manifold The justi cation comes from the role of the Laplacian operator in pro viding an optimal embedding The Laplacian of the graph obtained from the data points may be viewed as an approximation to the Laplace Beltrami operator de ned on the manifold The embedding maps for the data come from approximations to a natural map that is de ned on the entire manifold The framework of analysis presented here makes this connection explicit While this connection is known to geometers and specialists in spectral graph theory for example see to the best of our knowledge we do not know of any application to data representation yet The connection of the Laplacian to the heat kernel enables us to choose the weights of the graph in a principled manner The locality preserving character of the Laplacian Eigenmap algorithmmakes it rel atively insensitive to outliers and noise A byproduct of this is that the algorithm implicitly emphasizes the natural clusters in the data Connections to spectral clus tering algorithms developed in learning and computer vision see Shi and Malik become very clear Following the discussion of Roweis and Saul and Tenenbaum et al we note that the biological perceptual apparatus is con fronted with high dimensional stimuli from which it must recover low dimensional structure One might argue that if the approach to recovering such low dimensional structure is inherently local then a natural clustering will emerge and thus might serve as the basis for the development of categories in biological perception The Algorithm Given k points x xk in R we construct a weighted graph with k nodes one for each point and the set of edges connecting neighboring points to each other Step Constructing the Graph We put an edge between nodes i and j if xi and xj are close There are two variations a neighborhoods parameter R Nodes i and j are connected by an edge if jjxi xj jj Advantages geometrically motivated the relationship is naturally symmetric Disadvantages often leads to graphs with several connected compo nents di cult to choose b n nearest neighbors parameter n N Nodes i and j are connected by an edge if i is among n nearest neighbors of j or j is among n nearest neighbors of i Advantages simpler to choose tends to lead to connected graphs Disadvantages less geometrically intuitive Step Choosing the weights Here as well we have two variations for weighting the edges a Heat kernel parameter t R If nodes i and j are connected put Wij e jjxi j jj t The justi cation for this choice of weights will be provided later b Simple minded No parameters Wij if and only if vertices i and j are connected by an edge A simpli cation which avoids the necessity of choosing t Step Eigenmaps Assume the graph G constructed above is connected otherwise proceed with Step for each connected component 0 20 40 0 10 20 30 40 −5 0 5 x 10 −3 −8 −6 −4 −2 0 2 4 6 8 x 10 −3