Graph Cuts without Eigenvectors

906 views · Published 6 September 2016 · 39:50 · Indexed 8 November 2026

Channel: Microsoft Research · 2016 · Science & Technology

Watch on YouTube

Graph clustering---clustering the nodes of a graph---is a fundamental problem arising in many machine learning and data mining applications.  The last few years have seen a surge of interest in spectral clustering methods, which use eigenvectors of the graph adjacency matrix (or a matrix derived from the adjacency matrix) to optimize one of several graph cut objective functions.  These methods are powerful and theoretically well-motivated; however, computing eigenvectors of a large matrix is computationally expensive and requires significant memory overhead.    I will describe my recent research on optimizing spectral clustering objectives without costly eigenvector computation.  After deriving a mathematical connection between spectral clustering objectives and weighted kernel k-means, I will propose a simple iterative algorithm for optimizing various graph cut objectives, and then embed this into a multilevel algorithm.  This resulting algorithm outperforms state-of-the-art spectral clustering algorithms in terms of quality (graph cut value), speed (up to 2000 times faster on graphs under a million nodes), and memory usage (requiring memory on the order of the input graph).  I will also discuss applications of this algorithm to image segmentation, protein network clustering, and social network analysis.    This is joint work with Inderjit Dhillon and Yuqiang Guan.

More from this channel