Fairness constraints can help exact inference in structured prediction
Abstract
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 and true vector of binary labels, it has been previously shown that when has good expansion properties, such as complete graphs or -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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Fairgen: Towards Fair Graph GenerationLecheng Zheng, Dawei Zhou, Hanghang Tong, Jiejun Xu et al.ICDE 2024 · 1 citation
- Exact Inference in High-order Structured PredictionChuyang Ke, Jean HonorioICML 2023 · 4 citations
- Fair GLASSO: Estimating Fair Graphical Models with Unbiased Statistical BehaviorMadeline Navarro, Samuel Rey, Andrei Buciulea, Antonio G. Marques et al.NeurIPS 2024 · 14 citations
- On Dyadic Fairness: Exploring and Mitigating Bias in Graph ConnectionsPeizhao Li, Yifei Wang, Han Zhao, Pengyu Hong et al.ICLR 2021 · 142 citations
- Fair and Optimal Classification via Post-ProcessingRuicheng Xian, Lang Yin, Han ZhaoICML 2023 · 57 citations
