Melia et al AISTATS 2001

Citation

Marina Melia and Jianbo Shi. 2001. A Random Walks View of Spectral Segmentation. In AISTATS 2001.

Online version

Available on Marina Melia's Website

Summary

This paper gives a general theoretical interpretation of a wide variety of spectral methods. Drawing on the general problem of normalized graph cuts, the authors show that the problem can be interpreted in terms of a random walk.

The authors first present the general framework of normalized cuts. We assume we are given an index set $I$ and similarity matrix $S$ where entry $S_{ij}$ represents a similarity between item $i$ and item $j$. We then seek a partition of $I$ into two sets $A,{\overline {A}}$. This partition is a normalized cut if it minimizes the following criteria:

$NCut(A,{\overline {A}})=\left({\frac {1}{Vol(A)}}+{\frac {1}{vol({\overline {A}})}}\right)\sum _{i\in A;j\in {\overline {A}}}S_{ij},$

where, for $C\subseteq I$ , we define:

$Vol(C)=\sum _{i\in C}\sum _{j\in I}S_{ij}.$

However, the above problem is computationally intractable in general. We can approximate solutions to this problem using the following generalized eigenvalue problem:

$Lx=\lambda Dx$

Here, $D$ is a diagonal matrix with $D_{ii}=\sum _{j\in I}S_{ij}$ (we define this as the degree of $i$), and $L=D-S$.. By using the smallest eigenvectors from this solution, and looking for index sets in which the entry values are constant, we can get approximate solutions to the normalized graph cuts problem.

The authors recast the problem by simply rewriting the eigenvalue problem as:

$D^{-1}Sx=\lambda x$