  Many inference problems in structured prediction can be modeled as maximizing
a score function on a space of labels, where graphs are a natural
representation to decompose the total score into a sum of unary (nodes) and
pairwise (edges) scores. Given a generative model with an undirected connected
graph $G$ and true vector of binary labels, it has been previously shown that
when $G$ has good expansion properties, such as complete graphs or $d$-regular
expanders, one can exactly recover the true labels (with high probability and
in polynomial time) from a single noisy observation of each edge and node. We
analyze the previously studied generative model by Globerson et al. (2015)
under a notion of statistical parity. That is, given a fair binary node
labeling, we ask the question whether it is possible to recover the fair
assignment, with high probability and in polynomial time, from single edge and
node observations. We find that, in contrast to the known trade-offs between
fairness and model performance, the addition of the fairness constraint
improves the probability of exact recovery. We effectively explain this
phenomenon and empirically show how graphs with poor expansion properties, such
as grids, are now capable to achieve exact recovery with high probability.
Finally, as a byproduct of our analysis, we provide a tighter
minimum-eigenvalue bound than that of Weyl's inequality.
