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.

我们研究了随机块模型（SBM）中具有大型簇和无法恢复的小型簇的图聚类。我们提出了一种基于半定规划（SDP）的算法，可以恢复大型簇而不受其余簇大小的影响。我们的研究结果在存在大量小簇的情况下，达到了更低的样本复杂度，并为递归聚类问题提供了改进的算法。

无特征差距的聚类

Clustering Without an Eigengap

Motivated by many applications, we study clustering with a faulty oracle. In
this problem, there are $n$ items belonging to $k$ unknown clusters, and the
algorithm is allowed to ask the oracle whether two items belong to the same
cluster or not. However, the answer from the oracle is correct only with
probability $\frac{1}{2}+\frac{\delta}{2}$. The goal is to recover the hidden
clusters with minimum number of noisy queries. Previous works have shown that
the problem can be solved with $O(\frac{nk\log n}{\delta^2} +
\text{poly}(k,\frac{1}{\delta}, \log n))$ queries, while
$\Omega(\frac{nk}{\delta^2})$ queries is known to be necessary. So, for any
values of $k$ and $\delta$, there is still a non-trivial gap between upper and
lower bounds. In this work, we obtain the first matching upper and lower bounds
for a wide range of parameters. In particular, a new polynomial time algorithm
with $O(\frac{n(k+\log n)}{\delta^2} + \text{poly}(k,\frac{1}{\delta}, \log
n))$ queries is proposed. Moreover, we prove a new lower bound of
$\Omega(\frac{n\log n}{\delta^2})$, which, combined with the existing
$\Omega(\frac{nk}{\delta^2})$ bound, matches our upper bound up to an additive
$\text{poly}(k,\frac{1}{\delta},\log n)$ term. To obtain the new results, our
main ingredient is an interesting connection between our problem and
multi-armed bandit, which might provide useful insights for other similar
problems.

本文研究了带有错误预言机的聚类问题，利用多臂赌博机算法解决该问题的上下界。