Multi-View Stochastic Block Models
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866907929493372928 |
|---|---|
| author | Cohen-Addad, Vincent d'Orsi, Tommaso Lattanzi, Silvio Nasser, Rajai |
| author_facet | Cohen-Addad, Vincent d'Orsi, Tommaso Lattanzi, Silvio Nasser, Rajai |
| contents | 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 has access to multiple data sources. In this paper we formalize a new family of models, called \textit{multi-view stochastic block models} that captures 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. Furthermore, we complement our results with an information-theoretic lower bound studying the limits of what can be done in this model. Finally, we corroborate our results with experimental evaluations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_04860 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Multi-View Stochastic Block Models Cohen-Addad, Vincent d'Orsi, Tommaso Lattanzi, Silvio Nasser, Rajai Machine Learning Data Structures and Algorithms F.2; G.3 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 has access to multiple data sources. In this paper we formalize a new family of models, called \textit{multi-view stochastic block models} that captures 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. Furthermore, we complement our results with an information-theoretic lower bound studying the limits of what can be done in this model. Finally, we corroborate our results with experimental evaluations. |
| title | Multi-View Stochastic Block Models |
| topic | Machine Learning Data Structures and Algorithms F.2; G.3 |
| url | https://arxiv.org/abs/2406.04860 |