Source-linked AI summary
Graph-Guided Selective Unlearning for Language Models: Controlling Support Routes Beyond Forget Seeds
Waqas Khan, Tabinda Sarwar, Jingyue Cong, Xun Yi, Estrid He
TL;DR
Selective unlearning must remove requested knowledge from customized language models without full retraining, yet seed-only scopes can leave recovery routes through related examples. GRAPHSU expands the deletion scope with a weighted support graph and graded neighbor forgetting, achieving the lowest utility-feasible soft leakage across the evaluated benchmarks and settings, with reductions of up to 49.5 percentage points over Seed-Only. The paper concludes that reliable removal depends on controlling support routes as well as the local unlearning objective.
Problem
Seed forget sets may miss related training instances that preserve recovery routes, making deletion scope an under-addressed issue in selective unlearning.
Method
GRAPHSU constructs a weighted multi-view support graph, propagates deletion pressure from forget seeds, and applies graded forgetting strengths to high-risk neighbors before local unlearning.
Results
Across TOFU and PISTOL with GPT-2 Medium and Llama-3.2-3B-Instruct, GRAPHSU achieves the lowest utility-feasible soft leakage in all deletion settings, reducing leakage by up to 49.5 percentage points over Seed-Only.
Takeaways & Limitations
The results suggest that deletion scope, not only the unlearning loss, is a key determinant of reliable knowledge removal.
Takeaways & Limitations
Soft leakage measures recoverability under fixed recovery-route probes rather than certified representational erasure, and partial deletion is structurally constrained by the need to preserve safe answer content.
Abstract
from arXiv · showhide
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.
1 Introduction
Selective unlearning is needed to remove sensitive or obsolete information from customized language models without the cost of full retraining. GRAPHSU addresses a key gap in seed-only approaches by expanding deletion to support routes through related training instances while preserving utility.
- Approximate unlearning updates deployed models to make target knowledge unrecoverable while keeping behavior on retained data close to the original model.
- Enterprise customization creates recurring needs to remove proprietary information for privacy, regulatory, contractual, intellectual-property, and policy reasons.
- Seed-only unlearning can miss paraphrases, aliases, and semantically related training instances that still support recovery of forgotten information.
- GRAPHSU constructs a weighted support graph and propagates deletion pressure from forget seeds to influential neighbors, assigning graded forgetting strengths before local unlearning.The graph combines semantic similarity, symbolic entity/relation/tail overlap, and answer-side gradient alignment.
- GRAPHSU achieves the lowest utility-feasible soft leakage across TOFU and PISTOL deletion settings while maintaining retain perplexity below 10.
2 Methodology
GRAPHSU formulates selective unlearning as recovery-route control: it expands seed forget sets using a request-conditioned support graph, then applies graded forgetting while preserving unrelated knowledge. The method approximates an infeasible ideal support closure through multi-view graph diffusion and relevance-weighted objectives.
- Problem formulation: GRAPHSU extracts factual units from prompt–answer pairs and uses them for target specification and support-graph construction, not additional training supervision.
- Recovery-aware deletion scope: The ideal forgetting scope includes seed examples and non-seed examples whose removal would materially reduce recovery of the target facts.Exact construction is infeasible because it would require leave-one-out retraining or exact causal attribution.
- Support graph construction: GRAPHSU builds a weighted multi-view support graph combining symbolic overlap, semantic similarity, and answer-side gradient alignment to represent complementary recovery routes.The graph serves as an affinity structure for support expansion rather than a calibrated estimate of causal influence.
- Graph-guided scope approximation: Personalized diffusion propagates deletion pressure from forget seeds across stronger support edges, with restart anchoring the process to the request.The resulting score ranks request-specific support evidence and aggregates contributions over paths from the seed examples.
- Graph-guided scope approximation: The estimated support closure selects high-scoring non-seed examples or a top-B expansion, approximating the ideal scope with graph relevance as the ranking signal.Selected non-seed examples receive bounded forgetting pressure, while seed examples receive full pressure.
- Selective unlearning objective: The unlearning objective combines entropy maximization, unlikelihood, and representation repulsion for target tokens with safe-token retain loss and KL anchoring.Representation repulsion is enabled for complete and entity/instance deletion settings.
3 Experiments
Experiments evaluate GRAPHSU across two benchmarks, three deletion settings, and multiple language-model backbones using soft leakage and retention metrics. GRAPHSU consistently improves utility-feasible forgetting and route-level robustness over Seed-Only.
- Experimental settings: TOFU and PISTOL evaluate complete, entity/instance, and partial deletion with GPT-2 Medium and Llama-3.2-3B-Instruct.All methods use identical forget seeds and prompts from the same supervised fine-tuned checkpoint.
- Metrics: Soft leakage counts recovery routes whose generated continuation reaches cosine similarity 0.85 with the sensitive target.Retention is assessed with retain PPL, retain F1, ROUGE-L F1, and retain-neighbor, retain-far, and partial-retain-only panels.
- Utility-constrained results: Across both datasets and deletion settings, GRAPHSU achieves the lowest soft leakage among methods with retain PPL below 10.On TOFU complete deletion, GRU reaches lower leakage than GRAPHSU but has retain PPL 79.11, violating the utility constraint.
- Support expansion: 46.42, 41.65, and 18.33 percentage points are GRAPHSU’s TOFU reductions over Seed-Only for complete, entity/instance, and partial deletion.On PISTOL, the corresponding reductions are 49.50, 21.66, and 12.22 points.
- Partial deletion: Partial deletion remains difficult, with 81.67% leakage at retain PPL 1.91 on TOFU despite GRAPHSU’s improved frontier.The setting requires suppressing sensitive spans while preserving the remaining answer content.
- Recovery-route robustness: 36.8 percentage points is the average route-level reduction across seven recovery-route families and three deletion settings.Complete deletion averages 45.9 points with a 55.0-point maximum under relation-inversion prompts; partial deletion averages 22.6 points.
4 Related Work
Prior unlearning methods primarily improve local update objectives, while GRAPHSU addresses the complementary question of where updates should be applied. The paper positions graph-guided support expansion as compatible with these objective-level approaches.
- Existing objectives: Early and recent methods adapt gradient ascent, retain regularization, preference objectives, gradient rectification, or energy-based formulations.These approaches target known failures such as catastrophic collapse, nonsensical forget responses, and the unlearning–retention trade-off.
- GRAPHSU’s distinction: GRAPHSU is complementary because it determines the support routes, masks, and forgetting strengths targeted by an update.It addresses deletion scope rather than replacing objective-level improvements.
5 Conclusions
The paper concludes that selective unlearning should control support routes beyond explicitly identified forget seeds. GRAPHSU uses graph-guided scope expansion and achieves utility-feasible leakage reductions across the evaluated settings.
- Conclusion: GRAPHSU builds a weighted multi-view support graph, propagates seed relevance, and applies graded forgetting strengths to high-risk neighbors.The controller can be paired with existing unlearning objectives without modifying them.
- Conclusion: Up to 49.5 percentage points of leakage reduction over matched Seed-Only baselines is reported across TOFU and PISTOL.The conclusion also reports the lowest utility-feasible soft leakage in all deletion settings while maintaining low retain perplexity.
Limitations
Partial deletion is structurally constrained because sensitive spans must be removed while safe answer content is preserved. Soft leakage measures recoverability under fixed probes rather than certified representational erasure, and graph construction adds amortized offline cost.
- Partial deletion: Partial deletion requires answers containing separable sensitive and safe facts so the sensitive span can be removed without disturbing retained content.Residual leakage largely reflects this structural difficulty rather than any particular method.
- Evaluation scope: Soft leakage measures behavioral recoverability under fixed recovery-route probes, not certified representational erasure.The results therefore indicate substantially reduced target reachability rather than certified erasure.
- Operational scope: Offline fact extraction and support-graph construction incur a one-time corpus cost that is amortized across deletion requests.
Ethical Considerations
Selective unlearning can support privacy, copyright compliance, stale-information removal, and safer model maintenance, but weak evaluation can create a false sense of compliance or enable removal of safety-relevant knowledge.
- Selective unlearning supports privacy, copyright compliance, stale-information removal, and safer model maintenance.
- Weak evaluation can create a false sense of compliance, while unlearning may be misused to remove safety-relevant knowledge.
- GRAPHSU is presented as an approximate technique rather than certified erasure.
- The paper recommends pairing selective unlearning with governance, audit trails, and independent verification.
A Experiment Results on LLAMA-3.2-3B-INSTRUCT
On the larger Llama-3.2-3B-Instruct backbone, the experiments preserve the GPT-2 Medium pattern: support expansion helps most when targets remain reachable through related or entity-centered examples, while partial deletion is harder.
- Llama-3.2-3B-Instruct evaluation on TOFU tests whether graph-guided support expansion transfers beyond GPT-2 Medium.
- The larger-backbone results preserve the central pattern that expanding edit scope beyond forget seeds helps when targets remain reachable through related examples or entity-centered routes.
- Partial deletion remains more difficult because sensitive spans must be suppressed while the remainder of the answer is preserved.
- Retain perplexity is teacher-forced scoring on a frozen retain set, with answer-token NLL averaged and exponentiated once.
- The corrected DPO partial-deletion retain PPL is exp(0.03) ≈1.03, and its 96.36% soft leakage ranking is unchanged.
- The plots compare forget–retain trade-offs across three model–dataset settings, with lower-left preferred and PPL ≤10 shown as an operational guardrail rather than a universal cutoff.
- GRAPHSU is Pareto-optimal across all three deletion settings and has the lowest leakage under every PPL cap from 5 through 50.
- Without a retention cap, GRU reaches 38.13% complete-deletion leakage at retain PPL 79.11, illustrating the forgetting–retention trade-off.
D Local Fact Extraction and Error Propagation
The local-extraction study rebuilds GRAPHSU’s symbolic graph without external API calls and finds close graph agreement, improved robustness to unseen probes, and a measurable forgetting–utility trade-off.
- Local Fact Extraction: A local Qwen2.5-3B-Instruct model rebuilds the symbolic graph while holding the GPT-2 Medium experiment and deletion recipe fixed.
- Local Fact Extraction: Qwen returns valid triples for 3,942 of 4,005 QA examples, while exact-triple F1 is 15.57% for Qwen and 9.88% for GPT-4.1.
- Local Fact Extraction: The structured audit is diagnostic rather than a complete semantic gold standard because equivalent facts can decompose into different triples.
- Error Propagation: The rebuilt graphs remain close, with diffusion-score correlation ρ = 0.996 and selected-support Jaccard similarity 0.895.
- Error Propagation: At 40% corruption, diffusion retains 69 of 72 support nodes for random-active corruption and 66 of 72 for graph-critical corruption.
- Error Propagation: The perturbation results indicate that semantic and gradient views, weighted fusion, and diffusion attenuate symbolic noise rather than propagating it through the full support closure.
- Matched Evaluation: Local extraction yields 49.83% soft leakage versus 46.83% for re-verified GPT-4.1-based GRAPHSU, while avoiding external corpus transmission.
- Matched Evaluation: The local approach trades lower lexical retain utility and neighbour-retain PPL 11.54 for privacy-preserving deployment without external transmission.
H.1 Graph-construction scaling benchmark
Graph construction has linear storage and sparse-diffusion scaling for fixed degree cap, while exact cosine candidate retrieval may become the dominant bottleneck as the dataset grows.
- The benchmark evaluates graph construction and request-conditioned selection as stored GPT-2 Medium TOFU samples increase.
- The graph degree is capped at K = 30, with embeddings and symbolic processing on CPU and gradient-alignment features on GPU.
- At 4,000 samples, graph construction takes 452.36 seconds, cached artefacts occupy 7.82 MB, and warm support selection takes 4.01 seconds.
- With fixed K, stored edges scale as O(NK), making graph storage and sparse diffusion iterations linear in N.
- Exact cosine candidate retrieval is approximately quadratic in sample count and may become the dominant bottleneck.
- Full request-conditioned processing additionally includes request grounding, one- and two-hop retrieval, support scoring, and retain-safety filtering.
- Fact extraction and graph construction are one-time preprocessing costs amortised across deletion requests, while recurring graph overhead is small relative to model updating and offline route auditing.
I Additional Utility Evaluation Beyond PPL
The paper evaluates utility beyond PPL using locality-sensitive retention metrics alongside soft leakage. These measures show that GRAPHSU provides a stronger forgetting–utility balance across deletion settings, while ablation and sensitivity coverage qualify the conclusions.
- Beyond PPL: PPL alone does not fully capture retained factual behaviour, so evaluation jointly considers soft leakage, retain F1, ROUGE-L F1, far-retain F1, neighbour-retain F1, and safe-span F1.Safe-span F1 applies only to partial deletion, and PPL ≤10 is an operational guardrail rather than a universal threshold.
- Controlled comparison: GRAPHSU shows a stronger forgetting–utility balance than the controlled alternatives in all three deletion settings.This comparison evaluates forgetting together with retention rather than interpreting leakage in isolation.
- Locality-sensitive retention: 54.54 vs. 0.83 neighbour-retain F1 favors GRAPHSU over Seed-Only under partial deletion, alongside 46.17 vs. 34.69 for entity/instance deletion and 32.77 vs. 31.79 for complete deletion.These comparisons indicate preserved or improved neighbour retention relative to the seed-only scope.
- Forgetting–utility trade-off: 38.13% soft leakage from GRU under complete deletion is lower than GRAPHSU’s, but GRU’s retain PPL reaches 79.11; under partial deletion, NPO-TR has 64.97 safe-span F1 but 95.13% leakage and 10.75 retain PPL.The results illustrate why leakage must be interpreted together with retention metrics.
- Ablation and scope: The Seed-Only ablation omits graph-neighbour expansion while retaining the same local objective, and additional experiments indicate that graph-guided expansion matters.The reported archive lacks complete leave-one-view-out and fusion-weight sensitivity sweeps, and the study uses one training seed.