Estimating Block Model Graphons via Spectral Recovery in the Irregular Sparse Setting

Abstract

The problem of estimating graphons extends the popular topic of Stochastic Block Model (SBM) recovery to the continuous setting. Spectral recovery methods are particularly useful as they are direct and generalizable to the graphon setting. Past sparse SBM and graphon research developed spectral recovery algorithms assuming regular expected degree. Meanwhile, algorithms for SBM community recovery in the irregular setting rely on more involved techniques exploiting the block structure. We present a spectral algorithm for asymptotic estimation of sparse block model graphons and recovery of SBM communities with no assumption of regularity. We discuss the implications of this finding for the estimation of general sparse irregular graphons.