acceptodds
Under review as a conference paper at ICLR 2027

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

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.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Machine Unlearning, Approximate Unlearning, Knowledge Graph Embedding, Relearning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_YUQTOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the problem of benign relearning in knowledge graph embedding unlearning and proposes a framework named Kernel-Anticipated Unlearning (KAU). KAU leverages tangent kernels to approximate how continued training affects forgotten facts through shared entity embeddings. It incorporates the predicted post-update scores into the forgetting objective, using sampled retained and stand-in edges to model future updates while preserving retained knowledge. The authors also introduce an evaluation protocol that measures relearning leakage relative to a retrained oracle. Experiments on two knowledge graph datasets with three embedding backbones demonstrate that KAU achieves lower relearning leakage and better retained utility than the evaluated baselines.

Critical strengths

S1. The paper addresses an important and underexplored problem of relearning in knowledge graph embeddings. The proposed evaluation protocol accounts for knowledge recovery in the retrained oracle, providing a meaningful measure of excess relearning.

S2. The proposed framework makes effective use of the structural properties of knowledge graph embeddings. The experiments cover multiple backbones and include extensive comparisons and ablation studies that support the effectiveness of the proposed method.

Critical weaknesses

W1. The evaluation does not sufficiently examine the model's ability to learn new knowledge during continued training. It remains unclear whether the improved relearning robustness comes at the cost of reduced learning plasticity.

W2. The experimental evaluation relies primarily on synthetic update scenarios and a single random deletion setting, leaving the generalizability of the proposed method to more realistic knowledge graph updates and deletion requests insufficiently explored.

Questions for authors

Q1. In Section 5.2, the evaluation focuses on the recovery of forgotten facts during continued training, while retained and test performance are mainly reported at release. Although KAU achieves lower relearning leakage, could this improvement come at the cost of reduced learning plasticity? Could the authors report the performance on newly introduced triples and retained knowledge after continued training, compared with the updated retrained oracle? This would help clarify whether KAU can selectively prevent forgotten facts from returning while preserving its ability to acquire new knowledge.

Q2. In Appendix C.3, the update configurations are constructed partly by sampling retained neighbors of the forgotten probe triples' endpoints. This creates a strong structural overlap between the update data and forgotten facts. How representative is this setting of ordinary knowledge graph updates? Would KAU maintain its advantages under updates sampled independently of the forgotten facts or constructed from naturally evolving knowledge graphs?

Q3. The experiments use a uniformly sampled forget set containing 10% of the training triples, as described in Section 5.1 and Appendix C.1. How would KAU perform under different deletion settings, such as smaller forget sets or entity-centric deletion requests? These settings may lead to different degrees of parameter sharing between forgotten and retained facts.

Q4. In Appendix D.5, Table 15 shows that the predicted and realized per-fact recovery have a relatively low Spearman correlation of 0.207, with a noticeable discrepancy between their average values. Although the authors discuss the ranking-based interpretation of the response, how consistent is this prediction quality across different backbones and update configurations? Could the authors further clarify why this approximation remains effective for optimizing the anticipated forgetting objective?

Q5. Appendix C.1 describes a sealed probe of 1,000 forgotten triples used for relearning evaluation, while Appendix C.3 states that the unlearner never sees this probe. Could the authors clarify whether these triples participate in the unlearning objective or are entirely excluded from the unlearning procedure? This distinction is important for understanding the evaluation protocol.

8 comments

Thank you for the constructive review and the clear questions. We answer them in the order of the review, and where a weakness and a question raise the same point we answer them together.

W1: "The evaluation does not sufficiently examine the model's ability to learn new knowledge during continued training. It remains unclear whether the improved relearning robustness comes at the cost of reduced learning plasticity."

Q1: "[...] Could the authors report the performance on newly introduced triples and retained knowledge after continued training, compared with the updated retrained oracle? [...]"

Response: Thank you for raising this. It is the natural question for any method that resists relearning, and the answer is that KAU's robustness does not come at the cost of plasticity. We now show this directly. We continued training on newly introduced triples only, with half of them held out, in all six dataset-backbone combinations. We then compared every model with the identically updated retrained oracle and with the original model that never unlearned (Table R1).

Table R1. Learning new facts (seven seeds). The gain is the improvement of the MRR on the new triples during the update, divided by the oracle's improvement, so that 1.00 means learning exactly as much as the oracle. Distances are differences in MRR on the new triples after the update. The last column is the leakage of the forgotten facts (Eq. 1) in the same runs.

Gain relative to the oracle: KAU / never unlearnedDistance to the oracle on new triples: KAU / GraphDPO / ZeroFisherHeld-out new triples: KAU minus oracleLeakage: KAU / GraphDPO / ZeroFisher
FB15k-237 TransE0.92 / 0.860.005 / 0.036 / 0.188-0.0050.004 / 0.015 / 0.045
FB15k-237 TransH0.91 / 0.910.005 / 0.028 / 0.183-0.0030.006 / 0.012 / 0.040
FB15k-237 RotatE0.89 / 0.880.001 / 0.013 / 0.157+0.0010.001 / 0.015 / 0.049
CoDEx-L TransE0.99 / 0.880.003 / 0.059 / 0.179+0.0050.014 / 0.032 / 0.100
CoDEx-L TransH1.11 / 0.880.009 / 0.077 / 0.258+0.0010.023 / 0.035 / 0.126
CoDEx-L RotatE1.07 / 0.940.003 / 0.047 / 0.1830.0000.003 / 0.018 / 0.135

