Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding

Vertex clustering in a stochastic blockmodel graph has wide applicability and has been the subject of extensive research. In thispaper, we provide a short proof that the adjacency spectral embedding can be used to obtain perfect clustering for the stochastic blockmodel and the degree-corrected stochastic blockmodel. We also show an analogous result for the more general random dot product graph model.

• Publication year

  2013

• Venue

  arXiv: Machine Learning

• Publication date

  2013-10-02

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1214/14-EJS978arXiv 1310.0532
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Consistency Thresholds for Binary Symmetric Block Models

  2014cited by this paper
• Empirical Bayes Estimation for the Stochastic Blockmodel

  2014cited by this paper
• Consistency Thresholds for the Planted Bisection Model

  2014cited by this paper
• A nonparametric two-sample hypothesis testing problem for random dot product graphs

  2014cited by this paper
• Spectral clustering for divide-and-conquer graph matching

  2013cited by this paper
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel

  2013cited by this paper
• A central limit theorem for scaled eigenvectors of random dot product graphs

  2013cited by this paper
• Nonparametric graphon estimation

  2013cited by this paper
• Consistency of spectral clustering in stochastic block models

  2013cited by this paper
• A Limit Theorem for Scaled Eigenvectors of Random Dot Product Graphs

  2013cited by this paper
• Stochastic Block Models and Reconstruction

  2012cited by this paper
• Universally consistent vertex classification for latent positions graphs

  2012cited by this paper
• Co-clustering separately exchangeable network data

  2012cited by this paper
• Universally Consistent Latent Position Estimation and Vertex Classification for Random Dot Product Graphs

  2012cited by this paper
• FREEDMAN'S INEQUALITY FOR MATRIX MARTINGALES

  2011cited by this paper
• The method of moments and degree distributions for network models

  2011cited by this paper
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs

  2011cited by this paper
• Spectral clustering and the high-dimensional stochastic blockmodel

  2010cited by this paper
• Stochastic blockmodels and community structure in networks

  2010cited by this paper
• Stochastic blockmodels with growing number of classes

  2010cited by this paper
• A nonparametric view of network models and Newman–Girvan and other modularities

  2009cited by this paper
• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges

  2009cited by this paper
• A Survey of Statistical Network Models

  2009cited by this paper
• Random Dot Product Graph Models for Social Networks

  2007cited by this paper
• Modularity and community structure in networks.

  2006cited by this paper
• Latent Space Approaches to Social Network Analysis

  2002cited by this paper
• Estimation and Prediction for Stochastic Blockmodels for Graphs with Latent Block Structure

  1997cited by this paper
• Stochastic blockmodels: First steps

  1983cited by this paper
• Strong Consistency of $K$-Means Clustering

  1981cited by this paper

• Adjacency Spectral Embeddings of Correlation Networks

  2026cites this paper
• KRAFTY: Khatri-Rao Framework for Joint Cluster Recovery

  2026cites this paper
• Network biomarkers of Alzheimer’s disease risk derived from joint volume and texture covariance patterns in mouse models

  2025cites this paper
• Nonparametric learning of heterogeneous graphical model on network-linked data

  2025cites this paper
• Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)

  2025cites this paper
• A Unified Framework for Community Detection and Model Selection in Blockmodels

  2025cites this paper
• Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy

  2025influential citation
• Network Biomarkers of Alzheimer’s Disease Risk Derived from Joint Volume and Texture Covariance Patterns in Mouse Models

  2025cites this paper
• Optimal Network-Guided Covariate Selection for High-Dimensional Data Integration

  2025cites this paper
• Consistent community detection approach in the nonparametric weighted stochastic blockmodel with unspecified number of communities

  2025cites this paper
• ACRONYM: Augmented Degree Corrected, Community Reticulated Organized Network Yielding Model

  2024cites this paper
• Co-Factor Analysis of Citation Networks

  2024cites this paper
