2007/09/17 by Huaijun Qiu, Edwin R. Hancock · 1 citation
Computer Science · Neuroscience · Physics and Astronomy · Mathematics · #Topological and Geometric Data Analysis #Functional Brain Connectivity Studies #Complex Network Analysis Techniques #Embedding #Laplacian matrix #Random walk #Cluster analysis #Random walker algorithm #Computer science #Artificial intelligence #Spectral clustering #Laplace operator #Segmentation #Image segmentation #Mathematics #Graph #Pattern recognition (psychology) #Algorithm #Theoretical computer science #Image (mathematics)
paper · doi:10.1109/tpami.2007.1103
openalex publication_date 2007/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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.