Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering
Authors: Mikhail Belkin, Partha Niyogi
Published in: Advances in Neural Information Processing Systems 14  (NIPS 2001) (Main Conference Track), 2001

Abstract: 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(cid:173) mensional manifold embedded  in  a  higher  dimensional space.  The  algorithm  provides  a  computationally  efficient  approach  to  non(cid:173) linear  dimensionality  reduction  that  has  locality  preserving  prop(cid:173) erties  and  a  natural  connection  to  clustering.  Several  applications  are  considered. 
In  many  areas  of artificial  intelligence,  information retrieval  and  data mining, one  is  often  confronted  with intrinsically low  dimensional  data lying  in  a  very  high  di(cid:173) mensional space.  For example, gray scale  n  x  n  images of a  fixed  object taken with  a  moving camera yield data points in rn: n2 .  However , the intrinsic dimensionality of  the  space  of all  images  of t he  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  rn: n2 .  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  aI,  2000 ;  Roweis  and  Saul,  2000)  in  the  problem of devel(cid:173) 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  reflects  th e  intrinsic  geom etric structure  of the  manifold.  The justification  comes from  the  role  of the  Laplacian  operator  in  pro(cid:173) viding  an  optimal emb edding.  The  Laplacian  of the  graph obtained  from  the  data  points may be viewed as an approximation to the Laplace-Beltrami operator defined  on  the  manifold.  The  emb edding  maps for  the  data come from  approximations to  a  natural  map  that  is  defined  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  [1,  2])  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 algorithm makes it rel(cid:173) 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(cid:173) tering  algorithms  developed  in  learning  and  computer  vision  (see  Shi  and  Malik ,  1997)  become  very  clear.  Following the  discussion  of Roweis  and  Saul  (2000) , and  Tenenbaum et  al  (2000),  we  note  that  the  biological  perceptual  apparatus  is  con(cid:173) 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.