When Forgotten Facts Return: Relearning-Aware Unlearning of Knowledge Graph Embeddings via Tangent Kernels
The paper studies whether facts deleted from knowledge-graph embeddings stay deleted under ordinary continued training. It shows that standard approximate unlearners fail because entity embeddings are shared between forgotten and new facts, and proposes Kernel-Anticipated Unlearning (KAU), which uses the tangent kernel to predict and counteract this relearning inside the forgetting objective. This matters for the right to be forgotten in search, recommendation, and question-answering systems built on evolving knowledge graphs.
The paper identifies a concrete failure mode in knowledge-graph unlearning: approximate unlearners leak forgotten facts under benign continued training because entity embeddings are shared with new edges. It proposes KAU, which embeds a closed-form tangent-kernel prediction of the update $\operatorname{upd}_N(\theta)$ into the forgetting loss and differentiates through it. Experiments across TransE, TransH and RotatE on FB15k-237 and CoDEx-L show KAU cuts the best baseline's leakage by 46–82% while improving retained MRR. The contribution is both theoretically grounded and practically impactful, though the analysis relies on a first-order linearization of the update that omits Adam's per-coordinate scaling and freezes features during backprop.
The paper's central observation is sharp: when an unlearner moves an entity row to forget a fact, the ordinary update restores adjacent retained edges, and "the forgotten fact returns with them" (Section 1). By exploiting the sparsity of KG score gradients—each triple touches only three rows—the authors derive an explicit, closed-form linearized response $\Delta\theta(\theta;N)$ via the tangent kernel, then backpropagate through it inside $\mathcal{L}(\theta)$. This is a genuinely novel mechanism for persistent unlearning. The empirical protocol is also rigorous: leakage is measured against a retrained oracle given the identical update, and the ablation study shows that removing anticipation "more than doubles leakage" (Section 5.5). The survival-filter interpretation (Section 4.6) elegantly connects the method to classical spectral regularization.
KAU rests on several approximations that are acknowledged but not fully quantified. First, "The score is nonlinear in the rows and the shift is not small relative to the score's per-coordinate terms, so a first-order expansion is not a controlled approximation" (Section 4.3), yet the method freezes features during differentiation and omits second-order effects. Second, the stand-ins for never-trained edges are synthetic: "A stand-in pairs an involved entity with a relation from its retained edges and a partner entity the original model scores as plausible for that relation" (Section 4.1). This heuristic may not capture the real update distribution, and no sensitivity analysis is provided. Finally, relation rows are fixed in the response despite being shared, justified only by an appendix note that they "contribute little to recovery" (Appendix D.4).
The evidence strongly supports the main claims. KAU "attains the lowest ExRec, Leak and RER on every dataset and backbone" (Section 5.3), with reductions of 46–82% over GraphDPO and higher retained MRR. The comparisons are fair: the oracle, baselines, and KAU all receive the identical continued-training stream, and the evaluation distinguishes benign relearning from oracle recovery. The paper also tests relearning-resistant add-ons—NTK projection, SAM, and TAR—finding that "No add-on reduces leakage by more than 11%" (Section 5.4), which isolates KAU's gain as coming from the anticipated objective rather than generic regularization. A limitation is that all backbones are shallow translational models; there is no evidence that the tangent-kernel approximation remains tractable or accurate for deep GNN-based encoders.
Experimental detail is thorough: "Appendix C gives full experimental details, including the split, update fine-tuning data and 48 configurations, shared selection rule, CoDEx-L settings, and training recipes for the original and retrained models." However, the authors do not provide a code repository or release scripts, and several algorithmic details—such as the exact stand-in generation procedure and the conjugate-gradient solver for equation 6—are described only in prose and pseudocode (Algorithm 1). Without released code, an independent team would have to reimplement the Jacobian assembly and the pessimistic composition of scores, which is nontrivial and would block exact reproduction. On the plus side, the authors report timing: "A release takes 13.4 seconds on CoDEx-L with TransE, against 72.8 for GraphDPO and 240.4 for retraining" (Appendix B.10).
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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.