  Structured prediction can be thought of as a simultaneous prediction of
multiple labels. This is often done by maximizing a score function on the space
of labels, which decomposes as a sum of pairwise and unary potentials. The
above is naturally modeled with a graph, where edges and vertices are related
to pairwise and unary potentials, respectively. We consider the generative
process proposed by Globerson et al. and apply it to general connected graphs.
We analyze the structural conditions of the graph that allow for the exact
recovery of the labels. Our results show that exact recovery is possible and
achievable in polynomial time for a large class of graphs. In particular, we
show that graphs that are bad expanders can be exactly recovered by adding
small edge perturbations coming from the Erd\H{o}s-R\'enyi model. Finally, as a
byproduct of our analysis, we provide an extension of Cheeger's inequality.