KAU learns new facts at the oracle's rate. Its gain on the new triples is 89% to 111% of the oracle's. The original model that never unlearned gains 86% to 94% under the same update, and KAU gains at least as much as this model in all six combinations. Unlearning with KAU therefore costs no plasticity.

After learning, KAU sits at the oracle's level. Its MRR on the new triples differs from the oracle's by only 0.001 to 0.009 in every combination, which is the closest of the three methods in every seed (GraphDPO is 0.013 to 0.077 away, and ZeroFisher 0.157 to 0.258). On the held-out new triples, KAU is within 0.006 of the oracle in all six combinations. As for retained knowledge, KAU's MRR on held-out retained triples after the update is above GraphDPO's in all six combinations and in every seed. It is 0.005 to 0.017 below the oracle's, where GraphDPO is 0.023 to 0.103 below. KAU's test MRR after the update is within 0.003 of the oracle's.

KAU stays selective while it learns. In the same runs, its forgotten facts rise only 0.001 to 0.023 beyond the oracle's, against 0.012 to 0.035 for GraphDPO and 0.040 to 0.135 for ZeroFisher. This is the lowest value in all six combinations. New knowledge is acquired while the forgotten knowledge stays forgotten.

The same holds for new facts that are unrelated to the forgotten ones. When the new triples share no entity with the evaluated forgotten facts, KAU learns at 94% to 105% of the oracle's rate and again ends closest to the oracle. In this case no method relearns the forgotten facts, as the mechanism of our Introduction and Appendix D.4 predicts: recovery travels through entity embeddings that are shared with the update, and this update shares none.

One remark on the baselines: their larger raw gains do not indicate better plasticity. They start below the oracle and end far from it (GraphDPO by up to 0.077 MRR and ZeroFisher by up to 0.258), whereas KAU ends at the oracle's level. KAU is the method whose learning matches that of the retrained model. These results will be in a new appendix section of the updated draft.

W2: "The experimental evaluation relies primarily on synthetic update scenarios and a single random deletion setting [...]"

Q2: "[...] How representative is this setting of ordinary knowledge graph updates? Would KAU maintain its advantages under updates sampled independently of the forgotten facts or constructed from naturally evolving knowledge graphs?"

We answer the part of W2 on update scenarios here, together with Q2, and the part on deletion settings in comment 3, together with Q3.

Response: Yes. KAU has the lowest leakage under both kinds of update, in every setting we ran.

Updates sampled independently of the forgotten facts. Each update is a uniform sample of 10%, 25% or all of the retained graph plus held-out triples as new knowledge, at two learning rates, or two such 10% updates in sequence (five or seven configurations per setting, seven seeds), in all six settings of Table 1. Averaged over all configurations, KAU's leakage is 46%, 18%, 58%, 68%, 54% and 85% below the better baseline (Table R2), and below GraphDPO's in every seed in five settings (paired sign-flip test, p = 0.016) and in 6 of 7 seeds in the sixth. Under the worst-case rule of Table 1, KAU is again the lowest in all six settings, on CoDEx-L by 71%, 62% and 86% in every seed. On a second set of 750 forgotten facts, disjoint from the probe and used for no selection, its leakage in the same runs is 40% to 90% below the better baseline.

At comparable forgetting depth. On FB15k-237 TransE and TransH, KAU's Table 1 releases forget more deeply than GraphDPO's, and leakage grows with depth (Figure 3, Appendix D.6). We therefore gave both methods the same search of 56 release settings per backbone on one seed, selected for each the setting with the lowest worst-case graph-wide leakage in two depth bands by a rule fixed in advance, and evaluated the selected releases on 13 further seeds. KAU leaks 26% to 41% less than GraphDPO in all five comparisons (p ≤ 0.005; Table R2b), at higher retained MRR. On the second set of forgotten facts, which the selection did not use, the same KAU releases also leak less in all five comparisons (by 14% to 48%).

Table R2. Leakage under graph-wide updates at the Table 1 releases (seven seeds) as KAU / GraphDPO / ZeroFisher, with the seeds in which KAU is below GraphDPO. Worst case: the rule of Table 1. Mean: over all configurations.

Probe, worst caseProbe, meanSecond set, mean
FB15k-237 TransE0.0165 / 0.0198 / 0.0376 (5/7)0.0114 / 0.0212 / 0.0373 (7/7)0.0080 / 0.0140 / 0.0305 (7/7)
FB15k-237 TransH0.0213 / 0.0227 / 0.0399 (3/7)0.0201 / 0.0246 / 0.0391 (6/7)0.0102 / 0.0175 / 0.0289 (6/7)
FB15k-237 RotatE0.0126 / 0.0367 / 0.0213 (7/7)0.0063 / 0.0341 / 0.0150 (7/7)0.0105 / 0.0397 / 0.0174 (7/7)
CoDEx-L TransE0.0083 / 0.0290 / 0.0843 (7/7)0.0073 / 0.0224 / 0.0691 (7/7)0.0245 / 0.0449 / 0.0801 (7/7)
CoDEx-L TransH0.0162 / 0.0426 / 0.1075 (7/7)0.0168 / 0.0367 / 0.0935 (7/7)0.0143 / 0.0417 / 0.0989 (7/7)
CoDEx-L RotatE0.0096 / 0.0817 / 0.0678 (7/7)0.0086 / 0.0732 / 0.0563 (7/7)0.0081 / 0.0833 / 0.0838 (7/7)