• Entrywise error bounds for low-rank approximations of kernel matrices

  2024cites this paper
• On Inference for Modularity Statistics in Structured Networks

  2024cites this paper
• Independence testing for inhomogeneous random graphs

  2023cites this paper
• A stochastic network approach to clustering and visualising single-cell genomic count data

  2023cites this paper
• Detection of Model-Based Planted Pseudo-Cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding

  2023cites this paper
• Statistical Network Analysis: Past, Present, and Future

  2023cites this paper
• Clustered Graph Matching for Label Recovery and Graph Classification

  2023cites this paper
• Consistency of Lloyd's Algorithm Under Perturbations

  2023cites this paper
• Correlation networks, dynamic factor models and community detection

  2023cites this paper
• Minimax rates for latent position estimation in the generalized random dot product graph

  2023influential citation
• The Heritability of Human Connectomes: a Causal Modeling Analysis

  2023cites this paper
• Occam Factor for Random Graphs: Erd¨os-R´enyi, Independent Edge, and a Uniparametric Stochastic Blockmodel

  2023cites this paper
• Human Connectomes are Heritable

  2023cites this paper
• Spectral clustering and model reduction for weakly-connected coherent network systems

  2022influential citation
• of the Bernoulli Society for Mathematical Statistics and Probability Volume Twenty Eight Number Two May 2022

  2022cites this paper
• Estimating network-mediated causal effects via spectral embeddings

  2022cites this paper
• Joint Spectral Clustering in Multilayer Degree-Corrected Stochastic Blockmodels

  2022influential citation
• Learning Coherent Clusters in Weakly-Connected Network Systems

  2022cites this paper
• Numerical Tolerance for Spectral Decompositions of Random Matrices and Applications to Network Inference

  2022cites this paper
• From Local to Global: Spectral-Inspired Graph Neural Networks

  2022cites this paper
• Estimating the number of communities in the stochastic block model with outliers

  2022cites this paper
• Dynamic network sampling for community detection

  2022cites this paper
• Adversarial contamination of networks in the setting of vertex nomination: a new trimming method

  2022cites this paper
• Lost in the shuffle: Testing power in the presence of errorful network vertex labels

  2022cites this paper
• Statistical inference of random graphs with a surrogate likelihood function

  2022cites this paper
• Probability density estimation for sets of large graphs with respect to spectral information using stochastic block models

  2022cites this paper
• Perfect Spectral Clustering with Discrete Covariates

  2022cites this paper
• Spectral embedding and the latent geometry of multipartite networks

  2022cites this paper
• Inducing a hierarchy for multi-class classification problems

  2021cites this paper
• Exact Recovery of Community Structures Using DeepWalk and Node2vec

  2021cites this paper
• Exploring patterns in modularity of protein interaction networks across the tree of life using Spectral Entropy

  2021influential citation
• Community detection in complex networks: From statistical foundations to data science applications

  2021cites this paper
• Latent structure blockmodels for Bayesian spectral graph clustering

  2021cites this paper
• Spectral embedding for dynamic networks with stability guarantees

  2021cites this paper
• Matrix factorisation and the interpretation of geodesic distance

  2021cites this paper
• Hypothesis testing for equality of latent positions in random graphs

  2021cites this paper
• Spectral analysis of networks with latent space dynamics and signs

  2021cites this paper
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian

  2021influential citation
• Random line graphs and edge-attributed network inference

  2021cites this paper
• On Spectral Algorithms for Community Detection in Stochastic Blockmodel Graphs With Vertex Covariates

  2020cites this paper
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models

  2020cites this paper
• Entrywise convergence of iterative methods for eigenproblems

  2020cites this paper
• Spectral graph clustering via the expectation-solution algorithm

  2020cites this paper
• Bias-Variance Tradeoffs in Joint Spectral Embeddings

  2020influential citation
• Detecting Latent Communities in Network Formation Models

  2020cites this paper
