  In this paper, we propose a family of label recovery problems on weighted
Euclidean random graphs. The vertices of a graph are embedded in $\mathbb{R}^d$
according to a Poisson point process, and are assigned to a discrete community
label. Our goal is to infer the vertex labels, given edge weights whose
distributions depend on the vertex labels as well as their geometric positions.
Our general model provides a geometric extension of popular graph and matrix
problems, including submatrix localization and $\mathbb{Z}_2$-synchronization,
and includes the Geometric Stochastic Block Model (proposed by Sankararaman and
Baccelli) as a special case. We study the fundamental limits of exact recovery
of the vertex labels. Under a mild distinctness of distributions assumption, we
determine the information-theoretic threshold for exact label recovery, in
terms of a Chernoff-Hellinger divergence criterion. Impossibility of recovery
below the threshold is proven by a unified analysis using a Cram\'er lower
bound. Achievability above the threshold is proven via an efficient two-phase
algorithm, where the first phase computes an almost-exact labeling through a
local propagation scheme, while the second phase refines the labels. The
information-theoretic threshold is dictated by the performance of the so-called
genie estimator, which decodes the label of a single vertex given all the other
labels. This shows that our proposed models exhibit the local-to-global
amplification phenomenon.
