Benchmark reveals limits of forgetting edges in graph neural networks
Lethe: Link Inference Attacks For Evaluation of Edge Unlearning Methods
Machine Learning
Summary
Forgetting the effect of specific edges in graph-based AI models is hard and important for privacy or updates. The authors point out that current tests are incomplete and sometimes misleading. They created Lethe, a new system to fairly compare methods for erasing edges' impact in large graphs. Lethe uses tougher challenges and a new way to check how well the forgetting works by trying to guess deleted links. This helps better measure and improve edge unlearning techniques.
What this means in practice
- •For data privacy teams: Evaluate and select efficient methods to remove specific connections from graph models without full retraining, enhancing privacy controls in network data.
- •For social network platform engineers: Use Lethe’s benchmark to test and improve how quickly and accurately edges can be forgotten in user-relationship graphs for compliance with data removal requests.
Authors
Andrea D'Angelo, Francesco Gullo, Davide Mottin, Sayan Ranu, Giovanni Stilo
Abstract
Graph Unlearning (GU) aims to remove the influence of specific training data from a Graph Neural Network without retraining anew. While most methods address removal of nodes and features, Edge Unlearning (EU), aiming at forgetting edges, has recently attracted dedicated attention as a standalone problem due to the hardness of completely removing the impact of an edge in the model. Despite this, no dedicated benchmark for EU exists besides isolated evaluations on feature-rich datasets such as Cora and Citeseer where GNNs exploit node features rather than graph structure. As such, we show two systematic limitations in existing evaluations: dedicated EU methods can be slower than retraining anew, and accuracy metrics are uninformative due to the negligible impact of edge removal. To address this gap, we introduce Lethe, the first comprehensive benchmark for Edge Unlearning, featuring 15 methods and 8 datasets. Our benchmark emphasizes large graphs, introduces evaluation tasks of varying difficulty, and proposes empirical measures based on link inference attacks rather than proxy accuracy metrics. We provide a comprehensive empirical analysis, demonstrate the shortcomings of current evaluations, and release Lethe as a reproducible, extensible benchmark.