Discretization-free exact recovery in geometric community detection

Many graph-learning problems combine relational observations with continuous geometric side information, yet existing exact-recovery methods for geometric community detection propagate labels according to a fixed spatial discretization. We instead introduce an information-adaptive algorithm for the Geometric Hidden Community Model that operates directly on the observed geometry: at each step it labels the frontier vertex whose already labeled neighbors provide the strongest worst-case Hellinger evidence, so the propagation order is determined by statistical information rather than by a spatial mesh. This perspective also permits heterogeneous information across communities and distances: different community pairs may rely on different witness communities and different distance ranges. In particular, our condition covers canonical symmetric multi-community models, including the geometric stochastic block model, for which the previous all-witness condition fails whenever there are at least three communities. Under an explicit witness-connectivity condition and the known Chernoff–Hellinger information condition, we prove polynomial-time exact recovery; in the standard fully distinguishable regime, the sufficient boundary coincides with the information-theoretic threshold. Experiments show that information-adaptive ordering substantially reduces propagation errors relative to spatial and degree-based schedules, succeeds beyond the regime covered by our proof, and performs competitively with calibrated block propagation on a canonical geometric block-model benchmark.