A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs

By Daniel Lewis Sussman, Minh Tang, Donniell E. Fishkind, Carey E. Priebe. 2011

318 citations recorded by the source corpus.

We present a method to estimate block membership of nodes in a random graph generated by a stochastic blockmodel. We use an embedding procedure motivated by the random dot product graph model, a particular example of the latent position model. The embedding associates each node with a vector; these vectors are clustered via minimization of a square error criterion. We prove that this method is consistent for assigning nodes to blocks, as only a negligible number of nodes will be misassigned. We prove consistency of the method for directed and undirected graphs. The consistent block assignment makes possible consistent parameter estimation for a stochastic blockmodel. We extend the result in the setting where the number of blocks grows slowly with the number of nodes. Our method is also computationally feasible even for very large graphs. We compare our method with Laplacian spectral clustering through analysis of simulated data and a graph derived from Wikipedia documents.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/c3cb2511b03088b10e057f54d564bb5d4da0071a

How researchers see this paper

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

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

A Limit Theorem for Scaled Eigenvectors of Random Dot Product Graphs (2013, methodology): “We also plot the misclassification rate of (C log n)/n as given in Sussman et al. (2012) where the constant C was chosen to match the misclassification rate of K-means clustering for n = 1000.”
Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks (2008, methodology): “For instance, the spectral algorithm associated with the RB random walk on an undirected graph makes use of the second eigenvector of the adjacency matrix A , similarly to the ‘adjacency spectral clustering’ of Sussman et al. [60].”
Consistency of spectral clustering in stochastic block models (2013, background): “Analogous conditions can be found elsewhere: see, e.g., Sussman et al. (2013), Balakrishnan et al. (2011), and Sussman et al. (2012).”
Representation Learning for Dynamic Graphs: A Survey (2019, background): “Sussman et al. (2012) suggested to use a slightly different embedding based on the eigenvalue decomposition of the adjacency matrix A = UΣU′ (this matrix is symmetric for an undirected graph).”
Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey (2019, methodology): “…to solving a generalized eigenvalue decomposition: where L is a graph Laplacian; and the matrix Y can be obtained by considering the Sussman et al. [211] suggested to use a slightly different embedding based on the eigenvalue decomposition of the adjacency matrix A = UΣU (cid:48) (this matrix is…”
Limit theorems for eigenvectors of the normalized Laplacian for random graphs (2016, background): “The stochastic blockmodel [20] is a popular generative model for random graphs with latent community structure and many results are known regarding consistent recovery of the block assignments; see for example [7, 13, 24, 28, 29, 31, 35, 37, 40] and the references therein.”
Statistical Inference on Random Dot Product Graphs: a Survey (2017, methodology): “For the number of vertices considered here, the upper bound for the constant C from [90] will give a vacuous upper bound of the order of 10(6) for the misclassification rate in this example.”
Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel (2013, background): “Several previous authors have studied the estimation properties of spectral clustering under various statistical network models (McSherry [3], Dasgupta et al. [4], Coja-Oghlan and Lanka [5], Ames and Vavasis [6], Rohe et al. [7], Sussman et al. [8] and Chaudhuri et al. [1]).”
Asymptotically perfect seeded graph matching without edge correlation (and applications to inference) (2025, unknown): “Spectral methods provide suitable estimates (cid:98) X of X that are then amenable to subsequent (more) classical inference methods such as clustering [37]–[39], testing [13], [14], [40], classification [41], etc; for a survey of work done in this area, see [29].”
Approximately optimal domain adaptation with Fisher's Linear Discriminant Analysis (2023, background): “The two-dimensional representations for MATB and Mental Math are ﬁrst two components of the spectral embedding (Sussman et al., 2012) of the afﬁnity matrix A with entries a ij = ( ω ( i ) ω ( j ) + 1) / 2 and a ii = 0 .”