# Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding

arXiv: https://arxiv.org/abs/1310.0532 · HTML: https://mlsanity.com/paper/1310.0532/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2013.

## Built on by (most cited first, 23 of 23)

- [Spectral embedding for dynamic networks with stability guarantees](https://mlsanity.com/paper/2106.01282/) (2021)
- [From Local to Global: Spectral-Inspired Graph Neural Networks](https://mlsanity.com/paper/2209.12054/) (2022)
- [Spectral clustering under degree heterogeneity: a case for the random walk Laplacian](https://mlsanity.com/paper/2105.00987/) (2021)
- [Matrix factorisation and the interpretation of geodesic distance](https://mlsanity.com/paper/2106.01260/) (2021)
- [Inducing a hierarchy for multi-class classification problems](https://mlsanity.com/paper/2102.10263/) (2021)
- [Hypothesis Testing for Equality of Latent Positions in Random Graphs](https://mlsanity.com/paper/2105.10838/) (2021)
- [Lost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labels](https://mlsanity.com/paper/2208.08638/) (2022)
- [Exact Recovery of Community Structures Using DeepWalk and Node2vec](https://mlsanity.com/paper/2101.07354/) (2021)
- [Consistency of Lloyd's Algorithm Under Perturbations](https://mlsanity.com/paper/2309.00578/) (2023)
- [Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding](https://mlsanity.com/paper/2312.11054/) (2023)
- [Latent structure blockmodels for Bayesian spectral graph clustering](https://mlsanity.com/paper/2107.01734/) (2021)
- [Spectral embedding and the latent geometry of multipartite networks](https://mlsanity.com/paper/2202.03945/) (2022)
- [Perfect Spectral Clustering with Discrete Covariates](https://mlsanity.com/paper/2205.08047/) (2022)
- [Probability density estimation for sets of large graphs with respect to spectral information using stochastic block models](https://mlsanity.com/paper/2207.02168/) (2022)
- [Adversarial contamination of networks in the setting of vertex nomination: a new trimming method](https://mlsanity.com/paper/2208.09710/) (2022)
- [Dynamic Network Sampling for Community Detection](https://mlsanity.com/paper/2208.13921/) (2022)
- [Learning Coherent Clusters in Weakly-Connected Network Systems](https://mlsanity.com/paper/2211.15301/) (2022)
- [Entrywise error bounds for low-rank approximations of kernel matrices](https://mlsanity.com/paper/2405.14494/) (2024)
- [Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy](https://mlsanity.com/paper/2504.17274/) (2025)
- [Asymptotically perfect seeded graph matching without edge correlation (and applications to inference)](https://mlsanity.com/paper/2506.02825/) (2025)
- [Nonparametric learning of heterogeneous graphical model on network-linked data](https://mlsanity.com/paper/2507.01473/) (2025)
- [Adjacency Spectral Embeddings of Correlation Networks](https://mlsanity.com/paper/2602.21055/) (2026)
- [Uncovering Locally Low-dimensional Structure in Networks by Locally Optimal Spectral Embedding](https://mlsanity.com/paper/2603.11965/) (2026)

## Abstract (arXiv)

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.