# Exact Recovery of Community Detection in dependent Gaussian Mixture Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 26 references that are in the map.
- First posted on arXiv 23 Sep 2022.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [On the low-rank approach for semidefinite programs arising in synchronization and community detection](https://mlsanity.com/paper/1602.04426/) (2016)
- [Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms](https://mlsanity.com/paper/1503.00609/) (2015)
- [Exact recovery in the Ising blockmodel](https://mlsanity.com/paper/1612.03880/) (2016)
- [Exact Recovery of Community Detection in k-Community Gaussian Mixture Model](https://mlsanity.com/paper/2009.01185/) (2020)
- [Exact Recovery of Community Detection in k-partite Graph Models](https://mlsanity.com/paper/1910.04320/) (2019)

## Abstract (arXiv)

We study exact recovery for community detection in a Gaussian mixture model with dependent and heterogeneous Gaussian noise. The noise covariance matrix Sigma may be non-diagonal and, in the general formulation, singular. In the singular case, we write the Gaussian likelihood on the support of the induced measure and show that the maximum likelihood estimator (MLE) is a constrained quadratic optimization problem involving the Moore--Penrose inverse. For general covariance structures, we obtain sufficient conditions for exact recovery of the MLE when the community sizes are unknown and when they are known. These conditions are driven by the Sigma-whitened separation L_Sigma(x,y) together with local one-step comparison inequalities in the near-truth regime. Under the additional assumption that Sigma is invertible, we derive converse results showing failure of exact recovery when a large family of local perturbations has sufficiently nondegenerate Gaussian comparison statistics. We then analyze a full-rank non-diagonal block-covariance model, prove a sharp exact-recovery threshold in the unknown-size setting, and identify a general no-gap mechanism under which the sufficient and necessary conditions coincide asymptotically.