# Unlearning Algorithmic Biases over Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Graph unlearning, one of 12 directions in LLM safety and security.
- Builds on 44 of its 65 references that are in the map.
- First posted on arXiv 20 May 2025.

## Placed in

- LLM safety and security / [Graph unlearning](https://mlsanity.com/safety/graph-unlearning/)

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://mlsanity.com/paper/2007.02923/) (2020)
- [Approximate Data Deletion from Machine Learning Models](https://mlsanity.com/paper/2002.10077/) (2020)
- [Machine Unlearning of Features and Labels](https://mlsanity.com/paper/2108.11577/) (2021)
- [Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information](https://mlsanity.com/paper/2009.01454/) (2020)
- [Graph Unlearning](https://mlsanity.com/paper/2103.14991/) (2021)
- [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)
- [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)
- [Fast Model Debias with Machine Unlearning](https://mlsanity.com/paper/2310.12560/) (2023)
- [FairDrop: Biased Edge Dropout for Enhancing Fairness in Graph Representation Learning](https://mlsanity.com/paper/2104.14210/) (2021)
- [Improving Fairness in Graph Neural Networks via Mitigating Sensitive Attribute Leakage](https://mlsanity.com/paper/2206.03426/) (2022)
- [GIF: A General Graph Unlearning Strategy via Influence Function](https://mlsanity.com/paper/2304.02835/) (2023)
- [Learning Fair Node Representations with Graph Counterfactual Fairness](https://mlsanity.com/paper/2201.03662/) (2022)
- [DeBayes: a Bayesian Method for Debiasing Network Embeddings](https://mlsanity.com/paper/2002.11442/) (2020)
- [Certified Graph Unlearning](https://mlsanity.com/paper/2206.09140/) (2022)
- [Towards Fair Classifiers Without Sensitive Attributes: Exploring Biases in Related Features](https://mlsanity.com/paper/2104.14537/) (2021)
- [GNNDelete: A General Strategy for Unlearning in Graph Neural Networks](https://mlsanity.com/paper/2302.13406/) (2023)
- [Machine Unlearning: Taxonomy, Metrics, Applications, Challenges, and Prospects](https://mlsanity.com/paper/2403.08254/) (2024)
- [Unlearning Graph Classifiers with Limited Data Resources](https://mlsanity.com/paper/2211.03216/) (2022)
- [Inductive Graph Unlearning](https://mlsanity.com/paper/2304.03093/) (2023)
- [Towards Effective and General Graph Unlearning via Mutual Evolution](https://mlsanity.com/paper/2401.11760/) (2024)
- [Fair Machine Unlearning: Data Removal while Mitigating Disparities](https://mlsanity.com/paper/2307.14754/) (2023)

## Abstract (arXiv)

The growing enforcement of the right to be forgotten regulations has propelled recent advances in certified (graph) unlearning strategies to comply with data removal requests from deployed machine learning (ML) models. Motivated by the well-documented bias amplification predicament inherent to graph data, here we take a fresh look at graph unlearning and leverage it as a bias mitigation tool. Given a pre-trained graph ML model, we develop a training-free unlearning procedure that offers certifiable bias mitigation via a single-step Newton update on the model weights. This way, we contribute a computationally lightweight alternative to the prevalent training- and optimization-based fairness enhancement approaches, with quantifiable performance guarantees. We first develop a novel fairness-aware nodal feature unlearning strategy along with refined certified unlearning bounds for this setting, whose impact extends beyond the realm of graph unlearning. We then design structural unlearning methods endowed with principled selection mechanisms over nodes and edges informed by rigorous bias analyses. Unlearning these judiciously selected elements can mitigate algorithmic biases with minimal impact on downstream utility (e.g., node classification accuracy). Experimental results over real networks corroborate the bias mitigation efficacy of our unlearning strategies, and delineate markedly favorable utility-complexity trade-offs relative to retraining from scratch using augmented graph data obtained via removals.