{"ID":2889943,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.00893","arxiv_id":"2508.00893","title":"Multi-Community Spectral Clustering for Geometric Graphs","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2508.00893","url_pdf":"https://arxiv.org/pdf/2508.00893v1","authors":"[\"Luiz Emilio Allem\",\"Konstantin Avrachenkov\",\"Carlos Hoppen\",\"Hariprasad Manjunath\",\"Lucas Siviero Sibemberg\"]","published":"2025-07-27T14:09:00Z","proceeding":"cs.SI","tasks":"[\"cs.SI\",\"cs.LG\",\"math.PR\",\"math.SP\",\"stat.ML\"]","methods":"[]","has_code":false}