Table R2b. FB15k-237 at comparable forgetting depth (13 seeds not used for the selection). Depth is the forgetting rate at release; leakage is the per-seed maximum over three graph-wide updates.

KAU depthGraphDPO depthLeakage, KAU / GraphDPOKAU lower by (seeds; p)
TransE68.961.50.0085 / 0.013839% (10/13; 0.004)
TransE84.077.30.0127 / 0.021340% (12/13; 0.0005)
TransH66.771.60.0125 / 0.018834% (11/13; 0.001)
TransH78.471.60.0139 / 0.018826% (12/13; 0.003)
TransH78.496.60.0139 / 0.023641% (12/13; 0.0005)

A naturally evolving knowledge graph. ICEWS05-15 is a temporal knowledge graph of dated political events. We trained on all facts observed before 2013, deleted 10% of them, and used as the update the real stream of facts that appeared afterwards, so nothing in this update is constructed by us. KAU leaks 0.0071, against 0.0135 for GraphDPO and 0.0151 for ZeroFisher. This is 47% below the better baseline, and below GraphDPO in every seed of each evaluated configuration, while KAU retains the most knowledge (a retained MRR of 0.149, with the oracle at 0.154). GraphDPO's forgetting is fully undone by the stream in 14 of its 21 runs, and KAU's in none (Table R3).

Table R3. ICEWS05-15 with TransE (seven seeds, three update configurations).

KAUGraphDPOZeroFisherOracle
Leakage, under the update where each method leaks most0.00710.01350.0151n/a
Forgetting depth at release (100 = oracle)10684113100
Retained MRR at release0.1490.1260.1230.154
Runs, out of 21, in which the forgetting is fully undone0140n/a
Test MRR after the update0.1120.1140.0900.112

Other training procedures. Under SGD, Adagrad and self-adversarial training, KAU has the lowest leakage in all seven cases that we ran.

How representative is the main protocol? Recovery flows through the entity embeddings that are shared with the update (Appendix D.4, Table 14). When an update avoids the entities of the evaluated forgotten facts, these facts do not come back for KAU or GraphDPO. In practice such sharing is the rule, since 97% to 99% of all retained edges touch an entity of some forgotten fact, so ordinary updates reach these parameters too. The updates of our main protocol concentrate on them (82% to 100% of their edges touch a probe entity, against about 55% for a uniform sample) and therefore act as a stress test. The paper also varies this protocol: the 48 configurations of Appendix D.1 change the number of new edges, the number of neighbours, the learning rate and whether random retained edges away from the probe are added, and Appendix D.2 uses an update made of never-trained edges only.

KAU's advantage is thus not specific to the update class of our protocol: it holds under graph-wide updates in all six settings, at comparable forgetting depth, and on a real temporal stream. These results will be in a new appendix section of the updated draft, and the graph-wide and ICEWS results will be reported next to Table 1.

Reviewer_1KUiOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies benign relearning of approximately unlearned knowledge graph embeddings (KGEs) under continued training that excludes the forgotten triples. It defines leakage as the increase in forget-set mean reciprocal rank (MRR) of an unlearned model beyond the increase of an identically updated model retrained without those triples. The proposed method, Kernel-Anticipated Unlearning (KAU), constructs a ridge-damped tangent-kernel response from sampled retained edges and synthetic stand-ins for previously unseen edges. Its forgetting objective uses the current and anticipated post-update scores, together with retained-score preservation and an entity-embedding norm retraction. Experiments on FB15k-237 and CoDEx-L with TransE, TransH, and RotatE report lower leakage and higher retained MRR at release than GraphDPO and ZeroFisher. The paper also presents a linearized analysis, component ablations, and comparisons with relearning-resistant objectives.

Critical strengths
  1. The paper asks whether forgotten triples stay forgotten under continued training without them. Since the retained graph can let a retrained model recover rankings, forget-set MRR alone is not conclusive. Eq. (1) subtracts the identically updated retrained oracle’s MRR increase, extending Siddiqui et al. to KGE where the oracle also recovers. Appendix D.4 further supports the shared-entity-row motivation: under the TransE update, changes to involved entity rows reproduce most of the recovery.

  2. Table 1 shows lower leakage than GraphDPO and ZeroFisher on all six dataset-backbone pairs, with higher release-time retained MRR. Fig. 3, Table 16, and Table 18 support the anticipated objective.

Critical weaknesses
  1. The spectral survival-filter analysis assumes a linearized model with signed residual and uniform ridge, while the implementation uses a one-sided residual, per-entity damping, nonlinear score evaluation, and Adam with margin-ranking and sampled negatives. Appendix A.5 notes the one-sided operator is generally nonsymmetric and can have norm >1, but the paper does not establish that the implemented gradient has the same spectral factors or that Adam follows the predicted edit-direction ordering. The linearized results may hold under their assumptions; the issue is how much they explain the method.

  2. Table 15 reports Pearson/Spearman 0.526/0.207 for the joint response on FB15k-237/TransE, with mean predicted change -0.009 vs. realized +0.159. The low Spearman correlation and single dataset-backbone setting limit support for the response approximation.

  3. Eq. (1) measures excess recovery, not the absolute post-update gap to the oracle; lower leakage need not imply a smaller gap when release-time forgetting differs. Appendix C.3 also notes probe MRR levels differ from Table 5, so release-time and leakage values cannot be combined directly. Table 14 uses one TransE configuration and one seed at peak-leakage epochs, and Table 1 lacks post-update retained/test MRR. Matched-epoch, matched-configuration forget-set MRR for each method and the updated oracle, plus post-update retained/test MRR, would allow a direct assessment.

  4. The never-trained set is formed by withholding random triples, and the local update uses incident retained edges and never-trained triples; the 48 configurations and never-trained-only update test robustness only within this class. Since KAU approximates unknown update data with sampled retained edges and stand-ins, results may not extend to graph-wide updates independent of the evaluation probe or to other continued-training procedures.

