  A variety of information processing tasks in practice involve recovering $n$
objects from single-shot graph-based measurements, particularly those taken
over the edges of some measurement graph $\mathcal{G}$. This paper concerns the
situation where each object takes value over a group of $M$ different values,
and where one is interested to recover all these values based on observations
of certain pairwise relations over $\mathcal{G}$. The imperfection of
measurements presents two major challenges for information recovery: 1)
$\textit{inaccuracy}$: a (dominant) portion $1-p$ of measurements are
corrupted; 2) $\textit{incompleteness}$: a significant fraction of pairs are
unobservable, i.e. $\mathcal{G}$ can be highly sparse.
  Under a natural random outlier model, we characterize the $\textit{minimax
recovery rate}$, that is, the critical threshold of non-corruption rate $p$
below which exact information recovery is infeasible. This accommodates a very
general class of pairwise relations. For various homogeneous random graph
models (e.g. Erdos Renyi random graphs, random geometric graphs, small world
graphs), the minimax recovery rate depends almost exclusively on the edge
sparsity of the measurement graph $\mathcal{G}$ irrespective of other graphical
metrics. This fundamental limit decays with the group size $M$ at a square root
rate before entering a connectivity-limited regime. Under the Erdos Renyi
random graph, a tractable combinatorial algorithm is proposed to approach the
limit for large $M$ ($M=n^{\Omega(1)}$), while order-optimal recovery is
enabled by semidefinite programs in the small $M$ regime.
  The extended (and most updated) version of this work can be found at
(http://arxiv.org/abs/1504.01369).
