Multi-Community Spectral Clustering for Geometric Graphs
Luiz Emilio Allem, Konstantin Avrachenkov, Carlos Hoppen, Hariprasad Manjunath, Lucas Siviero Sibemberg · 2025
Read Multi-Community Spectral Clustering for Geometric Graphs by Luiz Emilio Allem, Konstantin Avrachenkov, Carlos Hoppen, Hariprasad Manjunath, Lucas Siviero Sibemberg (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-00893.txt.
Introduction
Luiz Emilio Allem and co-authors show in a 2025 paper how communities in geometric graphs can be found by spectral clustering. That method reads the shape of a graph through its key directions. Their setting is the soft geometric block model, with a fixed count of even communities packed densely. Points in space link up more readily inside their own community, which mixes shape with block structure in the graph.
Their method places each point by using the eigenvectors of the adjacency matrix. Those vectors are tied to the eigenvalues nearest a value set by the model's inputs. A grouping step, K-means, on that placement brings the communities back. Weak consistency is proved, and a short local cleanup step lifts it to strong consistency. A non-standard Davis-Kahan theorem keeps control of the spaces when eigenvalues repeat. The end shape of the spectrum is worked out.
Catalog record
| CREATOR | Luiz Emilio Allem, Konstantin Avrachenkov, Carlos Hoppen, Hariprasad Manjunath, Lucas Siviero Sibemberg |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-00893
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi-Community Spectral Clustering for Geometric Graphs Luiz Emilio Allem, Konstantin Avrachenkov, Carlos Hoppen, Hariprasad Manjunath, Lucas Siviero Sibemberg Abstract . In this paper, we consider the soft geometric block model (SGBM) with a fixed number k ≥ 2 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 ℝ k − 1 \mathbb{R}^{k-1} using the eigenvectors associated with the k − 1 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 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. Keywords. Random Matrices, Random Geometric Graphs, Block Models, Spectral Clustering 1. Introduction and Main Results The history of science has been marked by attempts to make sense of data and measurements and to explain them in a sensible way. A natural step in this direction is to organize the data in a (hopefully small) number of groups that somehow capture the main features of its objects. Objects with similar characteristics must belong to the same group, while dissimilar objects must be placed in separate groups. Quoting Jain [ 17 ] , “cluster analysis is the formal study of methods and algorithms for grouping, or clustering, objects according to measured or perceived intrinsic characteristics or similarity.” In opposition to classification or discriminant analysis (supervised learning), for which objects are tagged with class labels defined by an external source, data clustering aims to assign the objects to classes that are not defined a priori, and is supposed to capture intrinsic properties or the underlying structure of the data set. Algorithms based on eigenvalues and eigenvectors play a prominent role in uncovering complex dependencies in a data set. Data clustering is widely used in real-world applications in areas such as biology [ 28 ] , computer science [ 35 ] , economics [ 24 ] , medicine [ 11 ] and social sciences [ 8 ] . In parallel, there is a large body of work related to the design and analysis of clustering algorithms [ 22 , 26 , 27 , 30 ] . Success is often based on the algorithm’s ability to recover “the ground truth” of an artificial data set or to achieve high agreement with the classifications of benchmark data sets. Von Luxburg, Williamson, and Guyon [ 34 ] discuss practical and epistemological difficulties of context-free evaluation of clustering algorithms and argue for a more problem-dependent approach and for a systematic catalog of clustering problems. As Jain [ 17 ] puts it, “a cluster is a subjective entity that is in the eye of the beholder and whose significance and interpretation require domain knowledge”. According to [ 34 ] , an environment that greatly simplifies real-world data sets and where the aim of cluster analysis can be made precise is that of constraint-based models that assume interactions between samples, which lend themselves to graph partitioning methods. For example, Spielman and Teng [ 31 ] showed that spectral partitioning methods based on the eigenvector associated with the algebraic connectivity work well on bounded-degree planar graphs and finite element meshes. Lee, Gharan, and Trevisan [ 19 ] provided a theoretical justification for algorithms that use the eigenspaces associated with the bottom k eigenvalues of Laplacian matrices to embed data points in \mathbb{R}^{k} , and then cluster these points based on geometric considerations. Von Luxburg, Belkin, and Bousquet [ 33 ] have obtained results about the consistency of spectral clustering. Under some mild assumptions, they have shown that clusterings constructed by Laplacian-based spectral clustering algorithms converge almost surely to a limit clustering of the entire data space. A very natural random graph model with an underlying structure is the Stochastic Block Model (SBM, for short), which was introduced by Holland, Laskey, and Leinhardt [ 15 ] . Given a number of nodes n and a number of communities k , an initial partition is given, or, alternatively, each node is initially assigned uniformly at random to one of the communities. Next, for any two nodes i and j , an edge \{i,j\} is drawn, independently from the other edges, with some probability p_{i,j} that only depends on the communities of i and j . Clustering in such a graph corresponds to the inverse problem where one wishes to extract the k communities from a graph G that was generated using SBM. Lei and Rinaldo [ 20 ] showed that spectral clustering leads to perfect extraction under reasonably mild conditions, also for rather sparse regimes. We refer the interested reader to Abbe [ 1 ] for a survey of related results. In most practical situations, nodes would typically have other attributes beyond the community label. For instance, spatial attributes may be captured by an embedding in a metric space. In such geometric models, the connection between a pair of nodes depends both on their communities and on their relative positions in the metric space. Models of this type may be classified as geometric block models if the embedding of the nodes into the metric space is random, but the criterion for drawing an edge is deterministic based on their locations, or as soft geometric block models if the locations of the nodes define a probability distribution for the edges. In both cases, given three nodes i , j , and \ell , the event that i and \ell are adjacent is not independent from the events that i and j , or j and \ell , are adjacent. Community detection has been explored for geometric block models [ 9 , 10 ] , for Euclidean random geometric graphs [ 2 , 5 , 12 , 13 , 29 ] and for the soft geometric block model of Avrachenkov, Bobu, and Dreveton [ 3 ] . This body of work shows that there are methods that can successfully identify the community structure in (soft) geometric block models. Nevertheless, direct applications of classical spectral clustering algorithms, which consider eigenvectors associated with the top or bottom eigenvalues of the corresponding matrices, often fail. This is to be expected, as classical algorithms seek a classification such that the elements in the same class are all similar to each other, while elements in different classes are dissimilar. In terms of graphs, this typically means that elements in the same class tend to be joined to each other by short paths. However, the dependence on the geometry may force elements of the same community to be far from each other. To illustrate the difference with an informal example, suppose that we have a graph such that the nodes are people and the edges tell us when two people are friends. Classical algorithms would likely sort people according to where they live, while the underlying community