FROG: Fair Removal on Graphs
This addresses privacy and fairness issues in graph-based applications like social networks, but it is incremental as it builds on prior unlearning methods.
The paper tackles the problem of machine unlearning on graphs, where existing methods can harm fairness, and proposes a framework that jointly optimizes graph structure and model to achieve fair unlearning, with experiments showing it outperforms baselines in effectiveness and fairness.
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.