# Promoting Fairness in GNNs: A Characterization of Stability

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 50 references that are in the map.
- First posted on arXiv 7 Sep 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [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)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2001.06216/) (2020)
- [The Lipschitz Constant of Self-Attention](https://mlsanity.com/paper/2006.04710/) (2020)
- [Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information](https://mlsanity.com/paper/2009.01454/) (2020)
- [Compositional Fairness Constraints for Graph Embeddings](https://mlsanity.com/paper/1905.10674/) (2019)
- [iFair: Learning Individually Fair Data Representations for Algorithmic Decision Making](https://mlsanity.com/paper/1806.01059/) (2018)
- [Operationalizing Individual Fairness with Pairwise Fair Representations](https://mlsanity.com/paper/1907.01439/) (2019)
- [DeBayes: a Bayesian Method for Debiasing Network Embeddings](https://mlsanity.com/paper/2002.11442/) (2020)
- [Learning Fair Representations for Recommendation: A Graph-based Perspective](https://mlsanity.com/paper/2102.09140/) (2021)
- [Learning Graph-Level Representation for Drug Discovery](https://mlsanity.com/paper/1709.03741/) (2017)
- [Lipschitz Normalization for Self-Attention Layers with Application to Graph Neural Networks](https://mlsanity.com/paper/2103.04886/) (2021)
- [Are Defenses for Graph Neural Networks Robust?](https://mlsanity.com/paper/2301.13694/) (2023)
- [On Lipschitz Bounds of General Convolutional Neural Networks](https://mlsanity.com/paper/1808.01415/) (2018)
- [AceKG: A Large-scale Knowledge Graph for Academic Data Mining](https://mlsanity.com/paper/1807.08484/) (2018)
- [Information Obfuscation of Graph Neural Networks](https://mlsanity.com/paper/2009.13504/) (2020)
- [Graph-Enhanced Multi-Task Learning of Multi-Level Transition Dynamics for Session-based Recommendation](https://mlsanity.com/paper/2110.03996/) (2021)
- [Characterizing the Influence of Graph Elements](https://mlsanity.com/paper/2210.07441/) (2022)

## Abstract (arXiv)

The Lipschitz bound, a technique from robust statistics, can limit the maximum changes in the output concerning the input, taking into account associated irrelevant biased factors. It is an efficient and provable method for examining the output stability of machine learning models without incurring additional computation costs. Recently, Graph Neural Networks (GNNs), which operate on non-Euclidean data, have gained significant attention. However, no previous research has investigated the GNN Lipschitz bounds to shed light on stabilizing model outputs, especially when working on non-Euclidean data with inherent biases. Given the inherent biases in common graph data used for GNN training, it poses a serious challenge to constraining the GNN output perturbations induced by input biases, thereby safeguarding fairness during training. Recently, despite the Lipschitz constant's use in controlling the stability of Euclideanneural networks, the calculation of the precise Lipschitz constant remains elusive for non-Euclidean neural networks like GNNs, especially within fairness contexts. To narrow this gap, we begin with the general GNNs operating on an attributed graph, and formulate a Lipschitz bound to limit the changes in the output regarding biases associated with the input. Additionally, we theoretically analyze how the Lipschitz constant of a GNN model could constrain the output perturbations induced by biases learned from data for fairness training. We experimentally validate the Lipschitz bound's effectiveness in limiting biases of the model output. Finally, from a training dynamics perspective, we demonstrate why the theoretical Lipschitz bound can effectively guide the GNN training to better trade-off between accuracy and fairness.