research-article

GAEA: Graph Augmentation for Equitable Access via Reinforcement Learning

Authors:

Govardana Sachithanandam Ramachandran,

Lav R. Varshney,

Caiming XiongAuthors Info & Claims

AIES '21: Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society

Pages 884 - 894

https://doi.org/10.1145/3461702.3462615

Published: 30 July 2021 Publication History

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.

References

[1]

Rediet Abebe, Nicole Immorlica, Jon Kleinberg, and Brendan Lucier. 2019. Triadic Closure Alleviates Network Segregation. In Joint Workshop on AI for Social Good (NeurIPS '19).

[2]

Robert Bowerman, Brent Hall, and Paul Calamai. 1995. A multi-objective optimization approach to urban school bus routing: Formulation and solution method. Transportation Research Part A: Policy and Practice 29, 2 (March 1995), 107--123. https://doi.org/10.1016/0965--8564(94)E0006-U

[3]

Nicolas Carion, Nicolas Usunier, Gabriel Synnaeve, and Alessandro Lazaric. 2019. A Structured Prediction Approach for Generalization in Cooperative Multi-Agent Reinforcement Learning. In Advances in Neural Information Processing Systems 32, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (Eds.). Curran Associates, Inc., 8128--8138.

[4]

Fan Chung and Linyuan Lu. 2002. Connected components in random graphs with given expected degree sequences. Annals of Combinatorics 6, 2 (2002), 125--145.

[5]

Megan J. Cole, Richard M. Bailey, James D. S. Cullis, and Mark G. New. 2018. Spatial inequality in water access and water use in South Africa. Water Policy 20, 1 (Feb. 2018), 37--52. https://doi.org/10.2166/wp.2017.111

[6]

Pierluigi Crescenzi, Gianlorenzo D'angelo, Lorenzo Severini, and Yllka Velaj. 2016. Greedily improving our own closeness centrality in a network. ACM Transactions on Knowledge Discovery from Data 11, 1 (2016), 1--32.

[7]

Cynthia Dwork and Christina Ilvento. 2018. Fairness Under Composition. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). 33:1--33:20. https://doi.org/10.4230/LIPIcs.ITCS.2019.33

[8]

Uriel Feige. 1998. A threshold of ln?? for approximating set cover. J. ACM 45, 4 (1998), 634--652.

Digital Library

[9]

