# BeMap: Balanced Message Passing for Fair Graph Neural Network

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 47 of its 69 references that are in the map.
- First posted on arXiv 7 Jun 2023.

## Builds on (most cited first, 30 of 47)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Age Progression/Regression by Conditional Adversarial Autoencoder](https://mlsanity.com/paper/1702.08423/) (2017)
- [Point-GNN: Graph Neural Network for 3D Object Detection in a Point Cloud](https://mlsanity.com/paper/2003.01251/) (2020)
- [Embed to Control: A Locally Linear Latent Dynamics Model for Control from Raw Images](https://mlsanity.com/paper/1506.07365/) (2015)
- [Graph Neural Network for Traffic Forecasting: A Survey](https://mlsanity.com/paper/2101.11174/) (2021)
- [Graph Random Neural Network for Semi-Supervised Learning on Graphs](https://mlsanity.com/paper/2005.11079/) (2020)
- [Adaptive Sampling Towards Fast Graph Representation Learning](https://mlsanity.com/paper/1809.05343/) (2018)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information](https://mlsanity.com/paper/2009.01454/) (2020)
- [GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks](https://mlsanity.com/paper/2103.08826/) (2021)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [Towards a Unified Framework for Fair and Stable Graph Representation Learning](https://mlsanity.com/paper/2102.13186/) (2021)
- [Compositional Fairness Constraints for Graph Embeddings](https://mlsanity.com/paper/1905.10674/) (2019)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [Discrimination in Online Ad Delivery](https://mlsanity.com/paper/1301.6822/) (2013)
- [EDITS: Modeling and Mitigating Data Bias for Graph Neural Networks](https://mlsanity.com/paper/2108.05233/) (2021)
- [DiffWire: Inductive Graph Rewiring via the Lov'asz Bound](https://mlsanity.com/paper/2206.07369/) (2022)

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

- [How Efficient is LLM-Generated Code? A Rigorous & High-Standard Benchmark](https://mlsanity.com/paper/2406.06647/) (2024)
- [Large Language Models as Topological Structure Enhancers for Text-Attributed Graphs](https://mlsanity.com/paper/2311.14324/) (2023)
- [Fairness-Aware Graph Neural Networks: A Survey](https://mlsanity.com/paper/2307.03929/) (2023)
- [BACKTIME: Backdoor Attacks on Multivariate Time Series Forecasting](https://mlsanity.com/paper/2410.02195/) (2024)
- [Pave Your Own Path: Graph Gradual Domain Adaptation on Fused Gromov-Wasserstein Geodesics](https://mlsanity.com/paper/2505.12709/) (2025)
- [PageRank Bandits for Link Prediction](https://mlsanity.com/paper/2411.01410/) (2024)
- [GRAPHGINI: Fostering Individual and Group Fairness in Graph Neural Networks](https://mlsanity.com/paper/2402.12937/) (2024)
- [Estimating Fair Graphs from Graph-Stationary Data](https://mlsanity.com/paper/2510.07536/) (2025)
- [FnRGNN: Distribution-aware Fairness in Graph Neural Network](https://mlsanity.com/paper/2510.19257/) (2025)
- [Quantile-Free Uncertainty Quantification in Graph Neural Networks](https://mlsanity.com/paper/2605.04847/) (2026)
- [Fairness-Aware Network Embeddings: Methods, Applications, and Challenges](https://mlsanity.com/paper/2608.19381/) (2026)

## Abstract (arXiv)

Fairness in graph neural networks has been actively studied recently. However, existing works often do not explicitly consider the role of message passing in introducing or amplifying the bias. In this paper, we first investigate the problem of bias amplification in message passing. We empirically and theoretically demonstrate that message passing could amplify the bias when the 1-hop neighbors from different demographic groups are unbalanced. Guided by such analyses, we propose BeMap, a fair message passing method, that leverages a balance-aware sampling strategy to balance the number of the 1-hop neighbors of each node among different demographic groups. Extensive experiments on node classification demonstrate the efficacy of BeMap in mitigating bias while maintaining classification accuracy. The code is available at https://github.com/xiaolin-cs/BeMap.