Exact Recovery by Neighborhood Smoothing in Directed Stochastic Block Models

Abstract

We study exact community recovery in sparse directed stochastic block models using neighborhood smoothing of connection-probability profiles. The proposed method clusters vertices according to their estimated outgoing connection-probability profiles. For each vertex, its complete outgoing profile is estimated by averaging the adjacency rows of empirically similar vertices, after which \(K\)-means is applied to the estimated profiles. An analogous procedure based on incoming connection-probability profiles is obtained by applying the same construction to the transposed adjacency matrix. We establish a finite-sample uniform row-wise error bound for the asymmetric smoothed estimator and derive consistency in the normalized two-to-infinity norm. We then show that exact recovery follows when the minimum separation between distinct population profiles dominates the row-wise estimation error. The result permits a vanishing sparsity factor, a general asymmetric block-probability matrix, and a number of communities that may diverge with the network size. We are unaware of a previous exact-recovery theorem that simultaneously covers these features for a directed stochastic block model. Numerical studies and an application to a directed neuronal connectome illustrate the practical behavior and limitations of the profile-based clustering approach.