@article{filippone2008ska, author = {Filippone, M. and Camastra, F. and Masulli, F. and Rovetta, S.}, title = {A survey of kernel and spectral methods for clustering}, journal = {Pattern recognition}, publisher = {Elsevier}, year = {2008}, volume = {41}, number = {1}, pages = {176--190}, keywords = {community, detection, graph, kernel, spectral, survey, theory} }

%0 = article %A = Filippone, M. and Camastra, F. and Masulli, F. and Rovetta, S. %D = 2008 %I = Elsevier %T = A survey of kernel and spectral methods for clustering

@inproceedings{1454017, author = {Symeonidis, Panagiotis and Nanopoulos, Alexandros and Manolopoulos, Yannis}, title = {Tag recommendations based on tensor dimensionality reduction}, booktitle = {RecSys '08: Proceedings of the 2008 ACM conference on Recommender systems}, publisher = {ACM}, address = {New York, NY, USA}, year = {2008}, pages = {43--50}, url = {http://portal.acm.org/citation.cfm?id=1454017}, doi = {http://doi.acm.org/10.1145/1454008.1454017}, isbn = {978-1-60558-093-7}, keywords = {community, detection, graph, recommender, spectral, tag, theory} }

%0 = inproceedings %A = Symeonidis, Panagiotis and Nanopoulos, Alexandros and Manolopoulos, Yannis %B = RecSys '08: Proceedings of the 2008 ACM conference on Recommender systems %C = New York, NY, USA %D = 2008 %I = ACM %T = Tag recommendations based on tensor dimensionality reduction %U = http://portal.acm.org/citation.cfm?id=1454017

@article{1288832, author = {Luxburg, Ulrike}, title = {A tutorial on spectral clustering}, journal = {Statistics and Computing}, publisher = {Kluwer Academic Publishers}, address = {Hingham, MA, USA}, year = {2007}, volume = {17}, number = {4}, pages = {395--416}, url = {http://portal.acm.org/citation.cfm?id=1288832}, doi = {http://dx.doi.org/10.1007/s11222-007-9033-z}, issn = {0960-3174}, keywords = {community, detection, graph, spectral, theory} }

%0 = article %A = Luxburg, Ulrike %C = Hingham, MA, USA %D = 2007 %I = Kluwer Academic Publishers %T = A tutorial on spectral clustering %U = http://portal.acm.org/citation.cfm?id=1288832

@article{newman2006fcs, author = {Newman, MEJ}, title = {Finding community structure in networks using the eigenvectors of matrices}, journal = {Physical Review E}, publisher = {APS}, year = {2006}, volume = {74}, number = {3}, pages = {36104}, keywords = {community, detection, graph, modularity, spectral, theory} }

%0 = article %A = Newman, MEJ %D = 2006 %I = APS %T = Finding community structure in networks using the eigenvectors of matrices

@article{newman2006mac, author = {Newman, MEJ}, title = {Modularity and community structure in networks}, journal = {Proceedings of the National Academy of Sciences}, publisher = {National Acad Sciences}, year = {2006}, volume = {103}, number = {23}, pages = {8577--8582}, keywords = {community, detection, graph, modularity, spectral, theory} }

%0 = article %A = Newman, MEJ %D = 2006 %I = National Acad Sciences %T = Modularity and community structure in networks

Recently, a variety of clustering algorithms have been proposed to handle data that is not linearly separable. Spectral clustering and kernel k-means are two such methods that are seemingly quite different. In this paper, we show that a general weighted kernel k-means objective is mathematically equivalent to a weighted graph partitioning objective. Special cases of this graph partitioning objective include ratio cut, normalized cut and ratio association. Our equivalence has important consequences: the weighted kernel k-means algorithm may be used to directly optimize the graph partitioning objectives, and conversely, spectral methods may be used to optimize the weighted kernel k-means objective. Hence, in cases where eigenvector computation is prohibitive, we eliminate the need for any eigenvector computation for graph partitioning. Moreover, we show that the Kernighan-Lin objective can also be incorporated into our framework, leading to an incremental weighted kernel k-means algorithm for local optim ization of the objective. We further discuss the issue of convergence of weighted kernel k-means for an arbitrary graph affinity matrix and provide a number of experimental results. These results show that non-spectral methods for graph partitioning are as effective as spectral methods and can be used for problems such as image segmentation in addition to data clustering.

@techreport{Dhillon:EtAl:05, author = {Dhillon, Inderjit S. and Guan, Yuqiang and Kulis, Brian}, title = {A Unified View of Kernel k-means, Spectral Clustering and Graph Cuts}, year = {2005}, number = {TR-04-25}, url = {http://www.cs.utexas.edu/ftp/pub/techreports/tr04-25.pdf}, keywords = {community, detection, graph, k-means, spectral, theory}, abstract = {Recently, a variety of clustering algorithms have been proposed to handle data that is not linearly separable. Spectral clustering and kernel k-means are two such methods that are seemingly quite different. In this paper, we show that a general weighted kernel k-means objective is mathematically equivalent to a weighted graph partitioning objective. Special cases of this graph partitioning objective include ratio cut, normalized cut and ratio association. Our equivalence has important consequences: the weighted kernel k-means algorithm may be used to directly optimize the graph partitioning objectives, and conversely, spectral methods may be used to optimize the weighted kernel k-means objective. Hence, in cases where eigenvector computation is prohibitive, we eliminate the need for any eigenvector computation for graph partitioning. Moreover, we show that the Kernighan-Lin objective can also be incorporated into our framework, leading to an incremental weighted kernel k-means algorithm for local optim ization of the objective. We further discuss the issue of convergence of weighted kernel k-means for an arbitrary graph affinity matrix and provide a number of experimental results. These results show that non-spectral methods for graph partitioning are as effective as spectral methods and can be used for problems such as image segmentation in addition to data clustering. } }

%0 = techreport %A = Dhillon, Inderjit S. and Guan, Yuqiang and Kulis, Brian %B = } %C = %D = 2005 %I = %T = A Unified View of Kernel k-means, Spectral Clustering and Graph Cuts} %U = http://www.cs.utexas.edu/ftp/pub/techreports/tr04-25.pdf

@article{white2005sca, author = {White, S. and Smyth, P.}, title = {A spectral clustering approach to finding communities in graph}, booktitle = {SIAM Data Mining}, year = {2005}, keywords = {community, detection, graph, spectral, theory} }

%0 = article %A = White, S. and Smyth, P. %B = SIAM Data Mining %D = 2005 %T = A spectral clustering approach to finding communities in graph

@article{estrada2003smb, author = {Estrada, E. and Rodriguez-Velázquez, J.A.}, title = {Spectral measures of bipartivity in complex networks}, journal = {SIAM Rev Phys Rev E}, publisher = {APS}, year = {2003}, volume = {72}, pages = {046105}, keywords = {bipartite, community, detection, graph, modularity, spectral, theory} }

%0 = article %A = Estrada, E. and Rodriguez-Velázquez, J.A. %D = 2003 %I = APS %T = Spectral measures of bipartivity in complex networks

@article{verma2003csc, author = {Verma, D. and Meila, M.}, title = {A comparison of spectral clustering algorithms}, journal = {University of Washington, Tech. Rep. UW-CSE-03-05-01}, year = {2003}, keywords = {community, detection, graph, spectral, theory} }

%0 = article %A = Verma, D. and Meila, M. %D = 2003 %T = A comparison of spectral clustering algorithms

@inproceedings{coclustering01, author = {Dhillon, Inderjit S.}, title = {Co-clustering documents and words using bipartite spectral graph partitioning}, booktitle = {KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining}, publisher = {ACM Press}, address = {New York, NY, USA}, year = {2001}, pages = {269--274}, url = {http://portal.acm.org/citation.cfm?id=502512.502550}, doi = {10.1145/502512.502550}, isbn = {158113391X}, keywords = {community, detection, graph, spectral, theory} }

%0 = inproceedings %A = Dhillon, Inderjit S. %B = KDD '01: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining %C = New York, NY, USA %D = 2001 %I = ACM Press %T = Co-clustering documents and words using bipartite spectral graph partitioning %U = http://portal.acm.org/citation.cfm?id=502512.502550

Despite many empirical successes of spectral clustering methods| algorithms that cluster points using eigenvectors of matrices derived from the data|there are several unresolved issues. First, there are a wide variety of algorithms that use the eigenvectors in slightly dierent ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems. 1

@inproceedings{Ng01onspectral, author = {Ng, Andrew Y. and Jordan, Michael I. and Weiss, Yair}, title = {On spectral clustering: Analysis and an algorithm}, booktitle = {Advances in Neural Information Processing Systems 14}, publisher = {MIT Press}, year = {2001}, pages = {849--856}, keywords = {clustering, community, detection, graph, spectral, theory}, abstract = {Despite many empirical successes of spectral clustering methods| algorithms that cluster points using eigenvectors of matrices derived from the data|there are several unresolved issues. First, there are a wide variety of algorithms that use the eigenvectors in slightly dierent ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems. 1} }

%0 = inproceedings %A = Ng, Andrew Y. and Jordan, Michael I. and Weiss, Yair %B = Advances in Neural Information Processing Systems 14 %D = 2001 %I = MIT Press %T = On spectral clustering: Analysis and an algorithm

@techreport{Spielman:1996, author = {Spielman, Daniel A. and Teng, Shang}, title = {Spectral Partitioning Works: Planar Graphs and Finite Element Meshes}, publisher = {University of California at Berkeley}, address = {Berkeley, CA, USA}, year = {1996}, keywords = {clustering, community, detection, graph, spectral, survey, theory} }

%0 = techreport %A = Spielman, Daniel A. and Teng, Shang %B = } %C = Berkeley, CA, USA %D = 1996 %I = University of California at Berkeley %T = Spectral Partitioning Works: Planar Graphs and Finite Element Meshes} %U =

@inproceedings{Alpert95spectralpartitioning:, author = {Alpert, Charles J. and Kahng, Andrew B. and zen Yao, So}, title = {Spectral partitioning: The more eigenvectors, the better}, booktitle = {Proc. ACM/IEEE Design Automation Conf}, year = {1995}, pages = {195--200}, keywords = {community, detection, graph, spectral, theory} }

%0 = inproceedings %A = Alpert, Charles J. and Kahng, Andrew B. and zen Yao, So %B = Proc. ACM/IEEE Design Automation Conf %D = 1995 %T = Spectral partitioning: The more eigenvectors, the better

@article{journals/tcad/ChanSZ94, author = {Chan, Pak K. and Schlag, Martine D. F. and Zien, Jason Y.}, title = {Spectral K-way ratio-cut partitioning and clustering.}, journal = {IEEE Trans. on CAD of Integrated Circuits and Systems}, year = {1994}, volume = {13}, number = {9}, pages = {1088-1096}, url = {http://dblp.uni-trier.de/db/journals/tcad/tcad13.html#ChanSZ94}, keywords = {community, detection, graph, partitioning, spectral, theory} }

%0 = article %A = Chan, Pak K. and Schlag, Martine D. F. and Zien, Jason Y. %D = 1994 %T = Spectral K-way ratio-cut partitioning and clustering. %U = http://dblp.uni-trier.de/db/journals/tcad/tcad13.html#ChanSZ94

@article{partitioning89, author = {Pothen, A. and Simon, H.D. and Liou, K.P.}, title = {Partitioning Sparse Matrices with Eigenvectors of Graphs}, journal = {SIAM J. MATRIX ANAL. APPLIC.}, year = {1990}, volume = {11}, number = {3}, pages = {430--452}, url = {http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19970011963_1997016998.pdf }, keywords = {clustering, community, graph, partitioning, spectral, theory} }

%0 = article %A = Pothen, A. and Simon, H.D. and Liou, K.P. %D = 1990 %T = Partitioning Sparse Matrices with Eigenvectors of Graphs %U = http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19970011963_1997016998.pdf

@article{donath1973lbp, author = {Donath, W.E. and Hoffman, A.J.}, title = {Lower bounds for the partitioning of graphs}, journal = {IBM Journal of Research and Development}, year = {1973}, volume = {17}, number = {5}, pages = {420--425}, keywords = {clustering, community, detection, graph, spectral, theory} }

%0 = article %A = Donath, W.E. and Hoffman, A.J. %D = 1973 %T = Lower bounds for the partitioning of graphs