Exact label recovery threshold found for Euclidean random graphs

In a new paper from authors Julia Gaudio, Charlie Guan, Xiaochun Niu, and Ermin Wei, the team tackles a fundamental problem in network analysis: exactly recovering discrete community labels assigned to vertices embedded in Euclidean space. They model vertices as a Poisson point process in R^d, with edge weights that depend on both vertex labels and their geometric positions. This framework extends classic problems like submatrix localization and Z2-synchronization into a spatial setting, and includes the Geometric Stochastic Block Model (GSBM) as a special case.

The paper's key contribution is establishing the exact threshold for information-theoretic recovery. Under a mild distinctness condition on the weight distributions, the authors prove that if the Chernoff-Hellinger divergence between the distributions is too low, no algorithm can recover all labels exactly. Conversely, above this threshold, their proposed efficient two-phase algorithm succeeds. The first phase uses a local propagation scheme to get an almost-exact labeling, and the second refines that to exact recovery. This two-phase approach mirrors the local-to-global amplification phenomenon seen in other community detection problems.

The technical method is notable for its unified analysis: impossibility is proven via a Cramér lower bound, while achievability relies on the so-called genie estimator, which decodes a single vertex's label assuming all others are known. The threshold is exactly dictated by this genie estimator's performance. This result is both theoretically and practically significant for understanding when geometric node labeling is possible, with implications for social networks, sensor networks, and any domain where nodes have both connectivity and spatial relationships.