# On Structural Explanation of Bias in Graph Neural Networks

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 45 references that are in the map.
- First posted on arXiv 24 Jun 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [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)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Wasserstein GAN](https://mlsanity.com/paper/1701.07875/) (2017)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [Explainability in Graph Neural Networks: A Taxonomic Survey](https://mlsanity.com/paper/2012.15445/) (2020)
- [Session-based Recommendation with Graph Neural Networks](https://mlsanity.com/paper/1811.00855/) (2018)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [XGNN: Towards Model-Level Explanations of Graph Neural Networks](https://mlsanity.com/paper/2006.02587/) (2020)
- [PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2010.05788/) (2020)
- [GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2001.06216/) (2020)
- [Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information](https://mlsanity.com/paper/2009.01454/) (2020)
- [Explainability Techniques for Graph Convolutional Networks](https://mlsanity.com/paper/1905.13686/) (2019)
- [Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking](https://mlsanity.com/paper/2010.00577/) (2020)
- [A Semi-supervised Graph Attentive Network for Financial Fraud Detection](https://mlsanity.com/paper/2003.01171/) (2020)
- [Towards a Unified Framework for Fair and Stable Graph Representation Learning](https://mlsanity.com/paper/2102.13186/) (2021)
- [EDITS: Modeling and Mitigating Data Bias for Graph Neural Networks](https://mlsanity.com/paper/2108.05233/) (2021)
- [Fairness in Graph Mining: A Survey](https://mlsanity.com/paper/2204.09888/) (2022)
- [Improving Fairness in Graph Neural Networks via Mitigating Sensitive Attribute Leakage](https://mlsanity.com/paper/2206.03426/) (2022)
- [Learning Fair Node Representations with Graph Counterfactual Fairness](https://mlsanity.com/paper/2201.03662/) (2022)
- [Graph Transformation Policy Network for Chemical Reaction Prediction](https://mlsanity.com/paper/1812.09441/) (2018)
- [Learning Individual Causal Effects from Networked Observational Data](https://mlsanity.com/paper/1906.03485/) (2019)

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

- [Interpreting Unfairness in Graph Neural Networks via Training Node Attribution](https://mlsanity.com/paper/2211.14383/) (2022)
- [CEB: Compositional Evaluation Benchmark for Fairness in Large Language Models](https://mlsanity.com/paper/2407.02408/) (2024)
- [A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions](https://mlsanity.com/paper/2308.13821/) (2023)
- [RELIANT: Fair Knowledge Distillation for Graph Neural Networks](https://mlsanity.com/paper/2301.01150/) (2023)
- [GFairHint: Improving Individual Fairness for Graph Neural Networks via Fairness Hint](https://mlsanity.com/paper/2305.15622/) (2023)
- [Adversarial Attacks on Fairness of Graph Neural Networks](https://mlsanity.com/paper/2310.13822/) (2023)
- [On Explaining Unfairness: An Overview](https://mlsanity.com/paper/2402.10762/) (2024)
- [Fair Few-shot Learning with Auxiliary Sets](https://mlsanity.com/paper/2308.14338/) (2023)
- [KGMark: A Diffusion Watermark for Knowledge Graphs](https://mlsanity.com/paper/2505.23873/) (2025)
- [Poison Once, Refuse Forever: Weaponizing Alignment for Injecting Bias in LLMs](https://mlsanity.com/paper/2508.20333/) (2025)
- [A Comparative Analysis of Bias Amplification in Graph Neural Network Approaches for Recommender Systems](https://mlsanity.com/paper/2301.07639/) (2023)
- [Vision Paper: Designing Graph Neural Networks in Compliance with the European Artificial Intelligence Act](https://mlsanity.com/paper/2410.22120/) (2024)
- [Adaptive Node Feature Selection For Graph Neural Networks](https://mlsanity.com/paper/2510.03096/) (2025)
- [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)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have shown satisfying performance in various graph analytical problems. Hence, they have become the de facto solution in a variety of decision-making scenarios. However, GNNs could yield biased results against certain demographic subgroups. Some recent works have empirically shown that the biased structure of the input network is a significant source of bias for GNNs. Nevertheless, no studies have systematically scrutinized which part of the input network structure leads to biased predictions for any given node. The low transparency on how the structure of the input network influences the bias in GNN outcome largely limits the safe adoption of GNNs in various decision-critical scenarios. In this paper, we study a novel research problem of structural explanation of bias in GNNs. Specifically, we propose a novel post-hoc explanation framework to identify two edge sets that can maximally account for the exhibited bias and maximally contribute to the fairness level of the GNN prediction for any given node, respectively. Such explanations not only provide a comprehensive understanding of bias/fairness of GNN predictions but also have practical significance in building an effective yet fair GNN model. Extensive experiments on real-world datasets validate the effectiveness of the proposed framework towards delivering effective structural explanations for the bias of GNNs. Open-source code can be found at https://github.com/yushundong/REFEREE.