Questions for authors
  1. I suggest that the authors report response-prediction correlations for the remaining dataset-backbone combinations, with calibration and sign-agreement statistics, and show how they vary with update configuration and number of shared neighboring edges.

  2. The authors should report forget-set MRR for each unlearned model and the identically updated oracle at release and at matched update epochs on the same 500-triple report subset and update configuration, together with post-update retained and test MRR.

  3. Appendix C.1 reserves a 1,000-triple probe and says the unlearner never sees it, but Eq. (3)/Algorithm 1 optimize a forgetting loss over F. Are probe triples included in that loss? Please clarify data used for unlearning, hyperparameter selection, and evaluation, and report Table 15 correlations separately on the independent 500-triple report half if the configuration was selected on the other half.

  4. Appendix C.2 lists GraphDPO epochs {1,2,3,6,12,24,48}, but Appendix C.4 reports 26 and 96 epochs. Please clarify whether additional epochs were searched or runs extended, and give the precise definition and normalization of the two shortfalls used for selection.

13 comments
AuthorsOpenReview ↗

Response to Reviewer 1KUi (1/9)

Thank you for the careful and detailed review, and in particular for the close reading of Appendix A. We answer your points in the order of the review: W1 in comments 1 to 5 (together with Q1), W2 in comments 6 to 8 (together with Q2), and Q3 and Q4 in comment 9.

W1 (first two paragraphs): "[...] these results do not establish that the gradient of the implemented objective has the same spectral factors, or that the actual Adam update follows the ordering of edit directions predicted by the surrogate. [...] the concern is the extent to which they explain the implemented method."

You name two links between the theory and the implemented method that are not established. Comments 1 and 1 continued answer the first, and comment 2 the second.

Response: The gradient of the implemented objective is a survival filter of the same form, and we now prove this for the objective as it is implemented, with the one-sided residual, the joint response with per-entity damping, and the score evaluated at the shifted parameters. The new Proposition A.3 of the updated draft gives its spectral factors, 1/(1+μk)1/(1+\mu_k), defined below. They reduce to the factors σ/(λk+σ)\sigma/(\lambda_k+\sigma) of Proposition A.1 under its signed residual and uniform ridge, and at the released model on FB15k-237 with TransE the two filters assign the same factor to 90% of a forgotten fact's feature (comment 1, continued).

Statement. Take the objective exactly as it is implemented, where Δθ\Delta\theta is the joint response of Eq. (6) with an arbitrary per-entity damping Σ\Sigma, and the features are detached by the stop-gradient of Algorithm 1. For one draw, let A\mathcal{A} be the drawn edges whose residual in Eq. (4) is positive and Aˉ\bar{\mathcal{A}} the other drawn edges, with feature matrices ΦA\Phi_{\mathcal{A}} and ΦAˉ\Phi_{\bar{\mathcal{A}}}. Write CA=ΦA⊤ΦAC_{\mathcal{A}}=\Phi_{\mathcal{A}}^{\top}\Phi_{\mathcal{A}} and Σeff=Σ+ΦAˉ⊤ΦAˉ\Sigma_{\mathrm{eff}}=\Sigma+\Phi_{\bar{\mathcal{A}}}^{\top}\Phi_{\bar{\mathcal{A}}}, and let ϕf+\phi_f^{+} be the feature of the forgotten fact ff at θ+Δθ\theta+\Delta\theta. Then

∇θdf(θ+Δθ)=Σeff(CA+Σeff)−1ϕf+,wk⊤∇θdf(θ+Δθ)=11+μkwk⊤ϕf+,\nabla_{\theta} d_f(\theta+\Delta\theta)=\Sigma_{\mathrm{eff}}(C_{\mathcal{A}}+\Sigma_{\mathrm{eff}})^{-1}\phi_f^{+},\qquad w_k^{\top}\nabla_{\theta} d_f(\theta+\Delta\theta)=\frac{1}{1+\mu_k}w_k^{\top}\phi_f^{+},

where (μk,wk)(\mu_k,w_k) are the eigenpairs of CAwk=μkΣeffwkC_{\mathcal{A}}w_k=\mu_k\Sigma_{\mathrm{eff}}w_k and μk≥0\mu_k\ge 0. Every factor therefore lies in (0,1](0,1]: it is 1 along directions that the update does not train, and close to 0 along directions that it trains strongly. With a signed residual and a uniform ridge, μk=λk/σ\mu_k=\lambda_k/\sigma and the factor becomes σ/(λk+σ)\sigma/(\lambda_k+\sigma). As in Proposition A.1 and Theorem A.1, the statement holds for each draw of the sample, and comment 1, continued, gives the average over draws. Since Eq. (3) takes its gradient through this anticipated score (Appendix B.3), the forgetting gradient of every KAU step is this filtered feature, scaled by the loss.

The three differences in the objective that you list are all covered by the statement (the Adam update is the subject of comment 2). The one-sided residual decides which edges form the spectrum, namely those in A\mathcal{A}, while the other drawn edges only add damping. The joint response and the per-entity damping are covered because the formula holds for the joint system and for any positive Σ\Sigma, so a uniform ridge is no longer needed. Exact score evaluation is covered because no first-order expansion is used: the feature is taken at the shifted parameters.

