Contextual Stochastic Block Model: Sharp Thresholds and Contiguity

In the simplest version of this problem, given access to a graph, one seeks to cluster the vertices into interpretable communities or groups of vertices, which are believed to reflect latent similarities among the nodes. From a theoretical standpoint, this problem has been extensively analyzed under specific generative assumptions on the observed graph; the most popular generative model in this context is the stochastic block model (SBM) [22]. Inspired by intriguing conjectures arising from the statistical physics community [29], community detection under the stochastic block model has been studied extensively. As a consequence, the precise information theoretic limits for recovering the underlying communities have been derived, and optimal algorithms have been identified in this setting (for a survey of these recent breakthroughs, see [1]). In reality, the practitioner often has access to additional information in the form of node covariates, which complements the graph information.