Graph Attributed Unlearning via Propagation Suppression and Knowledge Dissipation

Abstract

With the growing global emphasis on data privacy protection, particularly the enforcement of the “right to be forgotten” under the GDPR, effectively deleting private information from models has become an urgent challenge. Graph-structured data presents a particularly challenging unlearning scenario due to its non-Euclidean nature and strong relational dependencies, which are prevalent in real-world applications such as social and recommendation systems. To address this issue, graph unlearning has been introduced to eliminate the influence of deleted data on models while preserving their overall performance. The effectiveness of graph unlearning is typically evaluated by three key metrics: model performance, unlearning efficiency, and robustness against membership inference attacks, which together determine the overall quality of an unlearning method. Existing graph unlearning methods fall into exact and approximate regimes. Most studies focus on edge/node-level unlearning, and existing attempts at feature-level unlearning remain limited. Exact unlearning methods that adopt the SISA partition and retraining paradigm may inadvertently reintroduce the features intended to be unlearned during the aggregation phase, thereby leading to incomplete unlearning. Approximate methods, on the other hand, often incur excessive information loss in feature-level removal, which degrades predictive accuracy. Accordingly, we propose a graph unlearning framework specifically designed for feature-level unlearning, consisting of two main stages. In the first stage, we zero out the features of the unlearned nodes at each layer to block their propagation through the GNN, thereby reducing their influence on neighboring node representations. In the second stage, we induce misclassification of the unlearned nodes to progressively degrade model representations and learned knowledge associated with them, enabling more thorough feature-level unlearning. Experiments on multiple graph datasets and models demonstrate that our method achieves favorable overall unlearning performance in most settings, offering a balanced trade-off between accuracy, unlearning efficiency, and unlearning effectiveness.