We consider spectral clustering algorithms for community detection under a
general bipartite stochastic block model (SBM). A modern spectral clustering
algorithm consists of three steps: (1) regularization of an appropriate
adjacency or Laplacian matrix (2) a form of spectral truncation and (3) a
k-means type algorithm in the reduced spectral domain. We focus on the
adjacency-based spectral clustering and for the first step, propose a new
data-driven regularization that can restore the concentration of the adjacency
matrix even for the sparse networks. This result is based on recent work on
regularization of random binary matrices, but avoids using unknown population
level parameters, and instead estimates the necessary quantities from the data.
We also propose and study a novel variation of the spectral truncation step and
show how this variation changes the nature of the misclassification rate in a
general SBM. We then show how the consistency results can be extended to models
beyond SBMs, such as inhomogeneous random graph models with approximate
clusters, including a graphon clustering problem, as well as general
sub-Gaussian biclustering. A theme of the paper is providing a better
understanding of the analysis of spectral methods for community detection and
establishing consistency results, under fairly general clustering models and
for a wide regime of degree growths, including sparse cases where the average
expected degree grows arbitrarily slowly.

本文提出一种新的数据驱动正则化方法来解决稀疏网络中恢复邻接矩阵集中性的问题，进而探讨了一种新的谱截断方法对一般 SBM 中的分类错误率的影响，并在模型的一些扩展，包括不均匀随机图模型和二元聚类问题中得到更优性能的证明。

基于谱聚类算法的社区检测分析：一般二分图情形

Analysis of spectral clustering algorithms for community detection: the  general bipartite setting

Discovering statistical structure from links is a fundamental problem in the
analysis of social networks. Choosing a misspecified model, or equivalently, an
incorrect inference algorithm will result in an invalid analysis or even
falsely uncover patterns that are in fact artifacts of the model. This work
focuses on unifying two of the most widely used link-formation models: the
stochastic blockmodel (SBM) and the small world (or latent space) model (SWM).
Integrating techniques from kernel learning, spectral graph theory, and
nonlinear dimensionality reduction, we develop the first statistically sound
polynomial-time algorithm to discover latent patterns in sparse graphs for both
models. When the network comes from an SBM, the algorithm outputs a block
structure. When it is from an SWM, the algorithm outputs estimates of each
node's latent position.

该研究致力于融合社交网络中两个最常用的链路生成模型：随机块模型（SBM）和小世界模型（SWM），通过核学习、谱图理论和非线性降维等技术，开发了第一个可在多项式时间内发现稀疏图中潜在模式的统计算法。