Multi-View Stochastic Block Models
<|reference_start|>Multi-View Stochastic Block Models: 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.<|reference_end|>
@article{cohen-addad2024multi-view,
    title={Multi-View Stochastic Block Models},
    author={Vincent Cohen-Addad, Tommaso d'Orsi, Silvio Lattanzi, Rajai Nasser},
    journal={arXiv preprint arXiv:2406.04860},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.04860},
    primaryClass={cs.LG cs.DS stat.ML}
}