Clustering and Embedding Using Commute Times Export

@article{citeulike:3371451, abstract = {This paper exploits the properties of the commute time between nodes of a graph for the purposes of clustering and embedding, and explores its applications to image segmentation and multi-body motion tracking. Our starting point is the lazy random walk on the graph, which is determined by the heatkernel of the graph and can be computed from the spectrum of the graph Laplacian. We characterize the random walk using the commute time (i.e. the expected time taken for a random walk to travel between two nodes and return) and show how this quantity may be computed from the Laplacian spectrum using the discrete Green\&\#8217;s function. Our motivation is that the commute time can be anticipated to be a more robust measure of the proximity of data than the raw proximity matrix. In this paper, we explore two applications of the commute time. The first is to develop a method for image segmentation using the eigenvector corresponding to the smallest eigenvalue of the commute time matrix. We show that our commute time segmentation method has the property of enhancing the intra-group coherence while weakening inter-group coherence and is superior to the normalized cut. The second application is to develop a robust multi-body motion tracking method using an embedding based on the commute time. Our embedding procedure preserves commute time, and is closely akin to kernel PCA, the Laplacian eigenmap and the diffusion map. We illustrate the results both on synthetic image sequences and real world video sequences, and compare our results with several alternative methods.}, address = {Washington, DC, USA}, author = {Qiu, Huaijun and Hancock, Edwin R.}, citeulike-article-id = {3371451}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1313055.1313286}, citeulike-linkout-1 = {http://dx.doi.org/10.1109/TPAMI.2007.1103}, doi = {10.1109/TPAMI.2007.1103}, issn = {0162-8828}, journal = {IEEE Trans. Pattern Anal. Mach. Intell.}, keywords = {commute-time}, number = {11}, pages = {1873--1890}, posted-at = {2008-10-03 19:16:53}, priority = {2}, publisher = {IEEE Computer Society}, title = {Clustering and Embedding Using Commute Times}, url = {http://dx.doi.org/10.1109/TPAMI.2007.1103}, volume = {29}, year = {2007} }

TY - JOUR ID - citeulike:3371451 L3 - citeulike-article-id:3371451 N2 - This paper exploits the properties of the commute time between nodes of a graph for the purposes of clustering and embedding, and explores its applications to image segmentation and multi-body motion tracking. Our starting point is the lazy random walk on the graph, which is determined by the heatkernel of the graph and can be computed from the spectrum of the graph Laplacian. We characterize the random walk using the commute time (i.e. the expected time taken for a random walk to travel between two nodes and return) and show how this quantity may be computed from the Laplacian spectrum using the discrete Green’s function. Our motivation is that the commute time can be anticipated to be a more robust measure of the proximity of data than the raw proximity matrix. In this paper, we explore two applications of the commute time. The first is to develop a method for image segmentation using the eigenvector corresponding to the smallest eigenvalue of the commute time matrix. We show that our commute time segmentation method has the property of enhancing the intra-group coherence while weakening inter-group coherence and is superior to the normalized cut. The second application is to develop a robust multi-body motion tracking method using an embedding based on the commute time. Our embedding procedure preserves commute time, and is closely akin to kernel PCA, the Laplacian eigenmap and the diffusion map. We illustrate the results both on synthetic image sequences and real world video sequences, and compare our results with several alternative methods. IS - 11 JF - IEEE Trans. Pattern Anal. Mach. Intell. SN - 0162-8828 AD - Washington, DC, USA EP - 1890 TI - Clustering and Embedding Using Commute Times PB - IEEE Computer Society VL - 29 SP - 1873 KW - commute-time AU - Qiu, Huaijun AU - Hancock, Edwin PY - 2007/// UR - http://dx.doi.org/10.1109/TPAMI.2007.1103 ER -