# Spectral clustering in the Gaussian mixture block model

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 57 references that are in the map.
- First posted on arXiv 29 Apr 2023.

## Builds on (most cited first, 24 of 24)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [Robustly Learning a Gaussian: Getting Optimal Error, Efficiently](https://mlsanity.com/paper/1704.03866/) (2017)
- [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017)
- [An Equivalence Principle for the Spectrum of Random Inner-Product Kernel Matrices with Polynomial Scalings](https://mlsanity.com/paper/2205.06308/) (2022)
- [How Robust are Reconstruction Thresholds for Community Detection?](https://mlsanity.com/paper/1511.01473/) (2015)
- [Belief propagation, robust reconstruction and optimal recovery of block models](https://mlsanity.com/paper/1309.1380/) (2013)
- [Robust recovery for stochastic block models](https://mlsanity.com/paper/2111.08568/) (2021)
- [A simple SVD algorithm for finding hidden partitions](https://mlsanity.com/paper/1404.3918/) (2014)
- [Local Statistics, Semidefinite Programming, and Community Detection](https://mlsanity.com/paper/1911.01960/) (2019)
- [Optimal hypothesis testing for stochastic block models with growing degrees](https://mlsanity.com/paper/1705.05305/) (2017)
- [Latent Distance Estimation for Random Geometric Graphs](https://mlsanity.com/paper/1909.06841/) (2019)
- [Graph powering and spectral robustness](https://mlsanity.com/paper/1809.04818/) (2018)
- [Community Detection on Euclidean Random Graphs](https://mlsanity.com/paper/1706.09942/) (2017)
- [The Geometric Block Model](https://mlsanity.com/paper/1709.05510/) (2017)
- [Community detection and percolation of information in a geometric setting](https://mlsanity.com/paper/2006.15574/) (2020)
- [Higher-Order Spectral Clustering for Geometric Graphs](https://mlsanity.com/paper/2009.11353/) (2020)
- [Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees](https://mlsanity.com/paper/2212.03362/) (2022)
- [Connectivity in Random Annulus Graphs and the Geometric Block Model](https://mlsanity.com/paper/1804.05013/) (2018)
- [Local and global expansion in random geometric graphs](https://mlsanity.com/paper/2210.00158/) (2022)

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

- [SimCalib: Graph Neural Network Calibration based on Similarity between Nodes](https://mlsanity.com/paper/2312.11858/) (2023)
- [Information-Theoretic Thresholds for Planted Dense Cycles](https://mlsanity.com/paper/2402.00305/) (2024)
- [Impossibility of latent inner product recovery via rate distortion](https://mlsanity.com/paper/2407.11932/) (2024)
- [Spectral Concentration and Recovery in Sparse High-Dimensional Random Geometric Graphs](https://mlsanity.com/paper/2607.14304/) (2026)
- [Detection of local geometry in random graphs: information-theoretic and computational limits](https://mlsanity.com/paper/2603.24545/) (2026)
- [Recovery of latent inner products from an anisotropic Gaussian random geometric graph](https://mlsanity.com/paper/2607.23723/) (2026)
- [Spectral graph clustering with inhomogeneous latent geometry](https://mlsanity.com/paper/2608.11321/) (2026)

## Abstract (arXiv)

Gaussian mixture block models are distributions over graphs that strive to model modern networks: to generate a graph from such a model, we associate each vertex i with a latent feature vector ui ∈ ℝd sampled from a mixture of Gaussians, and we add edge (i,j) if and only if the feature vectors are sufficiently similar, in that langle ui,uj rangle ≥ τ for a pre-specified threshold τ. The different components of the Gaussian mixture represent the fact that there may be different types of nodes with different distributions over features -- for example, in a social network each component represents the different attributes of a distinct community. Natural algorithmic tasks associated with these networks are embedding (recovering the latent feature vectors) and clustering (grouping nodes by their mixture component). In this paper we initiate the study of clustering and embedding graphs sampled from high-dimensional Gaussian mixture block models, where the dimension of the latent feature vectors d→ ∞ as the size of the network n → ∞. This high-dimensional setting is most appropriate in the context of modern networks, in which we think of the latent feature space as being high-dimensional. We analyze the performance of canonical spectral clustering and embedding algorithms for such graphs in the case of 2-component spherical Gaussian mixtures, and begin to sketch out the information-computation landscape for clustering and embedding in these models.