Efficient Partition-Localized Unlearning for Graph Transformers

Graph unlearning aims to reduce the influence of designated training nodes from a deployed graph model without retraining from scratch. Most existing approaches are developed for message-passing GNNs, where forgetting is often realized by editing local neighborhoods or fine-tuning on affected neighbors. A Graph Transformer instead relies on shared attention over tokens, so those neighborhood-based deletion recipes do not directly carry over to its computation. We propose PLU-GT, a partition-localized unlearning method for a shared Graph Transformer. The method identifies patches touched by a forget request, remaps forgotten nodes to virtual nodes to block their participation in intra-patch attention, and optimizes a localized objective that combines affected-region supervision, replay, entropy maximization, and cloak regularization. Experiments on four real-world graphs show that PLU-GT provides a favorable utility–efficiency trade-off under a unified unlearning protocol. It remains competitive with full retraining in predictive utility while achieving several-fold speedups, and substantially reduces posterior-based membership leakage under the specified attacker.