Unlink to Unlearn: Simplifying Edge Unlearning in GNNs
This work addresses data privacy concerns by enabling efficient and accurate edge unlearning in GNNs, offering a practical solution for applications requiring the right to be forgotten, though it is incremental as it builds on and simplifies an existing method.
The paper tackles the problem of over-forgetting in edge unlearning for Graph Neural Networks (GNNs), where existing methods like GNNDelete remove too much information, causing performance drops. The proposed method, Unlink to Unlearn (UtU), simplifies unlearning by unlinking edges, achieving over 97.3% of a retrained model's privacy protection and 99.8% of its link prediction accuracy with constant computational cost.
As concerns over data privacy intensify, unlearning in Graph Neural Networks (GNNs) has emerged as a prominent research frontier in academia. This concept is pivotal in enforcing the \textit{right to be forgotten}, which entails the selective removal of specific data from trained GNNs upon user request. Our research focuses on edge unlearning, a process of particular relevance to real-world applications. Current state-of-the-art approaches like GNNDelete can eliminate the influence of specific edges yet suffer from \textit{over-forgetting}, which means the unlearning process inadvertently removes excessive information beyond needed, leading to a significant performance decline for remaining edges. Our analysis identifies the loss functions of GNNDelete as the primary source of over-forgetting and also suggests that loss functions may be redundant for effective edge unlearning. Building on these insights, we simplify GNNDelete to develop \textbf{Unlink to Unlearn} (UtU), a novel method that facilitates unlearning exclusively through unlinking the forget edges from graph structure. Our extensive experiments demonstrate that UtU delivers privacy protection on par with that of a retrained model while preserving high accuracy in downstream tasks, by upholding over 97.3\% of the retrained model's privacy protection capabilities and 99.8\% of its link prediction accuracy. Meanwhile, UtU requires only constant computational demands, underscoring its advantage as a highly lightweight and practical edge unlearning solution.