An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees

Guillaume Braun, Hemant Tyagi, Christophe Biernacki
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:2257-2291, 2022.

Abstract

Real-world networks often come with side information that can help to improve the performance of network analysis tasks such as clustering. Despite a large number of empirical and theoretical studies conducted on network clustering methods during the past decade, the added value of side information and the methods used to incorporate it optimally in clustering algorithms are relatively less understood. We propose a new iterative algorithm to cluster networks with side information for nodes (in the form of covariates) and show that our algorithm is optimal under the Contextual Symmetric Stochastic Block Model. Our algorithm can be applied to general Contextual Stochastic Block Models and avoids hyperparameter tuning in contrast to previously proposed methods. We confirm our theoretical results on synthetic data experiments where our algorithm significantly outperforms other methods, and show that it can also be applied to signed graphs. Finally we demonstrate the practical interest of our method on real data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-braun22a, title = {An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees}, author = {Braun, Guillaume and Tyagi, Hemant and Biernacki, Christophe}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {2257--2291}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/braun22a/braun22a.pdf}, url = {https://proceedings.mlr.press/v162/braun22a.html}, abstract = {Real-world networks often come with side information that can help to improve the performance of network analysis tasks such as clustering. Despite a large number of empirical and theoretical studies conducted on network clustering methods during the past decade, the added value of side information and the methods used to incorporate it optimally in clustering algorithms are relatively less understood. We propose a new iterative algorithm to cluster networks with side information for nodes (in the form of covariates) and show that our algorithm is optimal under the Contextual Symmetric Stochastic Block Model. Our algorithm can be applied to general Contextual Stochastic Block Models and avoids hyperparameter tuning in contrast to previously proposed methods. We confirm our theoretical results on synthetic data experiments where our algorithm significantly outperforms other methods, and show that it can also be applied to signed graphs. Finally we demonstrate the practical interest of our method on real data.} }
Endnote
%0 Conference Paper %T An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees %A Guillaume Braun %A Hemant Tyagi %A Christophe Biernacki %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-braun22a %I PMLR %P 2257--2291 %U https://proceedings.mlr.press/v162/braun22a.html %V 162 %X Real-world networks often come with side information that can help to improve the performance of network analysis tasks such as clustering. Despite a large number of empirical and theoretical studies conducted on network clustering methods during the past decade, the added value of side information and the methods used to incorporate it optimally in clustering algorithms are relatively less understood. We propose a new iterative algorithm to cluster networks with side information for nodes (in the form of covariates) and show that our algorithm is optimal under the Contextual Symmetric Stochastic Block Model. Our algorithm can be applied to general Contextual Stochastic Block Models and avoids hyperparameter tuning in contrast to previously proposed methods. We confirm our theoretical results on synthetic data experiments where our algorithm significantly outperforms other methods, and show that it can also be applied to signed graphs. Finally we demonstrate the practical interest of our method on real data.
APA
Braun, G., Tyagi, H. & Biernacki, C.. (2022). An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:2257-2291 Available from https://proceedings.mlr.press/v162/braun22a.html.

Related Material