Benjamin Fish, Ashkan Bashardoust, Danah Boyd, Sorelle Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian. 2019. Gaps in Information Access in Social Networks?. In Proceedings of the World Wide Web Conference (WWW '19). 480--490. https://doi.org/10.1145/3308558.3313680

Digital Library

[10]

Lena V Groeger, Annie Waldman, and David Eads. 2018. Miseducation: Is there racial inequality at your school? Retreived from https://projects.propublica.org/miseducation (2018).

[11]

Swati Gupta, Akhil Jalan, Gireeja Ranade, Yang, and Simon Zhuang. 2020. Too Many Fairness Metrics: Is There a Solution?. In Ethics of Data Science Conference. https://doi.org/10.2139/ssrn.3554829

[12]

A. Hay and E. Trinder. 1991. Concepts of Equity, Fairness, and Justice Expressed by Local Transport Policymakers. Environment and Planning C: Politics and Space 9, 4 (Dec. 1991), 453--465. https://doi.org/10.1068/c090453

[13]

Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. 1983. Stochastic blockmodels: First steps. Social Networks 5, 2 (1983), 109--137.

[14]

Petter Holme and Beom Jun Kim. 2002. Growing scale-free networks with tunable clustering. Physical Review E 65, 2 (2002), 026107.

[15]

Tsan-Sheng. Hsu and Vijaya. Ramachandran. 1993. Finding a Smallest Augmentation to Biconnect a Graph. SIAM J. Comput. 22, 5 (1993), 889--912. https://doi.org/10.1137/0222056

Digital Library

[16]

Eric Jang, Shixiang Gu, and Ben Poole. 2016. Categorical reparameterization with Gumbel-softmax. arXiv:1611.01144 [stat.ML].

[17]

David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the Spread of Influence through a Social Network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '03). 137--146. https://doi.org/10.1145/956750.956769

Digital Library

[18]

François Le Gall. 2014. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. 296--303.

Digital Library

[19]

Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. 2007. Cost-Effective Outbreak Detection in Networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '07). 420--429. https://doi.org/10.1145/1281192.1281239

Digital Library

[20]

Y. Li, J. Fan, Y.Wang, and K. Tan. 2018. Influence Maximization on Social Graphs: A Survey. IEEE Transactions on Knowledge and Data Engineering 30, 10 (Oct 2018), 1852--1872. https://doi.org/10.1109/TKDE.2018.2807843

[21]

Michael L Littman. 1994. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994. Elsevier, 157--163.

Digital Library

[22]

John Logan. 2014. Diversity and Disparities: America Enters a New Century. Russell Sage Foundation.

[23]

Krishna Malakar, Trupti Mishra, and Anand Patwardhan. 2018. Inequality in water supply in India: an assessment using the Gini and Theil indices. Environment, Development and Sustainability 20 (April 2018), 841--864. https://doi.org/10.1007/s10668-017--9913-0

[24]

Marvin B. Mandell. 1991. Modelling Effectiveness-Equity Trade-Offs in Public Service Delivery Systems. Management Science 37, 4 (April 1991), 377--499. https://doi.org/10.1287/mnsc.37.4.467

[25]

Michael T. Marsh and David A. Schilling. 1994. Equity measurement in facility location analysis: A review and framework. European Journal of Operational Research 74, 1 (April 1994), 1--17. https://doi.org/10.1016/0377--2217(94)90200--3

[26]

Donald M. McAllister. 1976. Equity and Efficiency in Public Facility Location. Geographical Analysis 8, 1 (Jan. 1976), 47--63. https://doi.org/10.1111/j.1538--4632.1976.tb00528.x

[27]

Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. 2019. A survey on bias and fairness in machine learning. arXiv:1908.09635 [cs.LG].

[28]

Anthony J. Mumphrey, John E. Seley, and JulianWolpert. 1971. A Decision Model for Locating Controversial Facilities. Journal of the American Institute of Planners 37, 6 (1971), 397--402. https://doi.org/10.1080/01944367108977389

[29]

Jorge Nocedal and Stephen Wright. 2006. Numerical Optimization. Springer Science & Business Media.

[30]

C. Nowzari, V. M. Preciado, and G. J. Pappas. 2016. Analysis and Control of Epidemics: A Survey of Spreading Processes on Complex Networks. IEEE Control Systems Magazine 36, 1 (Feb 2016), 26--46. https://doi.org/10.1109/MCS.2015.2495000

[31]

Jennifer M. Orsi, Helen Margellos-Anast, and Steven Whitman. 2010. Black--White Health Disparities in the United States and Chicago: A 15-Year Progress Analysis. American Journal of Public Health 100, 2 (2010), 349--356. https://doi.org/10.2105/AJPH.2009.165407

[32]

Amanda L. Traud, Peter J. Mucha, and Mason A. Porter. 2012. Social structure of Facebook networks. Physica A: Statistical Mechanics and its Applications 391, 16 (Aug. 2012), 4165--4180. https://doi.org/10.1016/j.physa.2011.12.021

[33]

S. Verma and J. Rubin. 2018. Fairness Definitions Explained. In 2018 IEEE/ACM International Workshop on Software Fairness (FairWare). https://doi.org/10.23919/FAIRWARE.2018.8452913

[34]

Lin Xiao and Stephen Boyd. 2004. Fast linear iterations for distributed averaging. Systems & Control Letters 53, 1 (2004), 65--78.

[35]

Hyejin Youn, Michael T. Gastner, and Hawoong Jeong. 2008. Price of Anarchy in Transportation Networks: Efficiency and Optimality Control. Physical Review Letters 101, 12 (Sept. 2008), 128701. https://doi.org/10.1103/PhysRevLett.101.128701

[36]

Yao Zhang, Arvind Ramanathan, Anil Vullikanti, Laura Pullum, and B. Aditya Prakash. 2019. Data-driven efficient network and surveillance-based immunization. Knowledge and Information Systems 61, 3 (2019), 1667--1693. https://doi.org/10.1007/s10115-018-01326-x

Digital Library

[37]

Stephan Zheng, Alexander Trott, Sunil Srinivasa, Nikhil Naik, Melvin Gruesbeck, David C. Parkes, and Richard Socher. 2020. The AI Economist: Improving Equality and Productivity with AI-Driven Tax Policies. arXiv:2004.13332 [econ.GN].

Cited By

Michailidis DTasnim MGhebreab SSantos F(2024)Tackling school segregation with transportation network interventions: an agent-based modelling approachAutonomous Agents and Multi-Agent Systems10.1007/s10458-024-09652-x38:1Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1007/s10458-024-09652-x
Bashardoust AFriedler SScheidegger CSullivan BVenkatasubramanian S(2023)Reducing Access Disparities in Networks using Edge Augmentation✱Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency10.1145/3593013.3594105(1635-1651)Online publication date: 12-Jun-2023
https://dl.acm.org/doi/10.1145/3593013.3594105
Nie MChen DWang D(2023)Reinforcement Learning on Graphs: A SurveyIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2022.32225457:4(1065-1082)Online publication date: Aug-2023
https://doi.org/10.1109/TETCI.2022.3222545
Show More Cited By

Index Terms

GAEA: Graph Augmentation for Equitable Access via Reinforcement Learning
1. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
  2. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Network formation
    2. Machine learning theory
      1. Reinforcement learning

Recommendations

Equitable colorings of planar graphs without short cycles

An equitable coloring of a graph is a proper vertex coloring such that the sizes of every two color classes differ by at most 1. Chen, Lih, and Wu conjectured that every connected graph G with maximum degree @D>=2 has an equitable coloring with @D ...
Equitable and equitable list colorings of graphs

A proper k-vertex coloring of a graph is an equitable k-coloring if the sizes of the color classes differ by at most 1. A graph G is equitably k-choosable if, for any k-uniform list assignment L, G is L-colorable and each color appears on at most @?|V(G)...
Equitable Δ-coloring of graphs

Consider a graph G consisting of a vertex set V(G) and an edge set E(G). Let @D(G) and @g(G) denote the maximum degree and the chromatic number of G, respectively. We say that G is equitably @D(G)-colorable if there exists a proper @D(G)-coloring of G ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

AIES '21: Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society

July 2021

1077 pages

ISBN:9781450384735

DOI:10.1145/3461702

Program Chairs:
Marion Fourcade
University of California Berkeley, USA
,
Benjamin Kuipers
University of Michigan, USA
,
Seth Lazar
Australian National University, Australia
,
Deirdre Mulligan
University of California Berkeley, USA

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 July 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

AIES '21

Sponsor:

SIGAI

AIES '21: AAAI/ACM Conference on AI, Ethics, and Society

May 19 - 21, 2021

Virtual Event, USA

Acceptance Rates

Overall Acceptance Rate 61 of 162 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
157
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)4

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Michailidis DTasnim MGhebreab SSantos F(2024)Tackling school segregation with transportation network interventions: an agent-based modelling approachAutonomous Agents and Multi-Agent Systems10.1007/s10458-024-09652-x38:1Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1007/s10458-024-09652-x
Bashardoust AFriedler SScheidegger CSullivan BVenkatasubramanian S(2023)Reducing Access Disparities in Networks using Edge Augmentation✱Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency10.1145/3593013.3594105(1635-1651)Online publication date: 12-Jun-2023
https://dl.acm.org/doi/10.1145/3593013.3594105
Nie MChen DWang D(2023)Reinforcement Learning on Graphs: A SurveyIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2022.32225457:4(1065-1082)Online publication date: Aug-2023
https://doi.org/10.1109/TETCI.2022.3222545
Fabris AMessina SSilvello GSusto G(2022)Tackling Documentation Debt: A Survey on Algorithmic Fairness DatasetsProceedings of the 2nd ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization10.1145/3551624.3555286(1-13)Online publication date: 6-Oct-2022
https://dl.acm.org/doi/10.1145/3551624.3555286
Fabris AMessina SSilvello GSusto G(2022)Algorithmic fairness datasets: the story so farData Mining and Knowledge Discovery10.1007/s10618-022-00854-z36:6(2074-2152)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10618-022-00854-z

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents