How Robust are Reconstruction Thresholds for Community Detection?
Friday, June 21, 2019 - 9:00am - 9:50am
The stochastic block model is one of the oldest and most ubiquitous models for studying clustering and community detection. Here we revisit it from the perspective of semirandom models where we allow an adversary to make `helpful’ changes that strengthen ties within each community and break ties between them. We show a surprising result that these `helpful’ changes can shift the information-theoretic threshold, making the community detection problem strictly harder. Conceptually, any algorithm meeting the exact information-theoretic threshold in the average-case model must exploit the precise structure of the noise. These results point to an interesting new direction: Can semirandom (and related) models help explain why some algorithms are preferred to others in practice, in spite of gaps in their average-case performance?