Partitioning Well-Clustered Graphs : Spectral Clustering Works!
- Submitting institution
-
University of Bristol
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 95855907
- Type
- E - Conference contribution
- DOI
-
-
- Title of conference / published proceedings
- Proceedings of The 28th Conference on Learning Theory
- First page
- 1423
- Volume
- -
- Issue
- -
- ISSN
- 2640-3498
- Open access status
- Out of scope for open access requirements
- Month of publication
- July
- Year of publication
- 2015
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
D - Fundamentals of Computing
- Citation count
- -
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper extended the study of spectral clustering in well-clustered settings beyond the connectivity parameters of the pieces returned. It was the first to give upper bounds on the symmetric differences between the returned clusters and optimal ones based on separations between kth and (k+1)-th eigenvalues. Many subsequent papers in both theory and practice build upon tools and ideas from this paper. They include improving the dependence of the quality on the eigenvalue gap [Kolev-Mehlhorn, ESA’16, Mizutani IPL`20], extending bounds based on well-clusteredness to broader problems [Zhang-Zhao-Feng, ICESS’19, Louis-Venkat, FSTTCS’19], and more efficient randomized clustering algorithms [Be-Peng, SODA`20].
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -