Multi-View Stochastic Block Models
This work addresses graph clustering for applications with multiple data sources, presenting an incremental improvement over existing methods.
The paper tackles the problem of multi-view graph clustering by formalizing a new family of models called multi-view stochastic block models and introduces an efficient algorithm that outperforms previous approaches by analyzing each graph separately, with results supported by experimental evaluations.
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.