  We study graph clustering in the Stochastic Block Model (SBM) in the presence
of both large clusters and small, unrecoverable clusters. Previous convex
relaxation approaches achieving exact recovery do not allow any small clusters
of size $o(\sqrt{n})$, or require a size gap between the smallest recovered
cluster and the largest non-recovered cluster. We provide an algorithm based on
semidefinite programming (SDP) which removes these requirements and provably
recovers large clusters regardless of the remaining cluster sizes. Mid-sized
clusters pose unique challenges to the analysis, since their proximity to the
recovery threshold makes them highly sensitive to small noise perturbations and
precludes a closed-form candidate solution. We develop novel techniques,
including a leave-one-out-style argument which controls the correlation between
SDP solutions and noise vectors even when the removal of one row of noise can
drastically change the SDP solution. We also develop improved eigenvalue
perturbation bounds of potential independent interest. Our results are robust
to certain semirandom settings that are challenging for alternative algorithms.
Using our gap-free clustering procedure, we obtain efficient algorithms for the
problem of clustering with a faulty oracle with superior query complexities,
notably achieving $o(n^2)$ sample complexity even in the presence of a large
number of small clusters. Our gap-free clustering procedure also leads to
improved algorithms for recursive clustering.
