GAEA: Graph Augmentation for Equitable Access via Reinforcement Learning

Govardana Sachithanandam Ramachandran, Ivan Brugere, Lav R. Varshney, Caiming Xiong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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-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.

Original languageEnglish (US)
Title of host publicationAIES 2021 - Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society
PublisherAssociation for Computing Machinery
Pages884-894
Number of pages11
ISBN (Electronic)9781450384735
DOIs
StatePublished - Jul 21 2021
Externally publishedYes
Event4th AAAI/ACM Conference on Artificial Intelligence, Ethics, and Society, AIES 2021 - Virtual, Online, United States
Duration: May 19 2021May 21 2021

Publication series

NameAIES 2021 - Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society

Conference

Conference4th AAAI/ACM Conference on Artificial Intelligence, Ethics, and Society, AIES 2021
Country/TerritoryUnited States
CityVirtual, Online
Period5/19/215/21/21

Keywords

  • dataset
  • equity
  • fairness
  • reinforcement learning
  • social networks

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'GAEA: Graph Augmentation for Equitable Access via Reinforcement Learning'. Together they form a unique fingerprint.

Cite this