We consider the problem of graph unlearning, wherein graph neural network model is trained to specified accuracy and then deployed while a sequence of requests arrives to delete graph elements (nodes, edges) from the model. As GNN models are used in real-world implementation, this problem is increasingly vital to address — for example, when a user seeks to hide their connections with others in a social graph or when relationships in a knowledge graph become irrelevant or are not true anymore.
To unlearn information from a trained GNN, its influence on both GNN model weights as well as on representations of neighbors in the graph must be deleted from the model. However, existing methods using retraining and weight modification either degrade model weights shared across all nodes or are ineffective because of strong dependency of deleted edges on their local graph neighborhood. Realizing these pitfalls, we formalize the required properties for graph unlearning in the form of Deleted Edge Consistency and Neighborhood Influence and develop GNNDelete, a model-agnostic layer-wise operator that optimize both properties for unlearning tasks.
GNNDelete updates latent representations to delete nodes and edges from the model while keeping the rest of the learned knowledge intact. Experiments on six real-world and two knowledge graphs show that GNNDelete outperforms existing graph unlearning models by up to 36.9% in AUC on link prediction tasks and 22.5% in AUC on distinguishing deleted edges from nondeleted edges. GNNDelete efficient — e.g., it takes 12.3x less time and 9.3x less space than retraining from scratch on a large knowledge graph.
Graph neural networks (GNN) are increasingly used in real-world implementations, and the underlying graphs evolve over time in most deployed GNNs. Traditional machine learning approaches often work offline, wherein a model is trained once using the full training dataset and then locked for inference with few, if any, updates to the model. In contrast, online training can update the model using new training data points as they become available. However, neither offline nor online learning can deal with data deletion — the task of removing all traces of a data point from a model without sacrificing model performance. When data needs to be deleted from a model, the model must be updated accordingly. For example, GNNs must implement privacy provisions for preserving personal privacy (e.g., California Consumer Privacy Act (CCPA) and General Data Protection Regulation (GDPR)), meaning that endowing GNNs with data deletion capability is important yet sparsely studied in the literature.
Designing graph unlearning methods is nonetheless challenging. Removing data alone is insufficient to comply with recent demands for increased data privacy because models trained on the original data may still contain information about their patterns and features. A naive approach is to delete the data and retrain a model from scratch. However, this can be prohibitively expensive, especially in large datasets.
We introduce GNNDelete, a general approach for graph unlearning. We formalize two key GNN deletion properties:
- Deleted Edge Consistency: Predicted probability for deleted edges of the unlearned model should be similar to those for nonexistent edges. The property enforces GNNDelete to unlearn information such that deleted edges masquerade as unconnected nodes.
- Neighborhood Influence: We establish a connection between graph unlearning and Granger causality to ensure that local subgraphs after deletion are not affected and thus maintain the original predictive dependencies. However, existing graph unlearning methods do not consider this essential property, meaning they do not consider local connectivity influence, leading to sub-optimal deletion.
Using both properties, we develop GNNDelete, a layer-wise deletion operator to update node representations. When receiving deletion requests, GNNDelete freezes the model and learns additional small gated weight matrices that are shared across all nodes. Unlike existing methods that attempt to retrain several small models from scratch or directly update model weights which can be inefficient and suboptimal, GNNDelete uses small learnable matrices for inference without changing GNN model weights, achieving both efficiency and scalability. To optimize GNNDelete, we specify a novel objective function that satisfies Deleted Edge Consistency and Neighborhood Influence, yielding strong overall deletion.
Publication
GNNDelete: A General Unlearning Strategy for Graph Neural Networks
Jiali Cheng, George Dasoulas, Huan He, Chirag Agarwal, Marinka Zitnik
International Conference on Learning Representations, ICLR 2023
@inproceedings{cheng2023gnndelete,
title = {GNNDelete: A General Unlearning Strategy for Graph Neural Networks},
author = {Cheng, Jiali and Dasoulas, George and He, Huan and Agarwal, Chirag and Zitnik, Marinka},
booktitle = {International Conference on Learning Representations, ICLR},
year = {2023}
}
Code
PyTorch implementation together with documentation and examples of usage is available in the GitHub repository.