VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates

Guillaume Braun, Masashi Sugiyama
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:532-540, 2024.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-braun24a, title = {{VEC-SBM}: Optimal Community Detection with Vectorial Edges Covariates}, author = {Braun, Guillaume and Sugiyama, Masashi}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {532--540}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/braun24a/braun24a.pdf}, url = {https://proceedings.mlr.press/v238/braun24a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates %A Guillaume Braun %A Masashi Sugiyama %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-braun24a %I PMLR %P 532--540 %U https://proceedings.mlr.press/v238/braun24a.html %V 238 %X 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.
APA
Braun, G. & Sugiyama, M.. (2024). VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:532-540 Available from https://proceedings.mlr.press/v238/braun24a.html.

Related Material