# Exploring Algorithmic Fairness in Robust Graph Covering Problems

arXiv: https://arxiv.org/abs/2006.06865 · HTML: https://mlsanity.com/paper/2006.06865/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2020.

## Built on by (most cited first, 19 of 19)

- [Last Layer Re-Training is Sufficient for Robustness to Spurious Correlations](https://mlsanity.com/paper/2204.02937/) (2022)
- [Simple data balancing achieves competitive worst-group-accuracy](https://mlsanity.com/paper/2110.14503/) (2021)
- [Fairness in Graph Mining: A Survey](https://mlsanity.com/paper/2204.09888/) (2022)
- [RawlsGCN: Towards Rawlsian Difference Principle on Graph Convolutional Network](https://mlsanity.com/paper/2202.13547/) (2022)
- [A Sociotechnical View of Algorithmic Fairness](https://mlsanity.com/paper/2110.09253/) (2021)
- [Fairness Amidst Non-IID Graph Data: A Literature Review](https://mlsanity.com/paper/2202.07170/) (2022)
- [A Survey on Fairness for Machine Learning on Graphs](https://mlsanity.com/paper/2205.05396/) (2022)
- [A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions](https://mlsanity.com/paper/2308.13821/) (2023)
- [Algorithmic Bias and Data Bias: Understanding the Relation between Distributionally Robust Optimization and Data Curation](https://mlsanity.com/paper/2106.09467/) (2021)
- [Graph Learning with Localized Neighborhood Fairness](https://mlsanity.com/paper/2212.12040/) (2022)
- [Deceptive Fairness Attacks on Graphs via Meta Learning](https://mlsanity.com/paper/2310.15653/) (2023)
- [Learning Resource Allocation Policies from Observational Data with an Application to Homeless Services Delivery](https://mlsanity.com/paper/2201.10053/) (2022)
- [Fairness in Streaming Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2305.15118/) (2023)
- [A Benchmark for Fairness-Aware Graph Learning](https://mlsanity.com/paper/2407.12112/) (2024)
- [The Hardness of Achieving Impact in AI for Social Impact Research: A Ground-Level View of Challenges & Opportunities](https://mlsanity.com/paper/2506.14829/) (2025)
- [FairRARI: A Plug and Play Framework for Fairness-Aware PageRank](https://mlsanity.com/paper/2602.08589/) (2026)
- [Long-term Fairness in Ride-Hailing Platform](https://mlsanity.com/paper/2407.17839/) (2024)
- [A Critical Review of Predominant Bias in Neural Networks](https://mlsanity.com/paper/2502.11031/) (2025)
- [Estimating Fair Graphs from Graph-Stationary Data](https://mlsanity.com/paper/2510.07536/) (2025)

## Abstract (arXiv)

Fueled by algorithmic advances, AI algorithms are increasingly being deployed in settings subject to unanticipated challenges with complex social effects. Motivated by real-world deployment of AI driven, social-network based suicide prevention and landslide risk management interventions, this paper focuses on robust graph covering problems subject to group fairness constraints. We show that, in the absence of fairness constraints, state-of-the-art algorithms for the robust graph covering problem result in biased node coverage: they tend to discriminate individuals (nodes) based on membership in traditionally marginalized groups. To mitigate this issue, we propose a novel formulation of the robust graph covering problem with group fairness constraints and a tractable approximation scheme applicable to real-world instances. We provide a formal analysis of the price of group fairness (PoF) for this problem, where we show that uncertainty can lead to greater PoF. We demonstrate the effectiveness of our approach on several real-world social networks. Our method yields competitive node coverage while significantly improving group fairness relative to state-of-the-art methods.