Appendix A.5. The operator studied there is the per-entity case of the operator above. As you note, it is non-symmetric and its operator norm can exceed one. At the same time, it is similar to a symmetric matrix with eigenvalues 1/(1+μk)≤11/(1+\mu_k)\le 1, which makes it a shrinkage in the norm weighted by Σeff−1\Sigma_{\mathrm{eff}}^{-1}. The shrinkage property therefore does transfer to the one-sided residual, in this norm.

The numerical check of this statement, the average over draws and the comparison with the factors of Proposition A.1 follow in comment 1, continued.

AuthorsOpenReview ↗

Response to Reviewer 1KUi (1/9, continued)

W1 (continued): "[...] these results do not establish that the gradient of the implemented objective has the same spectral factors [...]"

Numerical check. For 304 forgotten facts of the released models, across all six dataset-backbone combinations, we compared the gradient that automatic differentiation returns for the implemented objective with the formula above. When Eq. (6) is solved to convergence, the cosine between the two is 1.0000 for every single fact. With conjugate gradient stopped after 20 steps, as in our training runs, the median cosine lies between 0.989 and 0.998 in the six combinations, and training KAU with the converged solve leaves its leakage unchanged (a difference of -0.002 with a 95% CI of [-0.006, +0.002] over seven seeds).

Table R1. Factors by group of directions on FB15k-237 with TransE. Columns 2 to 4 are for one draw (96 facts, converged solve), and the other five combinations show the same agreement. Entries are group means weighted by share, and the remaining 1% of the feature lies in smaller groups. The last column is the formula averaged over 23 further draws of the sample (three seeds, 48 of the facts), read in the groups of the first draw.

DirectionsShare of ∑k(wk⊤ϕf+)2\sum_k (w_k^{\top}\phi_f^{+})^2Predicted 1/(1+μk)1/(1+\mu_k)Measured, one drawAverage over draws
μk\mu_k near 0 (not trained by the update)73%1.00001.00000.85
μk\mu_k from 10210^2 to 10310^34%0.00190.00190.59
μk\mu_k from 10310^3 to 10410^422%0.00040.00040.34

One draw and the average over draws. For a single draw, every row of Table R1 is close to 1 or to 0. This is what the paper states for a small ridge: the gradient keeps "nearly nothing" along the drawn features (Section 4.2), and the filter tends to a projector as the ridge vanishes (Theorem A.1). KAU's ridge is small (σrel=10−3\sigma_{\mathrm{rel}}=10^{-3}), for the reason given in comment 2. Section 4.6 describes the soft weights as weights "by their surviving fraction under draws": every forgetting step takes a fresh draw (Section 4.1), and each draw leaves other directions off its span. Corollary A.3 takes this average under the assumptions of Theorem A.1, and the last column of Table R1 gives it for the implemented objective, that is, the filter of Proposition A.3 averaged over 23 further draws. A direction that one draw leaves alone is kept at 0.85 by the other draws. A direction that it removes is kept at 0.34 to 0.59, and less the more strongly the draw trains it, in each of the three seeds. The gradient of the released code, averaged over the same draws, gives 0.84, 0.61 and 0.35. On FB15k-237 with TransH and RotatE and on CoDEx-L with TransE, the same average gives 0.78 to 0.88 for the directions that a draw leaves alone and 0.33 to 0.66 for those that it removes.

How close the factors are to those of Proposition A.1. Proposition A.3 differs from Proposition A.1 in the three points that you list. We measured what each of them changes by applying both filters to the same feature in the same draw, at the released model (FB15k-237 with TransE). The per-entity damping in place of a uniform ridge changes almost nothing: the two filtered gradients have a cosine of 0.998. Exact evaluation changes the vector to which the filter is applied, ϕf+\phi_f^{+} in place of ϕf\phi_f, and leaves the factors as they are. The one-sided residual changes the factor only along the drawn edges whose score the edit has not raised. Proposition A.1 counts these edges as trained and removes their directions, whereas the implemented objective leaves them in place, for the reason given in Section 4.1 (the one-sided form blocks a shortcut). In Euclidean norm, 62% of a fact's feature is kept by both filters, 28% is removed by both, and 9% is kept by the implemented objective only (Table R1 measures its shares in the norm weighted by Σeff−1\Sigma_{\mathrm{eff}}^{-1}, which gives 73% and 26%). The two filters therefore assign the same factor to 90% of the feature, and Proposition A.3 gives the exact factor on the rest. In the other combinations the share that only the implemented objective keeps is 3% to 9%.

The full statement of Proposition A.3, its proof (a short chain-rule argument) and the complete version of Table R1 are in Appendix A of the updated draft.

AuthorsOpenReview ↗

Response to Reviewer 1KUi (2/9)

W1 (continued): "[...] or that the actual Adam update follows the ordering of edit directions predicted by the surrogate. [...]"

Response: The actual update does follow the predicted ordering. It does so in all seven seeds of all six dataset-backbone combinations, and at every update length from 2 to 40 epochs (80 epochs for TransE). Proposition A.1's parameter-free prediction, an off-span share of exactly 1, holds as well: where the features stay fixed, the off-span part of an edit survives in full.

