Exact Recovery in the Geometric Hidden Community Model

Julia Gaudio, Andrew Jin · 2026

Read Exact Recovery in the Geometric Hidden Community Model by Julia Gaudio, Andrew Jin (2026) 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-2601-17591.txt.

Introduction

Julia Gaudio and Andrew Jin study exact recovery in the geometric hidden community model. Hidden community tasks include block model detection and submatrix search. Social networks show transitive behavior, with many triangles. Geometric versions of the model build in that trait. The question is when exact recovery of the hidden groups is possible.

Exact recovery is a high bar: every node placed right. Thresholds tell users when data suffices and when it cannot. Such thresholds guide algorithm design and data collection. Network science uses them across biology and security as well. Gaudio and Jin add the geometric case to that map. Triangle-rich data needs its own rules.

Catalog record

CREATORJulia Gaudio, Andrew Jin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE112 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-17591

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Exact Recovery in the Geometric Hidden Community Model Julia Gaudio, Andrew Jin Abstract Hidden community problems, such as community detection in the Stochastic Block Model (SBM), submatrix localization, and ℤ 2 \mathbb{Z}_{2} synchronization, have received considerable attention in the probability, statistics, and information-theory literature. Motivated by transitive behavior in social networks, which tend to exhibit high triangle density, recent works have considered hidden community models in spatially-embedded networks. In particular, Baccelli and Sankararaman proposed the Geometric SBM, a spatially-embedded analogue of the standard SBM with dramatically more triangles. In this paper, we consider the problem of exact recovery for the Geometric Hidden Community Model (GHCM) of Gaudio, Guan, Niu, and Wei, which generalizes the Geometric SBM to allow for arbitrary pairwise observation distributions. Under mild technical assumptions, we find the information-theoretic threshold for exact recovery in the “distance-dependent” GHCM, which allows the pairwise distributions to depend on distance as well as community labels, thus completing the picture of exact recovery in spatially-embedded hidden community models. 1 Introduction Community detection is the problem of identifying hidden dense communities in networks. The Stochastic Block Model (SBM), introduced by Holland, Laskey, and Leinhardt in 1983 [ 12 ] , is considered the canonical model for generating random graphs with community structure. In its simplest version, the SBM comprises two communities of vertices of equal size. Pairs of vertices in the same community are connected with probability p , while pairs of vertices in opposite communities are connected with probability q . If p>q , then the graph exhibits assortative community structure; that is, typical instances of the SBM have two dense communities with sparse connections between them. Depending on the values of p and q , it may be possible to recover the communities exactly, almost exactly, or partially. These inference tasks have been the subject of a large body of research, much of it summarized in the survey of Abbe [ 4 ] . An emerging line of work studies spatially-embedded versions of community detection problems, which lead to transitive community structure; namely, if (u,v) and (u,w) are edges, then (v,w) is likely to be an edge as well. Recently, Baccelli and Sankararaman proposed the Geometric Stochastic Block Model (GSBM) [ 14 ] , a spatially-embedded analogue of the SBM in which vertices are placed in a bounded region of \mathbb{R}^{d} according to a homogeneous Poisson process, and vertices are connected by edges with probabilities that depend on both their communities as well as their distance. An important special case of the GSBM is one where vertices may only be connected by an edge if they are sufficiently close to each other (i.e., if the distance between u,v satisfies \|u-v\|\leq r_{n} ); in that case, they are connected with probability a if they are in the same community and with probability b otherwise. We refer to this as the constant-probability GSBM. In this special case, the GSBM has dramatically more triangles than the standard SBM. Fixing the average degree to be the same in the two models, the GSBM with \text{Pois}(\lambda n) vertices has order n times more triangles than the SBM with n vertices. Following the introduction of the GSBM, subsequent works focused on the exact recovery problem in the constant-probability GSBM. Gaudio, Niu, and Wei [ 11 ] determined the exact recovery threshold in the logarithmic-degree regime of the constant-probability GSBM, complementing the impossibility result that had been established by Abbe et al [ 1 ] . Furthermore, [ 11 ] proposed a linear-time algorithm for exact recovery which achieves the information-theoretic (IT) threshold. Gaudio, Guan, Niu, and Wei [ 9 ] then proposed the Geometric Hidden Community Model (GHCM), a generalization of the GSBM which allows for multiple, possibly unbalanced communities, and considers pairwise distributions that are not necessarily Bernoulli-valued (i.e. “edge” or “no edge”). The GHCM thus extends prominent hidden community models like submatrix localization and \mathbb{Z}_{2} synchronization to the spatially-embedded setting, capturing settings where pairwise observations are available only for vertices which are “close” in terms of their physical distance or their feature embedding. For example, consider the problem of sensor calibration in a physical network, in which relative measurements are available only for pairs of sensors that are close to each other. A variation of the algorithm of [ 11 ] was shown to achieve the IT threshold in the constant-probability GHCM, under some technical assumptions. Subsequently, Gaudio and Guan [ 8 ] showed that one of these assumptions, which requires a certain “distinctness of distributions,” is not required in the two-community setting, thus allowing for a spatially-embedded analogue of the planted dense subgraph and submatrix localization problems, among other hidden community problems. Moving away from the constant-probability assumption, Avrachenkov, Kumar, and Leskelä [ 5 ] considered the setting of two communities, where edge probabilities are governed by a pair of functions f_{\text{in}}(\cdot) and f_{\text{out}}(\cdot) : if u,v are in the same community, they are connected with probability f_{\text{in}}(\|u-v\|) ; otherwise, they are connected with probability f_{\text{out}}(\|u-v\|) . The authors considered only the case where d=1 and the functions differ by a constant factor. Subsequently, Gaudio and Jin [ 10 ] handled the case of arbitrary, constant dimension, where f_{\text{in}}(\cdot) and f_{\text{out}}(\cdot) only need to satisfy some regularity conditions but otherwise can be quite general. In this paper, we complete the picture for the exact recovery problem in the GHCM by allowing for distance dependence in pairwise distributions. We determine the IT threshold for exact recovery and show that an extension of the algorithms proposed by [ 9 ] and [ 10 ] achieves the IT threshold. Intuitively, the IT threshold is determined by the probability that a vertex can be accurately labeled when all other labels are accurately given. Since there are \Theta(n) vertices, the IT threshold occurs when the probability of misclassifying a given vertex is \Theta(1/n) . That is, if the error probability is \omega(1/n) , exact recovery is impossible, while if it is o(1/n) , then exact recovery is possible. While these asymptotics are intuitive, they are not immediate. The asymptotics of the impossibility result are established in [ 1 ] , and lower-bounding the error probability is accomplished by employing a Cramér lower bound from large deviations theory, following the analysis of [ 9 ] . On the other hand, the achievability result comes from adapting the algorithm proposed in [ 9 ] . The algorithm has three main steps: (1) label an initial seed set of \Theta(\log n) vertices using the maximum a posteriori (MAP) estimator; (2) propagate labels among “blocks” of vertices to achieve almost exact recovery; and (3) refine the almost exact labeling to turn it into an exact labeling. Step 3 is where the IT threshold is invoked. The main challenge in adapting the algorithm to the current, more general setting is in Steps (1) and (2). By allowing the observation distributions to be distance-dependent, there are pairs of vertices (u,v) such that their pairwise observation, given by X_{uv} , has a similar distribution no matter what communities u and v belong to. In this way, some distances are more informative than others. While the IT threshold accounts for the heterogeneity of information, accounting for this hurdle

Read the complete text