• On identifying unobserved heterogeneity in stochastic blockmodel graphs with vertex covariates

  2020cites this paper
• The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks

  2020cites this paper
• Correcting a nonparametric two-sample graph hypothesis test for graphs with different numbers of vertices with applications to connectomics

  2020cites this paper
• Overlapping Community Detection in Networks via Sparse Spectral Decomposition

  2020cites this paper
• Community Detection in Social Networks: Multilayer Networks and Pairwise Covariates

  2020cites this paper
• GRAPH MATCHING AND VERTEX NOMINATION

  2020cites this paper
• A NOTE ON THE ORTHOGONAL PROCRUSTES PROBLEM AND NORM-DEPENDENT OPTIMALITY∗

  2020cites this paper
• Scalable Community Detection in Massive Networks using Aggregated Relational Data

  2019cites this paper
• Optimal Bayesian estimation for random dot product graphs

  2019influential citation
• Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure

  2019cites this paper
• Limit theorems for out-of-sample extensions of the adjacency and Laplacian spectral embeddings

  2019influential citation
• Bootstrapping networks with latent space structure

  2019influential citation
• Bayesian estimation of the latent dimension and communities in stochastic blockmodels

  2019cites this paper
• Valid two‐sample graph testing via optimal transport Procrustes and multiscale graph correlation with applications in connectomics

  2019cites this paper
• Inference for Multiple Heterogeneous Networks with a Common Invariant Subspace

  2019influential citation
• A multiway p-spectral clustering algorithm

  2019cites this paper
• Recovering low-rank structure from multiple networks with unknown edge distributions

  2019influential citation
• Recovering shared structure from multiple networks with unknown edge distributions

  2019influential citation
• Vertex Nomination, Consistent Estimation, and Adversarial Modification

  2019cites this paper
• On Estimation and Inference in Latent Structure Random Graphs

  2018influential citation
• Determining the Number of Communities in Degree-corrected Stochastic Block Models

  2018cites this paper
• Vertex nomination: The canonical sampling and the extended spectral nomination schemes

  2018cites this paper
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting

  2018cites this paper
• Nouvelles méthodes pour l'apprentissage non-supervisé en grandes dimensions. (New methods for large-scale unsupervised learning)

  2018cites this paper
• Discussion of “Statistical methods for network surveillance”

  2018cites this paper
• Out-of-sample extension of graph adjacency spectral embedding

  2018influential citation
• Graph Inference with Applications to Low-Resource Audio Search and Indexing

  2017cites this paper
• A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference

  2017influential citation
• A Semiparametric Two-Sample Hypothesis Testing Problem for Random Graphs

  2017cites this paper
• Asymptotically efficient estimators for stochastic blockmodels: The naive MLE, the rank-constrained MLE, and the spectral estimator

  2017cites this paper
• A central limit theorem for an omnibus embedding of random dot product graphs

  2017influential citation
• Strong Consistency of Spectral Clustering for Stochastic Block Models

  2017cites this paper
• On Consistent Vertex Nomination Schemes

  2017cites this paper
• FUSION AND INFERENCE FROM MULTIPLE AND MASSIVE DISPARATE DISTRIBUTED DYNAMIC DATA SETS

  2017cites this paper
• Statistical Inference on Random Dot Product Graphs: a Survey

  2017influential citation
• A statistical interpretation of spectral embedding: The generalised random dot product graph

  2017influential citation
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics

  2017cites this paper
• Improved spectral community detection in large heterogeneous networks

  2017influential citation
• FUSION AND INFERENCE FROM MULTIPLE AND MASSIVE DISPARATE DISTRIBUTED DYNAMIC DATA SETS

  2017cites this paper
• Semiparametric spectral modeling of the Drosophila connectome

  2017cites this paper
• Estimating a network from multiple noisy realizations

  2017cites this paper
• Joint Embedding of Graphs

  2017cites this paper
• Numerical tolerance for spectral decompositions of random matrices.

  2016influential citation