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

There is a recent surge of interest in identifying the sharp recovery
thresholds for cluster recovery under the stochastic block model. In this
paper, we address the more refined question of how many vertices that will be
misclassified on average. We consider the binary form of the stochastic block
model, where $n$ vertices are partitioned into two clusters with edge
probability $a/n$ within the first cluster, $c/n$ within the second cluster,
and $b/n$ across clusters. Suppose that as $n \to \infty$, $a= b+ \mu \sqrt{ b}
$, $c=b+ \nu \sqrt{ b} $ for two fixed constants $\mu, \nu$, and $b \to \infty$
with $b=n^{o(1)}$. When the cluster sizes are balanced and $\mu \neq \nu$, we
show that the minimum fraction of misclassified vertices on average is given by
$Q(\sqrt{v^*})$, where $Q(x)$ is the Q-function for standard normal, $v^*$ is
the unique fixed point of $v= \frac{(\mu-\nu)^2}{16} + \frac{ (\mu+\nu)^2 }{16}
\mathbb{E}[ \tanh(v+ \sqrt{v} Z)],$ and $Z$ is standard normal. Moreover, the
minimum misclassified fraction on average is attained by a local algorithm,
namely belief propagation, in time linear in the number of edges. Our proof
techniques are based on connecting the cluster recovery problem to tree
reconstruction problems, and analyzing the density evolution of belief
propagation on trees with Gaussian approximations.

本文考虑二元随机块模型，研究平均误分类顶点的最小分数，结果表明，当群集大小平衡且 μ≠ν 时，平均误分类顶点数量的最小分数由 Q（sqrt（v *））给出，并由局部算法（即置信传播）在边数线性时间内实现，证明技巧基于将群集恢复问题与树重建问题相连，分析置信传播在具有高斯近似的树上的密度演化。

度相关随机块模型中的密度演化

Density Evolution in the Degree-correlated Stochastic Block Model

In standard clustering problems, data points are represented by vectors, and
by stacking them together, one forms a data matrix with row or column cluster
structure. In this paper, we consider a class of binary matrices, arising in
many applications, which exhibit both row and column cluster structure, and our
goal is to exactly recover the underlying row and column clusters by observing
only a small fraction of noisy entries. We first derive a lower bound on the
minimum number of observations needed for exact cluster recovery. Then, we
propose three algorithms with different running time and compare the number of
observations needed by them for successful cluster recovery. Our analytical
results show smooth time-data trade-offs: one can gradually reduce the
computational complexity when increasingly more observations are available.

通过观察少量的噪声数据，本文提出了三种算法用于精确恢复二进制矩阵中的行和列聚类结构，分析结果展示了时间和数据间平滑的折衷关系。