Learning Guarantee of SDP Relaxation on Directed Stochastic Block Models

Abstract

Community detection in networks has been a focal point in various scientific domains, but the study of directed networks remains relatively under-explored despite their prevalence and importance in capturing real-world systems. This work addresses this research gap by focusing on Directed Stochastic Block Models (DSBMs), a natural extension of traditional Stochastic Block Models (SBMs) to directed graphs. The inherent complexity of directionality in DSBMs makes them challenging to analyze, requiring new mathematical frameworks and computational approaches. We introduce an augmented matrix to encapsulate the directional relationships within these networks, providing a nuanced perspective for further analysis. In this work, we prove the information-theoretical threshold for exact recovery in the DSBMs and propose an SDP relaxation that can achieve this threshold, thereby contributing to the theoretical understanding of community detection in the realm of directed graphs.