When Forgotten Facts Return: Relearning-Aware Unlearning of Knowledge Graph Embeddings via Tangent Kernels

Parnian Fazel, Mohammad M Maheri, Hamed HaddadiarXiv 2026 · arXiv

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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
Figure 1: KAU’s objective (Section 4). The loss acts on each forgotten fact f’s score after a closed-form response ∆θ to a drawn edge set, pushing it to a target tf. Its gradient flows through ∆θ to the edited rows θ.

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).
Figure 2: Forget-set MRR along one update on FB15k-237 with TransE. GraphDPO and Ze- roFisher relearn far beyond the oracle; KAU stays closest.
  • 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

Abstract

Approximate unlearning answers a deletion request on a knowledge-graph embedding by editing entity embeddings instead of retraining from scratch. These embeddings keep being updated as new facts arrive. Under this ordinary continued training, forgotten facts recover more than in the exact-unlearning baseline, a model retrained without them and given the same continued training. We trace this relearning to entity embeddings shared by forgotten and new facts. To our knowledge, this is the first study of relearning in knowledge-graph embeddings. Relearning-robust methods developed for deep networks do not account for the graph structure underlying this recovery. We propose Kernel-Anticipated Unlearning (KAU), which uses the tangent kernel to model how continued training changes forgotten facts' scores through these shared parameters. KAU expresses this first-order response in closed form and differentiates through it inside the forgetting loss. The objective steers edits toward directions that continued training reverses less. We compare KAU with state-of-the-art knowledge-graph unlearners and relearning-robust methods under identical continued training, measuring leakage beyond the exact-unlearning baseline. Across three backbones, KAU reduces the strongest knowledge-graph unlearner's leakage by 46-63% on FB15k-237 and 50-82% on CoDEx-L, at higher retained utility.
BibTeX
@misc{fazel2026when,
  author = {Parnian Fazel and Mohammad M Maheri and Hamed Haddadi},
  title = {{When Forgotten Facts Return: Relearning-Aware Unlearning of Knowledge Graph Embeddings via Tangent Kernels}},
  year = {2026},
  eprint = {2610.31075},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.31075},
}
Figure