CorrelatedStochasticBlockModels: ExactGraphMatching withApplicationstoRecoveringCommunities
–Neural Information Processing Systems
Wederivethe precise information-theoretic threshold for exact recovery: above the threshold there exists an estimator that outputs the true correspondence with probability close to1,while belowitnoestimator canrecoverthetrue correspondence with probabilityboundedawayfrom0.
Neural Information Processing Systems
Feb-10-2026, 22:08:17 GMT