Spectral clustering and the high-dimensional stochastic blockmodel

By Karl Rohe, Sourav Chatterjee, Bin Yu. 2010

997 citations recorded by the source corpus.

Networks or graphs can easily represent a diverse set of data sources that are characterized by interacting units or actors. Social ne tworks, representing people who communicate with each other, are one example. Communities or clusters of highly connected actors form an essential feature in the structure of several empirical networks. Spectral clustering is a popular and computationally feasi ble method to discover these communities. The Stochastic Block Model (Holland et al., 1983) is a social network model with well defined communities; each node is a member of one community. For a network generated from the Stochastic Block Model, we bound the number of nodes "misclus- tered" by spectral clustering. The asymptotic results in th is paper are the first clustering results that allow the number of clusters in the model to grow with the number of nodes, hence the name high-dimensional. In order to study spectral clustering under the Stochastic Block Model, we first show that under the more general latent space model, the eigenvectors of the normalized graph Laplacian asymptotically converge to the eigenvectors of a "population" normal- ized graph Laplacian. Aside from the implication for spectral clustering, this provides insight into a graph visualization technique. Our method of studying the eigenvectors of random matrices is original. AMS 2000 subject classifications: Primary 62H30, 62H25; secondary 60B20.

Subfields: Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/7120779b4df86db4c6019b2c81c8c4f988aa94ea

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Statistical and Nonlinear Physics

Citations in the corpus

Exact Recovery in the Stochastic Block Model (2014, background): “A large body of literature in statistics and computer science [5], [6], [8], [9], [11], [13], [16], [25], [30], [34], [35]”
Asymptotic Normality of Maximum Likelihood and its Variational Approximation for Stochastic Blockmodels (2012, background): “In other papers, estimation of the latent Z is considered to be the primary inferential task [Rohe, Chatterjee and Yu (2011), Choi, Wolfe and Airoldi (2012)].”
A Limit Theorem for Scaled Eigenvectors of Random Dot Product Graphs (2013, result): “First, we see that the empirical error rates are much lower than those proved in previous work on spectral methods [21,24,8].”
A review of clustering techniques and developments (2017, background): “More literature (partially) on graph and spectral clustering can be seen in [182-190].”
Pseudo-likelihood methods for community detection in large sparse networks (2012, methodology): “Some faster approximations for block model fitting based on spectral representations are also available [25, 31], but the properties of these approximations are only partially known.”
Reconstruction and estimation in the planted partition model (2012, methodology): “[32] gave a theoretical analysis of spectral clustering under the planted bisection model and also applied the method to data from Facebook.”
A useful variant of the Davis--Kahan theorem for statisticians (2014, methodology): “In Theorem 1 below, we state a version in a form typically used in the statistical literature (e.g., von Luxburg, 2007; Rohe et al., 2011).”
Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics (2016, methodology): “derson, 2003; Johnstone and Lu, 2009; Cai et al., 2013), canonical correlation analysis (Hotelling, 1936; Hardoon et al., 2004; Gao et al., 2014, 2015), community detection (von Luxburg et al., 2008; Rohe et al., 2011; Balakrishnan et al., 2011; Lei and Rinaldo, 2015). Specic applications include co”
Matrix estimation by Universal Singular Value Thresholding (2012, background): “[85], and was followed up shortly thereafter by [16, 36, 73, 33] with more advanced results.”
Handbook of Big Data (2016, methodology): “The comment also alludes to the possibility that very diﬀerent types of information could be represented by the blocks, and this is indeed made use of by the AN software (see Sections 6.3.3 and 6.3.4)”
Statistical Inference on Random Dot Product Graphs: a Survey (2017, methodology): “The Davis-Kahan has a significant role in several approaches to spectral estimation for graphs: for example, Rohe, Chatterjee, and Yu leverage it in [81] to prove the accuracy of spectral estimates in high-dimensional stochastic blockmodels.”
Consistency of community detection in networks under degree-corrected stochastic block models (2011, methodology): “They developed general theory for checking the consistency of detection criteria under the stochastic block model (discussed in detail below) as the number of nodes grows and the number of communities remains fixed, and their result has been generalized to allow the number of communities to grow in ”
Limit theorems for eigenvectors of the normalized Laplacian for random graphs (2016, background): “For previous consistency results of X̆ as an estimator for X̃ in various random graphs models, the reader is referred to [34, 35, 43] among others.”
FAST COMMUNITY DETECTION BY SCORE (2012, result): “If we try to estimate the heterogeneity parameters of such nodes, we get relatively large estimation errors which may propagate to subsequent studies.”
The topology of probability distributions on manifolds (2013, background): “The motivating principle behind manifold learning is using low dimensional geometric summaries of the data for statistical inference [4, 10, 21, 31, 50].”
Finding and Leveraging Structure in Learning Problems (2012, background): “12 Algorithm 1 HS input (noisy) n× n similarity matrix W Compute Laplacian L = D −W v2 ← smallest non-constant eigenvector of L C1 ← {i : v2(i) ≥ 0}, C2 ← {j : v2(j) 0} C ← {C1, C2}∪ HS (WC1)∪ HS (WC2) output C More recently, Rohe et al [Rohe et al., 2010] analyze spectral clustering in the stocha”
Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking (2017, neutral): “…applied in numerous applications, e.g. matrix completion (Keshavan et al., 2010; Jain et al., 2013), phase retrieval (Candès et al., 2015; Chen and Candès, 2017), graph clustering (Rohe et al., 2011; Chaudhuri et al., 2012), synchronization and joint alignment (Singer, 2011; Chen and Candes, 2016).”
Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery (2015, background): “The model1 was first proposed in the 80s [20] and received significant attention in the mathematics and computer science literature [14], [13], [26], [27], [15], [28], [29], as well as in the statistics and machine learning literature [30], [24], [31], [32].”