Fetching the paper…
Reading the bibliography…
In this paper we study variants of the widely used spectral clustering that partitions a graph into k clusters by (1) embedding the vertices of a graph into a low-dimensional space using the bottom eigenvectors of the Laplacian matrix, and (2) grouping the embedded points into k clusters via k-means algorithms.
The rotation of eigenvectors by a perturbation. iii
Chandler Davis and William M. Kahan · 1970
Earlier work this paper cites.
Image segmentation by clustering
Guy B. Coleman and Harry C. Andrews · 1979
Earlier work this paper cites.
Sparsest cuts and bottlenecks in graphs
David W. Matula and Farhad Shahrokhi · 1990
Earlier work this paper cites.
Lectures on finite markov chains
L. Saloff-Coste · 1997
Earlier work this paper cites.
Approximate nearest neighbors: towards removing the curse of dimensionality
Piotr Indyk and Rajeev Motwani · 1998
Earlier work this paper cites.
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
Frank T. Leighton and Satish Rao · 1999
Earlier work this paper cites.
Normalized cuts and image segmentation
Jianbo Shi and Jitendra Malik · 2000
Earlier work this paper cites.
Spectral partitioning of random graphs
Frank McSherry · 2001
Earlier work this paper cites.
On spectral clustering: Analysis and an algorithm
Andrew Y. Ng, Michael I. Jordan, and Yair Weiss · 2002
Earlier work this paper cites.
An elementary proof of a theorem of Johnson and Lindenstrauss
Sanjoy Dasgupta and Anupam Gupta · 2003
Earlier work this paper cites.
On clusterings: Good, bad and spectral
Ravi Kannan, Santosh Vempala, and Adrian Vetta · 2004
Earlier work this paper cites.
A combinatorial, primal-dual approach to semidefinite programs
Sanjeev Arora and Satyen Kale · 2007
Earlier work this paper cites.
k k -means++: The advantages of careful seeding
David Arthur and Sergei Vassilvitskii · 2007
Earlier work this paper cites.
A tutorial on spectral clustering
Ulrike von Luxburg · 2007
Earlier work this paper cites.
On partitioning graphs via single commodity flows
Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, and Nisheeth K. Vishnoi · 2008
Cited alongside, same era.
Approximation algorithms for unique games
Luca Trevisan · 2008
Cited alongside, same era.
Expander flows, geometric embeddings and graph partitioning
Sanjeev Arora, Satish Rao, and Umesh V. Vazirani · 2009
Cited alongside, same era.
A local graph partitioning algorithm using heat kernel pagerank
Fan R. K. Chung · 2009
Cited alongside, same era.
Breaking the multicommodity flow barrier for O ( log n ) {O}(\sqrt{\log n}) -approximations to sparsest cut
Jonah Sherman · 2009
Cited alongside, same era.
Subexponential algorithms for unique games and related problems
Sanjeev Arora, Boaz Barak, and David Steurer · 2010
Cited alongside, same era.
Multi-way spectral partitioning and higher-order Cheeger inequalities
James R. Lee, Shayan Oveis Gharan, and Luca Trevisan · 2012
Later among the works it cites.
Many sparse cuts via higher eigenvalues
Anand Louis, Prasad Raghavendra, Prasad Tetali, and Santosh Vempala · 2012
Later among the works it cites.
Approximating the exponential, the Lanczos method and an O ~ ( m ) \widetilde{O}(m) -time spectral algorithm for balanced separator
Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K Vishnoi · 2012
Later among the works it cites.
The effectiveness of Lloyd-type methods for the k k -means problem
Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy · 2012
Later among the works it cites.
A local algorithm for finding well-connected clusters
Zeyuan Allen-Zhu, Silvio Lattanzi, and Vahab S. Mirrokni · 2013
Later among the works it cites.
A theoretical approach to the clustering selection problem
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Community detection in graphs
Santo Fortunato · 2010
Cited alongside, same era.
Spectral clustering and the high-dimensional stochastic blockmodel
Karl Rohe, Sourav Chatterjee, and Bin Yu · 2011
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2011
Cited alongside, same era.
Spectral sparsification of graphs
Daniel A. Spielman and Shang-Hua Teng · 2011
Cited alongside, same era.
The multiplicative weights update method: a meta-algorithm and applications
Sanjeev Arora, Elad Hazan, and Satyen Kale · 2012
Cited alongside, same era.
Center-based clustering under perturbation stability
Pranjal Awasthi, Avrim Blum, and Or Sheffet · 2012
Cited alongside, same era.
Shai Ben-David · 2013
Later among the works it cites.
Improved Cheeger’s inequality: analysis of spectral partitioning algorithms through higher order spectral gap
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan · 2013
Later among the works it cites.
Spectral concentration, robust k k -center, and simple clustering
Tamal K. Dey, Alfred Rossi, and Anastasios Sidiropoulos · 2014
Closest in time.
An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford · 2014
Closest in time.
Partitioning into expanders
Shayan Oveis Gharan and Luca Trevisan · 2014
Closest in time.
A simple SVD algorithm for finding hidden partitions
Van Vu · 2014
Closest in time.
Pavel Kolev and Kurt Mehlhorn · 2015
Closest in time.
Correlation clustering with noisy partial information
Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan · 2015
Closest in time.