We consider the problem of partially recovering hidden binary variables from
the observation of (few) censored edge weights, a problem with applications in
community detection, correlation clustering and synchronization. We describe
two spectral algorithms for this task based on the non-backtracking and the
Bethe Hessian operators. These algorithms are shown to be asymptotically
optimal for the partial recovery problem, in that they detect the hidden
assignment as soon as it is information theoretically possible to do so.

该研究考虑处理从（少量）被审查的边缘权重观察到的隐藏二进制变量的问题，并描述了两个基于非回溯和 Bethe Hessian 算法的谱算法，在部分恢复问题中表现出渐近最优的特点，一旦可以从信息理论角度进行的时候，便会侦测隐藏分配。

被审查的块模型中的光谱检测

Spectral Detection in the Censored Block Model

Spectral clustering is a standard approach to label nodes on a graph by
studying the (largest or lowest) eigenvalues of a symmetric real matrix such as
e.g. the adjacency or the Laplacian. Recently, it has been argued that using
instead a more complicated, non-symmetric and higher dimensional operator,
related to the non-backtracking walk on the graph, leads to improved
performance in detecting clusters, and even to optimal performance for the
stochastic block model. Here, we propose to use instead a simpler object, a
symmetric real matrix known as the Bethe Hessian operator, or deformed
Laplacian. We show that this approach combines the performances of the
non-backtracking operator, thus detecting clusters all the way down to the
theoretical limit in the stochastic block model, with the computational,
theoretical and memory advantages of real symmetric matrices.

该研究提出使用 Bethe Hessian operator 代替 non-backtracking operator 进行图的聚类，从而在检测聚类方面具备了 non-backtracking operator 的性能，同时具备了实数对称矩阵计算，理论和存储方面的优势。