Given a set of data, the goal of clustering is to partition
the data into different groups according to their similarities.
Often (as in computer vision) the data is given in terms of a similiary graph with weights between nodes indicating a measure of similarity. The method of normalized graph cuts, due to Shi and Malik, is one of the most effective methods for graph
clustering. This method was extended to multiple clusters
(K > 2) by Yu and Shi. 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; this reduces to an eigenvalue problem. The second stage consists of obtaining a discrete solution which approximates the continuous solution.
I will conclude by sketching a generalization of normalized cuts to graphs with negative edges (which capture dissimilarity).