Abstract
These are notes on the method of normalized graph cuts and its applications
to graph clustering. I provide a fairly thorough treatment of this deeply
original method due to Shi and Malik, including complete proofs. I include the
necessary background on graphs and graph Laplacians. I then explain in detail
how the eigenvectors of the graph Laplacian can be used to draw a graph. This
is an attractive application of graph Laplacians. The main thrust of this paper
is the method of normalized cuts. I give a detailed account for K = 2 clusters,
and also for K > 2 clusters, based on the work of Yu and Shi. Three points that
do not appear to have been clearly articulated before are elaborated:
1. The solutions of the main optimization problem should be viewed as tuples
in the K-fold cartesian product of projective space RP^N-1.
2. When K > 2, the solutions of the relaxed problem should be viewed as
elements of the Grassmannian G(K,N).
3. Two possible Riemannian distances are available to compare the closeness
of solutions: (a) The distance on (RP^N-1)^K. (b) The distance on the
Grassmannian.
I also clarify what should be the necessary and sufficient conditions for a
matrix to represent a partition of the vertices of a graph to be clustered.
Users
Please
log in to take part in the discussion (add own reviews or comments).