Multi-View Stochastic Block Models

Vincent Cohen-Addad, Tommaso D’Orsi, Silvio Lattanzi, Rajai Nasser
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:9180-9207, 2024.

Abstract

Graph clustering is a central topic in unsupervised learning with a multitude of practical applications. In recent years, multi-view graph clustering has gained a lot of attention for its applicability to real-world instances where one often has access to multiple data sources. In this paper we formalize a new family of models, called multi-view stochastic block models that capture this setting. For this model, we first study efficient algorithms that naively work on the union of multiple graphs. Then, we introduce a new efficient algorithm that provably outperforms previous approaches by analyzing the structure of each graph separately. Finally, we complement our results with an information-theoretic lower bound studying the limits of what can be done in this model.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-cohen-addad24b, title = {Multi-View Stochastic Block Models}, author = {Cohen-Addad, Vincent and D'Orsi, Tommaso and Lattanzi, Silvio and Nasser, Rajai}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {9180--9207}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/cohen-addad24b/cohen-addad24b.pdf}, url = {https://proceedings.mlr.press/v235/cohen-addad24b.html}, abstract = {Graph clustering is a central topic in unsupervised learning with a multitude of practical applications. In recent years, multi-view graph clustering has gained a lot of attention for its applicability to real-world instances where one often has access to multiple data sources. In this paper we formalize a new family of models, called multi-view stochastic block models that capture this setting. For this model, we first study efficient algorithms that naively work on the union of multiple graphs. Then, we introduce a new efficient algorithm that provably outperforms previous approaches by analyzing the structure of each graph separately. Finally, we complement our results with an information-theoretic lower bound studying the limits of what can be done in this model.} }
Endnote
%0 Conference Paper %T Multi-View Stochastic Block Models %A Vincent Cohen-Addad %A Tommaso D’Orsi %A Silvio Lattanzi %A Rajai Nasser %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-cohen-addad24b %I PMLR %P 9180--9207 %U https://proceedings.mlr.press/v235/cohen-addad24b.html %V 235 %X Graph clustering is a central topic in unsupervised learning with a multitude of practical applications. In recent years, multi-view graph clustering has gained a lot of attention for its applicability to real-world instances where one often has access to multiple data sources. In this paper we formalize a new family of models, called multi-view stochastic block models that capture this setting. For this model, we first study efficient algorithms that naively work on the union of multiple graphs. Then, we introduce a new efficient algorithm that provably outperforms previous approaches by analyzing the structure of each graph separately. Finally, we complement our results with an information-theoretic lower bound studying the limits of what can be done in this model.
APA
Cohen-Addad, V., D’Orsi, T., Lattanzi, S. & Nasser, R.. (2024). Multi-View Stochastic Block Models. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:9180-9207 Available from https://proceedings.mlr.press/v235/cohen-addad24b.html.

Related Material