Machine Learning Seminar

TITLE: A Semidefinite Program For Structured Stochastic Blockmodels

ABSTRACT: Semidefinite programs (SDP) have been intensely studied for a particular class of the stochastic blockmodel, which exhibits assortative connectivity and corresponds to community detection. However, there exist blockmodels outside of this class for which the known SDP formulation is not applicable, and it is of interest to consider whether this is an inherent limitation to the semidefinite programming approach, or if alternate formulations exist. Here, we present a family of semidefinite programs that can be tailored to such instances of the blockmodel, such as non-assortative networks, overlapping communities, and approximation of latent space models. We establish label recovery in sparse settings, with conditions that are analogous to known (though not the best known) results for community detection. When the blockmodel exhibits symmetry or label-switching ambiguities, the computation time of the SDP can be significantly reduced by parameterizing out the non-identifiable subspace, using a concept known in combinatorics as an association scheme.