Article

Regularized spectral clustering under the Degree-Corrected Stochastic Blockmodel

Authors:

Karl RoheAuthors Info & Claims

NIPS'13: Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2

Pages 3120 - 3128

Published: 05 December 2013 Publication History

Abstract

Spectral clustering is a fast and popular algorithm for finding clusters in networks. Recently, Chaudhuri et al. [1] and Amini et al. [2] proposed inspired variations on the algorithm that artificially inflate the node degrees for improved statistical performance. The current paper extends the previous statistical estimation results to the more canonical spectral clustering algorithm in a way that removes any assumption on the minimum degree and provides guidance on the choice of the tuning parameter. Moreover, our results show how the "star shape" in the eigenvectors-a common feature of empirical networks-can be explained by the Degree-Corrected Stochastic Blockmodel and the Extended Planted Partition model, two statistical models that allow for highly heterogeneous degrees. Throughout, the paper characterizes and justifies several of the variations of the spectral clustering algorithm in terms of these models.

References

[1]

K. Chaudhuri, F. Chung, and A. Tsiatas. Spectral clustering of graphs with general degrees in the extended planted partition model. Journal of Machine Learning Research, pages 1-23, 2012.

[2]

Arash A Amini, Aiyou Chen, Peter J Bickel, and Elizaveta Levina. Pseudo-likelihood methods for community detection in large sparse networks. 2012.

[3]

F. McSherry. Spectral partitioning of random graphs. In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 529-537. IEEE, 2001.

[4]

Anirban Dasgupta, John E Hopcroft, and Frank McSherry. Spectral analysis of random graphs with skewed degree distributions. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 602-610. IEEE, 2004.

[5]

Amin Coja-Oghlan and André Lanka. Finding planted partitions in random graphs with general degree distributions. SIAM Journal on Discrete Mathematics, 23(4):1682-1714, 2009.

[6]

Brendan PW Ames and Stephen A Vavasis. Convex optimization for the planted k-disjoint-clique problem. arXiv preprint arXiv:1008.2814, 2010.

[7]

K. Rohe, S. Chatterjee, and B. Yu. Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, 39(4):1878-1915, 2011.

[8]

D.L. Sussman, M. Tang, D.E. Fishkind, and C.E. Priebe. A consistent adjacency spectral embedding for stochastic blockmodel graphs. Journal of the American Statistical Association, 107(499):1119-1128, 2012.

[9]

P.W. Holland and S. Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.

[10]

Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical Review E, 83(1):016107, 2011.

[11]

Michael W Mahoney. Randomized algorithms for matrices and data. Advances in Machine Learning and Data Mining for Astronomy, CRC Press, Taylor & Francis Group, Eds.: Michael J. Way, Jeffrey D. Scargle, Kamal M. Ali, Ashok N. Srivastava, p. 647-672, 1:647-672, 2012.

[12]

Andrew Y Ng, Michael I Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 2:849-856, 2002.

[13]

Jiashun Jin. Fast network community detection by score. arXiv preprint arXiv:1211.5803, 2012.

[14]

Fan Chung and Mary Radcliffe. On the spectra of general random graphs. the electronic journal of combinatorics, 18(P215):1, 2011.

[15]

Peter H Schönemann. A generalized solution of the orthogonal procrustes problem. Psychometrika, 31(1):1-10, 1966.

[16]

D.S. Choi, P.J. Wolfe, and E.M. Airoldi. Stochastic blockmodels with a growing number of classes. Biometrika, 99(2):273-284, 2012.

[17]

Lada A Adamic and Natalie Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery, pages 36-43. ACM, 2005.

Cited By

Pirinen AAmes B(2021)Exact clustering of weighted graphs via semidefinite programmingThe Journal of Machine Learning Research10.5555/3322706.336197120:1(1007-1040)Online publication date: 9-Mar-2021
https://dl.acm.org/doi/10.5555/3322706.3361971
Wu QHare AWang STu YLiu ZBrinton CLi Y(2021)BATS: A Spectral Biclustering Approach to Single Document Topic Modeling and SegmentationACM Transactions on Intelligent Systems and Technology10.1145/346826812:5(1-29)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3468268
Jain AOrlitsky ALarochelle HRanzato MHadsell RBalcan MLin H(2020)Linear-sample learning of low-rank distributionsProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3497335(19201-19211)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3497335
Show More Cited By

Regularized spectral clustering under the Degree-Corrected Stochastic Blockmodel
1. Computing methodologies

Recommendations

Poisson degree corrected dynamic stochastic block model
Abstract
Stochastic Block Model (SBM) provides a statistical tool for modeling and clustering network data. In this paper, we propose an extension of this model for discrete-time dynamic networks that takes into account the variability in node degrees, ...
Spectral co-clustering ensemble

The goal of co-clustering is to simultaneously cluster the rows and columns of an input data matrix. It overcomes several limitations associated with traditional clustering methods by allowing automatic discovery of similarity based on a subset of ...
Quantum Algorithm for Regularized Spectral Clustering
ICMLC '23: Proceedings of the 2023 15th International Conference on Machine Learning and Computing

Spectral clustering is one of the most robust methods of an unsupervised machine learning field. Compared with the well-known k-means, spectral clustering uses the spectral properties of the Laplacian matrix to project data to a low-dimensional ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

NIPS'13: Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2

December 2013

3236 pages

Publisher

Curran Associates Inc.

Red Hook, NY, United States

Publication History

Published: 05 December 2013

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pirinen AAmes B(2021)Exact clustering of weighted graphs via semidefinite programmingThe Journal of Machine Learning Research10.5555/3322706.336197120:1(1007-1040)Online publication date: 9-Mar-2021
https://dl.acm.org/doi/10.5555/3322706.3361971
Wu QHare AWang STu YLiu ZBrinton CLi Y(2021)BATS: A Spectral Biclustering Approach to Single Document Topic Modeling and SegmentationACM Transactions on Intelligent Systems and Technology10.1145/346826812:5(1-29)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3468268
Jain AOrlitsky ALarochelle HRanzato MHadsell RBalcan MLin H(2020)Linear-sample learning of low-rank distributionsProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3497335(19201-19211)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3497335
Dall'Amico LCouillet RTremblay NWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Revisiting the Bethe-HessianProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3454650(4037-4047)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3454650
Zhou ZAmini A(2019)Analysis of spectral clustering algorithms for community detectionThe Journal of Machine Learning Research10.5555/3322706.336198820:1(1774-1820)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3322706.3361988
Razaee ZAmini ALi J(2019)Matched bipartite block model with covariatesThe Journal of Machine Learning Research10.5555/3322706.336197520:1(1174-1217)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3322706.3361975
Junuthula RHaghdan MXu KDevabhaktuni V(2019)The Block Point Process Model for Continuous-time Event-based Dynamic NetworksThe World Wide Web Conference10.1145/3308558.3313633(829-839)Online publication date: 13-May-2019
https://dl.acm.org/doi/10.1145/3308558.3313633
Su LWang WZhang Y(2019)Strong Consistency of Spectral Clustering for Stochastic Block ModelsIEEE Transactions on Information Theory10.1109/TIT.2019.293415766:1(324-338)Online publication date: 20-Dec-2019
https://dl.acm.org/doi/10.1109/TIT.2019.2934157
Meila M(2018)How to tell when a clustering is (approximately) correct using convex relaxationsProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3327757.3327842(7418-7429)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3327757.3327842
Zhang YRohe K(2018)Understanding regularized spectral clustering via graph conductanceProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3327546.3327723(10654-10663)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3327546.3327723
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents