# VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 43 references that are in the map.
- First posted on arXiv 29 Feb 2024.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [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)
- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [Community Detection in Degree-Corrected Block Models](https://mlsanity.com/paper/1607.06993/) (2016)
- [Community Detection on Mixture Multi-layer Networks via Regularized Tensor Decomposition](https://mlsanity.com/paper/2002.04457/) (2020)
- [Spectral and matrix factorization methods for consistent community detection in multi-layer networks](https://mlsanity.com/paper/1704.07353/) (2017)
- [Learning Latent Block Structure in Weighted Networks](https://mlsanity.com/paper/1404.0431/) (2014)
- [Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit](https://mlsanity.com/paper/2012.09996/) (2020)
- [Iterative Algorithm for Discrete Structure Recovery](https://mlsanity.com/paper/1911.01018/) (2019)
- [Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/1510.05956/) (2015)
- [An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees](https://mlsanity.com/paper/2112.10467/) (2021)
- [Multilayer stochastic block models reveal the multilayer structure of complex networks](https://mlsanity.com/paper/1411.1098/) (2014)
- [Optimal Clustering in Anisotropic Gaussian Mixture Models](https://mlsanity.com/paper/2101.05402/) (2021)
- [The Stochastic Topic Block Model for the Clustering of Vertices in Networks with Textual Edges](https://mlsanity.com/paper/1610.02427/) (2016)
- [Recovering Unbalanced Communities in the Stochastic Block Model With Application to Clustering with a Faulty Oracle](https://mlsanity.com/paper/2202.08522/) (2022)
- [Embedded Topics in the Stochastic Block Model](https://mlsanity.com/paper/2209.10097/) (2022)
- [A pseudo-likelihood approach to community detection in weighted networks](https://mlsanity.com/paper/2303.05909/) (2023)
- [The Deep Latent Position Topic Model for Clustering and Representation of Networks with Textual Edges](https://mlsanity.com/paper/2304.08242/) (2023)

## Abstract (arXiv)

Social networks are often associated with rich side information, such as texts and images. While numerous methods have been developed to identify communities from pairwise interactions, they usually ignore such side information. In this work, we study an extension of the Stochastic Block Model (SBM), a widely used statistical framework for community detection, that integrates vectorial edges covariates: the Vectorial Edges Covariates Stochastic Block Model (VEC-SBM). We propose a novel algorithm based on iterative refinement techniques and show that it optimally recovers the latent communities under the VEC-SBM. Furthermore, we rigorously assess the added value of leveraging edge's side information in the community detection process. We complement our theoretical results with numerical experiments on synthetic and semi-synthetic data.