# Perfect Spectral Clustering with Discrete Covariates

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 49 references that are in the map.
- First posted on arXiv 17 May 2022.

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

- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [Community Detection in Networks with Node Attributes](https://mlsanity.com/paper/1401.7267/) (2014)
- [The ground truth about metadata and community detection in networks](https://mlsanity.com/paper/1608.05878/) (2016)
- [Structure and inference in annotated networks](https://mlsanity.com/paper/1507.04001/) (2015)
- [Covariate-assisted spectral clustering](https://mlsanity.com/paper/1411.2158/) (2014)
- [Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding](https://mlsanity.com/paper/1310.0532/) (2013)
- [Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral](https://mlsanity.com/paper/1710.10936/) (2017)
- [Pairwise Covariates-adjusted Block Model for Community Detection](https://mlsanity.com/paper/1807.03469/) (2018)
- [Strong Consistency of Spectral Clustering for Stochastic Block Models](https://mlsanity.com/paper/1710.06191/) (2017)
- [Spectral inference for large Stochastic Blockmodels with nodal covariates](https://mlsanity.com/paper/1908.06438/) (2019)
- [On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models](https://mlsanity.com/paper/2003.14250/) (2020)
- [Community detection with nodal information](https://mlsanity.com/paper/1610.09735/) (2016)
- [On spectral algorithms for community detection in stochastic blockmodel graphs with vertex covariates](https://mlsanity.com/paper/2007.02156/) (2020)
- [Likelihood Inference for Large Scale Stochastic Blockmodels with Covariates based on a Divide-and-Conquer Parallelizable Algorithm with Communication](https://mlsanity.com/paper/1610.09724/) (2016)

## Abstract (arXiv)

Among community detection methods, spectral clustering enjoys two desirable properties: computational efficiency and theoretical guarantees of consistency. Most studies of spectral clustering consider only the edges of a network as input to the algorithm. Here we consider the problem of performing community detection in the presence of discrete node covariates, where network structure is determined by a combination of a latent block model structure and homophily on the observed covariates. We propose a spectral algorithm that we prove achieves perfect clustering with high probability on a class of large, sparse networks with discrete covariates, effectively separating latent network structure from homophily on observed covariates. To our knowledge, our method is the first to offer a guarantee of consistent latent structure recovery using spectral clustering in the setting where edge formation is dependent on both latent and observed factors.