ABSTRACT:

The widespread use of Machine Learning (ML) and Artificial Intelligence (AI) has recently led to rising privacy concerns. In several documented cases, AI systems have reproduced fragments of sensitive training data, including personal information. As a result, regulations have been enacted worldwide to govern the use of these technologies (e.g., GDPR, AI Act).
One crucial tenet of these regulations is the right to be forgotten, an individual’s right to have their data removed from the training of any ML or AI model. For model holders, this obligation would require retraining the model from scratch after each unlearning request, resulting in prohibitive economic and environmental costs, particularly for large-scale models. For instance, the training of GPT-3 consumed 1,287 MWh, the equivalent of powering 120 US homes for a year. The need for approximate solutions that avoid retraining while still ensuring complete data removal has led to the emergence of the field of Machine Unlearning (MU). MU for graph-based models and databases, called Graph Unlearning (GU), has recently gained worldwide research attention, as graphs (defined as a set of nodes, connected by edges) are a natural representation for many privacy-sensitive systems, like social networks. Moreover, tabular data and images can also be transformed into graphs (e.g., using k-nearest neighbors).
However, current GU methods do not guarantee robustness against external attacks, meaning that forgotten information may still be recoverable through malicious access. This issue is particularly critical in graph settings, where a removed edge can still be reconstructed from neighboring nodes. This exposes a critical gap, as MU and GU are specifically designed with privacy preservation as a core objective.
To address this lack of robustness, this project aims to (i) develop a systematic benchmark of the methods for GU in the literature, focusing on their robustness to malicious attacks, and (ii) propose a novel method that directly addresses this criticality. We also aim to (iii) establish theoretical guarantees for robust MU and provide principled guidelines to steer future research in this direction. This research has the potential to generate broad impact across multiple domains, including privacy-preserving ML and Green AI, where avoiding model retraining can significantly lower energy consumption, as well as bioinformatics, where graph-based models are foundational to tasks such as drug discovery.