ABSTRACT
Graph clustering using the method of normalized graph cuts is nowadays a standard technique in computer vision and other domains, owing to the seminal work of Shi and Malik. This method was extended to multiple clusters (K > 2) by Yu and Shi.
This talk will focus on Yu and Shi’s method, with clarification of certain details. The method proceeds in two stages. During the first stage, the clustering problem is formulated as an optimization problem which is translated in matrix form using a graph Laplacian.
This problem is NP-hard, so a relaxed continuous version is considered; I will show that this reduces to an eigenvalue problem. The second stage consists of obtaining a discrete solution which approximates the continuous solution.
In the first part of this talk, I will describe how to set up and solve stage 1 of the clustering problem. I conclude by sketching a generalization of normalized cuts to graphs with negative edges. This part assumes no prior knowledge.
Slides may be found here…