Hitting Time Properties of Spectral Clusters

Spectral clustering methods use eigenvectors for data segmentation, where the underlying matrix reflects the similarity structure in the data points. Piecewise constant eigenvectors are considered as indicators of a partition. We will call its components spectral clusters or classes. Main differences in the methods concern the concrete type of matrix (see \cite{wy}, \cite{ta1}) and the utilization of the eigenstructure (\cite{wy}). The methods are motivated by equivalence properties of spectral clusters (see \cite{ms}, \cite{ta1}) and the fact that spectral clusters are solutions to suitable optimization criteria (\cite{sm}, \cite{ms}, \cite{mx}). \newline In the present paper we give a very general presentation of spectral clustering and a corresponding segmentation criterion, which includes the mentioned methods as special cases. Additionally we characterize spectral clusters in terms of hitting times and give a novel segmentation criterion based on hitting times. We achieve this by utilizing the similarity structure of the data to define the transition matrix P of a Markov chain which is used for spectral clustering. The result is due to the fact that the eigenvectors of P coincide with those of its fundamental matrix, whose entries may be interpreted in terms of hitting times (\cite{al}). \begin{thebibliography}{99} \bibitem{al} Aldous D., Fill J.A., \emph{% Reversible Markov Chains and Random Walks on Graphs}. Draft http://www.stat.berkeley.edu/users/aldous/RWG/book.html \bibitem{ms} Meila M., Shi J. (2001), A Random Walks View of Spectral Segmentation. Proceedings International Workshop on AI and Statistics \bibitem{mx} Meila M., Xu L. (2003), Multiway Cuts and Spectral Clustering. Homepage, http://www.stat.washington.edu/mmp/ \bibitem{sm} Shi J., Malik J. (2000), Normalized Cuts and Image Segmentation. IEEE Transactions(PAMI) ....