提出一种新谱聚类算法，可准确恢复几何图中的多个社区结构。
Multi-Community Spectral Clustering for Geometric Graphs
- 基于邻接矩阵的前k-1个近似特征值构造低维嵌入
- 在稠密条件下实现弱一致性，局部优化后达到强一致性
- 突破传统假设，适用于非简并特征值场景，适合图聚类研究者
本文研究固定数量k≥2的同质社区在稠密情形下的软几何块模型（SGBM），提出一种针对该模型生成图的谱聚类算法。该算法利用邻接矩阵中与模型参数决定值最接近的k−1个特征值对应的特征向量，将图顶点嵌入到ℝ^{k−1}空间，再对嵌入结果进行k-均值聚类。我们证明了弱一致性，并通过一个简单的局部修正步骤确保强一致性。关键创新在于应用非标准形式的Davis-Kahan定理，控制非简并特征值情况下的特征子空间扰动。同时，结合组合与矩阵方法分析了邻接矩阵的极限谱结构。
原文摘要 · Abstract (English)
In this paper, we consider the soft geometric block model (SGBM) with a fixed number $k \geq 2$ of homogeneous communities in the dense regime, and we introduce a spectral clustering algorithm for community recovery on graphs generated by this model. Given such a graph, the algorithm produces an embedding into $\mathbb{R}^{k-1}$ using the eigenvectors associated with the $k-1$ eigenvalues of the adjacency matrix of the graph that are closest to a value determined by the parameters of the model. It then applies $k$-means clustering to the embedding. We prove weak consistency and show that a simple local refinement step ensures strong consistency. A key ingredient is an application of a non-standard version of Davis-Kahan theorem to control eigenspace perturbations when eigenvalues are not simple. We also analyze the limiting spectrum of the adjacency matrix, using a combination of combinatorial and matrix techniques.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。