### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | Advances in Neural Information Processing Systems 18 - Proceedings of the 2005 Conference |

Pages | 955-962 |

Number of pages | 8 |

State | Published - Dec 1 2005 |

Event | 2005 Annual Conference on Neural Information Processing Systems, NIPS 2005 - Vancouver, BC, Canada Duration: Dec 5 2005 → Dec 8 2005 |

### Publication series

Name | Advances in Neural Information Processing Systems |
---|---|

ISSN (Print) | 1049-5258 |

### Other

Other | 2005 Annual Conference on Neural Information Processing Systems, NIPS 2005 |
---|---|

Country | Canada |

City | Vancouver, BC |

Period | 12/5/05 → 12/8/05 |

### All Science Journal Classification (ASJC) codes

- Computer Networks and Communications
- Information Systems
- Signal Processing

### Keywords

- Algorithms and architectures
- Learning theory

## Fingerprint Dive into the research topics of 'Diffusion maps, spectral clustering and eigenfunctions of Fokker-Planck operators'. Together they form a unique fingerprint.

## Cite this

*Advances in Neural Information Processing Systems 18 - Proceedings of the 2005 Conference*(pp. 955-962). (Advances in Neural Information Processing Systems).