Protocol. We ran the paper's continued training unchanged (Adam, margin-ranking loss, sampled negatives) twice with identical data, batches and negatives: once from the original model, and once from the original model plus an edit of fixed norm. The share of the edit that remains is the difference between the two end points, projected onto the edit. For every entity vv with update edges, we build five edits, one in each of five classes of directions, which Proposition A.1 orders from least to most restored: orthogonal to the features Φv\Phi_v of the actual update's edges at vv (off-span, predicted share 1), and then the four quartiles of eigen-directions of Φv⊤Φv\Phi_v^{\top}\Phi_v, from the smallest λ\lambda (Q1) to the largest (Q4). For TransH and RotatE the features are the gradients of the score that the update itself trains. The update was run for up to 80 epochs and read at several lengths.

Table R2a. Share of an equal-norm edit that remains after the paper's 20-epoch update (mean over seven seeds).

Off-spanQ1Q2Q3Q4
FB15k-237 TransE0.660.590.560.520.44
FB15k-237 TransH0.770.720.690.650.51
FB15k-237 RotatE0.610.520.470.400.29
CoDEx-L TransE0.540.430.410.370.33
CoDEx-L TransH0.540.400.370.320.27
CoDEx-L RotatE0.800.710.630.510.38

The five classes fall in the predicted order in every seed of every combination. The same holds at 2, 5, 10 and 40 epochs in all six combinations, and at 80 epochs for TransE on both datasets. After a single epoch the order is complete in 40 of the 42 runs.

Table R2b. FB15k-237 with TransE, by update length (mean over seven seeds). A coordinate of row vv is fixed-feature up to a given epoch if no update edge at vv has changed the sign of its translation error on that coordinate (Appendix A.1) at any earlier epoch of the unedited run. The definition uses no threshold.

Update length (epochs)152080
Off-span, all coordinates0.990.890.660.38
Q4, all coordinates0.960.740.440.21
Share of the off-span edit lying on fixed-feature coordinates63%32%15%6%
Off-span, fixed-feature coordinates1.001.011.031.08
Q1, fixed-feature coordinates0.990.970.940.94
Q4, fixed-feature coordinates0.970.780.530.42

The parameter-free prediction. Proposition A.1 assumes frozen features and predicts that the off-span part of an edit is kept entirely. On the fixed-feature coordinates this is what happens: the share of the off-span edit that remains is between 1.00 and 1.03 for updates of up to 20 epochs (0.98 to 1.08 on CoDEx-L), while the in-span classes are restored in the order of their eigenvalues, in all seven seeds at every length from 2 to 20 epochs on both datasets. On the other coordinates a sign changes during the update, so the features move and every class loses part of the edit. This is why the off-span class keeps 0.66 on all coordinates after 20 epochs, and the classes are still in the predicted order there.

Sizes, and why KAU's ridge is small. How much of an in-span edit the update removes depends on how long it runs: the Q4 class keeps 0.96 of itself after one epoch, 0.44 after twenty and 0.21 after eighty. The unlearner does not know this length. KAU therefore uses a small ridge, which corresponds to a long update (σrel=10−3\sigma_{\mathrm{rel}}=10^{-3}, Appendix B.9). In this regime the filter keeps the off-span part of the gradient and removes the in-span part, as Table R1 shows. Since the off-span part is the one that the update restores least at every length, this choice places the forgetting where it survives best under short and long updates alike.

KAU's own edit. The edits above are constructed, so we repeated the test on the edit that KAU actually makes on TransE, that is, the released model minus the original model. We split it with the same Φv\Phi_v into its off-span part and its two in-span halves, with smaller and larger λ\lambda. The shares that remain after the 20-epoch update are 0.65, 0.50 and 0.44 on FB15k-237, and 0.50, 0.39 and 0.32 on CoDEx-L, in the predicted order in all seven seeds on both datasets.

Reviewer_uFF6OpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper presents a study of a new topic relearning in knowledge graph embeddings. Authors propose Kernel-Anticipated Unlearning anticipated on learning, KAU in short, In which the tangent kernel is used to model how continued training change forgotten facts' score through these shared parameters. Compared to state of the art knowledge graph on learners and relearning methods, KAU reduces the strongest knowledge graph on learners leakage significantly.

Critical strengths
  1. This paper shows the first study of relearning in knowledge graph embeddings, which is interesting.
  2. This paper points out that existing knowledge graph on learning methods relearn far beyond the oracle, But the proposed method KAU stay close.
Critical weaknesses
  1. As a relearning method, how would KAU perform on the knowledge graph unlearning data sets used in previous works such as GraphDPO? It would be interesting to present such results.
  2. Is KAU can be applied to other knowledge graph embedding method series such as linear projection embeddings such as DistMult, ComplEx or graph neural network based method RGCN. CompoGCN?
Questions for authors

See the weakness section.

3 comments
AuthorsOpenReview ↗

Response to Reviewer uFF6 (1/2)

Thank you for the positive assessment of our work and for the two suggestions. Both led to new experiments, which we describe below and have included in the updated draft.

W1: "As a relearning method, how would KAU perform on the knowledge graph unlearning data sets used in previous works such as GraphDPO? It would be interesting to present such results."

Response: Thank you for this suggestion. We would first like to clarify that the two datasets of our main results, FB15k-237 and CoDEx-L, already belong to GraphDPO's benchmark, and that we follow its 10% deletion rate and its base model, TransE (Section 5.1). On these two datasets, KAU lowers GraphDPO's leakage by 51% and 59% with TransE (Table 1). To widen the coverage further, we have now added WN18RR, a third dataset of GraphDPO's benchmark. We ran it with TransE under our full protocol (48 update configurations, seven unlearning seeds), and searched the hyperparameters of all three methods on this dataset.

