Block-Models, Spectral Clustering of Graphs, and a Benchmark for Theorems

This talk is concerned with clustering random graphs, under "block-model" assumptions, an area that has made remarkable progress recently. In the first part of the talk, I will describe an empirical comparison of the existing recovery theorems for the Degree-Corrected Stochastic Block Model (DC-SBM). The past few years have seen a number of new recovery algorithms with guarantees for this model. Since these represent sufficient conditions, one expects that cases exist which are not covered by the theory, but for which recovery is possible. We explore experimentally the limits of the current theory. We generate benchmark cases, with well defined parameters controlling their difficulty. Then we verify which of the existing results in the literature predict recovery. What we observe suggests that there is more ground to be covered towards deriving sharp thresholds for this problem. The second part of the talk will present a new class of block models recoverable by spectral clustering, that contains the DC-SBM as a special case. This class has O(n^2) free parameters (instead of the DC-SBM's O(n)), yet one can easily obtain the same recovery guarantees known for the DC-SBM, under conditions that expose with more clarity the parameters that control recovery.

Joint work with Yali Wan.