Graph Cuts without Eigenvectors

Опубликовано 6 сентября 2016, 6:32

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.