Preprint announcement: 'Matrix Concentration for Random Signed Graphs and Community Recovery in the Signed Stochastic Block Model'

I am excited to announce the release of my preprint “Matrix Concentration for Random Signed Graphs and Community Recovery in the Signed Stochastic Block Model.” The abstract is included below. I really enjoyed writing this paper as an opportunity to work with and develop new concentration inequalities for random graphs and their matrix representations. In particular, although I don’t mention it in so many words, this paper answers the question: What is the spectral gap of a “nice” signed graph with a random perturbation to its signatures? And the answer is pretty clean, which is surprising.

We consider graphs where edges and their signs are added independently at random from among all pairs of nodes. We establish strong concentration inequalities for adjacency and Laplacian matrices obtained from this family of random graph models. Then, we apply our results to study graphs sampled from the signed stochastic block model. Namely, we take a two-community setting where edges within the communities have positive signs and edges between the communities have negative signs and apply a random sign perturbation with probability $0< s <1/2$. In this setting, our findings include: first, the spectral gap of the corresponding signed Laplacian matrix concentrates near $2s$ with high probability; and second, the sign of the first eigenvector of the Laplacian matrix defines a weakly consistent estimator for the balanced community detection problem, or equivalently, the $\pm 1$ synchronization problem. We supplement our theoretical contributions with experimental data obtained from the models under consideration.