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 focuses on clustering and 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$

Now defining $P=D^{-1}S$, we can clearly see that each row of $P$ sums to 1. Therefore, we can interpret it as a transition matrix of a markov chain, where entry $P_{ij}$ represents the probability of transitioning from index $i$ to index $j$. This can be thought of as a random walk over the index set. We can thus interpret the a eigenvalue in this problem as groups of index sets which have similar transition probabilities to any other indices. That is, if we group our indices by the similar entries in an eigenvector, we have found subsets of $I$ which have similar transition probabilities to each other.

The authors consequently propose the following general approach. (1) Solve the eigenvalue problem $D^{-1}Sx=\lambda x$ (2) select the k-1 eigenvectors with the k-1 largest eigenvalues -- excluding the largest eigenvalue and (3) clustering the entries as if they were k-1 dimensional vectors. This approach gives an approximate solution to the normalized graph cuts problem.

Application to Social Media

The paper does not mention specific applications, so I make a brief note here about this. For social media, a common problem is desiring to partition a large social network, represented as a graph, into several sections. For example, perhaps we want to try and identify different countries from a large social graph of online friendship. The above method yields solutions to just such a problem: partitioning of the index set corresponds to clustering the nodes in a graph.

However, there is one important practical piece which is (understandably) left out of this paper. It is assumed that a similarity matrix between all nodes is available. While this may seem simple, there are many ways to calculate the similarity between nodes in a graph. This decision is often critical in the analysis, and is essential to random walk interpretation provided by this paper: the transition probabilities defined above are directly related to the similarity between the nodes.

Another example of a related application is Latent semantic indexing.