# FROG: Fair Removal on Graphs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Graph unlearning, one of 12 directions in LLM safety and security.
- Builds on 25 of its 40 references that are in the map.
- First posted on arXiv 23 Mar 2025.

## Placed in

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

## Builds on (most cited first, 25 of 25)

- [Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks](https://mlsanity.com/paper/1911.04933/) (2019)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Model Sparsity Can Simplify Machine Unlearning](https://mlsanity.com/paper/2304.04934/) (2023)
- [Graph Condensation for Graph Neural Networks](https://mlsanity.com/paper/2110.07580/) (2021)
- [All in One: Multi-task Prompting for Graph Neural Networks](https://mlsanity.com/paper/2307.01504/) (2023)
- [Graph Unlearning](https://mlsanity.com/paper/2103.14991/) (2021)
- [Beyond Parity: Fairness Objectives for Collaborative Filtering](https://mlsanity.com/paper/1705.08804/) (2017)
- [Towards Adversarial Evaluations for Inexact Machine Unlearning](https://mlsanity.com/paper/2201.06640/) (2022)
- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [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)
- [Challenging Forgets: Unveiling the Worst-Case Forget Sets in Machine Unlearning](https://mlsanity.com/paper/2403.07362/) (2024)
- [GNNDelete: A General Strategy for Unlearning in Graph Neural Networks](https://mlsanity.com/paper/2302.13406/) (2023)
- [Federated Contrastive Learning for Volumetric Medical Image Segmentation](https://mlsanity.com/paper/2204.10983/) (2022)
- [Towards Effective and General Graph Unlearning via Mutual Evolution](https://mlsanity.com/paper/2401.11760/) (2024)
- [IDEA: A Flexible Framework of Certified Unlearning for Graph Neural Networks](https://mlsanity.com/paper/2407.19398/) (2024)
- [Unlearning Protected User Attributes in Recommendations with Adversarial Training](https://mlsanity.com/paper/2206.04500/) (2022)
- [MultiDelete for Multimodal Machine Unlearning](https://mlsanity.com/paper/2311.12047/) (2023)
- [MixupExplainer: Generalizing Explanations for Graph Neural Networks with Data Augmentation](https://mlsanity.com/paper/2307.07832/) (2023)
- [MU-Bench: A Multitask Multimodal Benchmark for Machine Unlearning](https://mlsanity.com/paper/2406.14796/) (2024)
- [Tool Unlearning for Tool-Augmented LLMs](https://mlsanity.com/paper/2502.01083/) (2025)
- [Equality of Voice: Towards Fair Representation in Crowdsourced Top-K Recommendations](https://mlsanity.com/paper/1811.08690/) (2018)
- [Unlink to Unlearn: Simplifying Edge Unlearning in GNNs](https://mlsanity.com/paper/2402.10695/) (2024)
- [Debiasing Machine Unlearning with Counterfactual Examples](https://mlsanity.com/paper/2404.15760/) (2024)

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

- [Understanding Machine Unlearning Through the Lens of Mode Connectivity](https://mlsanity.com/paper/2504.06407/) (2025)
- [Unlearning Algorithmic Biases over Graphs](https://mlsanity.com/paper/2505.14945/) (2025)
- [Treatment Response Optimized Clinical Decision Support AI System via Digital Twin Simulation](https://mlsanity.com/paper/2606.17405/) (2026)
- [Understanding Machine Unlearning Through the Lens of Mode Connectivity](https://mlsanity.com/paper/2607.23970/) (2026)

## Abstract (arXiv)

With growing emphasis on privacy regulations, machine unlearning has become increasingly critical in real-world applications such as social networks and recommender systems, many of which are naturally represented as graphs. However, existing graph unlearning methods often modify nodes or edges indiscriminately, overlooking their impact on fairness. For instance, forgetting links between users of different genders may inadvertently exacerbate group disparities. To address this issue, we propose a novel framework that jointly optimizes both the graph structure and the model to achieve fair unlearning. Our method rewires the graph by removing redundant edges that hinder forgetting while preserving fairness through targeted edge augmentation. We further introduce a worst-case evaluation mechanism to assess robustness under challenging scenarios. Experiments on real-world datasets show that our approach achieves more effective and fair unlearning than existing baselines.