Table R1. WN18RR with TransE. The forgetting depth is the forgetting rate of Section 5.3, where 100 means that the evaluated facts are forgotten exactly as much as in the retrained oracle. Leakage (Eq. 1) is given for the two update configurations that we ran with seven seeds: A, with an update learning rate of 10−410^{-4}, and B, with 3×10−43\times10^{-4}. B is the configuration under which KAU and GraphDPO leak most.

KAUGraphDPOZeroFisherOracle
Forgetting depth at release83.775.194.4 (66 to 132 across seeds)100
Retained MRR at release0.6390.5490.1360.705
Leakage, update A0.05330.07280.0522n/a
Leakage, update B0.09540.09800.0465n/a
Forget MRR above the oracle's after the update, A / B0.119 / 0.1600.171 / 0.189n/an/a

KAU forgets more, retains more, and leaks no more. KAU forgets the evaluated facts more deeply than GraphDPO (a forgetting depth of 83.7 against 75.1) and keeps far more of the retained knowledge (a retained MRR of 0.639 against 0.549, with the oracle at 0.705). Even though it forgets more, its worst-case leakage is no higher than GraphDPO's (0.0954 against 0.0980), and under update A it is clearly lower, in all seven seeds. It is also lower in 45 of the 48 update configurations, and after the update its forget MRR is closer to the oracle's than GraphDPO's in every seed.

At equal forgetting depth, KAU leaks less in every comparison. A model that forgets less has less to relearn, so the fair comparison is at equal forgetting depth. We therefore built two matched pairs, one at GraphDPO's depth and one at a deeper level (Table R2). KAU leaks 12% to 40% less in all four comparisons (two pairs, each under updates A and B), and it does so in every seed. At GraphDPO's depth, for example, its leakage under update B is 0.0755 against 0.0980.

Table R2. WN18RR, the two methods at equal forgetting depth.

Forgetting depthLeakage, update A / B
KAU, stopped one forgetting epoch earlier74.20.0440 / 0.0755
GraphDPO, tuned75.10.0728 / 0.0980
KAU, tuned83.70.0533 / 0.0954
GraphDPO, trained longer89.60.0862 / 0.1226
KAU, one forgetting epoch longer90.50.0608 / 0.1081

ZeroFisher is not a usable alternative on this dataset. Its lower leakage (0.0522) comes from a release that keeps a retained MRR of only 0.136, against the oracle's 0.705, which means that most of the model's knowledge has been erased.

With WN18RR, our evaluation now covers three of the four datasets used by GraphDPO, and on each of them KAU offers the best combination of deep forgetting, retained utility and robustness to relearning. The WN18RR results are in a new appendix section of the updated draft.

W2: "Is KAU can be applied to other knowledge graph embedding method series such as linear projection embeddings such as DistMult, ComplEx or graph neural network based method RGCN. CompoGCN?"

