A Random Walks View of Spectral Segmentation.

Published 4 January 2001

Marina Meilă, Jianbo Shi

Citations631

TL;DR

It is proved that the Normalized Cut method arises naturally from the framework and a complete characterization of the cases when the Normalization Cut algorithm is exact is provided.

Abstract

We present a new view of clustering and segmentation by pairwise similarities. We interpret the similarities as edge flows in a Markov random walk and study the eigenvalues and eigenvectors of the walk&apos;s transition matrix. This view shows that spectral methods for clustering and segmentation have a probabilistic foundation. We prove that the Normalized Cut method arises naturally from our framework and we provide a complete characterization of the cases when the Normalized Cut algorithm is exact. Then we discuss other spectral segmentation and clustering methods showing that they are essentially the same as NCut.

Keywords

Computer SciencePhysics and Astronomy

IEEE Transactions on Pattern Analysis and Machine IntelligenceNormalized cuts and image segmentation

15,696 Citations2000Jianbo Shi, Jitendra Malik

Journal of the American Society for Information ScienceIndexing by latent semantic analysis

12,677 Citations1990Scott Deerwester, Susan Dumais +3 more

Journal of the ACMAuthoritative sources in a hyperlinked environment

9,060 Citations1999Jon Kleinberg

This work proposes and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure, and has connections to the eigenvectors of certain matrices associated with the link graph.

View PDF

Regional conference series in mathematicsSpectral Graph Theory

5,722 Citations1996Fan Chung

Segmentation using eigenvectors: a unifying view

722 Citations1999Yaakov Weiss

A unified treatment of eigenvectors of block matrices based on eigendecompositions in the context of segmentation is given, and close connections between them are shown while highlighting their distinguishing features.

On clusterings-good, bad and spectral

380 Citations2002Ramachandran Kannan, S. Vempala +1 more

Two results regarding the quality of the clustering found by a popular spectral algorithm are presented, one proffers worst case guarantees whilst the other shows that if there exists a "good" clustering then the spectral algorithm will find one close to it.

Learning Segmentation by Random Walks

370 Citations2000Marina Meilă, Jianbo Shi

This interpretation shows that spectral methods for clustering and segmentation have a probabilistic foundation and proves that the Normalized Cut method arises naturally from the framework.

Lecture notes in computer scienceA factorization approach to grouping

296 Citations1998P. Perona, William T. Freeman

The foreground group in a scene may be ‘discovered’ and computed as a factorized approximation to the pairwise affinity of the elements in the scene, and an algorithm called ‘affinity factorization’ is obtained which may be used for grouping.

Clustering in large graphs and matrices

187 Citations1999Petros Drineas, Alan Frieze +3 more

It is argued that in fact the relaxation provides a generalized clustering which is useful in its own right and can be applied to problems of very large size which typically arise in modern applications.