TL;DR
Unlearning facts in knowledge graph embeddings (KGE) is often temporary; deleted facts frequently "relearn" themselves during routine model updates. This paper introduces Kernel-Anticipated Unlearning (KAU), a method that uses Neural Tangent Kernels to predict how future training will affect forgotten facts, allowing for deletions that remain persistent even as the knowledge graph grows.
What Problem Does This Paper Address?
As knowledge graphs grow, the embeddings representing their entities and relations must be constantly updated. When a user requests the deletion of a specific fact (e.g., for privacy reasons under GDPR), retraining the entire model from scratch is computationally prohibitive. Instead, "approximate unlearning" methods edit the existing embeddings to "forget" the fact.
However, the authors identify a critical failure: benign relearning. Because entities are shared across many facts, subsequent training on new, true facts can inadvertently move entity embeddings back toward their original states, effectively "resurrecting" the deleted information. This paper is the first to study this phenomenon in KGEs and proposes a way to make unlearning robust to future updates.
Methods
The core idea behind Kernel-Anticipated Unlearning (KAU) is to anticipate the model's future response to new data and optimize the unlearning edit to survive that response.
- Tangent Kernel Modeling: The authors leverage the Neural Tangent Kernel (NTK). In KGEs, a fact's score depends on only a few parameters (the head, relation, and tail embeddings), making the tangent kernel explicit and sparse.
- Anticipated Loss: Instead of just minimizing the score of a forgotten fact at the moment of deletion, KAU minimizes an "anticipated loss"—the score the fact is predicted to have after a future update.
- Closed-Form Response: KAU uses a linearized, closed-form approximation of a future update (a ridge-damped Gauss-Newton step). This allows the unlearner to differentiate through the predicted update during the optimization process.
- Survival Filtering: The mathematical framework reveals that the update acts as a "survival filter." KAU steers the unlearning edits toward directions that future updates are least likely to reverse.
- Stochastic Update Simulation: Since the unlearner doesn't know exactly which new facts will arrive, it uses random draws of "stand-in" edges (plausible but non-existent triples) to model the distribution of potential future updates.
Datasets
The researchers evaluated KAU across three popular KGE backbones (TransE, TransH, and RotatE) using two major benchmarks:
- FB15k-237: A subset of Freebase containing 14,541 entities and 237 relations.
- CoDEx-L: A larger, more diverse dataset from Wikidata with 77,951 entities and 69 relations.
Key Insights and Ideas
- The Shared Embedding Trap: Relearning happens primarily through shared entity embeddings. When you update a model on a new fact about "Paris," you are moving the "Paris" embedding, which might accidentally restore a deleted, unrelated fact about "Paris."
- Leakage vs. Inference: The authors define "leakage" as the recovery of a forgotten fact beyond what a model retrained from scratch would naturally re-infer from the remaining graph structure.
- Soft Projection: Unlike previous "subspace" methods that try to hide edits in a null-space where they can't be seen, KAU uses a "soft" approach. It weights different directions of the embedding space by their "resistance to reversal," providing a more nuanced and effective defense.
- Efficiency: KAU is significantly faster than retraining and even faster than some other approximate unlearners like GraphDPO, making it practical for real-world systems.
Key Results
KAU consistently outperformed state-of-the-art unlearners (GraphDPO, ZeroFisher) and general relearning defenses (SAM, TAR) in terms of both persistence and utility.
- Leakage Reduction: KAU reduced the leakage of the strongest baseline by 46–63% on FB15k-237 and 50–82% on CoDEx-L.
- Persistence: As shown in the figure below, while other methods quickly relearn forgotten facts during fine-tuning, KAU stays closest to the "gold standard" (a model retrained from scratch).
- Utility Preservation: KAU maintained higher accuracy on the remaining "retained" facts compared to baselines, which often sacrifice general performance to achieve forgetting.
Limitations and Future Work
- Linearization: The method relies on a first-order (linear) approximation of the model's response. While KGE models are often shallow and well-suited for this, it might be less accurate for highly non-linear, deep architectures.
- Update Distribution: KAU assumes the unlearner knows the type of updates the model will receive (e.g., the general structure of the graph growth), even if it doesn't know the specific future facts.
- Scaling to GNNs: The current work focuses on embedding-based models. Extending this to Graph Neural Networks (GNNs), where message-passing creates more complex parameter dependencies, is a promising future direction.
Summary updated