Response: Thank you for this question. Yes, KAU applies to DistMult and ComplEx, and we now show this experimentally. KAU is not tied to translational models. As stated in Appendix B.8, it applies to any backbone that keeps one entity table and one relation table, and this includes the bilinear family. We ran KAU on FB15k-237 with ComplEx (using GraphDPO's own implementation) and with DistMult under our full protocol (48 update configurations, seven seeds), with both baselines tuned on each backbone.

Table R3. Bilinear backbones on FB15k-237. For each method we report the update configuration under which it leaks most, as in Table 1.

KAUGraphDPOZeroFisherOracle
ComplEx, leakage0.00250.02110.0694n/a
ComplEx, retained MRR at release0.3470.2700.2450.344
ComplEx, leakage with KAU at the oracle's forgetting depth (14 seeds)0.00390.0206n/an/a
DistMult, leakage0.00520.01550.0363n/a
DistMult, retained MRR at release0.2840.2510.2460.281

ComplEx. KAU's leakage is about eight times lower than GraphDPO's and 28 times lower than ZeroFisher's, and it is lower than GraphDPO's in every seed (p = 0.016). KAU leaks less than both baselines in all 48 update configurations, while its retained MRR stays at the oracle's level (0.347 against 0.344, with GraphDPO at 0.270). Its forget MRR remains below the oracle's throughout continued training, so the forgotten facts never rise above the level of a model that was retrained without them. This holds even though the baselines received a much larger hyperparameter search than KAU (149 and 94 configurations, against 14).

DistMult. KAU's leakage is three times lower than GraphDPO's and seven times lower than ZeroFisher's, again in every seed and in all 48 configurations. Here KAU and GraphDPO forget to the same depth, and KAU's retained MRR is again at the oracle's level (0.284 against 0.281, with GraphDPO at 0.251).

The advantage is not explained by forgetting depth. When KAU is released at exactly the oracle's forgetting depth on ComplEx, it still leaks five times less than GraphDPO (0.0039 against 0.0206), in each of 14 seeds.

Porting KAU to a new family takes few changes. Beyond the score function, only three choices depend on the backbone: the forgetting step size, which is selected per backbone as in the paper; the norm retraction, which we disable because a bilinear score scales with the length of the embeddings; and self-adversarial negative sampling in pretraining, which is applied identically to every method and to the oracle.

GNN-based models. KAU's closed-form response is derived for scores that depend on one embedding row per entity and per relation. In R-GCN and CompGCN the score also depends on encoder weights that are shared across entities and on whole neighbourhoods, so the response has to be extended to these shared weights. We see this as the natural next step and state this scope in the updated draft. Our leakage protocol itself applies to such models without any change.

KAU therefore covers the three main families of knowledge-graph embeddings (translational, rotational and bilinear), and its reductions against GraphDPO on the new family (88% on ComplEx and 66% on DistMult) are comparable to or larger than those of Table 1. These results will be in a new appendix section of the updated draft.

We hope that these answers and the new experiments address your concerns, and we would be glad to discuss any remaining question.

Reviewer_uFF6OpenReview ↗

After reading the feedback from authors

Thanks the authors for the detailed response. I'll keep my positive score.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response regarding the uploaded revised paper

We thank all three reviewers for their careful and constructive reviews. We have replied to each of you in your own thread, and the revised paper we have now uploaded contains everything those replies refer to.

The supplementary material includes a latexdiff PDF in which all added text is shown in blue. The numbering of the existing sections, tables and appendices is unchanged.

The revision adds:

  • a proof that the gradient of the implemented objective is the survival filter, confirmed on the released models and under the actual Adam update (Proposition A.3, Appendix D.9);
  • the validation of the response prediction on all six dataset-backbone combinations (Appendix D.10);
  • the gap to the retrained oracle, utility and learning of new facts after the update (Appendices D.11 and D.13);
  • graph-wide updates, a temporal knowledge graph, further deletion settings, WN18RR and bilinear backbones (Appendices D.12 and D.14 to D.16).

We hope the responses and the revised paper resolve the concerns raised in the reviews. We would be happy to discuss any point that remains open.

AuthorsOpenReview ↗

Rebuttal Summar

We thank Reviewers uFF6, 1KUi and YUQT for their thoughtful and constructive feedback. The reviewers recognized the paper as the first study of relearning in knowledge-graph embeddings, an important and underexplored problem (uFF6, YUQT). They also valued the evaluation against an identically updated retrained oracle as a meaningful measure of excess relearning (1KUi, YUQT), and the lower leakage of KAU compared with GraphDPO and ZeroFisher in all six dataset-backbone combinations, at higher retained utility and supported by extensive comparisons and ablations (1KUi, YUQT, uFF6).

The revision addresses the questions and concerns raised across the reviews. Broadly, the reviewers asked for stronger evidence that the theory and the response prediction describe the method as it is actually implemented and trained, and for a broader evaluation that covers the models after the update and extends to more update types, deletion settings, datasets and embedding families. The method and the claims of the paper are unchanged, and all additions are in the appendices.

Correspondence between the theory and the implemented method (1KUi).
The reviewer asked whether the linearized analysis also explains the objective as it is implemented and the optimizer that is actually used for the update. The new Proposition A.3 proves that the gradient of the implemented objective has the same filtering form as in the analysis, and we confirmed it numerically on the released models. We also verified that the actual Adam update restores edit directions in the order that the theory predicts, in every seed and on all six dataset-backbone combinations (Appendix D.9).

Generality of the response prediction and its role in the objective (1KUi, YUQT).
The reviewers asked how well the response predicts recovery beyond the single setting of the submission, and why it is sufficient for the objective. The validation now covers all six combinations and every update configuration, with a positive correlation in every seed. We further show that the response does what the objective needs from it, which is to compare candidate models. It ranks models by the forgetting they keep after the update far better than their forgetting depth does, and removing it raises leakage by more than 60% in every seed (Appendix D.10).

Gap to the retrained oracle and utility after the update (1KUi, YUQT).
The reviewers noted that lower leakage does not by itself imply that a model ends closer to the oracle, and asked for the gap and the utility after the update. We now report both for all six combinations. KAU ends closest to the oracle in every combination and in every seed, also when the methods are compared at equal forgetting depth, and its test performance stays at the oracle’s level. A substantial part of its forgetting survives the update, whereas the baselines end at or above a model that never unlearned in at least half of their runs (Appendix D.11).

Learning new knowledge after unlearning (YUQT).
The reviewer asked whether robustness to relearning reduces the ability to learn. It does not. KAU learns newly introduced facts at about the rate of the retrained oracle, and on these facts it ends closest to the oracle in every seed (Appendix D.13).

Updates and deletion settings beyond the main protocol (YUQT, 1KUi).
The reviewers asked whether the advantage depends on how our updates and forget sets are constructed. We added graph-wide updates sampled independently of the evaluated facts, the real stream of a temporal knowledge graph, and other optimizers for the update, and KAU has the lowest leakage in all of them. With smaller forget sets KAU again leaks less than GraphDPO in every seed, and under entity-centric deletion relearning essentially disappears for both methods (Appendices D.12 and D.14).

Datasets of previous work and other embedding families (uFF6).
The reviewer asked for results on the benchmarks of previous work and on other embedding families. We added WN18RR, a third dataset of GraphDPO’s benchmark, where KAU leaks less than GraphDPO at equal forgetting depth in every seed. We also added the bilinear models ComplEx and DistMult, where KAU’s reduction of leakage is comparable to or larger than on the original backbones, with retained utility at the oracle’s level (Appendices D.15 and D.16). Encoders based on graph neural networks are stated as future work.

Protocol clarifications (1KUi, YUQT).
The remaining questions concerned the probe triples and GraphDPO’s hyperparameter search. Our responses clarify that the probe triples are part of the forget set, with only their role as evaluation triples withheld from the unlearner, and describe the full search.

Taken together, the new results confirm the claims of the submission on more datasets, backbones, update types and deletion settings. We thank the reviewers for the questions that led to them.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.