Graph Attributed Unlearning via Propagation Suppression and Knowledge Dissipation

Certified Signed Graph Unlearning

Graph unlearning removes the influence of sensitive edges and nodes from trained Graph Neural Networks (GNNs) without full retraining, which is essential for privacy protection. However, existing graph unlearning methods do not account for the heterogeneity of positive and negative edges in signed graphs, thereby degrading both model utility and unlearning effectiveness when applied to widespread signed graph applications. To fill this research gap, we propose Certified Signed Graph Unlearning (CSGU), which leverages the sociological principles underlying signed graphs, providing provable privacy guarantees while maintaining model utility. Specifically, CSGU efficiently identifies minimal influenced neighborhoods via triangular structures, and then applies sociological theories to quantify edge influence. Subsequently, it performs influence-weighted parameter updates with calibrated noise injection to achieve certified privacy guarantees with minimal utility degradation. Extensive experiments across five datasets show that CSGU outperforms four competing graph unlearning methods on four GNN architectures in most settings, achieving state-of-the-art results in both utility preservation and unlearning effectiveness.

A Review on Machine Unlearning Algorithms and Privacy Protection

In recent years, machine learning algorithms are increasingly dependent on large volumes of data for their training, including personal data, while at the same time the law has strengthened the right of individuals to have such data deleted, thus creating an inherent tension. Regulations such as the General Data Protection Regulation (GDPR) oblige an organization to erase personal data on request, but deleting a record from a database is not enough. A trained model retains the influence of that record in its parameters and may still expose it, for example, through membership inference. Machine unlearning has emerged in order to remove this influence from the model itself, and it has rapidly developed into an active research area. However, existing surveys have not provided a unified, verifiability-centered account of what is required to demonstrate that unlearning has actually occurred. This review provides a unified treatment of machine unlearning, beginning with the taxonomy of exact and approximate algorithms and the trade-off between efficacy, fidelity, and efficiency that governs them. It then examines the role of unlearning in privacy protection and its dual role in security, where it serves as a defense against poisoning and backdoors but also becomes an attack surface. Particular attention is given to evaluation, because the empirical tests of the literature can measure a removal but cannot prove it. On this basis, the review examines verifiable, federated, and decentralized unlearning, including the Proof of Unlearning and zero-knowledge constructions. Taken together, the review’s findings indicate that most methods assert rather than prove removal, while verifiable unlearning in federated and decentralized environments remains a central open problem.

CUNO: Curriculum and Preference Optimization for Stable Graph Unlearning under Mass Deletion

Graph unlearning removes the influence of designated training data from a trained graph model without retraining from scratch. However, existing methods suffer a sharp drop in model utility under large deletion ratios (mass deletion), a phenomenon we refer to as catastrophic unlearning. We find that a key cause is the uniform treatment of all deleted samples, which is particularly damaging in graph learning: structural dependencies cause different nodes to play vastly different roles in the learned model, yet existing methods apply the same forgetting operation to the entire forget set. Based on this insight, we propose CUNO, a curriculum-based graph unlearning framework that removes the forget set progressively, ordering samples by their estimated unlearning difficulty across multiple stages. CUNO further employs a distribution-level negative preference optimization (NPO) objective at each curriculum stage that steers the model away from its original behavior on the current forget subset while preserving retained performance. Our theoretical analysis shows that the curriculum design is most beneficial when the forget set spans a wide range of unlearning difficulty, a condition naturally satisfied under mass deletion. Comprehensive experiments confirm that CUNO consistently mitigates catastrophic unlearning: at 20% deletion, it retains 74% of the original utility compared to 26-53% for existing methods, and maintains more than half the original utility even at 50% deletion. Our code is publicly available at https://anonymous.4open.science/r/cuno-D4FF.

Graph-Guided Selective Unlearning for Language Models: Controlling Support Routes Beyond Forget Seeds

Enterprises fine-tune language models on proprietary data that may later require removal due to privacy, contractual, or compliance obligations. Selective unlearning removes requested knowledge while preserving model utility, offering a practical alternative to full retraining, but existing methods treat the explicitly identified forget examples as the complete deletion scope. This is insufficient when target knowledge remains recoverable through paraphrases, aliases, or neighboring training examples. We propose GRAPHSU, a graph-guided controller that expands the deletion scope beyond forget seeds by constructing a weighted support-route graph, propagating deletion pressure through it, and applying graded forgetting strengths to high-risk neighbors. On the Task of Fictitious Unlearning (TOFU), a synthetic author-profile question-answering benchmark, and PISTOL, a structural-unlearning benchmark built around interconnected factual samples, with GPT-2 Medium and Llama-3.2-3B-Instruct, GRAPHSU achieves the lowest utility-feasible soft leakage across all deletion settings, reducing leakage by up to 49.5 percentage points over a matched seed-only baseline, demonstrating that effective enterprise unlearning requires controlling support routes, not just forget seeds.

A Durable Machine Unlearning Framework to Nullify Recall of Sensitive Data on Incremental Training

DECAF: De-Clustering for Adaptive Representational Unlearning

Machine unlearning, which aims to remove the influence of specific training data from a trained model, is a key requirement for privacy, accountability, and adaptive deployment. We argue that many unlearning methods are vulnerable to a simple clustering attack, which can recover class structure in an unsupervised manner, limiting their suitability for continual deployment where removal requests must be handled reliably on demand. To address this, we propose DECAF (DE-Clustering for Adaptive Forgetting), a post-hoc method that operates only on the forget set and is designed to break the cluster. DECAF combines input noise, confidence suppression, and entropy-based output diversification to disrupt the residual feature-space structure associated with forgotten data. On CIFAR-10 with ResNet-18, DECAF attains 0.10% forget-class accuracy, 79.4% retain accuracy, and an AUS of 0.88, surpassing all other baselines. In cluster-based analysis, it attains performance comparable to that of unlearning methods that use the full training set, while being significantly more efficient. Code: https://github.com/ale256/representation_unlearning.