%0 Journal Article %1 gallier2013notes %A Gallier, Jean %D 2013 %K approximate clustering graphs notes readings spectral survey %T Notes on Elementary Spectral Graph Theory. Applications to Graph Clustering Using Normalized Cuts %U http://arxiv.org/abs/1311.2492 %X 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.

@article{gallier2013notes, 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.}, added-at = {2020-01-15T03:02:34.000+0100}, author = {Gallier, Jean}, biburl = {https://www.bibsonomy.org/bibtex/2dbb8325608cfd6c20d2fcb9c1d293a02/kirk86}, description = {[1311.2492] Notes on Elementary Spectral Graph Theory. Applications to Graph Clustering Using Normalized Cuts}, interhash = {647cc649848c13199bd9cc466c256edf}, intrahash = {dbb8325608cfd6c20d2fcb9c1d293a02}, keywords = {approximate clustering graphs notes readings spectral survey}, note = {cite arxiv:1311.2492Comment: 76 pages}, timestamp = {2020-01-15T03:02:34.000+0100}, title = {Notes on Elementary Spectral Graph Theory. Applications to Graph Clustering Using Normalized Cuts}, url = {http://arxiv.org/abs/1311.2492}, year = 2013 }