GAEA: Graph Augmentation for Equitable Access via Reinforcement Learning

• URL: http://arxiv.org/abs/2012.03900v2
• Date: Fri, 9 Apr 2021 11:27:25 GMT
• Title: GAEA: Graph Augmentation for Equitable Access via Reinforcement Learning
• Authors: Govardana Sachithanandam Ramachandran, Ivan Brugere, Lav R. Varshney, and Caiming Xiong
• Abstract summary: Disparate access to resources by different subpopulations is a prevalent issue in societal and sociotechnical networks. 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.
• Score: 50.90625274621288
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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-\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.

Related papers

• Anonymized Network Sensing Graph Challenge [6.896725738630828]
  The anonymized network sensing Graph Challenge seeks to enable large, open, community-based approaches to protecting networks. This challenge provides an opportunity to highlight novel approaches for optimizing the construction and analysis of anonymized traffic matrices. A GraphBLAS reference implementation is provided, but the use of GraphBLAS is not required in this Graph Challenge.
  arXiv  Detail & Related papers  (2024-09-12T15:07:16Z)
• Learning Regularization for Graph Inverse Problems [16.062351610520693]
  We introduce a framework leveraging GNNs to solve Graph Inverse Problems (GRIP) The framework is based on a combination of likelihood and prior terms, which are used to find a solution that fits the data. We study our approach on a number of representative problems that demonstrate the effectiveness of the framework.
  arXiv  Detail & Related papers  (2024-08-19T22:03:02Z)
• Marginal Nodes Matter: Towards Structure Fairness in Graphs [77.25149739933596]
  We propose textbfStructural textbfFair textbfGraph textbfNeural textbfNetwork (SFairGNN) to achieve structure fairness. Our experiments show SFairGNN can significantly improve structure fairness while maintaining overall performance in the downstream tasks.
  arXiv  Detail & Related papers  (2023-10-23T03:20:32Z)
• Learning Strong Graph Neural Networks with Weak Information [64.64996100343602]
  We develop a principled approach to the problem of graph learning with weak information (GLWI) We propose D$2$PT, a dual-channel GNN framework that performs long-range information propagation on the input graph with incomplete structure, but also on a global graph that encodes global semantic similarities.
  arXiv  Detail & Related papers  (2023-05-29T04:51:09Z)
• Cost Sensitive GNN-based Imbalanced Learning for Mobile Social Network Fraud Detection [37.14877936257601]
  We present a novel Cost-Sensitive Graph Neural Network (CSGNN) by creatively combining cost-sensitive learning and graph neural networks. The results show that CSGNN can effectively solve the graph imbalance problem and then achieve better detection performance than the state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2023-03-28T01:43:32Z)
• Ranking-based Group Identification via Factorized Attention on Social Tripartite Graph [68.08590487960475]
  We propose a novel GNN-based framework named Contextualized Factorized Attention for Group identification (CFAG) We devise tripartite graph convolution layers to aggregate information from different types of neighborhoods among users, groups, and items. To cope with the data sparsity issue, we devise a novel propagation augmentation layer, which is based on our proposed factorized attention mechanism.
  arXiv  Detail & Related papers  (2022-11-02T01:42:20Z)
• FastCover: An Unsupervised Learning Framework for Multi-Hop Influence Maximization in Social Networks [39.86798194955807]
  Finding influential users in social networks is a fundamental problem with many possible useful applications. In this paper, we reduce the problem of IM to a budget-constrained d-hop dominating set problem (kdDSP) We propose a unified machine learning (ML) framework, FastCover, to solve kdDSP by learning an efficient greedy strategy in an unsupervised way. FastCover determines the entire seed set from the nodes' scores computed with only one forward propagation of the GNN and has a time complexity quasi-linear in the graph size.
  arXiv  Detail & Related papers  (2021-10-31T10:49:21Z)
• CrossWalk: Fairness-enhanced Node Representation Learning [39.21278285140597]
  We develop a simple, effective and general method, CrossWalk, that enhances fairness of various graph algorithms. The key idea is to bias random walks to cross group boundaries, by upweighting edges which are closer to the groups' peripheries or (2) connect different groups in the network. CrossWalk pulls nodes that are near groups' peripheries towards their neighbors from other groups.
  arXiv  Detail & Related papers  (2021-05-06T14:45:34Z)
• QD-GCN: Query-Driven Graph Convolutional Networks for Attributed Community Search [54.42038098426504]
  QD-GCN is an end-to-end framework that unifies the community structure as well as node attributes to solve the ACS problem. We show that QD-GCN outperforms existing attributed community search algorithms in terms of both efficiency and effectiveness.
  arXiv  Detail & Related papers  (2021-04-08T07:52:48Z)
• Interpretable Signed Link Prediction with Signed Infomax Hyperbolic Graph [54.03786611989613]
  signed link prediction in social networks aims to reveal the underlying relationships (i.e. links) among users (i.e. nodes) We develop a unified framework, termed as Signed Infomax Hyperbolic Graph (textbfSIHG) In order to model high-order user relations and complex hierarchies, the node embeddings are projected and measured in a hyperbolic space with a lower distortion.
  arXiv  Detail & Related papers  (2020-11-25T05:09:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.