GAEA: Graph Augmentation for Equitable Access via Reinforcement Learning
This work addresses the critical problem of disparate access to resources in societal and sociotechnical networks, aiming to enhance equity for various subpopulations by strategically modifying network structures.
This paper introduces Graph Augmentation for Equitable Access (GAEA), a new problem class focused on editing graph edges under budget constraints to enhance equity in networked systems. The authors prove the problem is NP-hard and inapproximable within a factor of (1-1/3e), and propose a Markov Reward Process-based mechanism design framework. Their algorithm outperforms baselines on synthetic graphs and is demonstrated on real-world Chicago bus networks to improve equitable access to schools across racial groups, and on university Facebook networks to increase equitable access to attributed nodes across gender groups.
Disparate access to resources by different subpopulations is a prevalent issue in societal and sociotechnical networks. For example, urban infrastructure networks may enable certain racial groups to more easily access resources such as high-quality schools, grocery stores, and polling places. Similarly, social networks within universities and organizations may enable certain groups to more easily access people with valuable information or influence. Here we introduce a new class of problems, Graph Augmentation for Equitable Access (GAEA), to enhance equity in networked systems by editing graph edges under budget constraints. We prove such problems are NP-hard, and cannot be approximated within a factor of $(1-\tfrac{1}{3e})$. We develop a principled, sample- and time- efficient Markov Reward Process (MRP)-based mechanism design framework for GAEA. Our algorithm outperforms baselines on a diverse set of synthetic graphs. We further demonstrate the method on real-world networks, by merging public census, school, and transportation datasets for the city of Chicago and applying our algorithm to find human-interpretable edits to the bus network that enhance equitable access to high-quality schools across racial groups. Further experiments on Facebook networks of universities yield sets of new social connections that would increase equitable access to certain attributed nodes across gender groups.