The DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index.
On clusterings-good, bad and spectral
Abstract
We propose a new measure for assessing the quality of a clustering. A simple heuristic is shown to give worst-case guarantees under the new measure. Then we present two results regarding the quality of the clustering found by a popular spectral algorithm. One proffers worst case guarantees whilst the other shows that if there exists a "good" clustering then the spectral algorithm will find one close to it.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,502
Co-clustering documents and words using bipartite spectral graph partitioning
Dhillon, I. S. (2001) · Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/502512.502550 · Cited by 1,697
Latent semantic indexing: a probabilistic analysis
Papadimitriou, C. H., Tamaki, H., Raghavan, P., & Vempala, S. (1998) · Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems · doi:10.1145/275487.275505 · Cited by 863
Self-citationNormalized cuts and image segmentation
Shi, J., & Malik, J. (2002) · Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.1997.609407 · Cited by 849
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
Leighton, T., & Rao, S. (1999) · Journal of the ACM · doi:10.1145/331524.331526 · Cited by 820
Approximate counting, uniform generation and rapidly mixing Markov chains
Sinclair, A., & Jerrum, M. (1989) · Information and Computation · doi:10.1016/0890-5401(89)90067-9 · Cited by 735
Segmentation using eigenvectors: a unifying view
Weiss, Y. (1999) · Proceedings of the Seventh IEEE International Conference on Computer Vision · doi:10.1109/iccv.1999.790354 · Cited by 729
Error and Perturbation Bounds for Subspaces Associated with Certain Eigenvalue Problems
Stewart, G. W. (1973) · SIAM Review · doi:10.1137/1015095 · Cited by 573
Latent Semantic Indexing: A Probabilistic Analysis
Papadimitriou, C. H., Raghavan, P., Tamaki, H., & Vempala, S. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.2000.1711 · Cited by 556
Self-citation
Cited by
A Survey of Clustering Data Mining Techniques
Berkhin, P. (2006) · Grouping Multidimensional Data · doi:10.1007/3-540-28349-8_2 · Cited by 2,804
Computing Communities in Large Networks Using Random Walks
Pons, P., & Latapy, M. (2005) · Lecture Notes in Computer Science · doi:10.1007/11569596_31 · Cited by 2,048
Brandes, U., Delling, D., Gaertler, M., Gorke, R., Hoefer, M., Nikoloski, Z., & Wagner, D. (2008) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2007.190689 · Cited by 1,242
Kernel k-means: spectral clustering and normalized cuts
Dhillon, I. S., Guan, Y., & Kulis, B. (2004) · Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1014052.1014118 · Cited by 1,193
Clustering data streams: theory and practice
Guha, S., Meyerson, A., Mishra, N., Motwani, R., & O'Callaghan, L. (2003) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2003.1198387 · Cited by 882
Social big data: recent achievements and new challenges
Bello-Orgaz, G., Jung, J. J., & Camacho, D. (2016) · Information Fusion · doi:10.1016/j.inffus.2015.08.005 · Cited by 846
“Considering both connectivity and density, a possible definition of a graph cluster could be a connected component or a maximal clique [48] .”
BackgroundA survey of kernel and spectral methods for clustering
Filippone, M., Camastra, F., Masulli, F., & Rovetta, S. (2008) · Pattern Recognition · doi:10.1016/j.patcog.2007.05.018 · Cited by 827
Semi-Supervised Learning on Riemannian Manifolds
Belkin, M., & Niyogi, P. (2004) · Machine Learning · doi:10.1023/b:mach.0000033120.25363.1e · Cited by 781
Clustering on the Unit Hypersphere using von Mises-Fisher Distributions
Banerjee, A., Dhillon, I. S., Ghosh, J., & Sra, S. (2005) · MPG.PuRe (Max Planck Society) · doi:10.5555/1046920.1088718 · Cited by 766
(2015) · Chapman & Hall/CRC eBooks · doi:10.1201/b19706 · Cited by 643
Graph mining: Laws, generators, and algorithms
Chakrabarti, D., & Faloutsos, C. (2006) · ACM Computing Surveys · doi:10.1145/1132952.1132954 · Cited by 609
Spectral partitioning of random graphs
McSherry, F. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959929 · Cited by 584
Consistency of spectral clustering
von Luxburg, U., Belkin, M., & Bousquet, O. (2008) · The Annals of Statistics · doi:10.1214/009053607000000640 · Cited by 540
Community Detection and Stochastic Block Models
Abbe, E. (2018) · now publishers, Inc. eBooks · doi:10.1561/9781680834772 · Cited by 544
Stability of graph communities across time scales
Delvenne, J.-C., Yaliraki, S. N., & Barahona, M. (2010) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0903215107 · Cited by 475
Towards a theoretical foundation for Laplacian-based manifold methods
Belkin, M., & Niyogi, P. (2008) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.08.006 · Cited by 464
Beyond streams and graphs: dynamic tensor analysis
Sun, J., Tao, D., & Faloutsos, C. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150445 · Cited by 462
Networks and the Epidemiology of Infectious Disease
Danon, L., Ford, A. P., House, T., Jewell, C. P., Keeling, M. J., Roberts, G. O., Ross, J. V., & Vernon, M. C. (2011) · Interdisciplinary Perspectives on Infectious Diseases · doi:10.1155/2011/284909 · Cited by 454
Graph Clustering and Minimum Cut Trees
Flake, G. W., Tarjan, R. E., & Tsioutsiouliklis, K. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129093 · Cited by 333
Neighborhood Formation and Anomaly Detection in Bipartite Graphs
Sun, J., Qu, H., Chakrabarti, D., & Faloutsos, C. (2006) · Fifth IEEE International Conference on Data Mining (ICDM'05) · doi:10.1109/icdm.2005.103 · Cited by 308
Azar, Y., Fiat, A., Karlin, A., McSherry, F., & Saia, J. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380859 · Cited by 289
Name disambiguation in author citations using a K-way spectral clustering method
Han, H., Zha, H., & Giles, C. L. (2005) · Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries · doi:10.1145/1065385.1065462 · Cited by 272
Incremental tensor analysis: Theory and applications
Sun, J., Tao, D., Papadimitriou, S., Yu, P. S., & Faloutsos, C. (2008) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1409620.1409621 · Cited by 254
Metadata
- Authors
- Kannan, R., Vempala, S., & Veta, A.
- Venue
- Proceedings 41st Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE Comput. Soc
- Published
- 2002-11-07
- Pages
- 367-377
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2130891992
- Cited by
- 372
- References
- 15
- FWCI
- 20.66
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.