Clustering Without an Eigengap
Matthew Zurek Yudong Chen
We study graph clustering in the Stochastic Block Model (SBM) in the presence
of both large clusters and small, unrecoverable clusters. Previous 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. 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. Our results extend to certain
heterogeneous probability settings that are challenging for alternative
algorithms.