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.

Machine Learning (stat.ML); Machine Learning (cs.LG); Applications (stat.AP); Methodology (stat.ME)

arXiv:2601.16427 [stat.ML]

(or arXiv:2601.16427v3 [stat.ML] for this version)

https://doi.org/10.48550/arXiv.2601.16427 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.