Multi-Community Spectral Clustering for Geometric Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908476560637952 |
|---|---|
| author | Allem, Luiz Emilio Avrachenkov, Konstantin Hoppen, Carlos Manjunath, Hariprasad Sibemberg, Lucas Siviero |
| author_facet | Allem, Luiz Emilio Avrachenkov, Konstantin Hoppen, Carlos Manjunath, Hariprasad Sibemberg, Lucas Siviero |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_00893 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multi-Community Spectral Clustering for Geometric Graphs Allem, Luiz Emilio Avrachenkov, Konstantin Hoppen, Carlos Manjunath, Hariprasad Sibemberg, Lucas Siviero Social and Information Networks Machine Learning Probability Spectral Theory 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. |
| title | Multi-Community Spectral Clustering for Geometric Graphs |
| topic | Social and Information Networks Machine Learning Probability Spectral Theory |
| url | https://arxiv.org/abs/2508.00893 |