Introduction
Once a fact has been deleted from a knowledge-graph embedding, does it stay deleted? Such embeddings rank facts, many of them about real people, for search, recommendation and question answering. When a person requests erasure or a curator retracts a false fact, the released model must stop ranking the deleted facts highly while still ranking the rest as a model retrained without them would. Retraining at every request is impractical, so knowledge-graph unlearners edit the released model instead (Liu et al., 2026; Xiao et al., 2025a;b; Xu et al., 2025). Evaluation usually stops at release, although the embeddings keep changing as the graph grows.
As new facts arrive, users keep training their embeddings on old and new true edges ([38 ] ). We call this continued training the update . The update is ordinary use: it contains no forgotten fact and requires no adversary, yet it can undo unlearning. This failure, known as benign relearning , has been observed in language and vision models ([28 , 41 , 72 , 68 , 49 ] ). In a knowledge graph, the same entity embeddings must support new learning and preserve the deletion.
Measuring this failure in a knowledge graph requires a reference that itself moves. A language model retrained without facts about fictitious authors regains none under benign fine-tuning ([72 ] ). Facts in a graph, however, predict one another ([61 ] ), so a model retrained without the forgotten facts partly recovers them by re-inferring them from the remaining graph. Only recovery beyond that can count as a failure to forget, so, following Siddiqui et al. [49 ] , we give this retrained oracle the identical update and measure the released model’s gain in forget-set mean reciprocal rank (MRR) beyond the oracle’s own ([14 ] ). We call this leakage .
Measured this way, two recent knowledge-graph unlearners, GraphDPO (Liu et al., [39 ] ) and ZeroFisher (Xiao et al., [64 ] ), leak on every tested graph and backbone. At release, GraphDPO on FB15k-237 with TransE ranks the forgotten facts nearly as low as the retrained oracle. Yet under the update it regains, beyond the oracle, about as much as it removed (Figure 2 ).
Figure 2. Forget-set MRR along one update on FB15k-237 with TransE. GraphDPO and ZeroFisher relearn far beyond the oracle; KAU stays closest.
What carries the return? Not the relation rows, which every edge of a relation shares, but the entity rows that the forgotten facts share with the update’s edges (Appendix § 10 .§ 4 ). To forget a fact, an unlearner moves its endpoints’ rows, which also raises the loss of true edges at those entities. The update repairs those edges by moving the rows back, and the forgotten fact returns with them. The retrained oracle re-infers through the same rows but has no edit to undo. If this repair undoes forgetting, each fact must be forgotten where the update will leave its rows, not only where they sit at release. Existing relearning-robust methods simulate the update, penalize a proxy, or confine the edit to a subspace ([55 , 19 , 37 , 17 , 49 , 21 , 9 , 65 ] ), but none writes in closed form how the update’s edges move a forgotten fact.
A knowledge-graph embedding makes this tractable. A fact’s score gradient touches only its three rows, so the tangent kernel (Jacot et al., [31 ] ), which couples two facts’ scores to first order, is explicit and sparse. The update’s linearized response has a closed form, known from continual-learning theory (Doan et al., [15 ] ; Bennani et al., [3 ] ) and used by Golatkar et al. [21 ] for a forgetting edit. We propose Kernel-Anticipated Unlearning (KAU), which minimizes an anticipated loss , the forgetting loss evaluated after this response (Figure 1 ). A score-preservation term keeps the retained facts near their pre-edit scores, leaving the update little to repair. In a linearized model where the update repairs every edge that it edited, the update multiplies the edit by a survival filter (§ 4.6 ). The filter keeps little of each direction that strongly moves the scores of the update’s edges, more of weaker ones, and all others. KAU’s anticipated loss is then the plain forgetting loss on the surviving edit, so its gradient favors directions the update restores least. On both FB15k-237 (Toutanova and Chen, [56 ] ) and CoDEx-L (Safavi and Koutra, [46 ] ), with each of TransE, TransH and RotatE (Bordes et al., [4 ] ; Wang et al., [60 ] ; Sun et al., [53 ] ), KAU leaks less than either unlearner and ranks the retained facts higher (Table 1 ). Our main contributions are:
Figure 1. KAU’s objective (§ 4 ). The loss acts on each forgotten fact f f f Δ θ \Delta\theta Δ θ t f t_f t f Δ θ \Delta\theta Δ θ θ \theta θ
Table 1. Relearning on FB15k-237 and CoDEx-L, with each method at its highest-leakage update configuration and peak-leakage epoch (§ 5.2 ). Means over seven unlearning seeds. Bold marks the best result, and Reduction is KAU’s relative reduction from the better baseline.
Forgotten facts return under the update. We provide, to our knowledge, the first evidence that deletions by knowledge-graph unlearners do not last under ordinary continued training. We find that the forgotten facts return beyond what a retrained model recovers, through the representations of the entities they share with the training edges.
A kernel-based framework for persistent unlearning. We introduce KAU, which anticipates how continued training restores forgotten facts through shared entity embeddings. By differentiating through a closed-form tangent-kernel response inside the forgetting objective, KAU optimizes edits for persistence after the update. Our linearized theory shows that the update acts on the edit as a classical spectral filter weighting directions by resistance to reversal, with retained-gradient projection as a limiting case.
Relearning defences on knowledge-graph embeddings. We adapt relearning defences built for deep networks to knowledge-graph embeddings and find that none closes the gap to the retrained oracle, while those added to an existing unlearner leave most of its leakage (§ 5.4 and § 5.5 ).
Related work
Knowledge-graph unlearning. GraphDPO (Liu et al., [39 ] ) updates the entity and relation tables by preferring reconstructed alternatives over forgotten facts and replaying adjacent retained edges. ZeroFisher (Xiao et al., [64 ] ) applies a Fisher-based influence update to the rows of the forgotten facts’ local neighbours. Schema (Xiao et al., [63 ] ) re-embeds the deleted entities’ neighbourhood, and MetaEU (Xu et al., [66 ] ) regenerates the forgotten entities’ rows from their relations and neighbours. Like graph neural network unlearners ([11 , 62 , 12 ] ), all four use graph structure as edit scope or a term preserving neighbours. None computes how training on those neighbours changes a forgotten fact’s score or has been evaluated for recovery under continued training. KAU edits only the entity rows at the forgotten facts’ endpoints, and its loss also acts on each fact’s score after a closed-form response to the update.
Relearning-robust methods. These methods were built for deep networks, where linking a training example to the parameters it moves is neither explicit nor cheap. Unrolled methods evaluate the forgetting loss after a simulated update ([19 , 55 , 51 ] ). Proxy methods replace the update by a cheaper quantity: sharpness ([17 ] ), weight distance ([49 ] ) or the weight spectrum ([45 ] ). Subspace methods place the edit off the retained gradients’ span to protect utility ([21 , 9 , 74 ] ), in slowly restored directions ([65 , 52 ] (Sondej and Yang 2025)), or on weights a retain-only update leaves inert ([10 ] ). In a knowledge graph no row is inert, because forgotten facts share rows with retained neighbours. Subspace methods also estimate their subspaces from retained or forget data, so they miss the update’s never-trained edges. None of these methods writes in closed form how the update’s edges move each forgotten fact. KAU does so to first order, with draws that include stand-ins for never-trained edges (§ 4.1 ). In the linearized model of § 4.6 , retained-span projection and slow-direction methods take the form of hard thresholds of the survival filter, which KAU’s gradient applies softly.
Tangent-kernel response. The tangent kernel (Jacot et al., [31 ] ) describes pretrained models’ fine-tuning (Malladi et al., [42 ] ), expresses interference between consecutive tasks in closed form ([3 , 15 , 26 ] ) and underlies a scrubbing update ([21 ] ). Unlike these works, KAU places the response to the post-edit update inside its objective and differentiates through it. Appendix E extends this comparison (Table 19 ).
Table 19. Relearning-robust unlearning methods, retained-span projection methods and unlearners for graphs, by what their objective reasons about and how they are evaluated. Update model: the update the study resists or measures, benign (no forgotten item in it) or forget-set (forgotten items in it), and whether it adapts to the method. Coupling: whether the objective relates retained to forgotten data, and through what. Data effect: whether the objective computes what training on the update’s data does to the forgotten items. Reference: whether a retrained model is the reference. Matched: whether the unlearned and the retrained model receive the same fine-tune.
Problem formulation
Knowledge-graph embeddings. A knowledge graph is a set of triples x = ( h , r , t ) x = (h,r,t) x = ( h , r , t ) V \mathcal{V} V R \mathcal{R} R e v ∈ R m \mathbf{e}_v \in\mathbb{R}^{m} e v ∈ R m v ∈ V v \in\mathcal{V} v ∈ V w r \mathbf{w}_r w r r ∈ R r \in\mathcal{R} r ∈ R d x ( θ ) d_x(\theta) d x ( θ ) d x ( θ ) = ∥ e h + w r − e t ∥ 1 d_x(\theta) = \lVert\mathbf{e}_h + \mathbf{w}_r - \mathbf{e}_t \rVert_1 d x ( θ ) = ∥ e h + w r − e t ∥ 1 e ˉ = e / ∥ e ∥ 2 \bar{\mathbf{e}} = \mathbf{e}/\lVert\mathbf{e} \rVert_2 e ˉ = e / ∥ e ∥ 2 [4 ] ). RotatE (Sun et al., [53 ] ) and TransH (Wang et al., [60 ] ) are given in Appendix § 8 .8. The score function and its row parameterization define a backbone. Each backbone is trained with a margin-ranking loss over random corruptions of each triple (Table 3 ), with margin γ \gamma γ relu ( a ) = [ a ] + = max { a , 0 } \operatorname{relu}(a) = [a]_+ = \max\{a,0\} relu ( a ) = [ a ] + = max { a , 0 }
Table 3. Hyperparameters on FB15k-237 (FB). The CoDEx-L settings are selected by the same rule (Appendix § 9 .§ 2 ) and listed in Appendix § 9 .§ 4 .
Unlearning. The unlearner receives an original model θ ∘ \theta^\circ θ ∘ D t r a i n ∖ B D_{\mathrm{train}} \setminus B D train ∖ B F ⊂ D t r a i n ∖ B \mathcal{F} \subset D_{\mathrm{train}} \setminus B F ⊂ D train ∖ B D R = D t r a i n ∖ ( B ∪ F ) D_{\mathcal{R}} = D_{\mathrm{train}} \setminus(B \cup\mathcal{F}) D R = D train ∖ ( B ∪ F ) θ u \theta_u θ u B B B θ g \theta_g θ g D R D_{\mathcal{R}} D R θ ∘ \theta^\circ θ ∘ § 9 ). The forgotten facts’ endpoints are the involved entities V F \mathcal{V}_{\mathcal{F}} V F V F \mathcal{V}_{\mathcal{F}} V F θ u − θ ∘ \theta_u - \theta^\circ θ u − θ ∘ Θ i n v \Theta_{\mathrm{inv}} Θ inv θ ∘ \theta^\circ θ ∘
The update. After release, the user continues training on true edges. The update uses the training loss under Adam (Kingma and Ba, [34 ] ) on a set N \mathcal{N} N B B B N ∩ F = ∅ \mathcal{N} \cap\mathcal{F} = \varnothing N ∩ F = ∅ upd N ( θ ) \operatorname{upd}_{\mathcal{N}}(\theta) upd N ( θ ) § 5 . The update class N \mathcal{N} N N ∼ N \mathcal{N} \sim\mathcal{N} N ∼ N B B B
Leakage and the problem. Two mean reciprocal ranks measure a model (Appendix § 9 ): the forget-MRR M R R F ( θ ) \mathrm{MRR}_{\mathcal{F}}(\theta) MRR F ( θ ) M R R R ( θ ) \mathrm{MRR}_{\mathcal{R}}(\theta) MRR R ( θ ) M R R F ( θ u ) − M R R F ( θ g ) \mathrm{MRR}_{\mathcal{F}}(\theta_u) - \mathrm{MRR}_{\mathcal{F}}(\theta_g) MRR F ( θ u ) − MRR F ( θ g )
Leak ( θ u ; N ) : = [ M R R F ( upd N ( θ u ) ) − M R R F ( θ u ) ] − [ M R R F ( upd N ( θ g ) ) − M R R F ( θ g ) ] , (1) \operatorname{Leak}(\theta_u;\mathcal{N}) := \left[\mathrm{MRR}_{\mathcal{F}}\left(\operatorname{upd}_{\mathcal{N}}(\theta_u)\right) - \mathrm{MRR}_{\mathcal{F}}(\theta_u)\right] - \left[\mathrm{MRR}_{\mathcal{F}}\left(\operatorname{upd}_{\mathcal{N}}(\theta_g)\right) - \mathrm{MRR}_{\mathcal{F}}(\theta_g)\right], \tag*{(1)} Leak ( θ u ; N ) := [ MRR F ( upd N ( θ u ) ) − MRR F ( θ u ) ] − [ MRR F ( upd N ( θ g ) ) − MRR F ( θ g ) ] , (1) in MRR points, read beside the utility M R R R ( θ u ) \mathrm{MRR}_{R}(\theta_{u}) MRR R ( θ u ) § 5 reads equation (1) along the update and adds two normalized readings. The unlearner sees neither the oracle nor the draw and cannot evaluate equation (1) , but can act on each forgotten fact’s post-update score. Its problem is to choose θ u ∈ Θ i n v \theta_{u} \in\Theta_{\mathrm{inv}} θ u ∈ Θ inv
min θ ∈ Θ i n v E N ∼ N [ 1 ∣ F ∣ ∑ f ∈ F ℓ f ( d f ( upd N ( θ ) ) ) ] + β ℓ R ( θ ) . (2) \min_{\theta\in\Theta_{\mathrm{inv}}}\ \mathbb{E}_{N\sim\mathcal{N}}\left[\frac{1}{|\mathcal{F}|}\sum_{f\in\mathcal{F}}\ell_f\left(d_f\left(\operatorname{upd}_N(\theta)\right)\right)\right]+\beta\ell_R(\theta). \tag*{(2)} θ ∈ Θ inv min E N ∼ N ∣ F ∣ 1 f ∈ F ∑ ℓ f ( d f ( upd N ( θ ) ) ) + β ℓ R ( θ ) . (2) Here ℓ f \ell_f ℓ f f f f t f t_f t f θ ∘ \theta^{\circ} θ ∘ ℓ R \ell_R ℓ R θ ∘ \theta^{\circ} θ ∘ β \beta β upd N \operatorname{upd}_N upd N § 4 replaces it by its closed-form linearized response.
Kernel-anticipated unlearning
KAU replaces upd N ( θ ) \operatorname{upd}_N(\theta) upd N ( θ ) (2) by θ + Δ θ ( θ ; N ) \theta+\Delta\theta(\theta;N) θ + Δ θ ( θ ; N ) Δ θ ( θ ; N ) \Delta\theta(\theta;N) Δ θ ( θ ; N ) N N N
L ( θ ) = E N ∼ N [ 1 ∣ F ∣ ∑ f ∈ F relu ( t f − d ~ f ) 2 ] , d ~ f = min { d f ( θ ) , d f ( θ + Δ θ ( θ ; N ) ) } . (3) \mathcal{L}(\theta)=\mathbb{E}_{N\sim\mathcal{N}}\left[\frac{1}{|\mathcal{F}|}\sum_{f\in\mathcal{F}}\operatorname{relu}\left(t_f-\widetilde{d}_f\right)^2\right],\qquad
\widetilde{d}_f=\min\left\{d_f(\theta),d_f\left(\theta+\Delta\theta(\theta;N)\right)\right\}. \tag*{(3)} L ( θ ) = E N ∼ N ∣ F ∣ 1 f ∈ F ∑ relu ( t f − d f ) 2 , d f = min { d f ( θ ) , d f ( θ + Δ θ ( θ ; N ) ) } . (3) A lower score means stronger belief, so a fact counts as forgotten only if forgotten both now and after the predicted update. We call d f ( θ + Δ θ ) d_f(\theta+\Delta\theta) d f ( θ + Δ θ ) d ~ f \widetilde{d}_f d f t f t_f t f (7) ) the target. Because Δ θ \Delta\theta Δ θ θ \theta θ § 8 .§ 3 ).
The update model and its residual
The response needs a model of which edges the update trains on and how strongly it pulls each. KAU takes the edges from a random draw and measures each pull by a residual. Since the unlearner lacks the never-trained edges the class draws from B B B N \mathcal{N} N (3) with a two-channel distribution N ^ \widehat{\mathcal{N}} N k max k_{\max} k m a x § 4.2 ). Each forgetting step, an optimizer step on equation (3) , takes a fresh draw, so its loss stochastically estimates that objective. Averaging the loss over draws, rather than applying it to the mean response, avoids underestimating it under a first-order score expansion (Lemma A.3). We use the model update, which minimizes the margin-ranking loss, as gradient descent on the drawn edges’ squared residual 1 2 ∑ i ∈ I r i 2 \frac{1}{2}\sum_{i\in\mathcal{I}}r_i^2 2 1 ∑ i ∈ I r i 2 § 4.2 ). Each residual is one-sided,
r i ( θ ) = relu ( d i ( θ ) − d i ( θ ∘ ) ) . (4) r_i(\theta)=\operatorname{relu}\left(d_i(\theta)-d_i(\theta^{\circ})\right). \tag*{(4)} r i ( θ ) = relu ( d i ( θ ) − d i ( θ ∘ ) ) . (4) An edge the edit raised above its original score d i ( θ ∘ ) d_i(\theta^{\circ}) d i ( θ ∘ ) d i ( θ ) − d i ( θ ∘ ) d_i(\theta)-d_i(\theta^{\circ}) d i ( θ ) − d i ( θ ∘ ) (3) also blocks this shortcut, since the loss vanishes only when both scores reach the target. § 4.6 still analyzes the signed residual, since it is linear in the edit under linearized scores. The modelled update also differs from the real one in which edges it pulls. It restores every raised edge, but the margin-ranking loss barely pulls an edge scored well over γ \gamma γ § 7 .9). The residual can thus ignore how far below the margin an edge lies. Scaling it by the edge’s margin-violation probability, the per-relation gate of Table 17 , leaves leakage unchanged.
Table 17. Remaining variants of KAU on FB15k-237 with TransE, in the setting of Table 16 ; the KAU row is repeated for reference. Means over three unlearning seeds.
The response in closed form
The linearized response has a sparse closed form because a triple’s score depends on only three rows. The slot feature of a triple x x x v v v ϕ x ( v ) = ∂ d x / ∂ θ v ∈ R m \phi_x^{(v)}=\partial d_x/\partial\theta_v\in\mathbb{R}^{m} ϕ x ( v ) = ∂ d x / ∂ θ v ∈ R m § 10 .§ 4 ). The full gradient ϕ x = ∇ θ d x \phi_x = \nabla_\theta d_x ϕ x = ∇ θ d x x x x K N N = Φ N Φ N ⊤ K_{NN} = \Phi_N \Phi_N^\top K N N = Φ N Φ N ⊤ Φ N \Phi_N Φ N r i = d i ( θ ) − y i r_i = d_i(\theta) - y_i r i = d i ( θ ) − y i y i = min { d i ( θ ) , d i ( θ ∘ ) } y_i = \min\{d_i(\theta), d_i(\theta^\circ)\} y i = min { d i ( θ ) , d i ( θ ∘ )}
Lemma 1 (Linearized response, Doan et al., [15 ] ; Bennani et al., [3 ] ). Freeze the features ϕ i \phi_i ϕ i θ \theta θ y i y_i y i r i = d i − y i r_i = d_i - y_i r i = d i − y i i i i r i ( θ + Δ θ ) = r i ( θ ) + ϕ i ⊤ Δ θ r_i(\theta+ \Delta\theta) = r_i(\theta) + \phi_i^\top\Delta\theta r i ( θ + Δ θ ) = r i ( θ ) + ϕ i ⊤ Δ θ σ > 0 \sigma> 0 σ > 0 Δ θ \Delta\theta Δ θ 1 2 ∑ i ∈ N r i 2 ( θ + Δ θ ) + σ 2 ∥ Δ θ ∥ 2 2 \frac{1}{2}\sum_{i\in N} r_i^2(\theta+ \Delta\theta) + \frac{\sigma}{2}\lVert\Delta\theta\rVert_2^2 2 1 ∑ i ∈ N r i 2 ( θ + Δ θ ) + 2 σ ∥ Δ θ ∥ 2 2
Δ θ ( θ ; N ) = − Φ N ⊤ ( K N N + σ I ) − 1 r N ( θ ) . (5) \Delta\theta(\theta; N) = -\Phi_N^\top(K_{NN} + \sigma I)^{-1}r_N(\theta). \tag*{(5)} Δ θ ( θ ; N ) = − Φ N ⊤ ( K N N + σ I ) − 1 r N ( θ ) . (5) The ridge σ \sigma σ T T T η ≤ 1 / λ max ( K N N ) \eta\le1/\lambda_{\max}(K_{NN}) η ≤ 1/ λ m a x ( K N N ) σ = 1 / ( η T ) \sigma= 1/(\eta T) σ = 1/ ( η T ) § 7 .12) and the features’ motion. For Lipschitz features, re-linearizing once at the shifted point changes the response only at second order in the residual (Lemma A.1). KAU recomputes the drawn features at each forgetting step and freezes them during differentiation, so the response’s gradient flows through the residual alone, without second derivatives.
KAU solves the lemma’s problem over the involved rows only, in parameter space rather than through the kernel form of equation 5. Holding every other entity row fixed assigns the whole residual of a drawn edge to its involved endpoints. Let Φ \Phi Φ Δ \Delta Δ Δ e v \Delta_{e_v} Δ e v v v v r r r 1 2 Δ ⊤ Σ Δ \frac{1}{2}\Delta^\top\Sigma\Delta 2 1 Δ ⊤ ΣΔ Σ = diag ( σ v I ) \Sigma= \operatorname{diag}(\sigma_v I) Σ = diag ( σ v I ) σ v \sigma_v σ v v v v § 7 .12). The minimizer solves the joint system,
( Φ ⊤ Φ + Σ ) Δ = − Φ ⊤ r . (6) (\Phi^\top\Phi+ \Sigma)\Delta= -\Phi^\top r. \tag*{(6)} ( Φ ⊤ Φ + Σ ) Δ = − Φ ⊤ r . (6) Zero-residual edges still enter Φ ⊤ Φ \Phi^\top\Phi Φ ⊤ Φ
The analysis uses a simpler per-entity form of equation 6, Δ e v = − A v r v \Delta_{e_v} = -A_v r_v Δ e v = − A v r v Φ ⊤ Φ \Phi^\top\Phi Φ ⊤ Φ A v = Φ v ⊤ ( Φ v Φ v ⊤ + σ v I ) − 1 A_v = \Phi_v^\top(\Phi_v\Phi_v^\top+ \sigma_v I)^{-1} A v = Φ v ⊤ ( Φ v Φ v ⊤ + σ v I ) − 1 Φ v \Phi_v Φ v v v v v v v r v r_v r v § 10 .§ 5 ). The per-entity form explains the cap k max k_{\max} k m a x § 8 .§ 1 ), the drawn features at v v v ϕ f ( v ) \phi_f^{(v)} ϕ f ( v ) λ min + \lambda_{\min}^{+} λ m i n + Φ v Φ v ⊤ \Phi_v\Phi_v^\top Φ v Φ v ⊤ v v v σ v / ( λ min + + σ v ) \sigma_v/(\lambda_{\min}^{+}+\sigma_v) σ v / ( λ m i n + + σ v ) ∥ ϕ f ( v ) ∥ 2 \lVert\phi_f^{(v)}\rVert_2 ∥ ϕ f ( v ) ∥ 2 σ v ≪ λ min + \sigma_v \ll\lambda_{\min}^{+} σ v ≪ λ m i n + v v v
The anticipated score and its target
KAU evaluates the anticipated score exactly, adding Δ e v \Delta_{e_v} Δ e v d f ( θ ) + ∑ v ϕ f ( v ) ⊤ Δ e v d_f(\theta) + \sum_v \phi_f^{(v)\top}\Delta_{e_v} d f ( θ ) + ∑ v ϕ f ( v ) ⊤ Δ e v § 7 .13). The shifted rows still come from the linearized response, so we judge the response by how well it ranks facts by recovery, not by the size it predicts. Exact evaluation ranks facts better than first-order evaluation (Appendix § 10 .§ 5 ) and lowers leakage (Table 16 ). Because the loss is one-sided, the target, not the response, sets how far each fact is pushed. It comes from the original model alone,
Table 16. KAU ablations on FB15k-237 with TransE, means over three unlearning seeds. Figure 7 gives both tables’ seed spreads. Each row changes one component. All rows, including KAU, are released within a fixed forgetting-rate band, so KAU’s values differ from Table 1 .
t f = d f ( θ ∘ ) + s relu ( q f − d f ( θ ∘ ) ) . (7) t_f = d_f(\theta^\circ) + s\ \operatorname{relu}(q_f - d_f(\theta^\circ)). \tag*{(7)} t f = d f ( θ ∘ ) + s relu ( q f − d f ( θ ∘ )) . (7) Here q f q_f q f f f f s s s
Two controls on the response
The edit can control both factors of a forgotten fact’s first-order score change under the update. Write A = Φ N ⊤ ( K N N + σ I ) − 1 A = \Phi_N^\top(K_{NN} + \sigma I)^{-1} A = Φ N ⊤ ( K N N + σ I ) − 1 r = r N ( θ ) r = r_N(\theta) r = r N ( θ ) § 4.3 ), the score of f f f
ϕ f T Δ θ ( θ ; N ) = − ϕ f T A r . (8) \phi_f^{\mathsf{T}}\Delta\theta(\theta;N)=-\phi_f^{\mathsf{T}}A r. \tag*{(8)} ϕ f T Δ θ ( θ ; N ) = − ϕ f T A r . (8) The change multiplies the residual r r r ϕ f T A \phi_f^{\mathsf{T}}A ϕ f T A A A A (2) ,
L t o t ( θ ) = L ( θ ) + β m e a n i ∈ S ( d i ( θ ) − d i ( θ ∘ ) ) 2 . (9) \mathcal{L}_{\mathrm{tot}}(\theta)=\mathcal{L}(\theta)+\beta\mathop{\mathrm{mean}}_{i\in S}\left(d_i(\theta)-d_i(\theta^\circ)\right)^2. \tag*{(9)} L tot ( θ ) = L ( θ ) + β mean i ∈ S ( d i ( θ ) − d i ( θ ∘ ) ) 2 . (9) Here S S S V F \mathcal{V}_{F} V F N N N V F \mathcal{V}_{F} V F S S S (4) and hence the known-channel response (Proposition A.2). The second control, alignment, sets how much of the residual left on the stand-ins and known edges reaches the fact. The response − A r -Ar − A r A A A L \mathcal{L} L § 4.6 ).
The full procedure
Each epoch runs a retained pass, then forgetting steps. The retained pass keeps utility by minimizing the margin-ranking loss on retained edges at V F \mathcal{V}_{F} V F (9) . Each forgetting step draws N ∼ N ^ N\sim\hat{\mathcal{N}} N ∼ N ^ (4) , solves equation (6) , scores the forgotten facts at the shifted rows and takes an Adam step on L \mathcal{L} L θ ∘ \theta^\circ θ ∘ § 8 .§ 4 ). KAU releases the checkpoint maximizing a weighted sum of the forget-MRR drop and retained MRR on their development subsets (Appendix § 8 .§ 6 ). Algorithm 1 (Appendix § 8 .7) lists one run. A release takes 13.4 seconds on CoDEx-L with TransE, against 72.8 for GraphDPO and 240.4 for retraining (Appendix § 8 .10).
What survives a linearized update
In a linearized model with the signed residual and a fixed draw’s features frozen at θ ∘ \theta^\circ θ ∘ δ = θ − θ ∘ \delta=\theta-\theta^\circ δ = θ − θ ∘ S δ S\delta S δ S = ( Φ T Φ + Σ ) − 1 Σ S=(\Phi^{\mathsf{T}}\Phi+\Sigma)^{-1}\Sigma S = ( Φ T Φ + Σ ) − 1 Σ [69 , 1 ] ) and linearized continual learning ([15 , 3 ] ). Under a uniform ridge Σ = σ I \Sigma=\sigma I Σ = σ I S S S σ / ( λ k + σ ) \sigma/(\lambda_k+\sigma) σ / ( λ k + σ ) Φ T Φ \Phi^{\mathsf{T}}\Phi Φ T Φ λ k > 0 \lambda_k>0 λ k > 0 L a n t ( δ ) = L p l a i n ( S δ ) \mathcal{L}_{\mathrm{ant}}(\delta)=\mathcal{L}_{\mathrm{plain}}(S\delta) L ant ( δ ) = L plain ( S δ ) S ϕ f S\phi_f S ϕ f λ k ≤ λ ˉ \lambda_k\leq\bar{\lambda} λ k ≤ λ ˉ λ ˉ \bar{\lambda} λ ˉ λ ˉ = 0 \bar{\lambda}=0 λ ˉ = 0 Φ δ = 0 \Phi\delta=0 Φ δ = 0 [21 , 9 , 74 ] ). The real update’s unseen edges can have features outside that span and move edits the projector keeps. Methods confining edits to slowly restored directions ([65 , 52 ] (Sondej and Yang 2025)) take the form of positive thresholds on spectra from forget or retained data. KAU instead weights directions softly, by their surviving fraction under draws whose stand-ins model unseen edges.
The filter explains why KAU composes the response into the loss rather than penalizing the predicted recovery d f ( θ ) − d f ( θ + Δ θ ) d_f(\theta)-d_f(\theta+\Delta\theta) d f ( θ ) − d f ( θ + Δ θ )
KAU freezes features at the current θ \theta θ v v v ( I − A v Φ v ) ϕ f ( v ) (I-A_v\Phi_v)\phi_f^{(v)} ( I − A v Φ v ) ϕ f ( v ) v v v § 5.5 ).
Experiments
We evaluate whether anticipating continued training improves the persistence of unlearning while preserving retained utility, against existing unlearners, relearning defences and ablations.
Experimental settings
Datasets. We evaluate graphs differing in source, size and relation sets: FB15k-237 [56 ] , from Freebase with 14,541 entities and 237 relations, and CoDEx-L [46 ] , from Wikidata with 77,951 entities and 69 relations. Let D t r a i n D_{\mathrm{train}} D train F F F D t r a i n D_{\mathrm{train}} D train B ⊂ D t r a i n B \subset D_{\mathrm{train}} B ⊂ D train D t r a i n ∖ B D_{\mathrm{train}} \setminus B D train ∖ B D R = D t r a i n ∖ ( B ∪ F ) D_R = D_{\mathrm{train}} \setminus(B \cup F) D R = D train ∖ ( B ∪ F )
Backbones and baselines. We use TransE [4 ] as the primary backbone and evaluate TransH [60 ] and RotatE [53 ] on both datasets to test whether results extend across scoring functions. Baselines are GraphDPO [39 ] , which uses preference optimization, and ZeroFisher [64 ] , which uses zeroth-order curvature information. All methods use the same deletion request and evaluation procedure. Appendix § 9 gives full experimental details and each method’s forgetting and utility at release.
Evaluation metrics
All methods and the oracle receive the same update data, excluding the deleted facts (§ 3 ). We measure three quantities relative to the oracle, which itself regains some deleted facts from the remaining graph. Leakage (Leak) is the rise of a method’s forget-set MRR beyond the oracle’s rise, equation (1) , in MRR points. Zero means the method relearns no faster than a model retrained without the deleted facts. Relative excess recovery (RER) is the leakage as a percentage of the erased knowledge, the original model’s forget-set MRR minus the oracle’s. Excess recovery (ExRec) compares the share of its own unlearning-induced drop that each model regains. It also reflects differences in forgetting depth, so Leak and RER are the primary measures. Each is read at the epoch of the method’s peak leakage. We select each method’s highest-leakage update from 48 shared configurations using the selection half of a 1,000-triple deleted-fact probe and report on the other half. M R M_R M R § 9 gives the formulas and the grid.
KAU improves robustness to relearning
Table 1 reports robustness on both datasets and three backbones under each method’s highest-leakage configuration chosen on the selection half. KAU attains the lowest ExRec, Leak and RER on every dataset and backbone. On FB15k-237, it cuts the strongest baseline’s leakage by about half on TransE and TransH and nearly two thirds on RotatE. On CoDEx-L it reduces the leakage of GraphDPO by 59% on TransE, 50% on TransH and 82% on RotatE. It keeps the retained MRR above both baselines on every backbone. The M R M_R M R § 10 .§ 2 and § 10 .§ 4 ). KAU leaves the update little to restore and places its edit where the update reaches least, so less of the deleted knowledge returns.
KAU stays closest to the oracle throughout the TransE update (Figure 2 ). Its advantage widens as forgetting deepens (Figure 3 ). Depth is the forgetting rate (FR), the forget-MRR drop at release as a percentage of the oracle’s. KAU achieves the lowest mean RER at every depth and backbone. From shallowest to deepest release, its RER rises by less than half as much as either baseline’s.
Figure 3. Relative excess recovery versus forgetting depth on FB15k-237, one update configuration per backbone. Points average three unlearning seeds. Each method is released at three depths by varying only its budget, and the release nearest each band is shown.
Relearning-resistant add-ons do not close the gap
We test whether established relearning defences close the leakage gap when added to our strongest baseline, GraphDPO, on FB15k-237. We use NTK projection [21 ] , sparsness-aware minimization (SAM) [17 ] and tamper-resistance training (TAR) [55 ] , each added to GraphDPO at its selected setting (Table 2 , Appendix § 9 .§ 5 ). NTK projection and SAM constrain edit directions using retained gradients and flatten the loss, respectively. Neither directly optimizes forgotten-fact scores after continued training. TAR simulates updates but leaks no less than SAM on TransE and TransH. No add-on reduces leakage by more than 11%, and none lowers GraphDPO’s leakage on RotatE. KAU leaks 43–61% less than the best add-on and retains more on every backbone.
Table 2 : Relearning-resistant add-ons on GraphDPO, means over three unlearning seeds. Each method uses its strongest update configuration at peak leakage, which may differ from Table 1 . Bold marks the best result, and the last row gives KAU’s reduction over the best add-on.
Table 2.
These results indicate that hardening GraphDPO’s objective does not reproduce KAU’s gains in forgetting persistence and retained utility.
The anticipated objective outperforms the tested alternatives
Ablation of KAU. We isolate how KAU’s components and approximations affect leakage and retained utility within a shared forgetting-rate band and update configuration (Table 16 in Appendix § 10 .7). Removing anticipation more than doubles leakage and causes the largest increase in excess recovery. Per-entity block solves and first-order score evaluation cause the next largest leakage increases, supporting the joint solve and exact evaluation. Removing either update channel increases leakage by roughly one third, and removing the known channel lowers retained MRR from 0.2860 to 0.2834. Using a signed residual also raises leakage. Without score preservation, leakage rises and retained MRR falls furthest, to 0.2788. Adding a retained-span projector increases leakage, consistent with the distinction between hard projection and the graded response (§ 4.6 ).
Alternative forgetting objectives. We test whether existing relearning-robust objectives can reproduce KAU’s robustness when substituted for its anticipated forgetting loss. On FB15k-237 with TransE, only the forgetting step changes, with releases in a shared forgetting-rate band (Table 18 in Appendix § 10 .7). Alternatives include retained-span projection [9 , 27 , 74 ] , SAM variants [17 ] , weight-distance regularization, connectivity-based fine-tuning and weight distortion [40 , 49 ] , TAR-style unrolling [55 ] , Booster [29 ] and NTK scrubbing [21 ] . Plain forgetting sets Δ = 0 \Delta= 0 Δ = 0 Table 16 ). KAU achieves the lowest ExRec, Leak and RER. The plain forgetting loss leaks 0.0250 forget-MRR beyond the retrained oracle, and the retained-span projection leaks 0.0158. All alternatives except weight distortion reduce leakage relative to plain forgetting, yet none matches KAU: the best alternative, SAM-GP, reaches 0.0150, against KAU’s 0.0111. TAR’s ten-step unrolling and Booster’s one-step retained-loss proxy also leave a gap. KAU evaluates forgotten-fact scores after a coupled response to sampled retained and stand-in edges. NTK scrubbing and weight distortion have the highest ExRec among the alternatives. With the surrounding procedure controlled and forgetting depth comparable, these results support the anticipated objective as a source of robustness beyond the tested regularizers and update proxies.
Table 18. Alternative objectives replacing only KAU’s forgetting step, in the setting of Table 16 . Means over three unlearning seeds.
Conclusion
We showed that existing knowledge-graph unlearners forget each fact where its entity embeddings sit at release, not where continued training will leave them. Under ordinary continued training, the deleted facts therefore return beyond what a retrained model recovers, which an audit at release cannot detect, undermining deletion requests in practice. To overcome this, we propose KAU, which predicts in closed form, through the tangent kernel, how continued training moves each forgotten fact and forgets it after that move. Our results confirm that KAU substantially reduces the relearning of forgotten facts while preserving the retained knowledge. By forgetting each fact where continued training will leave it, our approach is a promising step toward deletions that last in knowledge-graph embeddings.
Reproducibility statement
All experiments use the public benchmarks FB15k-237 and CoDEx-L with TransE, TransH and RotatE, each with a fixed-seed 10% forget split. 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. Appendices B and C.4 list all FB15k-237 unlearner hyperparameters, and Appendix B.10 gives the GPU and each method’s time per release. Proofs appear in Appendix A, with each assumption in its corresponding result statement.
Ethics statement
We ask whether a deletion request honored by an approximate unlearner survives ordinary continued training. This bears on the right to be forgotten for knowledge in embeddings when released models are edited rather than retrained. We study a standard training run that downstream users already perform on true edges with no deletion request, giving them no additional capability. We release the method to make deletions more durable. Both datasets are public benchmarks: FB15k-237 derives from Freebase and CoDEx-L from Wikidata, and both contain facts about public entities, including public figures. No personal data were collected and no human subjects were involved.
AI use statement
We used AI tools to assist with writing and presentation, including rewriting text, correcting grammar, and improving clarity, readability, and logical flow. We also used AI tools to assist in auditing mathematical proofs and exploring theoretical arguments. All AI-assisted outputs were reviewed, verified, and revised by the authors, who remain responsible for the correctness and content of the paper.
Analysis and proofs
§ 4.6 summarizes what the update does to an edit. Appendix A.1 states that analysis in full, in Proposition A.1, Corollaries A.1, A.2 and A.3, Theorem A.1 and Remark A.1. The remaining subsections prove these results and Lemma 1, and they state the supporting results that Section 4 cites.
Conventions. Throughout, v v v N N N P v ( N ) = { i ∈ N : v ∈ i } P_v(N)=\{i\in N:v\in i\} P v ( N ) = { i ∈ N : v ∈ i } v v v n v = ∣ P v ( N ) ∣ n_v=|P_v(N)| n v = ∣ P v ( N ) ∣ N N N i i i v v v ϕ i ( v ) = ∂ d i / ∂ e v ∈ R m \phi_i^{(v)}=\partial d_i/\partial e_v\in\mathbb{R}^m ϕ i ( v ) = ∂ d i / ∂ e v ∈ R m Φ v ∈ R n v × m \Phi_v\in\mathbb{R}^{n_v\times m} Φ v ∈ R n v × m ϕ i ( v ) ⊤ \phi_i^{(v)\top} ϕ i ( v ) ⊤ i ∈ P v ( N ) i\in P_v(N) i ∈ P v ( N )
ϕ i ( v ) = ( I − e ˉ v e ˉ v ⊤ ) g i ( v ) ∥ e v ∥ 2 , (10) \phi_i^{(v)}=\frac{(I-\bar e_v\bar e_v^\top)g_i^{(v)}}{\lVert e_v\rVert_2}, \tag*{(10)} ϕ i ( v ) = ∥ e v ∥ 2 ( I − e ˉ v e ˉ v ⊤ ) g i ( v ) , (10) where g i ( v ) g_i^{(v)} g i ( v ) e ˉ v \bar e_v e ˉ v g i ( v ) = ± sign ( e ˉ h + w ˉ r − e ˉ t ) g_i^{(v)}=\pm\operatorname{sign}(\bar e_h+\bar w_r-\bar e_t) g i ( v ) = ± sign ( e ˉ h + w ˉ r − e ˉ t ) e ˉ h + w ˉ r − e ˉ t \bar e_h+\bar w_r-\bar e_t e ˉ h + w ˉ r − e ˉ t g i ( v ) = ± P r sign ( P r e ˉ h + d r − P r e ˉ t ) g_i^{(v)}=\pm P_r\operatorname{sign}(P_r\bar e_h+d_r-P_r\bar e_t) g i ( v ) = ± P r sign ( P r e ˉ h + d r − P r e ˉ t ) P r P_r P r v v v e ˉ v ⊥ \bar e_v^\perp e ˉ v ⊥ e ˉ v \bar e_v e ˉ v m − 1 m-1 m − 1
Let Φ v = ∑ k ≤ ϱ λ k q k u k ⊤ \Phi_v=\sum_{k\leq\varrho}\sqrt{\lambda_k}\,q_k u_k^\top Φ v = ∑ k ≤ ϱ λ k q k u k ⊤ ϱ = rank Φ v \varrho=\operatorname{rank}\Phi_v ϱ = rank Φ v λ 1 ≥ ⋯ ≥ λ ϱ > 0 \lambda_1\geq\cdots\geq\lambda_\varrho>0 λ 1 ≥ ⋯ ≥ λ ϱ > 0 K v = Φ v Φ v ⊤ K_v=\Phi_v\Phi_v^\top K v = Φ v Φ v ⊤ q k ∈ R n v q_k\in\mathbb{R}^{n_v} q k ∈ R n v u k = Φ v ⊤ q k / λ k ∈ R m u_k=\Phi_v^\top q_k/\sqrt{\lambda_k}\in\mathbb{R}^m u k = Φ v ⊤ q k / λ k ∈ R m range ( Φ v ⊤ ) \operatorname{range}(\Phi_v^\top) range ( Φ v ⊤ ) σ v > 0 \sigma_v>0 σ v > 0
A v = Φ v ⊤ ( K v + σ v I ) − 1 = ∑ k ≤ ϱ λ k λ k + σ v u k q k ⊤ , A_v=\Phi_v^\top(K_v+\sigma_v I)^{-1}=\sum_{k\leq\varrho}\frac{\sqrt{\lambda_k}}{\lambda_k+\sigma_v}u_kq_k^\top, A v = Φ v ⊤ ( K v + σ v I ) − 1 = k ≤ ϱ ∑ λ k + σ v λ k u k q k ⊤ , P N , v ⊥ = I − A v Φ v = ∑ k ≤ ϱ σ v λ k + σ v u k u k ⊤ + Π N , v ⊥ , (11) P_{N,v}^{\perp}=I-A_v\Phi_v=\sum_{k\leq\varrho}\frac{\sigma_v}{\lambda_k+\sigma_v}u_ku_k^\top+\Pi_{N,v}^{\perp}, \tag*{(11)} P N , v ⊥ = I − A v Φ v = k ≤ ϱ ∑ λ k + σ v σ v u k u k ⊤ + Π N , v ⊥ , (11) where Π N , v = ∑ k ≤ ϱ u k u k ⊤ \Pi_{N,v}=\sum_{k\leq\varrho}u_ku_k^\top Π N , v = ∑ k ≤ ϱ u k u k ⊤ v v v Π N , v ⊥ = I − Π N , v \Pi_{N,v}^{\perp}=I-\Pi_{N,v} Π N , v ⊥ = I − Π N , v ( K v + σ v I ) − 1 (K_v+\sigma_v I)^{-1} ( K v + σ v I ) − 1 q k q_k q k 1 / ( λ k + σ v ) 1/(\lambda_k+\sigma_v) 1/ ( λ k + σ v ) range ( Φ v ) \operatorname{range}(\Phi_v) range ( Φ v ) Φ v ⊤ \Phi_v^\top Φ v ⊤ P N , v ⊥ P_{N,v}^{\perp} P N , v ⊥ { σ v / ( λ k + σ v ) } k ≤ ϱ \{\sigma_v/(\lambda_k+\sigma_v)\}_{k\leq\varrho} { σ v / ( λ k + σ v ) } k ≤ ϱ ϱ < m \varrho<m ϱ < m ϱ = 0 \varrho=0 ϱ = 0 Π N , v ⊥ \Pi_{N,v}^{\perp} Π N , v ⊥ σ v → 0 \sigma_v\to0 σ v → 0 ∥ A v ∥ o p = max k λ k / ( λ k + σ v ) ≤ 1 / ( 2 σ v ) \lVert A_v\rVert_{\mathrm{op}}=\max_k\sqrt{\lambda_k}/(\lambda_k+\sigma_v)\leq1/(2\sqrt{\sigma_v}) ∥ A v ∥ op = max k λ k / ( λ k + σ v ) ≤ 1/ ( 2 σ v ) λ / ( λ + σ ) \sqrt{\lambda}/(\lambda+\sigma) λ / ( λ + σ ) λ ≥ 0 \lambda\geq0 λ ≥ 0 λ = σ \lambda=\sigma λ = σ v v v Φ v \Phi_v Φ v Δ e v = 0 \Delta e_v=0 Δ e v = 0 P N , v ⊥ = I P_{N,v}^{\perp}=I P N , v ⊥ = I λ min + \lambda_{\min}^{+} λ m i n + ϱ ≥ 1 \varrho\geq1 ϱ ≥ 1
What survives a linearized update
This subsection gives the full statements behind § 4.6 . It shows what the update does to an edit, and what that implies for the objective of equation (3) and for subspace methods. In a linearized model the update multiplies the edit by a fixed matrix, the survival filter, and the anticipated loss is the plain forgetting loss on the filtered edit. Subspace methods confine the edit to a hard threshold of the same filter. Theorem A.1 gives the local version for the nonlinear objective, and Corollary A.3 averages it over draws.
The linearized model. Fix a draw N N N δ = θ − θ ∘ \delta=\theta-\theta^\circ δ = θ − θ ∘ Φ \Phi Φ ϕ \phi ϕ d f ( θ ∘ + δ ) = d f ( θ ∘ ) + ϕ f ⊤ δ d_f(\theta^\circ+\delta)=d_f(\theta^\circ)+\phi_f^\top\delta d f ( θ ∘ + δ ) = d f ( θ ∘ ) + ϕ f ⊤ δ r ( θ ) = Φ ( θ − θ ∘ ) r(\theta)=\Phi(\theta-\theta^\circ) r ( θ ) = Φ ( θ − θ ∘ ) Δ θ ( θ ) = − ( Φ ⊤ Φ + Σ ) − 1 Φ ⊤ r ( θ ) \Delta\theta(\theta)=-(\Phi^\top\Phi+\Sigma)^{-1}\Phi^\top r(\theta) Δ θ ( θ ) = − ( Φ ⊤ Φ + Σ ) − 1 Φ ⊤ r ( θ )
Proposition A.1 (The update filters the edit). In the linearized model, every edit δ \delta δ
θ ∘ + δ + Δ θ ( θ ∘ + δ ) = θ ∘ + S δ , S = ( Φ ⊤ Φ + Σ ) − 1 Σ , (12) \theta^\circ+\delta+\Delta\theta(\theta^\circ+\delta)=\theta^\circ+S\delta,\qquad S=(\Phi^\top\Phi+\Sigma)^{-1}\Sigma, \tag*{(12)} θ ∘ + δ + Δ θ ( θ ∘ + δ ) = θ ∘ + S δ , S = ( Φ ⊤ Φ + Σ ) − 1 Σ , (12) and θ + δ + Δ θ ( θ + δ ) = θ + Δ θ ( θ ) + S δ \theta+ \delta+ \Delta\theta(\theta+ \delta) = \theta+ \Delta\theta(\theta) + S\delta θ + δ + Δ θ ( θ + δ ) = θ + Δ θ ( θ ) + S δ θ \theta θ S δ = δ S\delta= \delta S δ = δ Φ δ = 0 \Phi\delta= 0 Φ δ = 0 Σ = σ I \Sigma= \sigma I Σ = σ I K = Φ Φ T K = \Phi\Phi^{\mathsf{T}} K = Φ Φ T
S = I − Φ T ( K + σ I ) − 1 Φ = ∑ k σ λ k + σ u k u k T + Π ⊥ , S = I - \Phi^{\mathsf{T}}(K + \sigma I)^{-1}\Phi= \sum_k \frac{\sigma}{\lambda_k + \sigma}u_k u_k^{\mathsf{T}} + \Pi^{\perp}, S = I − Φ T ( K + σ I ) − 1 Φ = k ∑ λ k + σ σ u k u k T + Π ⊥ , where ( λ k , u k ) (\lambda_k,u_k) ( λ k , u k ) Φ T Φ \Phi^{\mathsf{T}}\Phi Φ T Φ Π ⊥ \Pi^{\perp} Π ⊥ u k u_k u k σ / ( λ k + σ ) \sigma/(\lambda_k+\sigma) σ / ( λ k + σ ) T T T η ≤ 1 / λ max ( K ) \eta\le1/\lambda_{\max}(K) η ≤ 1/ λ m a x ( K ) 1 2 ∥ r ∥ 2 2 \frac{1}{2}\lVert r\rVert_2^2 2 1 ∥ r ∥ 2 2 ( I − η Φ T Φ ) T δ (I-\eta\Phi^{\mathsf{T}}\Phi)^T\delta ( I − η Φ T Φ ) T δ u k u_k u k ( 1 − η λ k ) T ≤ σ / ( λ k + σ ) (1-\eta\lambda_k)^T \le\sigma/(\lambda_k+\sigma) ( 1 − η λ k ) T ≤ σ / ( λ k + σ ) σ = 1 / ( η T ) \sigma= 1/(\eta T) σ = 1/ ( η T ) e v e_v e v δ v \delta_v δ v Δ e v = − A v r v \Delta e_v = -A_v r_v Δ e v = − A v r v § 4.2 obeys the same identities with the per-entity filter P N , v = I − Φ v T ( Φ v Φ v T + σ v I ) − 1 Φ v P_{N,v} = I - \Phi_v^{\mathsf{T}}(\Phi_v\Phi_v^{\mathsf{T}}+\sigma_v I)^{-1}\Phi_v P N , v = I − Φ v T ( Φ v Φ v T + σ v I ) − 1 Φ v S S S δ v \delta_v δ v δ \delta δ Φ v ≠ 0 \Phi_v \ne0 Φ v = 0 δ v ∈ range ( Φ v T ) \delta_v \in\operatorname{range}(\Phi_v^{\mathsf{T}}) δ v ∈ range ( Φ v T ) e v e_v e v ∥ P N , v δ v ∥ 2 ≤ σ v / ( λ min + σ v ) ∥ δ v ∥ 2 \lVert P_{N,v}\delta_v\rVert_2 \le\sigma_v/(\lambda_{\min}+\sigma_v)\lVert\delta_v\rVert_2 ∥ P N , v δ v ∥ 2 ≤ σ v / ( λ m i n + σ v ) ∥ δ v ∥ 2 λ min \lambda_{\min} λ m i n Φ v Φ v T \Phi_v\Phi_v^{\mathsf{T}} Φ v Φ v T
An update of finite length restores the directions in which its features are large and leaves the rest of the edit in place. The spectral form is the classical spectral filter of ridge and early-stopped least squares [69 , 1 ] (Remark A.2). It is also the operator that governs interference between tasks in linearized continual learning [15 , 3 ] . With the Gauss–Newton Hessian Φ T Φ \Phi^{\mathsf{T}}\Phi Φ T Φ [44 ] . Li et al. [37 ] use its full-Hessian form at a simulated fine-tune’s end point to differentiate a forgetting loss, whereas KAU’s response is the closed-form proximal point of the linearized squared residual. The proposition records that filter for the edit. What is new is its use in Corollaries A.1 and A.2. Because the signed residual vanishes at the original model, the anticipated loss is the plain loss on the filtered edit, and confinement to a subspace is its hard threshold. The identity of equation 12 and the identity of Corollary A.1 hold for every positive diagonal Σ \Sigma Σ S S S
The objective acts on the surviving edit. The next corollary shows that anticipating the update amounts to applying the plain loss to the surviving edit. Write L a n t ( δ ) \mathcal{L}_{\mathrm{ant}}(\delta) L ant ( δ ) N N N
Corollary A.1 (The objective acts on the surviving edit). In the linearized model the anticipated score of a forgotten fact is d f ( θ ∘ ) + ϕ f T S δ d_f(\theta^\circ) + \phi_f^{\mathsf{T}}S\delta d f ( θ ∘ ) + ϕ f T S δ
L a n t ( δ ) = L p l a i n ( S δ ) , L p l a i n ( δ ) = 1 ∣ F ∣ ∑ f ∈ F relu ( t f − d f ( θ ∘ ) − ϕ f T δ ) 2 , \mathcal{L}_{\mathrm{ant}}(\delta) = \mathcal{L}_{\mathrm{plain}}(S\delta), \qquad\mathcal{L}_{\mathrm{plain}}(\delta) = \frac{1}{|\mathcal{F}|}\sum_{f\in\mathcal{F}}\operatorname{relu}\left(t_f-d_f(\theta^\circ)-\phi_f^{\mathsf{T}}\delta\right)^2, L ant ( δ ) = L plain ( S δ ) , L plain ( δ ) = ∣ F ∣ 1 f ∈ F ∑ relu ( t f − d f ( θ ∘ ) − ϕ f T δ ) 2 , where L p l a i n \mathcal{L}_{\mathrm{plain}} L plain f f f max { ℓ f ( δ ) , ℓ f ( S δ ) } \max\{\ell_f(\delta),\ell_f(S\delta)\} max { ℓ f ( δ ) , ℓ f ( S δ )} ℓ f ( δ ) = relu ( t f − d f ( θ ∘ ) − ϕ f T δ ) 2 \ell_f(\delta)=\operatorname{relu}(t_f-d_f(\theta^\circ)-\phi_f^{\mathsf{T}}\delta)^2 ℓ f ( δ ) = relu ( t f − d f ( θ ∘ ) − ϕ f T δ ) 2 relu ( t − min { a , b } ) 2 = max { relu ( t − a ) 2 , relu ( t − b ) 2 } \operatorname{relu}(t-\min\{a,b\})^2=\max\{\operatorname{relu}(t-a)^2,\operatorname{relu}(t-b)^2\} relu ( t − min { a , b } ) 2 = max { relu ( t − a ) 2 , relu ( t − b ) 2 } ℓ f ( S δ ) \ell_f(S\delta) ℓ f ( S δ ) ϕ f T ( I − S ) δ ≥ 0 \phi_f^{\mathsf{T}}(I-S)\delta\ge0 ϕ f T ( I − S ) δ ≥ 0 δ = c ϕ f \delta=c\phi_f δ = c ϕ f δ = c S ϕ f \delta=cS\phi_f δ = c S ϕ f c ≥ 0 c\ge0 c ≥ 0 § 4 ), so the minimum changes a scalar weight and leaves the direction S T ϕ f S^{\mathsf{T}}\phi_f S T ϕ f
In the linearized model the anticipated loss is therefore the plain forgetting loss evaluated on the part of the edit that survives the update. It is the objective of KAU under the signed residual, wherever the minimum selects the anticipated score. For an edit that combines several facts, the condition of the corollary can fail for one of them. The minimum then changes the weight of that fact and leaves its direction unchanged. The identity relates the two objectives, and it holds for the joint response at every draw. That the anticipated loss is the plain loss at the post-update point holds by construction. The content of the identity is that, in the linearized model, the post-update edit is a fixed linear image S δ S\delta S δ
The identity alone leaves the location of a minimizer open, because the filter is invertible for every positive ridge. Under a uniform ridge, the edit S − 1 δ ′ S^{-1}\delta' S − 1 δ ′ δ ′ \delta' δ ′ u k u_k u k ( λ k + σ ) / σ (\lambda_k+\sigma)/\sigma ( λ k + σ ) / σ S T ϕ f S^{\mathsf{T}}\phi_f S T ϕ f σ / ( λ k + σ ) \sigma/(\lambda_k+\sigma) σ / ( λ k + σ )
Subspace methods as thresholds of the filter. A further corollary shows that confining the edit to a subspace is a hard threshold of the filter, at level zero or at a positive level.
Corollary A.2 (Two thresholds of the filter). Take a uniform ridge in the linearized model. (a) As σ → 0 \sigma\to0 σ → 0 S → Π ⊥ S \to\Pi^{\perp} S → Π ⊥ ( I − η Φ T Φ ) T → Π ⊥ (I-\eta\Phi^{\mathsf T}\Phi)^{T} \to\Pi^{\perp} ( I − η Φ T Φ ) T → Π ⊥ T → ∞ T \to\infty T → ∞ Φ δ = 0 \Phi\delta=0 Φ δ = 0 λ ˉ > 0 \bar{\lambda}>0 λ ˉ > 0 U λ ˉ U_{\bar{\lambda}} U λ ˉ u k u_k u k λ k ≤ λ ˉ \lambda_k\le\bar{\lambda} λ k ≤ λ ˉ δ ∈ U λ ˉ \delta\in U_{\bar{\lambda}} δ ∈ U λ ˉ ∥ S δ ∥ 2 ≥ λ ˉ λ ˉ + σ ∥ δ ∥ 2 \lVert S\delta\rVert_2\ge\frac{\bar{\lambda}}{\bar{\lambda}+\sigma}\lVert\delta\rVert_2 ∥ S δ ∥ 2 ≥ λ ˉ + σ λ ˉ ∥ δ ∥ 2 δ \delta δ λ k > λ ˉ \lambda_k>\bar{\lambda} λ k > λ ˉ ∥ S δ ∥ 2 ≤ λ ˉ λ ˉ + σ ∥ δ ∥ 2 \lVert S\delta\rVert_2\le\frac{\bar{\lambda}}{\bar{\lambda}+\sigma}\lVert\delta\rVert_2 ∥ S δ ∥ 2 ≤ λ ˉ + σ λ ˉ ∥ δ ∥ 2
Confining the edit to the complement of the update’s span is null-space projection, the threshold at level zero. When the update class is the retained edges at the involved entities, it is, restricted to the involved rows, the retained-span projector that Golatkar et al. [21 ] , Chen et al. [9 ] and Zhou et al. [74 ] use to protect utility. For an edit that moves one row alone, the constraint Φ δ = 0 \Phi\delta=0 Φ δ = 0 § 3 also trains on edges the unlearner never saw, whose features lie outside the retained span. That update can therefore move an edit that lies in the retained-span null space. The stand-ins of the unseen channel put modelled directions of this kind into Φ \Phi Φ U λ ˉ U_{\bar{\lambda}} U λ ˉ [65 ] ; Sondej et al. [52 ] ; Sondej and Yang (2025)). FRAG (Chen et al. [10 ] ) applies the same idea per coordinate, on weights the retained data barely activate. Those methods read the spectrum from a proxy, the activations or gradients of the forget set or of the retained data, because they do not hold the update’s data. For Xiao et al. [65 ] the shared-eigenstructure assumption is what licenses the proxy. The correspondence concerns the form of the constraint. Those methods compute their spectra from the activations or gradients of deep networks and use their own losses. The subspace U λ ˉ U_{\bar{\lambda}} U λ ˉ Φ T Φ \Phi^{\mathsf T}\Phi Φ T Φ § 7 .7). KAU applies the soft weights, σ / ( λ k + σ ) \sigma/(\lambda_k+\sigma) σ / ( λ k + σ )
The remark below shows what the one-sided residual of equation 4 adds to the subspace of Corollary A.2.
Remark A.1 (The one-sided residual relaxes the subspace to a cone). With the one-sided residual of equation 4 in the linearized model, the response at θ ∘ + δ \theta^{\circ}+\delta θ ∘ + δ − ( Φ T Φ + Σ ) − 1 Φ T relu ( Φ δ ) -(\Phi^{\mathsf T}\Phi+\Sigma)^{-1}\Phi^{\mathsf T}\operatorname{relu}(\Phi\delta) − ( Φ T Φ + Σ ) − 1 Φ T relu ( Φ δ ) Φ δ ≤ 0 \Phi\delta\le0 Φ δ ≤ 0 { Φ δ = 0 } \{\Phi\delta=0\} { Φ δ = 0 } { Φ δ ≤ 0 } \{\Phi\delta\le0\} { Φ δ ≤ 0 }
Null-space projection forbids every change to the score of an update edge, and the response of KAU restores only the raised edges.
Composition versus a penalty on predicted recovery. The filter also says why the response is composed into the loss and is not penalized beside it. The alternative, and the form a proxy method would take, is a penalty on the predicted score recovery ρ ^ f = d f ( θ ) − d f ( θ + Δ θ ) \hat{\rho}_f=d_f(\theta)-d_f(\theta+\Delta\theta) ρ ^ f = d f ( θ ) − d f ( θ + Δ θ ) θ = θ ∘ \theta=\theta^{\circ} θ = θ ∘ Δ θ = 0 \Delta\theta=0 Δ θ = 0 ρ ^ f = 0 \hat{\rho}_f=0 ρ ^ f = 0 ϕ f ( v ) T δ v < 0 \phi_f^{(v)\mathsf T}\delta_v<0 ϕ f ( v ) T δ v < 0 d f ( θ ) d_f(\theta) d f ( θ ) σ v / ( λ min + + σ v ) \sigma_v/(\lambda_{\min}^{+}+\sigma_v) σ v / ( λ m i n + + σ v ) ρ ^ f \hat{\rho}_f ρ ^ f ∣ ϕ f ( v ) T δ v ∣ |\phi_f^{(v)\mathsf T}\delta_v| ∣ ϕ f ( v ) T δ v ∣ ∥ ϕ f ( v ) ∥ 2 \lVert\phi_f^{(v)}\rVert_2 ∥ ϕ f ( v ) ∥ 2 ∥ δ v ∥ 2 \lVert\delta_v\rVert_2 ∥ δ v ∥ 2
Beyond the linearized model. The scores of the three backbones are nonlinear in the rows. Outside the linearized model, Corollary A.1 becomes a statement about the gradient at the current point θ \theta θ θ \theta θ § 4.2 ). For the TransE score the slot feature is the sign pattern of the translation error, projected on the outer tangent of the normalized row equation 10. The sign pattern is constant while no coordinate of the translation error changes sign, so inside such a cell the feature changes only through the normalization of the row. The post-update score is evaluated to first order,
d f ( θ + Δ θ ) ≈ d f l i n ( θ ; N ) : = d f ( θ ) + ∑ v ∈ { h , t } ϕ f ( v ) T Δ e v . d_f(\theta+\Delta\theta)\approx d_f^{\mathrm{lin}}(\theta;N):=d_f(\theta)+\sum_{v\in\{h,t\}}\phi_f^{(v)\mathsf T}\Delta e_v. d f ( θ + Δ θ ) ≈ d f lin ( θ ; N ) := d f ( θ ) + v ∈ { h , t } ∑ ϕ f ( v ) T Δ e v . The one-sided residual of equation 4 is replaced by the signed residual r i = d i ( θ ) − d i ( θ ∘ ) r_i=d_i(\theta)-d_i(\theta^{\circ}) r i = d i ( θ ) − d i ( θ ∘ ) e v e_v e v v v v ϕ f ( v ) \phi_f^{(v)} ϕ f ( v ) e v e_v e v
Theorem A.1 (Operator identity). Fix a draw N N N σ v > 0 \sigma_v > 0 σ v > 0 v v v θ \theta θ f f f θ \theta θ Φ v \Phi_v Φ v v v v v v v Δ e v ( θ ) = − A v r v ( θ ) \Delta e_v(\theta) = -A_v r_v(\theta) Δ e v ( θ ) = − A v r v ( θ ) A v = Φ v ⊤ ( Φ v Φ v ⊤ + σ v I ) − 1 A_v = \Phi_v^\top(\Phi_v\Phi_v^\top+ \sigma_v I)^{-1} A v = Φ v ⊤ ( Φ v Φ v ⊤ + σ v I ) − 1 Lemma 1 . Assume that the features Φ v \Phi_v Φ v ϕ f ( v ) \phi_f^{(v)} ϕ f ( v ) r i = d i ( θ ) − d i ( θ ∘ ) r_i = d_i(\theta) - d_i(\theta^\circ) r i = d i ( θ ) − d i ( θ ∘ ) v v v f f f
∂ ∂ e v [ d f ( θ ) + ϕ f ( v ) ⊤ Δ e v ( θ ) ] = ( I − Φ v ⊤ ( Φ v Φ v ⊤ + σ v I ) − 1 Φ v ) ϕ f ( v ) = P N , v ⊥ ϕ f ( v ) . (13) \frac{\partial}{\partial e_v}\left[d_f(\theta)+\phi_f^{(v)\top}\Delta e_v(\theta)\right]
=
\left(I-\Phi_v^\top(\Phi_v\Phi_v^\top+\sigma_v I)^{-1}\Phi_v\right)\phi_f^{(v)}
=
P_{N,v}^{\perp}\phi_f^{(v)}. \tag*{(13)} ∂ e v ∂ [ d f ( θ ) + ϕ f ( v ) ⊤ Δ e v ( θ ) ] = ( I − Φ v ⊤ ( Φ v Φ v ⊤ + σ v I ) − 1 Φ v ) ϕ f ( v ) = P N , v ⊥ ϕ f ( v ) . (13) The operator P N , v ⊥ P_{N,v}^{\perp} P N , v ⊥ k k k Φ v \Phi_v Φ v σ v / ( λ k + σ v ) \sigma_v/(\lambda_k+\sigma_v) σ v / ( λ k + σ v ) λ k \lambda_k λ k Φ v Φ v ⊤ \Phi_v\Phi_v^\top Φ v Φ v ⊤ σ v → 0 \sigma_v \to0 σ v → 0
Proof sketch. Hold A v A_v A v r v r_v r v θ \theta θ ∂ Δ e v / ∂ e v = − A v ∂ r v / ∂ e v \partial\Delta e_v/\partial e_v=-A_v\,\partial r_v/\partial e_v ∂ Δ e v / ∂ e v = − A v ∂ r v / ∂ e v d i ( θ ∘ ) d_i(\theta^\circ) d i ( θ ∘ ) ∂ d i / ∂ e v = ϕ i ( v ) ⊤ \partial d_i/\partial e_v=\phi_i^{(v)\top} ∂ d i / ∂ e v = ϕ i ( v ) ⊤ ∂ r v / ∂ e v = Φ v \partial r_v/\partial e_v=\Phi_v ∂ r v / ∂ e v = Φ v ϕ f ( v ) − ( A v Φ v ) ⊤ ϕ f ( v ) \phi_f^{(v)}-(A_v\Phi_v)^\top\phi_f^{(v)} ϕ f ( v ) − ( A v Φ v ) ⊤ ϕ f ( v ) (13) because the inverse is symmetric. The spectral claims follow from a singular value decomposition of Φ v \Phi_v Φ v § 7 .§ 5 gives the full proof, the operator under the one-sided residual, the cross-entity terms of the joint response, and the same operator at every further Gauss–Newton round (Remark A.3).
Theorem A.1 is the local form of Corollary A.1 for the per-entity response. At any point, the anticipated loss moves each row along the plain forgetting direction passed through the per-entity filter built at that point. The draw changes at every step, so the direction the optimizer follows over a run is an average of per-draw filters. The next corollary gives that average and two of its limits. The first limit is the projector off the span of every retained edge and stand-in at the entity. The second is the projector off the span of the retained gradients alone, which we call the retained-span projector and which Section 5 runs as the retained-span projection of Table 18 .
Corollary A.3 (Soft projector and its two limits). Under the hypotheses of Theorem A.1 at every draw, replace d ~ f \tilde d_f d ~ f d f l i n d_f^{\mathrm{lin}} d f lin f f f e v e_v e v v v v
− E N [ w N P N , v ⊥ ] ϕ f ( v ) , w N = 2 relu ( t f − d f l i n ( θ ; N ) ) ≥ 0 , -\mathbb{E}_N\left[w_N P_{N,v}^{\perp}\right]\phi_f^{(v)}, \qquad
w_N=2\operatorname{relu}\left(t_f-d_f^{\mathrm{lin}}(\theta;N)\right)\geq0, − E N [ w N P N , v ⊥ ] ϕ f ( v ) , w N = 2 relu ( t f − d f lin ( θ ; N ) ) ≥ 0 , with w N w_N w N N N N E N [ w N ] > 0 \mathbb{E}_N[w_N]>0 E N [ w N ] > 0 P ˉ v ⊥ = E N [ w N P N , v ⊥ ] / E N [ w N ] \bar P_v^{\perp}=\mathbb{E}_N[w_NP_{N,v}^{\perp}]/\mathbb{E}_N[w_N] P ˉ v ⊥ = E N [ w N P N , v ⊥ ] / E N [ w N ] σ v → 0 \sigma_v\to0 σ v → 0 P ˉ v ⊥ \bar P_v^{\perp} P ˉ v ⊥ u u u E N [ w N ∥ Π N , v u ∥ 2 ] / E N [ w N ] \mathbb{E}_N[w_N\|\Pi_{N,v}u\|^2]/\mathbb{E}_N[w_N] E N [ w N ∥ Π N , v u ∥ 2 ] / E N [ w N ] Π N , v \Pi_{N,v} Π N , v v v v k max k_{\max} k m a x σ v → 0 \sigma_v\to0 σ v → 0 P ˉ v ⊥ \bar P_v^{\perp} P ˉ v ⊥ v v v P ˉ v ⊥ \bar P_v^{\perp} P ˉ v ⊥ v v v e v e_v e v [21 ] , Chen et al. [9 ] , Saha et al. [47 ] , Wang et al. [59 ] and Zhou et al. [74 ] restricted to that row.
Averaged over draws, the filter removes each direction in proportion to how often, and how strongly, the modelled class draws it. Beyond the two limits, KAU adds the unseen channel, which puts edges the unlearner has never seen into the span. It also adds the sampled draw and the exact evaluation of the score at the shifted rows.
Scope and empirical counterparts. Proposition A.1, its two corollaries and Remark A.1 are exact in the linearized model, and Theorem A.1 is the local statement outside it. The theorem takes the per-entity response, and Appendix § 7 .§ 5 gives the cross-entity terms of the joint solve. Table 16 measures the joint solve against the per-entity block solve, first-order against exact evaluation, and the signed residual against KAU’s, one row each. Table 17 measures the sampled draw against the expected draw and the plain composition against KAU’s, one row each. Table 18 lists the retained-span projection, which approaches the second limit of Corollary A.3 as its ridge vanishes, released at KAU’s forgetting depth.
The filter describes the modelled update, a ridge or gradient-descent fit of a squared residual on the drawn edges. The update of Section 3 runs Adam on the ranking loss, its sampled corruptions add features outside Φ \Phi Φ Table 18 ). The same update restores 0.0158 for the retained-span projection and 0.0250 for the plain forgetting loss. The response predicts the order of recovery across facts (Appendix § 10 .§ 5 ). Corollary A.1 predicts where the gain appears. The loss stays active until the surviving score reaches t f t_f t f Figure 3 , KAU stays below GraphDPO and ZeroFisher at every depth, and the gap widens as forgetting deepens.
Proof of Lemma 1: the linearized response
Proof of Lemma 1. Write Δ \Delta Δ Δ θ \Delta\theta Δ θ r = r N ( θ ) ∈ R ∣ N ∣ r=r_N(\theta)\in\mathbb{R}^{\lvert N\rvert} r = r N ( θ ) ∈ R ∣ N ∣ Φ = Φ N \Phi=\Phi_N Φ = Φ N i i i ϕ i = ∇ θ d i \phi_i=\nabla_\theta d_i ϕ i = ∇ θ d i i i i θ \theta θ r i ( θ + Δ ) ≈ r i + ϕ i T Δ r_i(\theta+\Delta)\approx r_i+\phi_i^\mathsf{T}\Delta r i ( θ + Δ ) ≈ r i + ϕ i T Δ σ 2 ∥ Δ ∥ 2 2 \frac{\sigma}{2}\lVert\Delta\rVert_2^2 2 σ ∥ Δ ∥ 2 2 1 2 ∥ r + Φ Δ ∥ 2 2 + σ 2 ∥ Δ ∥ 2 2 \frac{1}{2}\lVert r+\Phi\Delta\rVert_2^2+\frac{\sigma}{2}\lVert\Delta\rVert_2^2 2 1 ∥ r + ΦΔ ∥ 2 2 + 2 σ ∥ Δ ∥ 2 2 σ > 0 \sigma>0 σ > 0 ( Φ T Φ + σ I ) Δ = − Φ T r (\Phi^\mathsf{T}\Phi+\sigma I)\Delta=-\Phi^\mathsf{T}r ( Φ T Φ + σ I ) Δ = − Φ T r Φ T ( Φ Φ T + σ I ) = ( Φ T Φ + σ I ) Φ T \Phi^\mathsf{T}(\Phi\Phi^\mathsf{T}+\sigma I)=(\Phi^\mathsf{T}\Phi+\sigma I)\Phi^\mathsf{T} Φ T ( Φ Φ T + σ I ) = ( Φ T Φ + σ I ) Φ T ( Φ T Φ + σ I ) − 1 (\Phi^\mathsf{T}\Phi+\sigma I)^{-1} ( Φ T Φ + σ I ) − 1 ( Φ Φ T + σ I ) − 1 (\Phi\Phi^\mathsf{T}+\sigma I)^{-1} ( Φ Φ T + σ I ) − 1 ( Φ T Φ + σ I ) − 1 Φ T = Φ T ( Φ Φ T + σ I ) − 1 (\Phi^\mathsf{T}\Phi+\sigma I)^{-1}\Phi^\mathsf{T}=\Phi^\mathsf{T}(\Phi\Phi^\mathsf{T}+\sigma I)^{-1} ( Φ T Φ + σ I ) − 1 Φ T = Φ T ( Φ Φ T + σ I ) − 1 1 2 ∑ i r i ( θ + Δ ) 2 \frac{1}{2}\sum_i r_i(\theta+\Delta)^2 2 1 ∑ i r i ( θ + Δ ) 2 Δ = 0 \Delta=0 Δ = 0 v v v e v e_v e v Δ e v = − ( Φ v T Φ v + σ v I ) − 1 Φ v T r v = − A v r v \Delta_{e_v}=-(\Phi_v^\mathsf{T}\Phi_v+\sigma_vI)^{-1}\Phi_v^\mathsf{T}r_v=-A_vr_v Δ e v = − ( Φ v T Φ v + σ v I ) − 1 Φ v T r v = − A v r v
Remark A.2 (Ridge damping and early stopping). Consider the linearized least-squares problem 1 2 ∥ r + Φ Δ ∥ 2 2 \frac{1}{2}\lVert r+\Phi\Delta\rVert_2^2 2 1 ∥ r + ΦΔ ∥ 2 2 Δ \Delta Δ Δ = 0 \Delta=0 Δ = 0 τ \tau τ η \eta η T T T η λ max ( K ) ≤ 1 \eta\lambda_{\max}(K)\le1 η λ m a x ( K ) ≤ 1 σ \sigma σ Δ = − Φ T ∑ k g ( λ k ) − 1 q k q k T r \Delta=-\Phi^\mathsf{T}\sum_k g(\lambda_k)^{-1}q_kq_k^\mathsf{T}r Δ = − Φ T ∑ k g ( λ k ) − 1 q k q k T r ( λ k , q k ) (\lambda_k,q_k) ( λ k , q k ) K = Φ Φ T K=\Phi\Phi^\mathsf{T} K = Φ Φ T
g τ ( λ ) = 1 − e − τ λ , g η , T ( λ ) = 1 − ( 1 − η λ ) T , g σ ( λ ) = λ λ + σ . g_\tau(\lambda)=1-e^{-\tau\lambda},\qquad
g_{\eta,T}(\lambda)=1-(1-\eta\lambda)^T,\qquad
g_\sigma(\lambda)=\frac{\lambda}{\lambda+\sigma}. g τ ( λ ) = 1 − e − τ λ , g η , T ( λ ) = 1 − ( 1 − η λ ) T , g σ ( λ ) = λ + σ λ . Gradient flow solves Δ ˙ = − Φ T ( r + Φ Δ ) \dot{\Delta}=-\Phi^\mathsf{T}(r+\Phi\Delta) Δ ˙ = − Φ T ( r + ΦΔ ) Δ ( τ ) = − ( I − e − τ Φ T Φ ) ( Φ T Φ ) + Φ T r \Delta(\tau)=-(I-e^{-\tau\Phi^\mathsf{T}\Phi})(\Phi^\mathsf{T}\Phi)^+\Phi^\mathsf{T}r Δ ( τ ) = − ( I − e − τ Φ T Φ ) ( Φ T Φ ) + Φ T r ( Φ T Φ ) Φ T = Φ T K + (\Phi^\mathsf{T}\Phi)\Phi^\mathsf{T}=\Phi^\mathsf{T}K^+ ( Φ T Φ ) Φ T = Φ T K + Φ T Φ \Phi^\mathsf{T}\Phi Φ T Φ Φ T q k / λ k \Phi^\mathsf{T}q_k/\sqrt{\lambda_k} Φ T q k / λ k λ k \lambda_k λ k e − τ λ e^{-\tau\lambda} e − τ λ ( 1 − η λ ) T (1-\eta\lambda)^T ( 1 − η λ ) T λ / ( λ + σ ) \lambda/(\lambda+\sigma) λ / ( λ + σ ) σ = 1 / ( τ T ) \sigma=1/(\tau T) σ = 1/ ( τ T ) τ = η T \tau=\eta T τ = η T λ ∈ [ 0 , 1 / η ] \lambda\in[0,1/\eta] λ ∈ [ 0 , 1/ η ] K K K η λ max ( K ) ≤ 1 \eta\lambda_{\max}(K)\le1 η λ m a x ( K ) ≤ 1
g σ ( λ ) ≤ g τ ( λ ) ≤ g η , T ( λ ) ≤ min { 1 , τ T λ } ≤ 2 g σ ( λ ) . g_\sigma(\lambda)\le g_\tau(\lambda)\le g_{\eta,T}(\lambda)\le\min\{1,\tau T\lambda\}\le2g_\sigma(\lambda). g σ ( λ ) ≤ g τ ( λ ) ≤ g η , T ( λ ) ≤ min { 1 , τ T λ } ≤ 2 g σ ( λ ) . The first inequality is e − u ≤ 1 / ( 1 + u ) e^{-u}\le1/(1+u) e − u ≤ 1/ ( 1 + u ) u = τ λ u=\tau\lambda u = τ λ ( 1 − η λ ) T ≤ e − η T λ (1-\eta\lambda)^T\le e^{-\eta T\lambda} ( 1 − η λ ) T ≤ e − η T λ ( 1 − η λ ) T ≥ 1 − T η λ (1-\eta\lambda)^T\ge1-T\eta\lambda ( 1 − η λ ) T ≥ 1 − T η λ g η , T ≤ 1 g_{\eta,T}\le1 g η , T ≤ 1 min { 1 , u } ≤ 2 u / ( 1 + u ) \min\{1,u\}\le2u/(1+u) min { 1 , u } ≤ 2 u / ( 1 + u ) u ≤ 1 u\le1 u ≤ 1 1 + u ≤ 2 1+u\le2 1 + u ≤ 2 u ≥ 1 u\ge1 u ≥ 1 1 + u ≤ 2 u 1+u\le2u 1 + u ≤ 2 u σ = 1 / ( η T ) \sigma=1/(\eta T) σ = 1/ ( η T ) [1 ] ). The ridge σ v \sigma_v σ v v v v § 8 .9), and every experiment runs the update as a training run rather than as a filter.
Score preservation is the known-channel residual
This subsection proves the claim of Section 4.4 that the score-preservation term of equation 9 bounds the known-channel part of the response.
Proposition A.2 (Score preservation is the known-channel residual). Let S S S β mean i ∈ S ( d i ( θ ) − d i ( θ ∘ ) ) 2 \beta\operatorname{mean}_{i\in S}(d_i(\theta)-d_i(\theta^\circ))^2 β mean i ∈ S ( d i ( θ ) − d i ( θ ∘ ) ) 2 β \beta β S S S β \beta β S S S r v k n r_v^{\mathrm{kn}} r v kn r v r_v r v ∥ A v r v k n ∥ 2 ≤ ∥ A v ∥ o p ∥ r v k n ∥ 2 \lVert A_vr_v^{\mathrm{kn}}\rVert_2\le\lVert A_v\rVert_{\mathrm{op}}\lVert r_v^{\mathrm{kn}}\rVert_2 ∥ A v r v kn ∥ 2 ≤ ∥ A v ∥ op ∥ r v kn ∥ 2 ∥ A v ∥ o p ≤ 1 / ( 2 σ v ) \lVert A_v\rVert_{\mathrm{op}}\le1/(2\sqrt{\sigma_v}) ∥ A v ∥ op ≤ 1/ ( 2 σ v ) S S S v v v
∥ A v r v k n ∥ 2 ≤ ∣ S ∣ 4 σ v ( mean i ∈ S ( d i ( θ ) − d i ( θ ∘ ) ) 2 ) . \lVert A_vr_v^{\mathrm{kn}}\rVert_2\le\sqrt{\frac{\lvert S\rvert}{4\sigma_v}\left(\operatorname{mean}_{i\in S}\left(d_i(\theta)-d_i(\theta^\circ)\right)^2\right)}. ∥ A v r v kn ∥ 2 ≤ 4 σ v ∣ S ∣ ( mean i ∈ S ( d i ( θ ) − d i ( θ ∘ ) ) 2 ) . so minimizing the term on such a sample bounds that displacement. The joint solve of Section 4.2 obeys the same bound for the stacked known-channel displacement, with min v σ v \min_v \sigma_v min v σ v σ v \sigma_v σ v S S S
Proof of Proposition A.2. For a retained edge i ∈ S i \in S i ∈ S d i ( θ ) − d i ( θ ∘ ) d_i(\theta)-d_i(\theta^\circ) d i ( θ ) − d i ( θ ∘ ) β mean i ∈ S ( d i ( θ ) − d i ( θ ∘ ) ) 2 \beta\operatorname{mean}_{i\in S}(d_i(\theta)-d_i(\theta^\circ))^2 β mean i ∈ S ( d i ( θ ) − d i ( θ ∘ ) ) 2 β \beta β S S S relu ( x ) 2 ≤ x 2 \operatorname{relu}(x)^2 \le x^2 relu ( x ) 2 ≤ x 2 x x x β \beta β (4) on S S S − A v r v = − A v r v s t − A v r v k n -A_vr_v=-A_vr_v^{\mathrm{st}}-A_vr_v^{\mathrm{kn}} − A v r v = − A v r v st − A v r v kn r v s t r_v^{\mathrm{st}} r v st ∥ A v r v k n ∥ 2 ≤ ∥ A v ∥ o p ∥ r v k n ∥ 2 \lVert A_vr_v^{\mathrm{kn}}\rVert_2\le\lVert A_v\rVert_{\mathrm{op}}\lVert r_v^{\mathrm{kn}}\rVert_2 ∥ A v r v kn ∥ 2 ≤ ∥ A v ∥ op ∥ r v kn ∥ 2 ∥ A v ∥ o p ≤ 1 / ( 2 σ v ) \lVert A_v\rVert_{\mathrm{op}}\le1/(2\sqrt{\sigma_v}) ∥ A v ∥ op ≤ 1/ ( 2 σ v ) (11) . By relu ( x ) 2 ≤ x 2 \operatorname{relu}(x)^2\le x^2 relu ( x ) 2 ≤ x 2 ∥ r v k n ∥ 2 2 ≤ ∑ i ∈ S v ( d i ( θ ) − d i ( θ ∘ ) ) 2 \lVert r_v^{\mathrm{kn}}\rVert_2^2\le\sum_{i\in S_v}(d_i(\theta)-d_i(\theta^\circ))^2 ∥ r v kn ∥ 2 2 ≤ ∑ i ∈ S v ( d i ( θ ) − d i ( θ ∘ ) ) 2 v v v S S S ∑ i ∈ S ( d i ( θ ) − d i ( θ ∘ ) ) 2 = ∣ S ∣ mean i ∈ S ( d i ( θ ) − d i ( θ ∘ ) ) 2 \sum_{i\in S}(d_i(\theta)-d_i(\theta^\circ))^2=|S|\operatorname{mean}_{i\in S}(d_i(\theta)-d_i(\theta^\circ))^2 ∑ i ∈ S ( d i ( θ ) − d i ( θ ∘ ) ) 2 = ∣ S ∣ mean i ∈ S ( d i ( θ ) − d i ( θ ∘ ) ) 2 A v r v u n A_vr_v^{\mathrm{un}} A v r v un Σ = diag ( σ v I ) \Sigma=\operatorname{diag}(\sigma_v I) Σ = diag ( σ v I ) Φ ~ = Φ Σ − 1 / 2 \widetilde{\Phi}=\Phi\Sigma^{-1/2} Φ = Φ Σ − 1/2 Φ ⊤ Φ + Σ = Σ 1 / 2 ( Φ ~ ⊤ Φ ~ + I ) Σ 1 / 2 \Phi^\top\Phi+\Sigma=\Sigma^{1/2}(\widetilde{\Phi}^{\top}\widetilde{\Phi}+I)\Sigma^{1/2} Φ ⊤ Φ + Σ = Σ 1/2 ( Φ ⊤ Φ + I ) Σ 1/2 ( Φ ⊤ Φ + Σ ) − 1 Φ ⊤ = Σ − 1 / 2 ( Φ ~ ⊤ Φ ~ + I ) − 1 Φ ~ ⊤ (\Phi^\top\Phi+\Sigma)^{-1}\Phi^\top=\Sigma^{-1/2}(\widetilde{\Phi}^{\top}\widetilde{\Phi}+I)^{-1}\widetilde{\Phi}^{\top} ( Φ ⊤ Φ + Σ ) − 1 Φ ⊤ = Σ − 1/2 ( Φ ⊤ Φ + I ) − 1 Φ ⊤ ∥ Σ − 1 / 2 ∥ o p ⋅ 1 2 = 1 2 min v σ v \lVert\Sigma^{-1/2}\rVert_{\mathrm{op}}\cdot\frac{1}{2}=\frac{1}{2\sqrt{\min_v\sigma_v}} ∥ Σ − 1/2 ∥ op ⋅ 2 1 = 2 m i n v σ v 1 min v σ v \min_v\sigma_v min v σ v σ v \sigma_v σ v
Beyond the linearized response
Lemma 1 gives the linearized response of the whole run of the update, modelled as a ridge-damped least-squares fit under frozen features. This subsection bounds what one re-linearization round adds and shows that the operator identity survives re-linearization. Fix a draw N N N n = ∣ N ∣ n=|N| n = ∣ N ∣ Φ \Phi Φ ϕ i ⊤ \phi_i^\top ϕ i ⊤ θ \theta θ K = Φ Φ ⊤ K=\Phi\Phi^\top K = Φ Φ ⊤ σ > 0 \sigma>0 σ > 0 r = r ( θ ) r=r(\theta) r = r ( θ ) r i ( θ + Δ ) = d i ( θ + Δ ) − y i r_i(\theta+\Delta)=d_i(\theta+\Delta)-y_i r i ( θ + Δ ) = d i ( θ + Δ ) − y i
F ( Δ ) = 1 2 ∑ i ∈ N r i ( θ + Δ ) 2 + σ 2 ∥ Δ ∥ 2 2 . F(\Delta)=\frac{1}{2}\sum_{i\in N}r_i(\theta+\Delta)^2+\frac{\sigma}{2}\lVert\Delta\rVert_2^2. F ( Δ ) = 2 1 i ∈ N ∑ r i ( θ + Δ ) 2 + 2 σ ∥ Δ ∥ 2 2 . Its Gauss–Newton iteration starts at Δ 0 = 0 \Delta_0=0 Δ 0 = 0
Δ k + 1 = Δ k − ( Φ k ⊤ Φ k + σ I ) − 1 ( Φ k ⊤ r ( θ + Δ k ) + σ Δ k ) , \Delta_{k+1}=\Delta_k-(\Phi_k^\top\Phi_k+\sigma I)^{-1}\bigl(\Phi_k^\top r(\theta+\Delta_k)+\sigma\Delta_k\bigr), Δ k + 1 = Δ k − ( Φ k ⊤ Φ k + σ I ) − 1 ( Φ k ⊤ r ( θ + Δ k ) + σ Δ k ) , with Φ k \Phi_k Φ k θ + Δ k \theta+\Delta_k θ + Δ k Δ 1 = − ( Φ ⊤ Φ + σ I ) − 1 Φ ⊤ r = − Φ ⊤ ( K + σ I ) − 1 r \Delta_1=-(\Phi^\top\Phi+\sigma I)^{-1}\Phi^\top r=-\Phi^\top(K+\sigma I)^{-1}r Δ 1 = − ( Φ ⊤ Φ + σ I ) − 1 Φ ⊤ r = − Φ ⊤ ( K + σ I ) − 1 r α = ( K + σ I ) − 1 r \alpha=(K+\sigma I)^{-1}r α = ( K + σ I ) − 1 r Δ 1 = − Φ ⊤ α \Delta_1=-\Phi^\top\alpha Δ 1 = − Φ ⊤ α r l i n ( Δ ) = r + Φ Δ r^{\mathrm{lin}}(\Delta)=r+\Phi\Delta r lin ( Δ ) = r + ΦΔ r l i n ( Δ 1 ) = r − K α = σ α r^{\mathrm{lin}}(\Delta_1)=r-K\alpha=\sigma\alpha r lin ( Δ 1 ) = r − K α = σ α
Lemma A.1 (One-round error). Assume that along the segment { θ + t Δ 1 : t ∈ [ 0 , 1 ] } \{\theta+t\Delta_1:t\in[0,1]\} { θ + t Δ 1 : t ∈ [ 0 , 1 ]} d i d_i d i i ∈ N i\in N i ∈ N ϕ i = ∇ θ d i \phi_i=\nabla_\theta d_i ϕ i = ∇ θ d i ∥ ϕ i ( θ + t Δ 1 ) − ϕ i ( θ + s Δ 1 ) ∥ 2 ≤ L ∣ t − s ∣ ∥ Δ 1 ∥ 2 \lVert\phi_i(\theta+t\Delta_1)-\phi_i(\theta+s\Delta_1)\rVert_2\le L\lvert t-s\rvert\lVert\Delta_1\rVert_2 ∥ ϕ i ( θ + t Δ 1 ) − ϕ i ( θ + s Δ 1 ) ∥ 2 ≤ L ∣ t − s ∣ ∥ Δ 1 ∥ 2 s , t ∈ [ 0 , 1 ] s,t\in[0,1] s , t ∈ [ 0 , 1 ] ∣ r i ( θ + Δ 1 ) − r i l i n ( Δ 1 ) ∣ ≤ L 2 ∥ Δ 1 ∥ 2 2 \lvert r_i(\theta+\Delta_1)-r_i^{\mathrm{lin}}(\Delta_1)\rvert\le\frac{L}{2}\lVert\Delta_1\rVert_2^2 ∣ r i ( θ + Δ 1 ) − r i lin ( Δ 1 )∣ ≤ 2 L ∥ Δ 1 ∥ 2 2 i ∈ N i\in N i ∈ N ∥ Φ 1 − Φ ∥ o p ≤ n L ∥ Δ 1 ∥ 2 \lVert\Phi_1-\Phi\rVert_{\mathrm{op}}\le\sqrt{n}L\lVert\Delta_1\rVert_2 ∥ Φ 1 − Φ ∥ op ≤ n L ∥ Δ 1 ∥ 2
∥ Δ 2 − Δ 1 ∥ 2 ≤ n L 4 σ ∥ Δ 1 ∥ 2 2 + n L ∥ Δ 1 ∥ 2 ∥ α ∥ 2 ≤ n L ∥ Φ ∥ o p ( ∥ Φ ∥ o p 4 σ + 1 ) ∥ α ∥ 2 2 . \lVert\Delta_2-\Delta_1\rVert_2\le\frac{\sqrt{n}L}{4\sqrt{\sigma}}\lVert\Delta_1\rVert_2^2+\sqrt{n}L\lVert\Delta_1\rVert_2\lVert\alpha\rVert_2\le\sqrt{n}L\lVert\Phi\rVert_{\mathrm{op}}\left(\frac{\lVert\Phi\rVert_{\mathrm{op}}}{4\sqrt{\sigma}}+1\right)\lVert\alpha\rVert_2^2. ∥ Δ 2 − Δ 1 ∥ 2 ≤ 4 σ n L ∥ Δ 1 ∥ 2 2 + n L ∥ Δ 1 ∥ 2 ∥ α ∥ 2 ≤ n L ∥ Φ ∥ op ( 4 σ ∥ Φ ∥ op + 1 ) ∥ α ∥ 2 2 . Proof. (i) By the fundamental theorem of calculus along the segment,
r i ( θ + Δ 1 ) − r i ( θ ) − ϕ i ⊤ Δ 1 = ∫ 0 1 ( ϕ i ( θ + t Δ 1 ) − ϕ i ( θ ) ) ⊤ Δ 1 d t , r_i(\theta+\Delta_1)-r_i(\theta)-\phi_i^\top\Delta_1=\int_0^1\bigl(\phi_i(\theta+t\Delta_1)-\phi_i(\theta)\bigr)^\top\Delta_1\,dt, r i ( θ + Δ 1 ) − r i ( θ ) − ϕ i ⊤ Δ 1 = ∫ 0 1 ( ϕ i ( θ + t Δ 1 ) − ϕ i ( θ ) ) ⊤ Δ 1 d t , and the Lipschitz hypothesis bounds the integrand by L t ∥ Δ 1 ∥ 2 2 Lt\lVert\Delta_1\rVert_2^2 L t ∥ Δ 1 ∥ 2 2 L 2 ∥ Δ 1 ∥ 2 2 \frac{L}{2}\lVert\Delta_1\rVert_2^2 2 L ∥ Δ 1 ∥ 2 2 Φ 1 − Φ \Phi_1-\Phi Φ 1 − Φ ϕ i ( θ + Δ 1 ) − ϕ i ( θ ) \phi_i(\theta+\Delta_1)-\phi_i(\theta) ϕ i ( θ + Δ 1 ) − ϕ i ( θ ) L ∥ Δ 1 ∥ 2 L\lVert\Delta_1\rVert_2 L ∥ Δ 1 ∥ 2 n L ∥ Δ 1 ∥ 2 \sqrt{n}L\lVert\Delta_1\rVert_2 n L ∥ Δ 1 ∥ 2 F F F Δ 1 \Delta_1 Δ 1 ∇ F ( Δ 1 ) = Φ 1 ⊤ r ( θ + Δ 1 ) + σ Δ 1 \nabla F(\Delta_1)=\Phi_1^\top r(\theta+\Delta_1)+\sigma\Delta_1 ∇ F ( Δ 1 ) = Φ 1 ⊤ r ( θ + Δ 1 ) + σ Δ 1 Δ 1 \Delta_1 Δ 1 1 2 ∥ r l i n ( Δ ) ∥ 2 2 + σ 2 ∥ Δ ∥ 2 2 \frac{1}{2}\lVert r^{\mathrm{lin}}(\Delta)\rVert_2^2+\frac{\sigma}{2}\lVert\Delta\rVert_2^2 2 1 ∥ r lin ( Δ ) ∥ 2 2 + 2 σ ∥ Δ ∥ 2 2 Φ ⊤ r l i n ( Δ 1 ) + σ Δ 1 = 0 \Phi^\top r^{\mathrm{lin}}(\Delta_1)+\sigma\Delta_1=0 Φ ⊤ r lin ( Δ 1 ) + σ Δ 1 = 0
∇ F ( Δ 1 ) = Φ 1 ⊤ e + ( Φ 1 − Φ ) ⊤ r l i n ( Δ 1 ) = Φ 1 ⊤ e + σ ( Φ 1 − Φ ) ⊤ α , \nabla F(\Delta_1)=\Phi_1^\top e+(\Phi_1-\Phi)^\top r^{\mathrm{lin}}(\Delta_1)=\Phi_1^\top e+\sigma(\Phi_1-\Phi)^\top\alpha, ∇ F ( Δ 1 ) = Φ 1 ⊤ e + ( Φ 1 − Φ ) ⊤ r lin ( Δ 1 ) = Φ 1 ⊤ e + σ ( Φ 1 − Φ ) ⊤ α , where e = r ( θ + Δ 1 ) − r l i n ( Δ 1 ) e=r(\theta+\Delta_1)-r^{\mathrm{lin}}(\Delta_1) e = r ( θ + Δ 1 ) − r lin ( Δ 1 ) ∥ e ∥ 2 ≤ n L 2 ∥ Δ 1 ∥ 2 2 \lVert e\rVert_2\le\frac{\sqrt{n}L}{2}\lVert\Delta_1\rVert_2^2 ∥ e ∥ 2 ≤ 2 n L ∥ Δ 1 ∥ 2 2 Δ 2 − Δ 1 = − ( Φ 1 ⊤ Φ 1 + σ I ) − 1 ∇ F ( Δ 1 ) \Delta_2-\Delta_1=-(\Phi_1^\top\Phi_1+\sigma I)^{-1}\nabla F(\Delta_1) Δ 2 − Δ 1 = − ( Φ 1 ⊤ Φ 1 + σ I ) − 1 ∇ F ( Δ 1 ) (11) holds for any matrix and any σ > 0 \sigma>0 σ > 0 Φ 1 \Phi_1 Φ 1 (11) give ∥ ( Φ 1 ⊤ Φ 1 + σ I ) − 1 Φ 1 ⊤ ∥ o p ≤ 1 / ( 2 σ ) \lVert(\Phi_1^\top\Phi_1+\sigma I)^{-1}\Phi_1^\top\rVert_{\mathrm{op}}\le1/(2\sqrt{\sigma}) ∥( Φ 1 ⊤ Φ 1 + σ I ) − 1 Φ 1 ⊤ ∥ op ≤ 1/ ( 2 σ ) ∥ ( Φ 1 ⊤ Φ 1 + σ I ) − 1 ∥ o p ≤ 1 / σ \lVert(\Phi_1^\top\Phi_1+\sigma I)^{-1}\rVert_{\mathrm{op}}\le1/\sigma ∥( Φ 1 ⊤ Φ 1 + σ I ) − 1 ∥ op ≤ 1/ σ ∥ Δ 2 − Δ 1 ∥ 2 ≤ ∥ e ∥ 2 / ( 2 σ ) + ∥ Φ 1 − Φ ∥ o p ∥ α ∥ 2 \lVert\Delta_2-\Delta_1\rVert_2\le\lVert e\rVert_2/(2\sqrt{\sigma})+\lVert\Phi_1-\Phi\rVert_{\mathrm{op}}\lVert\alpha\rVert_2 ∥ Δ 2 − Δ 1 ∥ 2 ≤ ∥ e ∥ 2 / ( 2 σ ) + ∥ Φ 1 − Φ ∥ op ∥ α ∥ 2 ∥ Δ 1 ∥ 2 = ∥ Φ ⊤ α ∥ 2 ≤ ∥ Φ ∥ o p ∥ α ∥ 2 \lVert\Delta_1\rVert_2=\lVert\Phi^\top\alpha\rVert_2\le\lVert\Phi\rVert_{\mathrm{op}}\lVert\alpha\rVert_2 ∥ Δ 1 ∥ 2 = ∥ Φ ⊤ α ∥ 2 ≤ ∥ Φ ∥ op ∥ α ∥ 2
Both terms of (iii) are quadratic in the dual coefficients α \alpha α σ α \sigma\alpha σ α § 8 .11 records that a second round on the same draw improved no reported quantity, which is why the objective uses one round. Appendix § 10 .§ 5 reports that the one-round response tracks the realized per-fact score recovery with a Pearson correlation of 0.53 and a Spearman correlation of 0.21, and it predicts the ranking of the facts and not the level of the change. The lemma bounds the correction of one further round. It does not bound the level gap of an update of many epochs, and the objective relies on the ranking while the target sets the level (§ 4.3 ).
For TransE and TransH the score is piecewise linear in the translation error of the triple and its slot features jump where a coordinate of that vector changes sign. Along a segment that crosses no sign change the sign vector s \boldsymbol{s} s ( I − e ˉ v e ˉ v T ) s / ∥ e v ∥ 2 (\mathbf{I}-\bar{\mathbf{e}}_v\bar{\mathbf{e}}_v^{\mathsf{T}})\boldsymbol{s}/\lVert\mathbf{e}_v\rVert_2 ( I − e ˉ v e ˉ v T ) s / ∥ e v ∥ 2 m / ∥ e v ∥ 2 2 \sqrt{m}/\lVert\mathbf{e}_v\rVert_2^2 m / ∥ e v ∥ 2 2 Lemma A.5 the gap of item (i) is then the normalization’s second-order term plus the crossed-coordinate excess ϰ ( D ) \varkappa(D) ϰ ( D ) § 7 .13, which is non-negative and, in a coordinate with ∣ x j ∣ \lvert x_j\rvert ∣ x j ∣ ∣ D j ∣ \lvert D_j\rvert ∣ D j ∣ § 10 .§ 5 measures its effect on the ranking.
Remark A.3 (The operator identity round by round). Hold the features fixed at every round and use the signed residual, as in Theorem A.1, so that Φ k \Phi_k Φ k θ + Δ k \theta+\Delta_k θ + Δ k G k = ( Φ k T Φ k + σ I ) − 1 G_k=(\Phi_k^{\mathsf{T}}\Phi_k+\sigma I)^{-1} G k = ( Φ k T Φ k + σ I ) − 1 θ \theta θ
∂ Δ k + 1 ∂ θ = ∂ Δ k ∂ θ − G k ( Φ k T Φ k ( I + ∂ Δ k ∂ θ ) + σ ∂ Δ k ∂ θ ) = − G k Φ k T Φ k . \frac{\partial\Delta_{k+1}}{\partial\theta}
=
\frac{\partial\Delta_k}{\partial\theta}
-
G_k\left(\Phi_k^{\mathsf{T}}\Phi_k\left(I+\frac{\partial\Delta_k}{\partial\theta}\right)+\sigma\frac{\partial\Delta_k}{\partial\theta}\right)
=
-G_k\Phi_k^{\mathsf{T}}\Phi_k. ∂ θ ∂ Δ k + 1 = ∂ θ ∂ Δ k − G k ( Φ k T Φ k ( I + ∂ θ ∂ Δ k ) + σ ∂ θ ∂ Δ k ) = − G k Φ k T Φ k . because G k ( Φ k T Φ k + σ I ) = I G_k(\Phi_k^{\mathsf{T}}\Phi_k+\sigma I)=I G k ( Φ k T Φ k + σ I ) = I θ + Δ k + 1 \theta+\Delta_{k+1} θ + Δ k + 1 I − G k Φ k T Φ k = I − Φ k T ( Φ k Φ k T + σ I ) − 1 Φ k I-G_k\Phi_k^{\mathsf{T}}\Phi_k=I-\Phi_k^{\mathsf{T}}(\Phi_k\Phi_k^{\mathsf{T}}+\sigma I)^{-1}\Phi_k I − G k Φ k T Φ k = I − Φ k T ( Φ k Φ k T + σ I ) − 1 Φ k Lemma 1 , a symmetric matrix, hence the shrinkage operator of equation (13) built from the features at the k k k [44 ] ). Theorem A.1 therefore holds for every round with Φ k \Phi_k Φ k Φ \Phi Φ k k k Φ k \Phi_k Φ k Σ \Sigma Σ σ I \sigma I σ I
Proof of Theorem A.1: the operator identity
Proof of Theorem A.1. Let u u u f f f
d f l i n ( θ ) = d f ( θ ) + ϕ f ( v ) T Δ e v ( θ ) + ϕ f ( u ) T Δ e u ( θ ) d_f^{\mathrm{lin}}(\theta)=d_f(\theta)+\phi_f^{(v)\mathsf{T}}\Delta\mathbf{e}_v(\theta)+\phi_f^{(u)\mathsf{T}}\Delta\mathbf{e}_u(\theta) d f lin ( θ ) = d f ( θ ) + ϕ f ( v ) T Δ e v ( θ ) + ϕ f ( u ) T Δ e u ( θ ) for the anticipated score evaluated to first order, with ϕ f ( v ) \phi_f^{(v)} ϕ f ( v ) ϕ f ( u ) \phi_f^{(u)} ϕ f ( u ) A v A_v A v A u A_u A u e v \mathbf{e}_v e v ∂ d f / ∂ e v = ϕ f ( v ) \partial d_f/\partial\mathbf{e}_v=\phi_f^{(v)} ∂ d f / ∂ e v = ϕ f ( v ) ( ∂ Δ e v / ∂ e v ) T ϕ f ( v ) (\partial\Delta\mathbf{e}_v/\partial\mathbf{e}_v)^{\mathsf{T}}\phi_f^{(v)} ( ∂ Δ e v / ∂ e v ) T ϕ f ( v ) C v = ( ∂ Δ e u / ∂ e v ) T ϕ f ( u ) C_v=(\partial\Delta\mathbf{e}_u/\partial\mathbf{e}_v)^{\mathsf{T}}\phi_f^{(u)} C v = ( ∂ Δ e u / ∂ e v ) T ϕ f ( u ) d f + ϕ f ( v ) T Δ e v d_f+\phi_f^{(v)\mathsf{T}}\Delta\mathbf{e}_v d f + ϕ f ( v ) T Δ e v
(a) The signed residual. Since Δ e v = − A v r v ( θ ) \Delta\mathbf{e}_v=-A_v r_v(\theta) Δ e v = − A v r v ( θ ) A v A_v A v r v r_v r v θ \theta θ ∂ Δ e v / ∂ e v = − A v ∂ r v / ∂ e v \partial\Delta\mathbf{e}_v/\partial\mathbf{e}_v=-A_v\,\partial r_v/\partial\mathbf{e}_v ∂ Δ e v / ∂ e v = − A v ∂ r v / ∂ e v r i = d i ( θ ) − d i ( θ ∘ ) r_i=d_i(\theta)-d_i(\theta^\circ) r i = d i ( θ ) − d i ( θ ∘ ) ∂ r i / ∂ e v = ϕ i ( v ) T \partial r_i/\partial\mathbf{e}_v=\phi_i^{(v)\mathsf{T}} ∂ r i / ∂ e v = ϕ i ( v ) T i ∈ P v ( N ) i\in P_v(N) i ∈ P v ( N ) ∂ r v / ∂ e v = Φ v \partial r_v/\partial\mathbf{e}_v=\Phi_v ∂ r v / ∂ e v = Φ v ∂ Δ e v / ∂ e v = − A v Φ v \partial\Delta\mathbf{e}_v/\partial\mathbf{e}_v=-A_v\Phi_v ∂ Δ e v / ∂ e v = − A v Φ v
ϕ f ( v ) + ( − A v Φ v ) T ϕ f ( v ) = ϕ f ( v ) − Φ v T ( K v + σ v I ) − 1 Φ v ϕ f ( v ) = P N , v ⊥ ϕ f ( v ) . \phi_f^{(v)}+(-A_v\Phi_v)^{\mathsf{T}}\phi_f^{(v)}
=
\phi_f^{(v)}-\Phi_v^{\mathsf{T}}(K_v+\sigma_v I)^{-1}\Phi_v\phi_f^{(v)}
=
P_{N,v}^{\perp}\phi_f^{(v)}. ϕ f ( v ) + ( − A v Φ v ) T ϕ f ( v ) = ϕ f ( v ) − Φ v T ( K v + σ v I ) − 1 Φ v ϕ f ( v ) = P N , v ⊥ ϕ f ( v ) . where the transpose was taken using the symmetry of ( K v + σ v I ) − 1 (K_v+\sigma_v I)^{-1} ( K v + σ v I ) − 1 (13) . The spectral claims of the statement are the first two facts read off equation (11) . For the loss of draw N N N relu ( t f − d f l i n ) 2 \operatorname{relu}(t_f-d_f^{\mathrm{lin}})^2 relu ( t f − d f lin ) 2
∂ relu ( t f − d f l i n ) 2 ∂ e v = − 2 relu ( t f − d f l i n ) ( P N , v ⊥ ϕ f ( v ) + C v ) . \frac{\partial\operatorname{relu}(t_f-d_f^{\mathrm{lin}})^2}{\partial\mathbf{e}_v}
=
-2\operatorname{relu}(t_f-d_f^{\mathrm{lin}})\left(P_{N,v}^{\perp}\phi_f^{(v)}+C_v\right). ∂ e v ∂ relu ( t f − d f lin ) 2 = − 2 relu ( t f − d f lin ) ( P N , v ⊥ ϕ f ( v ) + C v ) . (b) The one-sided residual. Under r i = relu ( d i ( θ ) − d i ( θ ∘ ) ) r_i=\operatorname{relu}(d_i(\theta)-d_i(\theta^\circ)) r i = relu ( d i ( θ ) − d i ( θ ∘ )) ∂ r i / ∂ e v = 1 [ r i > 0 ] ϕ i ( v ) T \partial r_i/\partial\mathbf{e}_v=\mathbf{1}_{[r_i>0]}\phi_i^{(v)\mathsf{T}} ∂ r i / ∂ e v = 1 [ r i > 0 ] ϕ i ( v ) T A ⊆ P v ( N ) \mathcal{A}\subseteq P_v(N) A ⊆ P v ( N ) D A D_{\mathcal{A}} D A A \mathcal{A} A ∂ Δ e v / ∂ e v = − A v D A Φ v \partial\Delta e_v/\partial e_v=-A_vD_A\Phi_v ∂ Δ e v / ∂ e v = − A v D A Φ v − Φ v T D A ( K v + σ v I ) − 1 Φ v -\Phi_v^{\mathsf T}D_A(K_v+\sigma_v I)^{-1}\Phi_v − Φ v T D A ( K v + σ v I ) − 1 Φ v (13) becomes
M N , v = I − Φ v T D A ( K v + σ v I ) − 1 Φ v . M_{N,v}=I-\Phi_v^{\mathsf T}D_A(K_v+\sigma_v I)^{-1}\Phi_v. M N , v = I − Φ v T D A ( K v + σ v I ) − 1 Φ v . Only the edges with positive residual enter through the residual, whereas every drawn edge still enters through the kernel. For σ v > 0 \sigma_v>0 σ v > 0 A ≠ P v ( N ) \mathcal{A}\ne P_v(N) A = P v ( N ) M N , v M_{N,v} M N , v M N , v = P N , v ⊥ M_{N,v}=P_{N,v}^{\perp} M N , v = P N , v ⊥ σ v → 0 \sigma_v\to0 σ v → 0 K v K_v K v Φ A \Phi_A Φ A Φ v \Phi_v Φ v A \mathcal{A} A K : , A = Φ v Φ A T K_{:,A}=\Phi_v\Phi_A^{\mathsf T} K : , A = Φ v Φ A T K v K_v K v K v − 1 K : , A K_v^{-1}K_{:,A} K v − 1 K : , A A \mathcal{A} A D A D_A D A M N , v Φ A T = Φ A T − Φ v T D A K v − 1 K : , A = Φ A T − Φ A T = 0 M_{N,v}\Phi_A^{\mathsf T}=\Phi_A^{\mathsf T}-\Phi_v^{\mathsf T}D_AK_v^{-1}K_{:,A}=\Phi_A^{\mathsf T}-\Phi_A^{\mathsf T}=0 M N , v Φ A T = Φ A T − Φ v T D A K v − 1 K : , A = Φ A T − Φ A T = 0
M N , v 2 = I − 2 Φ v T D A K v − 1 Φ v + Φ v T D A K v − 1 K v D A K v − 1 Φ v = I − Φ v T D A K v − 1 Φ v = M N , v , M_{N,v}^{2}=I-2\Phi_v^{\mathsf T}D_AK_v^{-1}\Phi_v+\Phi_v^{\mathsf T}D_AK_v^{-1}K_vD_AK_v^{-1}\Phi_v=I-\Phi_v^{\mathsf T}D_AK_v^{-1}\Phi_v=M_{N,v}, M N , v 2 = I − 2 Φ v T D A K v − 1 Φ v + Φ v T D A K v − 1 K v D A K v − 1 Φ v = I − Φ v T D A K v − 1 Φ v = M N , v , using D A 2 = D A D_A^2=D_A D A 2 = D A A \mathcal{A} A θ \theta θ
(c) Cross-entity terms and the joint response. Under the per-entity response, ∂ Δ e u / ∂ e v = − A u ∂ r u / ∂ e v \partial\Delta e_u/\partial e_v=-A_u\,\partial r_u/\partial e_v ∂ Δ e u / ∂ e v = − A u ∂ r u / ∂ e v i ∈ P u ( N ) i\in P_u(N) i ∈ P u ( N ) ∂ r i / ∂ e v \partial r_i/\partial e_v ∂ r i / ∂ e v v v v i i i C v = 0 C_v=0 C v = 0 u u u v v v C v = − Φ u ∣ v T A u T ϕ f ( u ) C_v=-\Phi_{u|v}^{\mathsf T}A_u^{\mathsf T}\phi_f^{(u)} C v = − Φ u ∣ v T A u T ϕ f ( u ) Φ u ∣ v ∈ R n u × m \Phi_{u|v}\in\mathbb{R}^{n_u\times m} Φ u ∣ v ∈ R n u × m ϕ i ( v ) T \phi_i^{(v)\mathsf T} ϕ i ( v ) T i ∈ P u ( N ) ∩ P v ( N ) i\in P_u(N)\cap P_v(N) i ∈ P u ( N ) ∩ P v ( N ) § 4.2 , stack the involved rows as Δ ∈ R m ∣ V F ∣ \Delta\in\mathbb{R}^{m|V_F|} Δ ∈ R m ∣ V F ∣ Φ ∈ R ∣ N ∣ × m ∣ V F ∣ \Phi\in\mathbb{R}^{|N|\times m|V_F|} Φ ∈ R ∣ N ∣ × m ∣ V F ∣ i i i ϕ i ( h ) T \phi_i^{(h)\mathsf T} ϕ i ( h ) T ϕ i ( t ) T \phi_i^{(t)\mathsf T} ϕ i ( t ) T ϕ f ∈ R m ∣ V F ∣ \phi_f\in\mathbb{R}^{m|V_F|} ϕ f ∈ R m ∣ V F ∣ f f f h h h t t t Δ = − ( Φ T Φ + Σ ) − 1 Φ T r \Delta=-(\Phi^{\mathsf T}\Phi+\Sigma)^{-1}\Phi^{\mathsf T}r Δ = − ( Φ T Φ + Σ ) − 1 Φ T r Φ \Phi Φ d f + ϕ f T Δ d_f+\phi_f^{\mathsf T}\Delta d f + ϕ f T Δ
ϕ f − Φ T Φ ( Φ T Φ + Σ ) − 1 ϕ f = Σ ( Φ T Φ + Σ ) − 1 ϕ f . \phi_f-\Phi^{\mathsf T}\Phi(\Phi^{\mathsf T}\Phi+\Sigma)^{-1}\phi_f=\Sigma(\Phi^{\mathsf T}\Phi+\Sigma)^{-1}\phi_f. ϕ f − Φ T Φ ( Φ T Φ + Σ ) − 1 ϕ f = Σ ( Φ T Φ + Σ ) − 1 ϕ f . For a uniform ridge Σ = σ I \Sigma=\sigma I Σ = σ I ( I − Φ T ( Φ Φ T + σ I ) − 1 Φ ) ϕ f (I-\Phi^{\mathsf T}(\Phi\Phi^{\mathsf T}+\sigma I)^{-1}\Phi)\phi_f ( I − Φ T ( Φ Φ T + σ I ) − 1 Φ ) ϕ f (13) with the full Jacobian in place of the per-entity one, and for a general diagonal Σ \Sigma Σ Σ 1 / 2 ( I − Φ ~ T ( Φ ~ Φ ~ T + I ) − 1 Φ ~ ) Σ − 1 / 2 ϕ f \Sigma^{1/2}(I-\widetilde{\Phi}^{\mathsf T}(\widetilde{\Phi}\widetilde{\Phi}^{\mathsf T}+I)^{-1}\widetilde{\Phi})\Sigma^{-1/2}\phi_f Σ 1/2 ( I − Φ T ( Φ Φ T + I ) − 1 Φ ) Σ − 1/2 ϕ f Φ ~ = Φ Σ − 1 / 2 \widetilde{\Phi}=\Phi\Sigma^{-1/2} Φ = Φ Σ − 1/2 ( v , v ) (v,v) ( v , v ) ϕ f ( v ) \phi_f^{(v)} ϕ f ( v ) e v e_v e v v v v ( v , u ) (v,u) ( v , u ) ϕ f ( u ) \phi_f^{(u)} ϕ f ( u ) Φ T Φ + Σ \Phi^{\mathsf T}\Phi+\Sigma Φ T Φ + Σ P N , v ⊥ P_{N,v}^{\perp} P N , v ⊥ Φ T Φ + Σ \Phi^{\mathsf T}\Phi+\Sigma Φ T Φ + Σ
Proof of Corollary A.3: the soft projector and its two limits
Proof of Corollary A.3. The draw. At entity v v v C v C_v C v v v v p k n p_{\mathrm{kn}} p kn v v v p u n ( v ) = min { 1 , ρ u n deg ( v ) / 32 } p_{\mathrm{un}}(v)=\min\{1,\rho_{\mathrm{un}}\deg(v)/32\} p un ( v ) = min { 1 , ρ un deg ( v ) /32 } k max k_{\max} k m a x k max k_{\max} k m a x P v ( N ) ⊆ C v P_v(N)\subseteq C_v P v ( N ) ⊆ C v
The soft projector. By Theorem A.1, the gradient of the loss of draw N N N v v v − w N P N , v ⊥ ϕ f ( v ) -w_NP_{N,v}^{\perp}\phi_f^{(v)} − w N P N , v ⊥ ϕ f ( v ) w N = 2 relu ( t f − d f l i n ( θ ; N ) ) ≥ 0 w_N=2\operatorname{relu}(t_f-d_f^{\mathrm{lin}}(\theta;N))\ge0 w N = 2 relu ( t f − d f lin ( θ ; N )) ≥ 0 − E N [ w N P N , v ⊥ ] ϕ f ( v ) -\mathbb{E}_N[w_NP_{N,v}^{\perp}]\phi_f^{(v)} − E N [ w N P N , v ⊥ ] ϕ f ( v ) ( 0 , 1 ] (0,1] ( 0 , 1 ] E N [ w N ] > 0 \mathbb{E}_N[w_N]>0 E N [ w N ] > 0 P ˉ v ⊥ = E N [ w N P N , v ⊥ ] / E N [ w N ] \bar{P}_v^{\perp}=\mathbb{E}_N[w_NP_{N,v}^{\perp}]/\mathbb{E}_N[w_N] P ˉ v ⊥ = E N [ w N P N , v ⊥ ] / E N [ w N ] ( 0 , 1 ] (0,1] ( 0 , 1 ] u u u (11) ,
u T ( I − P N , v ⊥ ) u = ∑ k ≤ ℓ λ k λ k + σ v ⟨ u k , u ⟩ 2 ∈ [ λ min + ( K v ) λ min + ( K v ) + σ v ∥ Π N , v u ∥ 2 2 , ∥ Π N , v u ∥ 2 2 ] . u^{\mathsf T}(I-P_{N,v}^{\perp})u=\sum_{k\leq\ell}\frac{\lambda_k}{\lambda_k+\sigma_v}\langle u_k,u\rangle^2\in\left[\frac{\lambda_{\min}^{+}(K_v)}{\lambda_{\min}^{+}(K_v)+\sigma_v}\lVert\Pi_{N,v}u\rVert_2^2,\lVert\Pi_{N,v}u\rVert_2^2\right]. u T ( I − P N , v ⊥ ) u = k ≤ ℓ ∑ λ k + σ v λ k ⟨ u k , u ⟩ 2 ∈ [ λ m i n + ( K v ) + σ v λ m i n + ( K v ) ∥ Π N , v u ∥ 2 2 , ∥ Π N , v u ∥ 2 2 ] . so the fraction of u u u P ˉ v ⊥ \bar{P}_v^{\perp} P ˉ v ⊥ u T ( I − P ˉ v ⊥ ) u u^{\mathsf T}(I-\bar{P}_v^{\perp})u u T ( I − P ˉ v ⊥ ) u w w w E N [ w N ∥ Π N , v u ∥ 2 2 ] / E N [ w N ] \mathbb{E}_N[w_N\lVert\Pi_{N,v}u\rVert_2^2]/\mathbb{E}_N[w_N] E N [ w N ∥ Π N , v u ∥ 2 2 ] / E N [ w N ] σ v → 0 \sigma_v\to0 σ v → 0 u u u E N [ P N , v ⊥ ] \mathbb{E}_N[P_{N,v}^{\perp}] E N [ P N , v ⊥ ]
Limit 1, the update span. If p k n → 1 p_{\mathrm{kn}}\to1 p kn → 1 p u n ( v ) → 1 p_{\mathrm{un}}(v)\to1 p un ( v ) → 1 P v ( N ) = C v P_v(N)=C_v P v ( N ) = C v P C v , v ⊥ P_{C_v,v}^{\perp} P C v , v ⊥ σ v → 0 \sigma_v\to0 σ v → 0 Π C v , v \Pi_{C_v,v} Π C v , v (11) , the orthogonal projector off the span of all retained edges and stand-ins at v v v − 2 relu ( t f − d f ( θ ) ) Π C v , v ⊥ ϕ f ( v ) -2\operatorname{relu}(t_f-d_f(\theta))\Pi^\perp_{C_{v,v}}\phi_f^{(v)} − 2 relu ( t f − d f ( θ )) Π C v , v ⊥ ϕ f ( v ) − w Π C v , v ⊥ ϕ f ( v ) -w\Pi^\perp_{C_{v,v}}\phi_f^{(v)} − w Π C v , v ⊥ ϕ f ( v ) w w w
Limit 2, the retained span. If ρ k n → 1 \rho_{kn}\to1 ρ k n → 1 ρ u n → 0 \rho_{un}\to0 ρ u n → 0 P v ( N ) P_v(N) P v ( N ) v v v σ v → 0 \sigma_v\to0 σ v → 0 θ \theta θ i i i e v e_v e v c i ϕ i ( v ) c_i\phi_i^{(v)} c i ϕ i ( v ) c i c_i c i v v v v v v c i ≠ 0 c_i\ne0 c i = 0 v v v e v e_v e v ϕ i ( v ) ⊤ δ v = 0 \phi_i^{(v)\top}\delta_v=0 ϕ i ( v ) ⊤ δ v = 0 v v v e v e_v e v
The m − 1 m-1 m − 1 By equation (10) , on the two normalized backbones every slot feature at v v v ϕ f ( v ) \phi_f^{(v)} ϕ f ( v ) e ˉ v ⊥ \bar{e}_v^\perp e ˉ v ⊥ m − 1 m-1 m − 1 v v v rank Φ v = m − 1 \operatorname{rank}\Phi_v=m-1 rank Φ v = m − 1 range ( Φ v ⊤ ) = e ˉ v ⊥ ∋ ϕ f ( v ) \operatorname{range}(\Phi_v^\top)=\bar{e}_v^\perp\ni\phi_f^{(v)} range ( Φ v ⊤ ) = e ˉ v ⊥ ∋ ϕ f ( v ) Π N , v ⊥ ϕ f ( v ) = 0 \Pi^\perp_{N,v}\phi_f^{(v)}=0 Π N , v ⊥ ϕ f ( v ) = 0 σ v > 0 \sigma_v>0 σ v > 0 ∥ P N , v ⊥ ϕ f ( v ) ∥ 2 ≤ σ v λ min + ( K v ) + σ v ∥ ϕ f ( v ) ∥ 2 \lVert P^\perp_{N,v}\phi_f^{(v)}\rVert_2\le\frac{\sigma_v}{\lambda_{\min}^{+}(K_v)+\sigma_v}\lVert\phi_f^{(v)}\rVert_2 ∥ P N , v ⊥ ϕ f ( v ) ∥ 2 ≤ λ m i n + ( K v ) + σ v σ v ∥ ϕ f ( v ) ∥ 2 m − 1 m-1 m − 1 m − 1 m-1 m − 1 m − 1 m-1 m − 1 rank Φ v ≤ k max = 96 < m − 1 = 199 \operatorname{rank}\Phi_v\le k_{\max}=96<m-1=199 rank Φ v ≤ k m a x = 96 < m − 1 = 199 k max < m = 400 k_{\max}<m=400 k m a x < m = 400 m m m m − 1 − k max m-1-k_{\max} m − 1 − k m a x v v v m − k max m-k_{\max} m − k m a x
Proofs for the survival filter
This subsection proves the statements of Appendix A.1 that are made in the linearized model, namely the joint form of Proposition A.1, Corollaries A.1 and A.2, and Remark A.1. Throughout, Φ ∈ R ∣ N ∣ × m ∣ V f ∣ \Phi\in\mathbb{R}^{|N|\times m|\mathcal{V}_f|} Φ ∈ R ∣ N ∣ × m ∣ V f ∣ θ ∘ \theta^\circ θ ∘ C = Φ ⊤ Φ C=\Phi^\top\Phi C = Φ ⊤ Φ K = Φ Φ ⊤ K=\Phi\Phi^\top K = Φ Φ ⊤ Σ = diag ( σ v I ) \Sigma=\operatorname{diag}(\sigma_v I) Σ = diag ( σ v I ) σ v > 0 \sigma_v>0 σ v > 0 C + Σ C+\Sigma C + Σ δ = θ − θ ∘ \delta=\theta-\theta^\circ δ = θ − θ ∘ r ( θ ) = Φ ( θ − θ ∘ ) r(\theta)=\Phi(\theta-\theta^\circ) r ( θ ) = Φ ( θ − θ ∘ ) Δ θ ( θ ) = − ( C + Σ ) − 1 Φ ⊤ r ( θ ) \Delta\theta(\theta)=-(C+\Sigma)^{-1}\Phi^\top r(\theta) Δ θ ( θ ) = − ( C + Σ ) − 1 Φ ⊤ r ( θ )
Proof of Proposition A.1, joint form. The identity. The residual is affine, r ( θ + δ ) = r ( θ ) + Φ δ r(\theta+\delta)=r(\theta)+\Phi\delta r ( θ + δ ) = r ( θ ) + Φ δ
Δ θ ( θ + δ ) = − ( C + Σ ) − 1 Φ ⊤ r ( θ ) − ( C + Σ ) − 1 Φ ⊤ Φ δ = Δ θ ( θ ) − ( C + Σ ) − 1 C δ . \Delta\theta(\theta+\delta)=-(C+\Sigma)^{-1}\Phi^\top r(\theta)-(C+\Sigma)^{-1}\Phi^\top\Phi\delta=\Delta\theta(\theta)-(C+\Sigma)^{-1}C\delta. Δ θ ( θ + δ ) = − ( C + Σ ) − 1 Φ ⊤ r ( θ ) − ( C + Σ ) − 1 Φ ⊤ Φ δ = Δ θ ( θ ) − ( C + Σ ) − 1 C δ . Adding θ + δ \theta+\delta θ + δ θ + δ + Δ θ ( θ + δ ) = θ + Δ θ ( θ ) + [ I − ( C + Σ ) − 1 C ] δ \theta+\delta+\Delta\theta(\theta+\delta)=\theta+\Delta\theta(\theta)+[I-(C+\Sigma)^{-1}C]\delta θ + δ + Δ θ ( θ + δ ) = θ + Δ θ ( θ ) + [ I − ( C + Σ ) − 1 C ] δ ( C + Σ ) − 1 ( C + Σ ) = I (C+\Sigma)^{-1}(C+\Sigma)=I ( C + Σ ) − 1 ( C + Σ ) = I
I − ( C + Σ ) − 1 C = ( C + Σ ) − 1 ( ( C + Σ ) − C ) = ( C + Σ ) − 1 Σ = S , I-(C+\Sigma)^{-1}C=(C+\Sigma)^{-1}((C+\Sigma)-C)=(C+\Sigma)^{-1}\Sigma=S, I − ( C + Σ ) − 1 C = ( C + Σ ) − 1 (( C + Σ ) − C ) = ( C + Σ ) − 1 Σ = S , which is the identity at every θ \theta θ θ = θ ∘ \theta=\theta^\circ θ = θ ∘ r ( θ ∘ ) = 0 r(\theta^\circ)=0 r ( θ ∘ ) = 0 Δ θ ( θ ∘ ) = 0 \Delta\theta(\theta^\circ)=0 Δ θ ( θ ∘ ) = 0 θ ∘ + δ + Δ θ ( θ ∘ + δ ) = θ ∘ + S δ \theta^\circ+\delta+\Delta\theta(\theta^\circ+\delta)=\theta^\circ+S\delta θ ∘ + δ + Δ θ ( θ ∘ + δ ) = θ ∘ + S δ
The edits left untouched. By the last display, S δ = δ S\delta=\delta S δ = δ ( C + Σ ) − 1 C δ = 0 (C+\Sigma)^{-1}C\delta=0 ( C + Σ ) − 1 C δ = 0 C δ = 0 C\delta=0 C δ = 0 ( C + Σ ) − 1 (C+\Sigma)^{-1} ( C + Σ ) − 1 Φ δ = 0 \Phi\delta=0 Φ δ = 0 C δ = Φ ⊤ Φ δ = 0 C\delta=\Phi^\top\Phi\delta=0 C δ = Φ ⊤ Φ δ = 0 C δ = 0 C\delta=0 C δ = 0 ∥ Φ δ ∥ 2 2 = δ ⊤ C δ = 0 \lVert\Phi\delta\rVert_2^2=\delta^\top C\delta=0 ∥ Φ δ ∥ 2 2 = δ ⊤ C δ = 0 S δ = δ S\delta=\delta S δ = δ Φ δ = 0 \Phi\delta=0 Φ δ = 0
The uniform ridge. Let Σ = σ I \Sigma=\sigma I Σ = σ I Lemma 1 gives ( C + σ I ) − 1 Φ ⊤ = Φ ⊤ ( K + σ I ) − 1 (C+\sigma I)^{-1}\Phi^\top=\Phi^\top(K+\sigma I)^{-1} ( C + σ I ) − 1 Φ ⊤ = Φ ⊤ ( K + σ I ) − 1
S = I − ( C + σ I ) − 1 Φ ⊤ Φ = I − Φ ⊤ ( K + σ I ) − 1 Φ . S=I-(C+\sigma I)^{-1}\Phi^\top\Phi=I-\Phi^\top(K+\sigma I)^{-1}\Phi. S = I − ( C + σ I ) − 1 Φ ⊤ Φ = I − Φ ⊤ ( K + σ I ) − 1 Φ. The derivation of equation 11 uses only a singular value decomposition of the matrix and σ > 0 \sigma>0 σ > 0 Φ \Phi Φ Φ = ∑ k ≤ ϱ λ k q k u k ⊤ \Phi=\sum_{k\le\varrho}\sqrt{\lambda_k}\,q_k u_k^\top Φ = ∑ k ≤ ϱ λ k q k u k ⊤
S = ∑ k ≤ ϱ σ λ k + σ u k u k ⊤ + Π ⊥ , Π ⊥ = I − ∑ k ≤ ϱ u k u k ⊤ . (14) S=\sum_{k\le\varrho}\frac{\sigma}{\lambda_k+\sigma}u_k u_k^\top+\Pi^\perp,\qquad\Pi^\perp=I-\sum_{k\le\varrho}u_k u_k^\top. \tag*{(14)} S = k ≤ ϱ ∑ λ k + σ σ u k u k ⊤ + Π ⊥ , Π ⊥ = I − k ≤ ϱ ∑ u k u k ⊤ . (14) The vectors u k u_k u k C = ∑ k ≤ q λ k u k u k T C = \sum_{k\leq q}\lambda_k u_k u_k^{\mathsf T} C = ∑ k ≤ q λ k u k u k T λ k > 0 \lambda_k > 0 λ k > 0 K K K range ( Φ T ) \operatorname{range}(\Phi^{\mathsf T}) range ( Φ T ) Π ⊥ \Pi^\perp Π ⊥ δ = ∑ k ≤ q c k u k + Π ⊥ δ \delta= \sum_{k\leq q} c_k u_k + \Pi^\perp\delta δ = ∑ k ≤ q c k u k + Π ⊥ δ c k = ⟨ u k , δ ⟩ c_k = \langle u_k,\delta\rangle c k = ⟨ u k , δ ⟩ S δ = ∑ k ≤ q σ λ k + σ c k u k + Π ⊥ δ S\delta= \sum_{k\leq q} \frac{\sigma}{\lambda_k+\sigma}c_k u_k + \Pi^\perp\delta S δ = ∑ k ≤ q λ k + σ σ c k u k + Π ⊥ δ u k u_k u k σ / ( λ k + σ ) \sigma/(\lambda_k+\sigma) σ / ( λ k + σ )
Gradient descent. Let the update start at the edited model θ ∘ + δ \theta^\circ+\delta θ ∘ + δ T T T η \eta η ϵ t \epsilon_t ϵ t t t t ϵ 0 = 0 \epsilon_0=0 ϵ 0 = 0 1 2 ∥ r ( θ ∘ + δ + ϵ ) ∥ 2 2 = 1 2 ∥ Φ ( δ + ϵ ) ∥ 2 2 \frac{1}{2}\|r(\theta^\circ+\delta+\epsilon)\|_2^2=\frac{1}{2}\|\Phi(\delta+\epsilon)\|_2^2 2 1 ∥ r ( θ ∘ + δ + ϵ ) ∥ 2 2 = 2 1 ∥Φ ( δ + ϵ ) ∥ 2 2 ϵ \epsilon ϵ C ( δ + ϵ ) C(\delta+\epsilon) C ( δ + ϵ ) ϵ t + 1 = ϵ t − η C ( δ + ϵ t ) \epsilon_{t+1}=\epsilon_t-\eta C(\delta+\epsilon_t) ϵ t + 1 = ϵ t − η C ( δ + ϵ t ) δ + ϵ t + 1 = ( I − η C ) ( δ + ϵ t ) \delta+\epsilon_{t+1}=(I-\eta C)(\delta+\epsilon_t) δ + ϵ t + 1 = ( I − η C ) ( δ + ϵ t ) t t t δ + ϵ 0 = δ \delta+\epsilon_0=\delta δ + ϵ 0 = δ δ + ϵ T = ( I − η C ) T δ \delta+\epsilon_T=(I-\eta C)^T\delta δ + ϵ T = ( I − η C ) T δ C C C
( I − η C ) T = ∑ k ≤ q ( 1 − η λ k ) T u k u k T + Π ⊥ , (I-\eta C)^T=\sum_{k\leq q}(1-\eta\lambda_k)^T u_k u_k^{\mathsf T}+\Pi^\perp, ( I − η C ) T = k ≤ q ∑ ( 1 − η λ k ) T u k u k T + Π ⊥ , so the surviving fraction along u k u_k u k ( 1 − η λ k ) T (1-\eta\lambda_k)^T ( 1 − η λ k ) T [ 0 , 1 ) [0,1) [ 0 , 1 ) 0 < η λ k ≤ 1 0<\eta\lambda_k\leq1 0 < η λ k ≤ 1 η ≤ 1 / λ max ( K ) \eta\leq1/\lambda_{\max}(K) η ≤ 1/ λ m a x ( K ) g σ ( λ ) ≤ g η , T ( λ ) g_\sigma(\lambda)\leq g_{\eta,T}(\lambda) g σ ( λ ) ≤ g η , T ( λ ) [ 0 , 1 / η ] [0,1/\eta] [ 0 , 1/ η ] σ = 1 / ( η T ) \sigma=1/(\eta T) σ = 1/ ( η T ) λ / ( λ + σ ) ≤ 1 − ( 1 − η λ ) T \lambda/(\lambda+\sigma)\leq1-(1-\eta\lambda)^T λ / ( λ + σ ) ≤ 1 − ( 1 − η λ ) T λ = λ k \lambda=\lambda_k λ = λ k ( 1 − η λ k ) T ≤ σ / ( λ k + σ ) (1-\eta\lambda_k)^T\leq\sigma/(\lambda_k+\sigma) ( 1 − η λ k ) T ≤ σ / ( λ k + σ ) g η , T ≤ 2 g σ g_{\eta,T}\leq2g_\sigma g η , T ≤ 2 g σ ( 1 − η λ k ) T ≥ ( σ − λ k ) / ( λ k + σ ) (1-\eta\lambda_k)^T\geq(\sigma-\lambda_k)/(\lambda_k+\sigma) ( 1 − η λ k ) T ≥ ( σ − λ k ) / ( λ k + σ )
The per-entity form. Restrict the computation of the first step to an edit that moves the row e v e_v e v Φ v \Phi_v Φ v σ v \sigma_v σ v r v r_v r v Φ \Phi Φ Σ \Sigma Σ r r r I − A v Φ v = P N , v N I-A_v\Phi_v=P^\mathsf{N}_{N,v} I − A v Φ v = P N , v N S S S □ \square □
Proof of Corollary A.1. The identity. In the linearized model the score of f f f d f ( θ ∘ + δ ) = d f ( θ ∘ ) + ϕ f T δ d_f(\theta^\circ+\delta)=d_f(\theta^\circ)+\phi_f^{\mathsf T}\delta d f ( θ ∘ + δ ) = d f ( θ ∘ ) + ϕ f T δ δ \delta δ θ ∘ + S δ \theta^\circ+S\delta θ ∘ + S δ
d f ( θ ∘ + δ + Δ θ ( θ ∘ + δ ) ) = d f ( θ ∘ ) + ϕ f T S δ , d_f(\theta^\circ+\delta+\Delta\theta(\theta^\circ+\delta))=d_f(\theta^\circ)+\phi_f^{\mathsf T}S\delta, d f ( θ ∘ + δ + Δ θ ( θ ∘ + δ )) = d f ( θ ∘ ) + ϕ f T S δ , which is the pre-update score d f ( θ ∘ ) + ϕ f T δ ′ d_f(\theta^\circ)+\phi_f^{\mathsf T}\delta' d f ( θ ∘ ) + ϕ f T δ ′ δ ′ = S δ \delta'=S\delta δ ′ = S δ 1 ∣ F ∣ ∑ relu ( t f − ⋅ ) 2 \frac{1}{|F|}\sum\operatorname{relu}(t_f-\cdot)^2 ∣ F ∣ 1 ∑ relu ( t f − ⋅ ) 2 L a n t ( δ ) = L p l a i n ( S δ ) \mathcal{L}_{\mathrm{ant}}(\delta)=\mathcal{L}_{\mathrm{plain}}(S\delta) L ant ( δ ) = L plain ( S δ ) N N N Φ \Phi Φ E N [ L p l a i n ( S N δ ) ] \mathbb{E}_N[\mathcal{L}_{\mathrm{plain}}(S_N\delta)] E N [ L plain ( S N δ )]
The minimum. The map x ↦ relu ( t − x ) 2 x\mapsto\operatorname{relu}(t-x)^2 x ↦ relu ( t − x ) 2 relu ( t − min { a , b } ) 2 = max { relu ( t − a ) 2 , relu ( t − b ) 2 } \operatorname{relu}(t-\min\{a,b\})^2=\max\{\operatorname{relu}(t-a)^2,\operatorname{relu}(t-b)^2\} relu ( t − min { a , b } ) 2 = max { relu ( t − a ) 2 , relu ( t − b ) 2 } a a a b b b f f f max { ℓ f ( δ ) , ℓ f ( S δ ) } \max\{\ell_f(\delta),\ell_f(S\delta)\} max { ℓ f ( δ ) , ℓ f ( S δ )} ℓ f ( S δ ) \ell_f(S\delta) ℓ f ( S δ ) d f ( θ ∘ ) + ϕ f T δ d_f(\theta^\circ)+\phi_f^{\mathsf T}\delta d f ( θ ∘ ) + ϕ f T δ ϕ f T S δ ≤ ϕ f T δ \phi_f^{\mathsf T}S\delta\leq\phi_f^{\mathsf T}\delta ϕ f T S δ ≤ ϕ f T δ ϕ f T ( I − S ) δ ≥ 0 \phi_f^{\mathsf T}(I-S)\delta\geq0 ϕ f T ( I − S ) δ ≥ 0 I − S = ∑ k ≤ q λ k λ k + σ u k u k T I-S=\sum_{k\leq q}\frac{\lambda_k}{\lambda_k+\sigma}u_k u_k^{\mathsf T} I − S = ∑ k ≤ q λ k + σ λ k u k u k T δ = c ϕ f \delta=c\phi_f δ = c ϕ f c ≥ 0 c\geq0 c ≥ 0 c ϕ f T ( I − S ) ϕ f ≥ 0 c\phi_f^{\mathsf T}(I-S)\phi_f\geq0 c ϕ f T ( I − S ) ϕ f ≥ 0 δ = c S ϕ f \delta=cS\phi_f δ = c S ϕ f c ϕ f T ( I − S ) S ϕ f ≥ 0 c\phi_f^{\mathsf T}(I-S)S\phi_f\geq0 c ϕ f T ( I − S ) S ϕ f ≥ 0 ( I − S ) S = ∑ k ≤ q σ λ k ( λ k + σ ) 2 u k u k T (I-S)S=\sum_{k\leq q}\frac{\sigma\lambda_k}{(\lambda_k+\sigma)^2}u_k u_k^{\mathsf T} ( I − S ) S = ∑ k ≤ q ( λ k + σ ) 2 σ λ k u k u k T Σ \Sigma Σ C ~ = Σ − 1 / 2 C Σ − 1 / 2 \widetilde C=\Sigma^{-1/2}C\Sigma^{-1/2} C = Σ − 1/2 C Σ − 1/2 I − S = ( C + Σ ) − 1 C = Σ − 1 / 2 ( C ~ + I ) − 1 C ~ Σ 1 / 2 I-S=(C+\Sigma)^{-1}C=\Sigma^{-1/2}(\widetilde C+I)^{-1}\widetilde C\Sigma^{1/2} I − S = ( C + Σ ) − 1 C = Σ − 1/2 ( C + I ) − 1 C Σ 1/2 δ = c Σ − 1 ϕ f \delta=c\Sigma^{-1}\phi_f δ = c Σ − 1 ϕ f c ≥ 0 c\geq0 c ≥ 0 z = Σ − 1 / 2 ϕ f z=\Sigma^{-1/2}\phi_f z = Σ − 1/2 ϕ f c z T ( C ~ + I ) − 1 C ~ z ≥ 0 cz^{\mathsf T}(\widetilde C+I)^{-1}\widetilde C z\geq0 c z T ( C + I ) − 1 C z ≥ 0 ( C ~ + I ) − 1 C ~ (\widetilde C+I)^{-1}\widetilde C ( C + I ) − 1 C I − S I-S I − S Σ \Sigma Σ C C C σ u = σ v \sigma_u=\sigma_v σ u = σ v C C C
The gradient. The composed loss of fact f f f relu ( t f − d ~ f ) 2 \operatorname{relu}(t_f-\widetilde d_f)^2 relu ( t f − d f ) 2 δ \delta δ − 2 relu ( t f − d ~ f ) S T ϕ f -2\operatorname{relu}(t_f-\widetilde d_f)S^{\mathsf T}\phi_f − 2 relu ( t f − d f ) S T ϕ f S T = Σ ( C + Σ ) − 1 S^{\mathsf T}=\Sigma(C+\Sigma)^{-1} S T = Σ ( C + Σ ) − 1 relu ( t f − d ~ f ) \operatorname{relu}(t_f-\widetilde d_f) relu ( t f − d f ) S T ϕ f S^{\mathsf T}\phi_f S T ϕ f
Nonlinear scores. For a score that is not linear in the rows, freeze the features at the current point θ \theta θ S T ϕ f S^{\mathsf T}\phi_f S T ϕ f Φ \Phi Φ θ \theta θ v v v □ \square □
Proof of Corollary A.2. Part (a). In equation 14 every λ k \lambda_k λ k σ / ( λ k + σ ) → 0 \sigma/(\lambda_k+\sigma)\to0 σ / ( λ k + σ ) → 0 σ → 0 \sigma\to0 σ → 0 S → Π ⊥ S\to\Pi^\perp S → Π ⊥ 0 ≤ 1 − η λ k < 1 0\leq1-\eta\lambda_k<1 0 ≤ 1 − η λ k < 1 ( 1 − η λ k ) T → 0 (1-\eta\lambda_k)^T\to0 ( 1 − η λ k ) T → 0 T → ∞ T\to\infty T → ∞ ( I − η C ) T → Π ⊥ (I-\eta C)^T\to\Pi^\perp ( I − η C ) T → Π ⊥ σ = 1 / ( η T ) \sigma=1/(\eta T) σ = 1/ ( η T ) Φ δ = 0 \Phi\delta=0 Φ δ = 0 S δ = δ S\delta=\delta S δ = δ Σ \Sigma Σ ( I − η C ) δ = δ (I-\eta C)\delta=\delta ( I − η C ) δ = δ C δ = 0 C\delta=0 C δ = 0 { δ : Φ δ = 0 } = range ( Π ⊥ ) \{\delta:\Phi\delta=0\}=\operatorname{range}(\Pi^\perp) { δ : Φ δ = 0 } = range ( Π ⊥ ) Φ \Phi Φ ϕ i T δ = 0 \phi_i^\mathsf{T}\delta=0 ϕ i T δ = 0 θ \theta θ
Part (b). Let δ ∈ U λ ˉ \delta\in U_{\bar{\lambda}} δ ∈ U λ ˉ δ = ∑ k : λ k ≤ λ ˉ c k u k + δ ⊥ \delta=\sum_{k:\lambda_k\le\bar{\lambda}}c_k u_k+\delta_\perp δ = ∑ k : λ k ≤ λ ˉ c k u k + δ ⊥ δ ⊥ = Π ⊥ δ \delta_\perp=\Pi^\perp\delta δ ⊥ = Π ⊥ δ
∥ S δ ∥ 2 2 = ∑ k : λ k ≤ λ ˉ ( σ λ k + σ ) 2 c k 2 + ∥ δ ⊥ ∥ 2 2 ≥ ( σ λ ˉ + σ ) 2 ( ∑ k : λ k ≤ λ ˉ c k 2 + ∥ δ ⊥ ∥ 2 2 ) = ( σ λ ˉ + σ ) 2 ∥ δ ∥ 2 2 . \lVert S\delta\rVert_2^2=\sum_{k:\lambda_k\le\bar{\lambda}}\left(\frac{\sigma}{\lambda_k+\sigma}\right)^2c_k^2+\lVert\delta_\perp\rVert_2^2\ge\left(\frac{\sigma}{\bar{\lambda}+\sigma}\right)^2\left(\sum_{k:\lambda_k\le\bar{\lambda}}c_k^2+\lVert\delta_\perp\rVert_2^2\right)=\left(\frac{\sigma}{\bar{\lambda}+\sigma}\right)^2\lVert\delta\rVert_2^2. ∥ S δ ∥ 2 2 = k : λ k ≤ λ ˉ ∑ ( λ k + σ σ ) 2 c k 2 + ∥ δ ⊥ ∥ 2 2 ≥ ( λ ˉ + σ σ ) 2 k : λ k ≤ λ ˉ ∑ c k 2 + ∥ δ ⊥ ∥ 2 2 = ( λ ˉ + σ σ ) 2 ∥ δ ∥ 2 2 . The inequality holds because λ ↦ σ / ( λ + σ ) \lambda\mapsto\sigma/(\lambda+\sigma) λ ↦ σ / ( λ + σ ) λ k ≤ λ ˉ \lambda_k\le\bar{\lambda} λ k ≤ λ ˉ σ / ( λ ˉ + σ ) \sigma/(\bar{\lambda}+\sigma) σ / ( λ ˉ + σ ) 1 ≥ σ / ( λ ˉ + σ ) 1\ge\sigma/(\bar{\lambda}+\sigma) 1 ≥ σ / ( λ ˉ + σ ) δ = ∑ k : λ k > λ ˉ c k u k \delta=\sum_{k:\lambda_k>\bar{\lambda}}c_k u_k δ = ∑ k : λ k > λ ˉ c k u k σ / ( λ ˉ + σ ) \sigma/(\bar{\lambda}+\sigma) σ / ( λ ˉ + σ ) ∥ S δ ∥ 2 ≤ λ ˉ + σ σ ∥ δ ∥ 2 \lVert S\delta\rVert_2\le\frac{\bar{\lambda}+\sigma}{\sigma}\lVert\delta\rVert_2 ∥ S δ ∥ 2 ≤ σ λ ˉ + σ ∥ δ ∥ 2 ( 1 − η λ ˉ ) T (1-\eta\bar{\lambda})^\mathsf{T} ( 1 − η λ ˉ ) T σ / ( λ ˉ + σ ) \sigma/(\bar{\lambda}+\sigma) σ / ( λ ˉ + σ ) λ ˉ ≤ 1 / η \bar{\lambda}\le1/\eta λ ˉ ≤ 1/ η λ ↦ ( 1 − η λ ) T \lambda\mapsto(1-\eta\lambda)^\mathsf{T} λ ↦ ( 1 − η λ ) T [ 0 , 1 / η ] [0,1/\eta] [ 0 , 1/ η ]
The reading of the slowly restored directions. A method of this kind confines the edit to the orthogonal complement of the top j j j j j j C C C λ j > λ j + 1 \lambda_j>\lambda_{j+1} λ j > λ j + 1 j < ϱ j<\varrho j < ϱ U λ ˉ U_{\bar{\lambda}} U λ ˉ λ ˉ ∈ [ λ j + 1 , λ j ) \bar{\lambda}\in[\lambda_{j+1},\lambda_j) λ ˉ ∈ [ λ j + 1 , λ j ) λ ˉ ∈ ( 0 , λ ϱ ) \bar{\lambda}\in(0,\lambda_\varrho) λ ˉ ∈ ( 0 , λ ϱ ) j = ϱ j=\varrho j = ϱ U λ ˉ U_{\bar{\lambda}} U λ ˉ span { u 1 , … , u j } \operatorname{span}\{u_1,\ldots,u_j\} span { u 1 , … , u j } [65 ] is a hypothesis of this form. The corollary is a statement about the filter of the linearized model of this paper. The published methods compute their spectra from the activations or gradients of deep networks and use their own losses, so the correspondence concerns the form of the constraint.
Proof of Remark A.1. In the linearized model the score of drawn edge i i i d i ( θ ∘ + δ ) = d i ( θ ∘ ) + ϕ i T δ d_i(\theta^\circ+\delta)=d_i(\theta^\circ)+\phi_i^\mathsf{T}\delta d i ( θ ∘ + δ ) = d i ( θ ∘ ) + ϕ i T δ θ ∘ + δ \theta^\circ+\delta θ ∘ + δ r = relu ( Φ δ ) r=\operatorname{relu}(\Phi\delta) r = relu ( Φ δ ) − ( C + Σ ) − 1 Φ T relu ( Φ δ ) -(C+\Sigma)^{-1}\Phi^\mathsf{T}\operatorname{relu}(\Phi\delta) − ( C + Σ ) − 1 Φ T relu ( Φ δ ) Φ δ ≤ 0 \Phi\delta\le0 Φ δ ≤ 0 r = 0 r=0 r = 0 θ ∘ + δ \theta^\circ+\delta θ ∘ + δ a = relu ( Φ δ ) ≥ 0 a=\operatorname{relu}(\Phi\delta)\ge0 a = relu ( Φ δ ) ≥ 0 Φ T a = 0 \Phi^\mathsf{T}a=0 Φ T a = 0 a T Φ δ = 0 a^\mathsf{T}\Phi\delta=0 a T Φ δ = 0 a i ( Φ δ ) i = relu ( ( Φ δ ) i ) 2 = a i 2 a_i(\Phi\delta)_i=\operatorname{relu}((\Phi\delta)_i)^2=a_i^2 a i ( Φ δ ) i = relu (( Φ δ ) i ) 2 = a i 2 a = 0 a=0 a = 0 Φ δ ≤ 0 \Phi\delta\le0 Φ δ ≤ 0 { δ : Φ δ ≤ 0 } \{\delta:\Phi\delta\le0\} { δ : Φ δ ≤ 0 } { δ : Φ δ = 0 } \{\delta:\Phi\delta=0\} { δ : Φ δ = 0 }
Proof of Proposition A.1, per-entity form. Fix a draw d d d θ \theta θ δ \delta δ e v e_v e v δ v \delta_v δ v v v v Φ v δ v \Phi_v\delta_v Φ v δ v A v A_v A v r v ( θ + δ ) = r v ( θ ) + Φ v δ v r_v(\theta+\delta)=r_v(\theta)+\Phi_v\delta_v r v ( θ + δ ) = r v ( θ ) + Φ v δ v
Δ e v ( θ + δ ) = − A v ( r v ( θ ) + Φ v δ v ) = Δ e v ( θ ) − A v Φ v δ v . \Delta e_v(\theta+\delta)=-A_v\bigl(r_v(\theta)+\Phi_v\delta_v\bigr)=\Delta e_v(\theta)-A_v\Phi_v\delta_v. Δ e v ( θ + δ ) = − A v ( r v ( θ ) + Φ v δ v ) = Δ e v ( θ ) − A v Φ v δ v . so e v + δ v + Δ e v ( θ + δ ) = e v + Δ e v ( θ ) + ( I − A v Φ v ) δ v = e v + Δ e v ( θ ) + P N , v ⊥ δ v e_v+\delta_v+\Delta e_v(\theta+\delta)=e_v+\Delta e_v(\theta)+(I-A_v\Phi_v)\delta_v=e_v+\Delta e_v(\theta)+P_{N,v}^{\perp}\delta_v e v + δ v + Δ e v ( θ + δ ) = e v + Δ e v ( θ ) + ( I − A v Φ v ) δ v = e v + Δ e v ( θ ) + P N , v ⊥ δ v δ v ∈ range ( Φ v T ) \delta_v\in\operatorname{range}(\Phi_v^\mathsf{T}) δ v ∈ range ( Φ v T ) δ v = ∑ k ≤ ϱ c k u k \delta_v=\sum_{k\le\varrho}c_k u_k δ v = ∑ k ≤ ϱ c k u k P N , v ⊥ δ v = ∑ k ≤ ϱ σ v λ k + σ v c k u k P_{N,v}^{\perp}\delta_v=\sum_{k\le\varrho}\frac{\sigma_v}{\lambda_k+\sigma_v}c_k u_k P N , v ⊥ δ v = ∑ k ≤ ϱ λ k + σ v σ v c k u k
∥ P N , v ⊥ δ v ∥ 2 2 = ∑ k ≤ ϱ ( σ v λ k + σ v ) 2 c k 2 ≤ ( σ v λ min + ( K v ) + σ v ) 2 ∥ δ v ∥ 2 2 . \lVert P_{N,v}^{\perp}\delta_v\rVert_2^2=\sum_{k\le\varrho}\left(\frac{\sigma_v}{\lambda_k+\sigma_v}\right)^2c_k^2\le\left(\frac{\sigma_v}{\lambda_{\min}^{+}(K_v)+\sigma_v}\right)^2\lVert\delta_v\rVert_2^2. ∥ P N , v ⊥ δ v ∥ 2 2 = k ≤ ϱ ∑ ( λ k + σ v σ v ) 2 c k 2 ≤ ( λ m i n + ( K v ) + σ v σ v ) 2 ∥ δ v ∥ 2 2 . the factor being largest on the direction of the smallest nonzero eigenvalue. Under first-order evaluation the anticipated score moves by ϕ f ( v ) T P N , v ⊥ δ v \phi_f^{(v)\mathsf{T}}P_{N,v}^{\perp}\delta_v ϕ f ( v ) T P N , v ⊥ δ v ∥ ϕ f ( v ) ∥ 2 \lVert\phi_f^{(v)}\rVert_2 ∥ ϕ f ( v ) ∥ 2
Consequence. Let ρ ^ f ( θ ) = d f ( θ ) − d f l i n ( θ ) \hat{\rho}_f(\theta)=d_f(\theta)-d_f^{\mathrm{lin}}(\theta) ρ ^ f ( θ ) = d f ( θ ) − d f lin ( θ ) δ v \delta_v δ v d f d_f d f ϕ f ( v ) T δ v \phi_f^{(v)\mathsf{T}}\delta_v ϕ f ( v ) T δ v ϕ f ( v ) T P N , v ⊥ δ v \phi_f^{(v)\mathsf{T}}P_{N,v}^{\perp}\delta_v ϕ f ( v ) T P N , v ⊥ δ v ρ ^ f \hat{\rho}_f ρ ^ f ϕ f ( v ) T ( I − P N , v ⊥ ) δ v = ϕ f ( v ) T A v Φ v δ v \phi_f^{(v)\mathsf{T}}(I-P_{N,v}^{\perp})\delta_v=\phi_f^{(v)\mathsf{T}}A_v\Phi_v\delta_v ϕ f ( v ) T ( I − P N , v ⊥ ) δ v = ϕ f ( v ) T A v Φ v δ v ϕ f ( v ) T δ v \phi_f^{(v)\mathsf{T}}\delta_v ϕ f ( v ) T δ v ϕ f ( v ) T P N , v ⊥ δ v \phi_f^{(v)\mathsf{T}}P_{N,v}^{\perp}\delta_v ϕ f ( v ) T P N , v ⊥ δ v ∥ ϕ f ( v ) ∥ 2 \lVert\phi_f^{(v)}\rVert_2 ∥ ϕ f ( v ) ∥ 2 f f f ϕ f ( v ) T δ v < 0 \phi_f^{(v)\mathsf{T}}\delta_v<0 ϕ f ( v ) T δ v < 0 ρ ^ f \hat{\rho}_f ρ ^ f relu ( t f − d f ( θ ) ) 2 + ζ relu ( ρ ^ f ) 2 \operatorname{relu}(t_f-d_f(\theta))^2+\zeta\operatorname{relu}(\hat{\rho}_f)^2 relu ( t f − d f ( θ ) ) 2 + ζ relu ( ρ ^ f ) 2 min { d f ( θ ) , d f ( θ + Δ θ ) } \min\{d_f(\theta),d_f(\theta+\Delta\theta)\} min { d f ( θ ) , d f ( θ + Δ θ )}
Expected force of the margin-loss update
This subsection supports the choice of the one-sided residual equation 4 in Section 4.1. The margin loss of the update on edge i i i ℓ i = max { 0 , d i − n ˉ i + γ } \ell_i=\max\{0,d_i-\bar n_i+\gamma\} ℓ i = max { 0 , d i − n ˉ i + γ } γ \gamma γ n ˉ i \bar n_i n ˉ i K K K i i i K = 10 K=10 K = 10 γ = 8 \gamma=8 γ = 8 μ i \mu_i μ i i i i θ ∘ \theta^\circ θ ∘ τ n \tau_n τ n K K K n ˉ i \bar n_i n ˉ i μ i \mu_i μ i K \sqrt{K} K Φ G \Phi_{\mathrm{G}} Φ G ϕ G \phi_{\mathrm{G}} ϕ G
Lemma A.2 (Expected margin force). Model n ˉ i ∼ Normal ( μ i , τ n 2 ) \bar n_i\sim\operatorname{Normal}(\mu_i,\tau_n^2) n ˉ i ∼ Normal ( μ i , τ n 2 ) g i = μ i − γ g_i=\mu_i-\gamma g i = μ i − γ d i d_i d i
E [ ∂ ℓ i ∂ d i ] = Pr ( n ˉ i < d i + γ ) = Φ G ( d i − g i τ n ) , \mathbb{E}\left[\frac{\partial\ell_i}{\partial d_i}\right]=\Pr(\bar n_i<d_i+\gamma)=\Phi_{\mathrm{G}}\left(\frac{d_i-g_i}{\tau_n}\right), E [ ∂ d i ∂ ℓ i ] = Pr ( n ˉ i < d i + γ ) = Φ G ( τ n d i − g i ) , E [ ℓ i ] = τ n ψ ( d i − g i τ n ) , ψ ( z ) = z Φ G ( z ) + ϕ G ( z ) , \mathbb{E}[\ell_i]=\tau_n\psi\left(\frac{d_i-g_i}{\tau_n}\right),\qquad\psi(z)=z\Phi_{\mathrm{G}}(z)+\phi_{\mathrm{G}}(z), E [ ℓ i ] = τ n ψ ( τ n d i − g i ) , ψ ( z ) = z Φ G ( z ) + ϕ G ( z ) , and ψ ′ = Φ G \psi'=\Phi_{\mathrm{G}} ψ ′ = Φ G d i − g i d_i-g_i d i − g i τ n \tau_n τ n
Proof. Almost surely ∂ ℓ i / ∂ d i = 1 [ d i − n ˉ i + γ > 0 ] \partial\ell_i/\partial d_i=\mathbf{1}[d_i-\bar n_i+\gamma>0] ∂ ℓ i / ∂ d i = 1 [ d i − n ˉ i + γ > 0 ] Pr ( n ˉ i < d i + γ ) = Φ G ( ( d i + γ − μ i ) / τ n ) \Pr(\bar n_i<d_i+\gamma)=\Phi_{\mathrm{G}}((d_i+\gamma-\mu_i)/\tau_n) Pr ( n ˉ i < d i + γ ) = Φ G (( d i + γ − μ i ) / τ n ) n ˉ i = μ i + τ n ξ \bar n_i=\mu_i+\tau_n\xi n ˉ i = μ i + τ n ξ ξ ∼ Normal ( 0 , 1 ) \xi\sim\operatorname{Normal}(0,1) ξ ∼ Normal ( 0 , 1 ) z = ( d i − g i ) / τ n z=(d_i-g_i)/\tau_n z = ( d i − g i ) / τ n ℓ i = τ n ( z − ξ ) + \ell_i=\tau_n(z-\xi)_+ ℓ i = τ n ( z − ξ ) +
E [ ( z − ξ ) + ] = ∫ − ∞ z ( z − ξ ) ϕ G ( ξ ) d ξ = z Φ G ( z ) + ϕ G ( z ) , \mathbb{E}[(z-\xi)_+]=\int_{-\infty}^{z}(z-\xi)\phi_{\mathrm{G}}(\xi)\,\mathrm{d}\xi=z\Phi_{\mathrm{G}}(z)+\phi_{\mathrm{G}}(z), E [( z − ξ ) + ] = ∫ − ∞ z ( z − ξ ) ϕ G ( ξ ) d ξ = z Φ G ( z ) + ϕ G ( z ) , using ∫ − ∞ z ξ ϕ G ( ξ ) d ξ = − ϕ G ( z ) \int_{-\infty}^{z}\xi\phi_{\mathrm{G}}(\xi)\,\mathrm{d}\xi=-\phi_{\mathrm{G}}(z) ∫ − ∞ z ξ ϕ G ( ξ ) d ξ = − ϕ G ( z ) ψ ′ ( z ) = Φ G ( z ) + z ϕ G ( z ) − z ϕ G ( z ) \psi'(z)=\Phi_{\mathrm{G}}(z)+z\phi_{\mathrm{G}}(z)-z\phi_{\mathrm{G}}(z) ψ ′ ( z ) = Φ G ( z ) + z ϕ G ( z ) − z ϕ G ( z ) ψ ′ ( z ) = Φ G ( z ) \psi'(z)=\Phi_{\mathrm{G}}(z) ψ ′ ( z ) = Φ G ( z )
The one-sided residual as the zero-slack bound. Define the slack of edge i i i ς i = g i − d i ( θ ∘ ) \varsigma_i=g_i-d_i(\theta^\circ) ς i = g i − d i ( θ ∘ ) ς i > 0 \varsigma_i>0 ς i > 0 θ ∘ \theta^\circ θ ∘ ς i \varsigma_i ς i τ n → 0 \tau_n\to0 τ n → 0 τ n ψ ( a / τ n ) → a + \tau_n\psi(a/\tau_n)\to a_+ τ n ψ ( a / τ n ) → a + a a a ( d i − d i ( θ ∘ ) − ς i ) + (d_i-d_i(\theta^\circ)-\varsigma_i)_+ ( d i − d i ( θ ∘ ) − ς i ) + 1 [ d i > d i ( θ ∘ ) + ς i ] \mathbf{1}[d_i>d_i(\theta^\circ)+\varsigma_i] 1 [ d i > d i ( θ ∘ ) + ς i ] r i = relu ( d i ( θ ) − d i ( θ ∘ ) ) r_i=\operatorname{relu}(d_i(\theta)-d_i(\theta^\circ)) r i = relu ( d i ( θ ) − d i ( θ ∘ )) ς i ≥ 0 \varsigma_i\geq0 ς i ≥ 0 τ n > 0 \tau_n>0 τ n > 0 θ ∘ \theta^\circ θ ∘
E [ ℓ i ] ( d i ) − E [ ℓ i ] ( d i ( θ ∘ ) ) ≤ relu ( d i − d i ( θ ∘ ) ) , \mathbb{E}[\ell_i](d_i)-\mathbb{E}[\ell_i](d_i(\theta^\circ))\leq\operatorname{relu}\left(d_i-d_i(\theta^\circ)\right), E [ ℓ i ] ( d i ) − E [ ℓ i ] ( d i ( θ ∘ )) ≤ relu ( d i − d i ( θ ∘ ) ) , because E [ ℓ i ] \mathbb{E}[\ell_i] E [ ℓ i ] Φ G ≤ 1 \Phi_{\mathrm{G}}\leq1 Φ G ≤ 1 a > 0 a>0 a > 0 a a a
Why inert edges move. The gate also explains why edges that never violate their margin are restored. Let A γ ⊆ P v ( N ) \mathcal{A}_{\gamma}\subseteq\mathcal{P}_v(N) A γ ⊆ P v ( N ) Δ e v = − Φ A γ ( Φ A γ Φ A γ T + σ v I ) − 1 r A γ \Delta e_v=-\Phi_{\mathcal{A}_\gamma}(\Phi_{\mathcal{A}_\gamma}\Phi_{\mathcal{A}_\gamma}^{\mathsf{T}}+\sigma_v I)^{-1}r_{\mathcal{A}_\gamma} Δ e v = − Φ A γ ( Φ A γ Φ A γ T + σ v I ) − 1 r A γ Φ − A γ Δ e v \Phi_{-\mathcal{A}_\gamma}\Delta e_v Φ − A γ Δ e v d v d_v d v δ v \delta_v δ v e v e_v e v − ϕ v ( v ) -\phi_v^{(v)} − ϕ v ( v ) − δ v -\delta_v − δ v δ v \delta_v δ v
Expected loss over the update class
This subsection supports the statement of Section 4.1 that the loss is averaged over draws and is never applied to an averaged response.
Lemma A.3 (Expected loss over draws). Let ℓ f ( d ) = relu ( t f − d ) 2 \ell_f(d)=\operatorname{relu}(t_f-d)^2 ℓ f ( d ) = relu ( t f − d ) 2 forgetting loss of equation (2) , which is convex and non-increasing in d d d d f l i n ( θ ; N ) = d f ( θ ) + ∑ v ϕ f ( v ) ⊤ Δ e ( v ) ( θ ; N ) d_f^{\mathrm{lin}}(\theta;N)=d_f(\theta)+\sum_v\phi_f^{(v)\top}\Delta_e^{(v)}(\theta;N) d f lin ( θ ; N ) = d f ( θ ) + ∑ v ϕ f ( v ) ⊤ Δ e ( v ) ( θ ; N ) E N [ d f l i n ( θ ; N ) ] \mathbb{E}_N[d_f^{\mathrm{lin}}(\theta;N)] E N [ d f lin ( θ ; N )] E N [ Δ θ ( θ ; N ) ] \mathbb{E}_N[\Delta\theta(\theta;N)] E N [ Δ θ ( θ ; N )]
ℓ f ( E N [ d f l i n ( θ ; N ) ] ) ≤ E N [ ℓ f ( d f l i n ( θ ; N ) ) ] ≤ max N ℓ f ( d f l i n ( θ ; N ) ) . \ell_f\left(\mathbb{E}_N[d_f^{\mathrm{lin}}(\theta;N)]\right)\leq\mathbb{E}_N\left[\ell_f(d_f^{\mathrm{lin}}(\theta;N))\right]\leq\max_N\ell_f(d_f^{\mathrm{lin}}(\theta;N)). ℓ f ( E N [ d f lin ( θ ; N )] ) ≤ E N [ ℓ f ( d f lin ( θ ; N )) ] ≤ N max ℓ f ( d f lin ( θ ; N )) . Proof. The left inequality is Jensen’s inequality for the convex function ℓ f \ell_f ℓ f
The loss of the expected response therefore underestimates the expected loss, and the expected loss lies between it and the worst case over the class. This is why equation (3) averages the loss over draws and never applies it to an averaged response. The expected-draw row of Table 17 replaces the random inclusion of edges by the response Δ θ W = − Φ ⊤ W 1 / 2 ( W 1 / 2 Φ Φ ⊤ W 1 / 2 + σ I ) − 1 W 1 / 2 r \Delta\theta_W=-\Phi^\top W^{1/2}(W^{1/2}\Phi\Phi^\top W^{1/2}+\sigma I)^{-1}W^{1/2}r Δ θ W = − Φ ⊤ W 1/2 ( W 1/2 Φ Φ ⊤ W 1/2 + σ I ) − 1 W 1/2 r W W W E N [ Δ θ ( θ ; N ) ] \mathbb{E}_N[\Delta\theta(\theta;N)] E N [ Δ θ ( θ ; N )]
Block-diagonal versus joint response
This subsection supports the statement of § 4.2 that the per-entity form counts the residual of a shared edge once at each endpoint. Stack the involved rows as Δ = ( Δ e ) v ∈ R m ∣ V F ∣ \Delta=(\Delta_e)_v\in\mathbb{R}^{m|\mathcal{V}_F|} Δ = ( Δ e ) v ∈ R m ∣ V F ∣ Φ ∈ R ∣ N ∣ × m ∣ V F ∣ \Phi\in\mathbb{R}^{|N|\times m|\mathcal{V}_F|} Φ ∈ R ∣ N ∣ × m ∣ V F ∣ i i i ϕ i ( h ) ⊤ \phi_i^{(h)\top} ϕ i ( h ) ⊤ ϕ i ( t ) ⊤ \phi_i^{(t)\top} ϕ i ( t ) ⊤ Σ = diag ( σ v I m ) v \Sigma=\operatorname{diag}(\sigma_v I_m)_v Σ = diag ( σ v I m ) v ( Φ ⊤ Φ + Σ ) Δ = − Φ ⊤ r (\Phi^\top\Phi+\Sigma)\Delta=-\Phi^\top r ( Φ ⊤ Φ + Σ ) Δ = − Φ ⊤ r v v v ( Φ v ⊤ Φ v + σ v I ) Δ e b d = − Φ v ⊤ r v (\Phi_v^\top\Phi_v+\sigma_v I)\Delta_e^{\mathrm{bd}}=-\Phi_v^\top r_v ( Φ v ⊤ Φ v + σ v I ) Δ e bd = − Φ v ⊤ r v Δ e b d = − A v r v \Delta_e^{\mathrm{bd}}=-A_vr_v Δ e bd = − A v r v Δ b d \Delta^{\mathrm{bd}} Δ bd
Lemma A.4 (Block-diagonal versus joint response). The off-diagonal block of Φ ⊤ Φ \Phi^\top\Phi Φ ⊤ Φ v ≠ u v\ne u v = u ∑ i ∋ v , u ϕ i ( v ) ϕ i ( u ) ⊤ \sum_{i\ni v,u}\phi_i^{(v)}\phi_i^{(u)\top} ∑ i ∋ v , u ϕ i ( v ) ϕ i ( u ) ⊤ v v v u u u σ v → 0 \sigma_v\to0 σ v → 0 i i i r i ≠ 0 r_i\ne0 r i = 0 ϕ i ⊤ Δ b d = − 2 r i \phi_i^\top\Delta^{\mathrm{bd}}=-2r_i ϕ i ⊤ Δ bd = − 2 r i ϕ i ⊤ Δ = − r i \phi_i^\top\Delta=-r_i ϕ i ⊤ Δ = − r i
Proof. The block structure follows from Φ ⊤ Φ = ∑ i ϕ i ϕ i ⊤ \Phi^\top\Phi=\sum_i\phi_i\phi_i^\top Φ ⊤ Φ = ∑ i ϕ i ϕ i ⊤ ϕ i \phi_i ϕ i Φ ⊤ Φ + Σ \Phi^\top\Phi+\Sigma Φ ⊤ Φ + Σ σ v → 0 \sigma_v\to0 σ v → 0 Φ v \Phi_v Φ v Φ v Δ e b d = − Φ v Φ v ⊤ K v − 1 r v = − r v \Phi_v\Delta_e^{\mathrm{bd}}=-\Phi_v\Phi_v^\top K_v^{-1}r_v=-r_v Φ v Δ e bd = − Φ v Φ v ⊤ K v − 1 r v = − r v ϕ i ⊤ Δ b d = ϕ i ( h ) ⊤ Δ e b d + ϕ i ( t ) ⊤ Δ e b d = − 2 r i \phi_i^\top\Delta^{\mathrm{bd}}=\phi_i^{(h)\top}\Delta_e^{\mathrm{bd}}+\phi_i^{(t)\top}\Delta_e^{\mathrm{bd}}=-2r_i ϕ i ⊤ Δ bd = ϕ i ( h ) ⊤ Δ e bd + ϕ i ( t ) ⊤ Δ e bd = − 2 r i Φ Δ = − r \Phi\Delta=-r ΦΔ = − r Φ ( Φ ⊤ Φ + Σ ) − 1 Φ ⊤ = K ~ ( K ~ + I ) − 1 \Phi(\Phi^\top\Phi+\Sigma)^{-1}\Phi^\top=\widetilde K(\widetilde K+I)^{-1} Φ ( Φ ⊤ Φ + Σ ) − 1 Φ ⊤ = K ( K + I ) − 1 K ~ = Φ Σ − 1 Φ ⊤ ⪰ Φ Φ ⊤ / max v σ v \widetilde K=\Phi\Sigma^{-1}\Phi^\top\succeq\Phi\Phi^\top/\max_v\sigma_v K = Φ Σ − 1 Φ ⊤ ⪰ Φ Φ ⊤ / max v σ v Φ \Phi Φ ϕ i ⊤ Δ = − r i \phi_i^\top\Delta=-r_i ϕ i ⊤ Δ = − r i
The joint system is symmetric positive definite of dimension m ∣ V F ∣ m|\mathcal{V}_F| m ∣ V F ∣ (Hestenes and Stiefel, 1952) without forming a matrix. Each iteration costs one product with Φ \Phi Φ Φ ⊤ \Phi^\top Φ ⊤ Σ \Sigma Σ
Within-row isotropy and the ridge
This subsection supports the statement of § 4.2 that the response leaves out Adam’s per-coordinate scaling. Remark A.4 (Within-row isotropy). For the TransE score the coordinates of the slot feature in equation (10) are ϕ i j ( v ) = ± ( s i j − e ˉ v j ( e ˉ v ⊤ s i ) ) / ∥ e v ∥ 2 \phi_{ij}^{(v)}=\pm(s_{ij}-\bar e_{vj}(\bar e_v^\top s_i))/\lVert e_v\rVert_2 ϕ ij ( v ) = ± ( s ij − e ˉ v j ( e ˉ v ⊤ s i )) / ∥ e v ∥ 2 s i s_i s i s i j ∈ { ± 1 } s_{ij}\in\{\pm1\} s ij ∈ { ± 1 }
∣ ∣ ϕ i j ( v ) ∣ ∥ e v ∥ 2 − 1 ∣ ≤ ∣ e ˉ v j ∣ ∣ e ˉ v ⊤ s i ∣ for every coordinate j , \left|\left|\phi_{ij}^{(v)}\right|\lVert e_v\rVert_2-1\right|\leq\left|\bar e_{vj}\right|\left|\bar e_v^\top s_i\right|\qquad\text{for every coordinate }j, ϕ ij ( v ) ∥ e v ∥ 2 − 1 ≤ ∣ e ˉ v j ∣ e ˉ v ⊤ s i for every coordinate j , by expanding ( I − e ˉ v e ˉ v T ) s i (\mathbf{I}-\bar{e}_v\bar{e}_v^{\mathsf{T}})s_i ( I − e ˉ v e ˉ v T ) s i ∣ s i j ∣ = 1 |s_{ij}|=1 ∣ s ij ∣ = 1 m m m ∣ e ˉ v j ∣ |\bar{e}_{vj}| ∣ e ˉ v j ∣ m − 1 / 2 m^{-1/2} m − 1/2 ∣ e ˉ v T s i ∣ |\bar{e}_v^{\mathsf{T}}s_i| ∣ e ˉ v T s i ∣ v v v 1 / ∥ e ˉ v ∥ 2 1/\|\bar{e}_v\|_2 1/∥ e ˉ v ∥ 2 1 / ∥ e v ∥ 2 1/\|e_v\|_2 1/∥ e v ∥ 2 V V V [34 ] is then approximately a scalar per row, so the Adam-preconditioned kernel Φ V − 1 Φ T \Phi V^{-1}\Phi^{\mathsf{T}} Φ V − 1 Φ T ⟨ sign ϕ i , sign ϕ j ⟩ \langle\operatorname{sign}\phi_i,\operatorname{sign}\phi_j\rangle ⟨ sign ϕ i , sign ϕ j ⟩ [74 ] is Euclidean orthogonality up to row scalars. Those scalars can be absorbed in a per-entity ridge, which is the second consequence, and it is stated as a hypothesis. Dense Adam over the embedding table keeps a second-moment average per coordinate, so for a row that receives gradient in a fraction p v p_v p v p v p_v p v η / p v \eta/\sqrt{p_v} η / p v T T T η T p v \eta T\sqrt{p_v} η T p v η T p v \eta T p_v η T p v η v ∝ p v \eta_v\propto\sqrt{p_v} η v ∝ p v
σ v = σ 0 ( p v p m e d ) − κ , \sigma_v=\sigma_0\left(\frac{p_v}{p_{\mathrm{med}}}\right)^{-\kappa}, σ v = σ 0 ( p med p v ) − κ , κ = 1 2 (Adam) , κ = 1 (stochastic gradient descent) , κ = 0 (degree-independent) , \kappa=\frac{1}{2}\ \text{(Adam)},\qquad\kappa=1\ \text{(stochastic gradient descent)},\qquad\kappa=0\ \text{(degree-independent)}, κ = 2 1 (Adam) , κ = 1 (stochastic gradient descent) , κ = 0 (degree-independent) , with p v p_v p v v v v p m e d p_{\mathrm{med}} p med p v \sqrt{p_v} p v κ = 0 \kappa=0 κ = 0 σ v \sigma_v σ v v v v § 4.2 ).
Piecewise-linear scores and exact evaluation
The anticipated score is evaluated at the shifted rows for a reason that holds on every backbone. The score is nonlinear in the rows, and the displacement the update produces is not small on the scale of the coordinate differences from which the score is built. On an L 1 L_1 L 1
Lemma A.5 (Piecewise-linear scores). For real x x x D D D sign 0 = 1 \operatorname{sign}0=1 sign 0 = 1
∣ x + D ∣ − ∣ x ∣ = sign ( x ) D + 2 ( ∣ D ∣ − ∣ x ∣ ) + 1 [ sign D ≠ sign x ] . (15) |x+D|-|x|=\operatorname{sign}(x)D+2\bigl(|D|-|x|\bigr)_+\mathbf{1}\bigl[\operatorname{sign}D\ne\operatorname{sign}x\bigr]. \tag*{(15)} ∣ x + D ∣ − ∣ x ∣ = sign ( x ) D + 2 ( ∣ D ∣ − ∣ x ∣ ) + 1 [ sign D = sign x ] . (15) The second term is non-negative, vanishes whenever ∣ D ∣ ≤ ∣ x ∣ |D|\le|x| ∣ D ∣ ≤ ∣ x ∣ 2 ( ∣ D ∣ − ∣ x ∣ ) 2(|D|-|x|) 2 ( ∣ D ∣ − ∣ x ∣ ) ∣ D ∣ |D| ∣ D ∣ ∣ D ∣ > ∣ x ∣ |D|>|x| ∣ D ∣ > ∣ x ∣ D D D x x x
Proof. If sign D = sign x \operatorname{sign}D=\operatorname{sign}x sign D = sign x ∣ x + D ∣ = ∣ x ∣ + ∣ D ∣ |x+D|=|x|+|D| ∣ x + D ∣ = ∣ x ∣ + ∣ D ∣ sign ( x ) D = ∣ D ∣ \operatorname{sign}(x)D=|D| sign ( x ) D = ∣ D ∣ ∣ D ∣ |D| ∣ D ∣ sign D ≠ sign x \operatorname{sign}D\ne\operatorname{sign}x sign D = sign x ∣ D ∣ ≤ ∣ x ∣ |D|\le|x| ∣ D ∣ ≤ ∣ x ∣ x + D x+D x + D x x x ∣ x + D ∣ = ∣ x ∣ − ∣ D ∣ = ∣ x ∣ + sign ( x ) D |x+D|=|x|-|D|=|x|+\operatorname{sign}(x)D ∣ x + D ∣ = ∣ x ∣ − ∣ D ∣ = ∣ x ∣ + sign ( x ) D ( ∣ D ∣ − ∣ x ∣ ) + = 0 (|D|-|x|)_+=0 ( ∣ D ∣ − ∣ x ∣ ) + = 0 sign D ≠ sign x \operatorname{sign}D\ne\operatorname{sign}x sign D = sign x ∣ D ∣ > ∣ x ∣ |D|>|x| ∣ D ∣ > ∣ x ∣ x + D x+D x + D D D D ( ∣ D ∣ − ∣ x ∣ ) − ∣ x ∣ = ∣ D ∣ − 2 ∣ x ∣ (|D|-|x|)-|x|=|D|-2|x| ( ∣ D ∣ − ∣ x ∣ ) − ∣ x ∣ = ∣ D ∣ − 2∣ x ∣ sign ( x ) D + 2 ( ∣ D ∣ − ∣ x ∣ ) = − ∣ D ∣ + 2 ∣ D ∣ − 2 ∣ x ∣ = ∣ D ∣ − 2 ∣ x ∣ \operatorname{sign}(x)D+2(|D|-|x|)= -|D|+2|D|-2|x|=|D|-2|x| sign ( x ) D + 2 ( ∣ D ∣ − ∣ x ∣ ) = − ∣ D ∣ + 2∣ D ∣ − 2∣ x ∣ = ∣ D ∣ − 2∣ x ∣ x = 0 x=0 x = 0 sign 0 = 1 \operatorname{sign}0=1 sign 0 = 1 D > 0 D>0 D > 0 D < 0 D<0 D < 0 ∣ D ∣ |D| ∣ D ∣ □ \square □
For a triple with translation error x = e ˉ b + w ˉ r − e ˉ t x=\bar{e}_b+\bar{w}_r-\bar{e}_t x = e ˉ b + w ˉ r − e ˉ t d x = ∥ x ∥ 1 d_x=\|x\|_1 d x = ∥ x ∥ 1 D D D (15) over coordinates gives d x ( θ + Δ θ ) − d x ( θ ) = s T D + ϰ ( D ) d_x(\theta+\Delta\theta)-d_x(\theta)=s^{\mathsf{T}}D+\varkappa(D) d x ( θ + Δ θ ) − d x ( θ ) = s T D + ϰ ( D ) s = sign ( x ) s=\operatorname{sign}(x) s = sign ( x ) ϰ ≥ 0 \varkappa\ge0 ϰ ≥ 0 ϕ x T Δ θ \phi_x^{\mathsf{T}}\Delta\theta ϕ x T Δ θ ∣ D j ∣ ≤ ∣ x j ∣ |D_j|\le|x_j| ∣ D j ∣ ≤ ∣ x j ∣ D D D ∣ x j ∣ |x_j| ∣ x j ∣ ∣ D j ∣ |D_j| ∣ D j ∣ ∣ x j ∣ |x_j| ∣ x j ∣ § 10 .§ 5 measures the consequence. Evaluating the score at the shifted rows captures both terms at the cost of one call to the score function, which is why KAU does so.
Method details
Section 4 defines the objective and names its parts. This appendix builds them. The first six subsections give the update draw, the targets, the composition rule, the refraction rule, the score-preservation term and the selection rule. The seventh lists one run as Algorithm 1. The eighth gives the three backbones and the way a slot feature is taken from each. The last three give every hyperparameter, the cost of a run, and three constructions the derivation admits that we do not use. Everything here is computed from the original model θ o \theta^o θ o F \mathcal{F} F D R \mathcal{D}_R D R
The update draw and its stand-ins
The unlearner never learns which edges the update will use, so it models that edge set as a random draw with two channels. The known channel is made of the unlearner’s own retained edges. At an involved entity v v v v v v ρ k n \rho_{\mathrm{kn}} ρ kn v v v
The unseen channel stands in for true edges that were in no training set. The unlearner has never seen such an edge, so it manufactures stand-ins. It keeps a pool of 32 stand-in triples at every involved entity, and each stand-in is built in two steps. A relation is drawn from the empirical relation profile of v v v F \mathcal{F} F D R \mathcal{D}_{R} D R min { 1 , ρ u n deg ( v ) / 32 } \min\{1,\rho_{\mathrm{un}}\deg(v)/32\} min { 1 , ρ un deg ( v ) /32 } v v v min { 32 , ρ u n deg ( v ) } \min\{32,\rho_{\mathrm{un}}\deg(v)\} min { 32 , ρ un deg ( v )}
Every draw obeys two constraints. At most k max = 96 k_{\max}=96 k m a x = 96 v v v m − 1 m-1 m − 1 § 8 .8), and m m m v v v § 4.2 , Appendix § 7 .§ 6 ). The second constraint is that a fresh draw is taken at every forgetting step, so the objective is the expected loss over the class. Over a run each known edge is drawn several times.
The residual of equation (4) is evaluated on the drawn edges at the current parameters. For a stand-in it uses that triple’s own score under the original model. A forgotten fact carries no residual, and its loss is measured against the target of Appendix § 8 .§ 2 .
Targets
The target t f t_f t f θ ∘ \theta^{\circ} θ ∘ q f q_f q f (7) is t f = d f ( θ ∘ ) + s relu ( q f − d f ( θ ∘ ) ) t_f=d_f(\theta^{\circ})+s\operatorname{relu}(q_f-d_f(\theta^{\circ})) t f = d f ( θ ∘ ) + s relu ( q f − d f ( θ ∘ )) s = 0.15 s=0.15 s = 0.15 t f t_f t f § 8 .§ 5 and the two ancillaries of Appendices § 8 .§ 4 and § 8 .§ 6 leave those targets alone and act on the rows instead.
Pessimistic composition
The loss of equation (3) acts on d ~ f = min { d f ( θ ) , d f ( θ + Δ θ ) } \tilde{d}_f=\min\{d_f(\theta),d_f(\theta+\Delta\theta)\} d ~ f = min { d f ( θ ) , d f ( θ + Δ θ )}
d ~ f = d f ( θ + Δ θ ) − sg [ relu ( d f ( θ + Δ θ ) − d f ( θ ) ) ] . \tilde{d}_f=d_f(\theta+\Delta\theta)-\operatorname{sg}\left[\operatorname{relu}\left(d_f(\theta+\Delta\theta)-d_f(\theta)\right)\right]. d ~ f = d f ( θ + Δ θ ) − sg [ relu ( d f ( θ + Δ θ ) − d f ( θ ) ) ] . with sg the stop-gradient, which has the value of the minimum and the gradient of the anticipated score. The optimizer step therefore always targets the post-update position. Because of the minimum, a predicted rise of the fact’s score cannot lower the loss, which closes the shortcut of § 4.1 .
Retraction
After every optimizer step, each edited entity row is rescaled to the length it had under the original model, e v ← ∥ e v ∘ ∥ 2 e v / ∥ e v ∥ 2 e_v\leftarrow\lVert e_v^{\circ}\rVert_2e_v/\lVert e_v\rVert_2 e v ← ∥ e v ∘ ∥ 2 e v / ∥ e v ∥ 2 v v v 1 / ∥ e v ∥ 2 1/\lVert e_v\rVert_2 1/ ∥ e v ∥ 2 [2 ] ; Heo et al. [24 ] ). For TransE and TransH the length is a gauge, because the score normalizes the rows inside its own forward pass, and retraction only fixes that gauge. For RotatE the length enters the score, so retraction is a genuine constraint on the edit. KAU retracts on all three backbones, and Appendix § 10 .§ 3 reads the row without retraction beside the full method and shows that the result does not rest on norm inflation.
Score preservation
The retained pass carries the ordinary margin-ranking loss on retained edges and the second term of the objective of equation 9 in Section 4, β mean i ( d i ( θ ) − d i ( θ ∘ ) ) 2 \beta\ \operatorname{mean}_{i}(d_i(\theta)-d_i(\theta^\circ))^2 β mean i ( d i ( θ ) − d i ( θ ∘ ) ) 2 Table 16 switches it off and Table 17 replaces it by a relational anchor, rows that Appendix § 10 .§ 3 reads beside the retraction row. A retained edge that the edit has pushed above its original score is an edge the update will pull back, and pulling it back drags the forgotten facts with it.
Selection
Once per epoch the run evaluates its current checkpoint and scores it by 0.7 ( 1 − M R R F ) + 0.3 M R R R 0.7\left(1-\mathrm{MRR}_{F}\right)+0.3\mathrm{MRR}_{R} 0.7 ( 1 − MRR F ) + 0.3 MRR R § 9 .§ 1 ). The released model is the maximizer over the epochs of the run. This is GraphDPO’s own rule applied unchanged, and it consults neither the retrained model nor any edge of the update. Its weight 0.7 is the value that Appendix § 9 .§ 2 selects for the checkpoint-rule weight. It chooses the checkpoint within a run. Hyperparameters are chosen before the run, by the criterion that every method shares (Appendix § 9 .§ 2 ).
The full procedure
Algorithm 1 lists one run of KAU. During the run only the rows of V F \mathcal{V}_{F} V F θ ∘ \theta^\circ θ ∘ B \mathcal{B} B V F \mathcal{V}_{F} V F J J J B \mathcal{B} B ℓ M R ( B ) \ell_{\mathrm{MR}}(\mathcal{B}) ℓ MR ( B ) ℓ R ( θ ; S ) \ell_{R}(\theta;\mathcal{S}) ℓ R ( θ ; S ) S \mathcal{S} S ADAM ( θ , L ) \operatorname{ADAM}(\theta,L) ADAM ( θ , L ) L L L V F \mathcal{V}_{F} V F θ ∘ \theta^\circ θ ∘ § 8 .§ 4 ). The stop-gradient sg keeps the features out of the gradient, and CG solves equation 6 by conjugate gradients without forming the matrix. The checkpoint score SELECT is the rule of Appendix § 8 .§ 6 , and the stand-in pools of Appendix § 8 .§ 1 are rebuilt every five epochs. The epoch count E E E s s s § 9 .§ 2 ).
Algorithm 1 KAU, one unlearning run
Require: original model θ ∘ \theta^\circ θ ∘ F \mathcal{F} F D R \mathcal{D}_{R} D R N ^ \widehat{\mathcal{N}} N σ r e l \sigma_{\mathrm{rel}} σ rel β \beta β s s s E E E J J J
Ensure: released model θ u \theta_u θ u
θ ← θ ∘ \theta\leftarrow\theta^\circ θ ← θ ∘
t f ← d f ( θ ∘ ) + s relu ( q f − d f ( θ ∘ ) ) t_f \leftarrow d_f(\theta^\circ)+s\ \operatorname{relu}\left(q_f-d_f(\theta^\circ)\right) t f ← d f ( θ ∘ ) + s relu ( q f − d f ( θ ∘ ) ) f ∈ F f\in\mathcal{F} f ∈ F
for e = 1 e=1 e = 1 E E E do
for each batch B \mathcal{B} B V F \mathcal{V}_{F} V F do
S ← \mathcal{S}\leftarrow S ← V F \mathcal{V}_{F} V F
θ ← RETRACT ( ADAM ( θ , ℓ M R ( B ) + β ℓ R ( θ ; S ) ) ) \theta\leftarrow\operatorname{RETRACT}\left(\operatorname{ADAM}\left(\theta,\ell_{\mathrm{MR}}(\mathcal{B})+\beta\ell_{R}(\theta;\mathcal{S})\right)\right) θ ← RETRACT ( ADAM ( θ , ℓ MR ( B ) + β ℓ R ( θ ; S ) ) )
for j = 1 j=1 j = 1 J J J do
N ∼ N ^ N\sim\widehat{\mathcal{N}} N ∼ N
Φ ← sg [ ∂ d N ( θ ) / ∂ e V F ] , r ← r N ( θ ) \Phi\leftarrow\operatorname{sg}\left[\partial d_N(\theta)/\partial e_{\mathcal{V}_{F}}\right],\quad r\leftarrow r_N(\theta) Φ ← sg [ ∂ d N ( θ ) / ∂ e V F ] , r ← r N ( θ )
Σ ← diag ( σ v I ) , σ v = σ r e l mean i ∥ ϕ i ( v ) ∥ 2 2 \Sigma\leftarrow\operatorname{diag}(\sigma_v I),\quad\sigma_v=\sigma_{\mathrm{rel}}\operatorname{mean}_{i}\lVert\phi_i^{(v)}\rVert_2^2 Σ ← diag ( σ v I ) , σ v = σ rel mean i ∥ ϕ i ( v ) ∥ 2 2
Δ ← CG ( Φ T Φ + Σ , − Φ T r ) \Delta\leftarrow\operatorname{CG}(\Phi^{\mathsf{T}}\Phi+\Sigma,-\Phi^{\mathsf{T}}r) Δ ← CG ( Φ T Φ + Σ , − Φ T r )
d ~ f ← d f ( θ + Δ ) − sg [ relu ( d f ( θ + Δ ) − d f ( θ ) ) ] \widetilde{d}_f\leftarrow d_f(\theta+\Delta)-\operatorname{sg}\left[\operatorname{relu}\left(d_f(\theta+\Delta)-d_f(\theta)\right)\right] d f ← d f ( θ + Δ ) − sg [ relu ( d f ( θ + Δ ) − d f ( θ ) ) ] f ∈ F f\in\mathcal{F} f ∈ F
θ ← RETRACT ( ADAM ( θ , 1 ∣ F ∣ ∑ f relu ( t f − d ~ f ) 2 ) ) \theta\leftarrow\operatorname{RETRACT}\left(\operatorname{ADAM}\left(\theta,\frac{1}{|\mathcal{F}|}\sum_f\operatorname{relu}\left(t_f-\widetilde{d}_f\right)^2\right)\right) θ ← RETRACT ( ADAM ( θ , ∣ F ∣ 1 ∑ f relu ( t f − d f ) 2 ) )
θ e ← θ , c e ← SELECT ( θ ) \theta_e\leftarrow\theta,\quad c_e\leftarrow\operatorname{SELECT}(\theta) θ e ← θ , c e ← SELECT ( θ )
return θ u ← θ e ⋆ \theta_u\leftarrow\theta_{e^\star} θ u ← θ e ⋆ e ⋆ = arg max e c e e^\star=\underset{e}{\operatorname{arg\,max}}\ c_e e ⋆ = e arg max c e
Backbones and where the features are taken
The method needs a score and its gradients with respect to the two endpoint rows, so it applies to any backbone that keeps one entity table and one relation table and is differentiable almost everywhere in those rows. We report three, all with 200 latent coordinates per entity. TransE stores one real row of m = 200 m=200 m = 200 [4 ] . RotatE packs 200 complex coordinates into a real row of m = 400 m=400 m = 400 [53 ] . Its rows are used without normalization, and its trained distances are about six times TransE’s. TransH keeps entity rows of m = 200 m = 200 m = 200 [60 ] . § 3 gives the TransE score, and the other two follow the cited definitions.
The slot feature ϕ x ( v ) = ∂ d x / ∂ e v \phi_x^{(v)} = \partial d_x / \partial e_v ϕ x ( v ) = ∂ d x / ∂ e v ( I − e ˉ e ˉ ⊤ ) / ∥ e ∥ 2 (\mathbf{I} - \bar{e}\bar{e}^{\top})/\lVert e\rVert_2 ( I − e ˉ e ˉ ⊤ ) / ∥ e ∥ 2
Hyperparameters
Table 3 lists the settings of the unlearner, of the update and of the models. The unlearner’s values are the same on the three backbones except for the forgetting learning rate, the epoch count and the target fraction s s s § 9 .§ 2 ). The retained-span projection of Table 18 shares this table and differs in two places. It applies the plain forgetting loss to the pre-update score, and it projects that loss’s gradient off the span of the incident retained edges through a ridge-damped projector, with KAU’s ancillaries.
Cost
This subsection gives the computational cost of KAU and compares its time to release with that of the baselines. A forgetting step draws about ten edges per involved entity, recomputes their features in one backward pass, solves for the response over all involved rows at once, and scores every forgotten fact at the shifted rows. Each conjugate-gradient iteration costs one product with Φ \Phi Φ
Table 4 gives the time to release one unlearned model on CoDEx-L with TransE, over unlearning seeds 21 to 27, with four CPU cores. KAU releases 5.4 times faster than GraphDPO and 18 times faster than retraining.
Constructions the derivation admits and we do not use
Three further constructions follow from the same derivation and are not part of the method. A second Gauss–Newton round re-linearizes the response at the shifted rows on the same draw and adds the correction to the first, which models the drift of the features during the update, and it improved no reported quantity. Letting the features carry gradient opens a channel in which the unlearner reshapes the update’s features instead of the residual they act on, and it was worse, so the features carry no gradient within a step. A penalty that holds the stand-ins at their original scores leaves the unseen channel free of residual at release, and it costs utility without moving the leakage. A fourth item is a hypothesis. Adam’s per-coordinate scaling suggests a ridge that falls with the number of update edges at an entity, as the inverse square root of its share of the steps (Remark A.4 in Appendix § 7 .12), and every experiment reported here uses the degree-independent ridge.
Experimental details
§ 3 defines the update and the leakage, and § 5 states the protocol in outline. This appendix gives the graphs and their splits, the edge set the update runs on, the budget each method receives, the seeds and tests behind every table, and the CoDEx-L results in full.
Training details
On FB15k-237 the training graph has 272,115 triples. The never-trained set B B B B B B θ ∘ \theta^\circ θ ∘ D t r a i n ∖ B \mathcal{D}_{\mathrm{train}} \setminus B D train ∖ B
Table 4. Time to release one unlearned model on CoDEx-L with TransE, median over seven unlearning seeds with the range in brackets.
model θ g \theta_g θ g D R \mathcal{D}_R D R
Pre-training. Original and gold models use the GraphDPO reference implementation of each backbone, with embedding dimension 200, a margin ranking loss with margin 8, ten negatives per positive, batch size 1,024, and Adam with learning rate 10 − 4 10^{-4} 1 0 − 4 Figure 4 ). Every relearning quantity of Appendix C.3 is a difference against this gold model, so each is read relative to the reference rather than as an absolute level.
Figure 4. Pre-training loss on FB15k-237, at every epoch of the schedule. Solid lines are the original model and dashed lines the gold model. The pair of each backbone shares the recipe above and its seed, and differs only in the training triples. Both curves flatten well before the schedule ends, and every quantity we report is a difference between the two.
Evaluation. All MRR values are filtered and averaged over head and tail prediction. Forget-set MRR is computed on a held-out subset of the deleted triples that is never used for selecting hyperparameters or update configurations, retain-set MRR on a fixed probe of retained training triples, and test MRR on the standard test split.
Unlearning stage
Metrics. We evaluate forgetting and utility immediately after unlearning. Forget MRR (M F M_F M F F \mathcal{F} F Retain MRR (M R M_R M R D R \mathcal{D}_R D R Test MRR (M T M_T M T
Hyperparameter selection. KAU and each baseline are tuned separately for every dataset–backbone setting, with the same criterion for all methods. Each configuration is scored by the larger of two shortfalls, one in forgetting and one in retained performance, each measured on the corresponding development subset, and the configuration with the smallest score is evaluated on disjoint held-out subsets, which produce all reported values. Selection and reporting use the same seven unlearning seeds.
For GraphDPO the search covers the learning rate { 10 − 4 , 3 × 10 − 4 , 10 − 3 , 3 × 10 − 3 , 10 − 2 } \{10^{-4}, 3 \times10^{-4}, 10^{-3}, 3 \times10^{-3}, 10^{-2}\} { 1 0 − 4 , 3 × 1 0 − 4 , 1 0 − 3 , 3 × 1 0 − 3 , 1 0 − 2 } { 1 , 2 , 3 , 6 , 12 , 24 , 48 } \{1, 2, 3, 6, 12, 24, 48\} { 1 , 2 , 3 , 6 , 12 , 24 , 48 } { 3 × 10 − 4 , 10 − 3 , 3 × 10 − 3 } \{3 \times10^{-4}, 10^{-3}, 3 \times10^{-3}\} { 3 × 1 0 − 4 , 1 0 − 3 , 3 × 1 0 − 3 } { 0.03 , 0.1 , 0.3 } \{0.03, 0.1, 0.3\} { 0.03 , 0.1 , 0.3 } { 1 , 3 } \{1, 3\} { 1 , 3 } { 4 , 8 } \{4, 8\} { 4 , 8 } ϵ ∈ { 10 − 5 , 10 − 4 , 10 − 3 } \epsilon\in\{10^{-5}, 10^{-4}, 10^{-3}\} ϵ ∈ { 1 0 − 5 , 1 0 − 4 , 1 0 − 3 } { 0.05 , 0.1 , 0.25 , 0.4 , 0.5 , 1 , 10 , 35 } \{0.05, 0.1, 0.25, 0.4, 0.5, 1, 10, 35\} { 0.05 , 0.1 , 0.25 , 0.4 , 0.5 , 1 , 10 , 35 } { 0 , − 0.01 , − 0.02 , − 0.03 , − 0.04 } \{0, -0.01, -0.02, -0.03, -0.04\} { 0 , − 0.01 , − 0.02 , − 0.03 , − 0.04 } { 10 − 5 , 3 × 10 − 5 , 10 − 4 , 3 × 10 − 4 , 10 − 3 } \{10^{-5}, 3 \times10^{-5}, 10^{-4}, 3 \times10^{-4}, 10^{-3}\} { 1 0 − 5 , 3 × 1 0 − 5 , 1 0 − 4 , 3 × 1 0 − 4 , 1 0 − 3 } { 2 , 3 , 5 , 10 , 20 } \{2, 3, 5, 10, 20\} { 2 , 3 , 5 , 10 , 20 } s s s (7) , s ∈ { 0.005 , 0.02 , 0.05 , 0.15 , 0.25 , 0.4 , 0.6 } s \in\{0.005, 0.02, 0.05, 0.15, 0.25, 0.4, 0.6\} s ∈ { 0.005 , 0.02 , 0.05 , 0.15 , 0.25 , 0.4 , 0.6 } { 1 , 2 , 4 } \{1, 2, 4\} { 1 , 2 , 4 } k max ∈ { 48 , 96 , 160 } k_{\max} \in\{48, 96, 160\} k m a x ∈ { 48 , 96 , 160 } ρ k n ∈ { 0.05 , 0.2 , 0.5 , 1 } \rho_{\mathrm{kn}} \in\{0.05, 0.2, 0.5, 1\} ρ kn ∈ { 0.05 , 0.2 , 0.5 , 1 } ρ u n ∈ { 0.01 , 0.05 , 0.3 } \rho_{\mathrm{un}} \in\{0.01, 0.05, 0.3\} ρ un ∈ { 0.01 , 0.05 , 0.3 } σ r e l ∈ { 10 − 4 , 10 − 3 , 10 − 2 , 10 − 1 } \sigma_{\mathrm{rel}} \in\{10^{-4}, 10^{-3}, 10^{-2}, 10^{-1}\} σ rel ∈ { 1 0 − 4 , 1 0 − 3 , 1 0 − 2 , 1 0 − 1 } β ∈ { 0.3 , 1 , 3 } \beta\in\{0.3, 1, 3\} β ∈ { 0.3 , 1 , 3 } (9) , called the anchor weight, and the weight of the checkpoint rule of Appendix § 8 .§ 6 , { 0.3 , 0.5 , 0.7 , 0.95 } \{0.3, 0.5, 0.7, 0.95\} { 0.3 , 0.5 , 0.7 , 0.95 } 3 × 10 − 5 3 \times10^{-5} 3 × 1 0 − 5 3 × 10 − 5 3 \times10^{-5} 3 × 1 0 − 5 3 × 10 − 4 3 \times10^{-4} 3 × 1 0 − 4 s = 0.15 s = 0.15 s = 0.15 k max = 96 k_{\max} = 96 k m a x = 96 ρ k n = 0.2 \rho_{\mathrm{kn}} = 0.2 ρ kn = 0.2 ρ u n = 0.05 \rho_{\mathrm{un}} = 0.05 ρ un = 0.05 σ r e l = 10 − 3 \sigma_{\mathrm{rel}} = 10^{-3} σ rel = 1 0 − 3 β = 1 \beta= 1 β = 1
Seed variation is below 0.002 MRR for KAU and GraphDPO in every cell, whereas ZeroFisher varies by 0.02 to 0.04 MRR at fixed hyperparameters, so its mean scores average over runs that barely forget and runs that over-forget.
The update
The update is the continued training of § 5 . It trains the released model further with the ordinary margin-ranking loss under Adam, with every parameter trainable. The update data are the retained triples together with the never-trained set B B B B B B B B B { 1 , 000 , 3 , 000 , 6 , 000 } \{1,000, 3,000, 6,000\} { 1 , 000 , 3 , 000 , 6 , 000 } { 0.15 , 0.25 , 0.35 , 0.5 } \{0.15, 0.25, 0.35, 0.5\} { 0.15 , 0.25 , 0.35 , 0.5 } { 0 , 0.02 } \{0, 0.02\} { 0 , 0.02 } { 10 − 4 , 3 × 10 − 4 } \{10^{-4}, 3 \times10^{-4}\} { 1 0 − 4 , 3 × 1 0 − 4 } 3 × 4 × 2 × 2 = 48 3 \times4 \times2 \times2 = 48 3 × 4 × 2 × 2 = 48 B B B B B B
All configurations run with three unlearning seeds. The probe of 1,000 deleted triples is split once into a selection half and a report half. For each method, the configuration under which it leaks most over the run on the selection half is selected; the selected configurations are then re-run with seven unlearning seeds, and each method is reported under the strongest of them against it, at each run’s epoch of peak leakage. The selection half serves only this selection, and every reported number is computed on the report half. The retrained oracle (the gold model of § 5 ) receives every configuration with the same data and settings. Its runs are computed once per dataset, backbone, configuration and unlearning seed and cached. Every method is therefore read against the oracle run on the same update sample at the same epoch. Because the probe is a sample of the deleted triples, the original and gold levels on it differ from those of Table 5 .
Table 5. Unlearning results on FB15k-237 with 10% triple deletion. M F M_F M F M R M_R M R M T M_T M T Table 6 . Bold marks the method closest to Gold on M F M_F M F M R M_R M R M T M_T M T
Table 6. Standard deviation over the seven unlearning seeds for every method cell of Table 5 . Original and Gold are single checkpoints and have no seed variation. This table prints the population standard deviation over the seven seeds (divisor n n n Table 7 and the tests of Table 8 use the sample standard deviation (divisor n − 1 n - 1 n − 1
Table 8. Significance of the leakage differences in Table 1 on FB15k-237: KAU against each baseline, seven unlearning seeds against seven, at the reported update configurations. Welch’s t t t U U U
Relearning metrics. Let M R R u , e \mathrm{MRR}_{u,e} MRR u , e M R R g o l d , e \mathrm{MRR}_{\mathrm{gold},e} MRR gold , e e e e e = 0 e = 0 e = 0 M R R o r i g \mathrm{MRR}_{\mathrm{orig}} MRR orig
Rec u ( e ) = 100 × M R R u , e − M R R u , 0 M R R o r i g − M R R u , 0 , Rec g o l d ( e ) = 100 × M R R g o l d , e − M R R g o l d , 0 M R R o r i g − M R R g o l d , 0 , (16) \operatorname{Rec}_{u}(e) = 100 \times\frac{\mathrm{MRR}_{u,e} - \mathrm{MRR}_{u,0}}{\mathrm{MRR}_{\mathrm{orig}} - \mathrm{MRR}_{u,0}}, \qquad\operatorname{Rec}_{\mathrm{gold}}(e) = 100 \times\frac{\mathrm{MRR}_{\mathrm{gold},e} - \mathrm{MRR}_{\mathrm{gold},0}}{\mathrm{MRR}_{\mathrm{orig}} - \mathrm{MRR}_{\mathrm{gold},0}}, \tag*{(16)} Rec u ( e ) = 100 × MRR orig − MRR u , 0 MRR u , e − MRR u , 0 , Rec gold ( e ) = 100 × MRR orig − MRR gold , 0 MRR gold , e − MRR gold , 0 , (16) where 100 is a return to the original model’s forget-set MRR. The excess recovery, the leakage of equation (1) read at epoch e e e
ExRec ( e ) = Rec u ( e ) − Rec g o l d ( e ) , (17) \operatorname{ExRec}(e) = \operatorname{Rec}_{u}(e) - \operatorname{Rec}_{\mathrm{gold}}(e), \tag*{(17)} ExRec ( e ) = Rec u ( e ) − Rec gold ( e ) , (17) Leak ( e ) = ( M R R u , e − M R R u , 0 ) − ( M R R g o l d , e − M R R g o l d , 0 ) , (18) \operatorname{Leak}(e) = \left(\mathrm{MRR}_{u,e} - \mathrm{MRR}_{u,0}\right) - \left(\mathrm{MRR}_{\mathrm{gold},e} - \mathrm{MRR}_{\mathrm{gold},0}\right), \tag*{(18)} Leak ( e ) = ( MRR u , e − MRR u , 0 ) − ( MRR gold , e − MRR gold , 0 ) , (18) RER ( e ) = 100 × Leak ( e ) M R R o r i g − M R R g o l d , 0 . (19) \operatorname{RER}(e) = 100 \times\frac{\operatorname{Leak}(e)}{\mathrm{MRR}_{\mathrm{orig}} - \mathrm{MRR}_{\mathrm{gold},0}}. \tag*{(19)} RER ( e ) = 100 × MRR orig − MRR gold , 0 Leak ( e ) . (19) Each is reported at e ∗ = arg max e Leak ( e ) e^{*} = \arg\max_{e} \operatorname{Leak}(e) e ∗ = arg max e Leak ( e ) e ∗ e^{*} e ∗
Budgets and selection
Two selections are made. The first picks the hyperparameters of each method, and the second picks the released checkpoint within a run.
The hyperparameters are selected per method and per dataset–backbone setting by the shortfall criterion of Appendix § 9 .§ 2 , with the same criterion for every method. The number of epochs and the learning rates are among the searched hyperparameters. GraphDPO searches its epoch count over { 1 , 2 , 3 , 6 , 12 , 24 , 48 } \{1, 2, 3, 6, 12, 24, 48\} { 1 , 2 , 3 , 6 , 12 , 24 , 48 } { 2 , 3 , 5 , 10 , 20 } \{2, 3, 5, 10, 20\} { 2 , 3 , 5 , 10 , 20 } § 9 .§ 2 and in Table 3 . The selected settings of GraphDPO on FB15k-237 are, for TransE, TransH and RotatE respectively, learning rate 10 − 4 10^{-4} 1 0 − 4 3 × 10 − 4 3 \times10^{-4} 3 × 1 0 − 4 3 × 10 − 3 3 \times10^{-3} 3 × 1 0 − 3 6 × 10 − 3 6 \times10^{-3} 6 × 1 0 − 3 3 × 10 − 4 3 \times10^{-4} 3 × 1 0 − 4 ϵ = 10 − 3 \epsilon= 10^{-3} ϵ = 1 0 − 3 ϵ = 10 − 4 \epsilon= 10^{-4} ϵ = 1 0 − 4 3 × 10 − 4 3 \times10^{-4} 3 × 1 0 − 4 3 × 10 − 4 3 \times10^{-4} 3 × 1 0 − 4 3 × 10 − 4 3 \times10^{-4} 3 × 1 0 − 4 s = 0.6 s = 0.6 s = 0.6 5 × 10 − 5 5 \times10^{-5} 5 × 1 0 − 5 10 − 4 10^{-4} 1 0 − 4 10 − 3 10^{-3} 1 0 − 3 3 × 10 − 3 3 \times10^{-3} 3 × 1 0 − 3 3 × 10 − 3 3 \times10^{-3} 3 × 1 0 − 3 10 − 3 10^{-3} 1 0 − 3 ϵ = 10 − 5 \epsilon= 10^{-5} ϵ = 1 0 − 5 ϵ = 10 − 4 \epsilon= 10^{-4} ϵ = 1 0 − 4 ϵ = 10 − 5 \epsilon= 10^{-5} ϵ = 1 0 − 5 − 0.01 -0.01 − 0.01
The released checkpoint within a run is chosen by the rule of Appendix § 8 .§ 6 . Once per epoch the run scores its current checkpoint by 0.7 ( 1 − M R R F ) + 0.3 M R R R 0.7\left(1 - \mathrm{MRR}_{F}\right) + 0.3\mathrm{MRR}_{R} 0.7 ( 1 − MRR F ) + 0.3 MRR R
Relearning-resistant add-ons
Table 2 adds three relearning defences to GraphDPO on FB15k-237. Each add-on is built on GraphDPO at its selected setting on that backbone (Appendix § 9 .§ 4 ).
NTK. We apply the scrubbing step of Golatkar et al. [21 ] once to GraphDPO’s released model. The step moves the parameters along the forgotten facts’ score gradients, projected off the span of the retained triples’ score gradients, with the step length of the authors’ code. It then adds Gaussian noise with covariance α F − 1 \alpha F^{-1} α F − 1 F F F α ∈ { 0 , 10 − 10 , 10 − 9 } \alpha\in\{0, 10^{-10}, 10^{-9}\} α ∈ { 0 , 1 0 − 10 , 1 0 − 9 } α = 0 \alpha= 0 α = 0
SAM. We follow Algorithm A1 of Fan et al. [17 ] at every GraphDPO step. GraphDPO’s forgetting terms, its margin and preference losses on the forget batch, are evaluated at parameters perturbed by ρ \rho ρ ρ ∈ { 0.03 , 0.1 , 0.3 } \rho\in\{0.03, 0.1, 0.3\} ρ ∈ { 0.03 , 0.1 , 0.3 } ρ ∈ { 0.003 , 0.01 , 0.03 , 0.1 , 0.3 } \rho\in\{0.003, 0.01, 0.03, 0.1, 0.3\} ρ ∈ { 0.003 , 0.01 , 0.03 , 0.1 , 0.3 } ρ = 0.03 , 0.01 \rho= 0.03, 0.01 ρ = 0.03 , 0.01 0.03 0.03 0.03
TAR. We continue GraphDPO’s released model with the adversarial training of Tamirisa et al. [55 ] for 750 outer steps. Each outer step simulates one update at learning rate 10 − 4 10^{-4} 1 0 − 4 3 × 10 − 4 3 \times10^{-4} 3 × 1 0 − 4 § 4.1 . The tamper-resistance loss penalizes any rise of a forgotten fact’s log-odds against its 50 strongest competing answers above its level in GraphDPO’s release, both along the simulated update and at the current parameters, and is differentiated to first order as in the authors’ code. A retained margin loss and an anchor to GraphDPO’s release hold utility. With the tamper-resistance weight fixed at 0.2, we search the outer learning rate over { 2 , 4 , 8 , 16 , 30 } × 10 − 5 \{2, 4, 8, 16, 30\} \times10^{-5} { 2 , 4 , 8 , 16 , 30 } × 1 0 − 5 2 × 10 − 5 2 \times10^{-5} 2 × 1 0 − 5 8 × 10 − 5 8 \times10^{-5} 8 × 1 0 − 5 § 10 .7, which replaces KAU’s forgetting step.
Selection and evaluation. For each add-on, the five settings are scored by the criterion of Appendix § 9 .§ 2 , and the selected setting is kept at every seed. Every row of Table 2 , GraphDPO and KAU included, is run at three of the seven unlearning seeds of Table 1 and receives the same three to six update configurations of Appendix § 9 .§ 3 on each backbone. Each row is reported under the configuration in which it leaks most, at its epoch of peak leakage.
Statistics
Table 5 and Table 1 report means over seven unlearning seeds. Table 6 gives the standard deviations of Table 5 over those seeds, and Table 7 those of the FB15k-237 block of Table 1. The standard deviation of the leakage is 0.0021, 0.0019 and 0.0032 for KAU on TransE, TransH and RotatE, 0.0057, 0.0079 and 0.0078 for GraphDPO, and 0.0470, 0.0421 and 0.0311 for ZeroFisher. For ZeroFisher the excess recovery spreads far more than the leakage, because its release-time drop, the denominator of its excess recovery, varies across seeds. Table 1 prints the excess recovery as the ratio of seed means, and Table 7 gives the mean and spread of the per-seed ratios. Tables 2, 16, 17 and 18 and Figures 3, 5, 6 and 7 report means over three unlearning seeds. Table 13 reports means over the seven seeds of Table 1. Table 12 uses three screening seeds per configuration, and its last row uses the seven seeds of Table 1. Tables 14 and 15 use one unlearning seed. Figure 2 shows means over three unlearning seeds under one update configuration, with every method released at a forgetting rate of 90 to 106 percent of the gold model’s. A seed varies the unlearner’s own randomness and the sample of update triples, while the split, the original model and the update configurations stay fixed. Selection and reporting use the same seeds (Appendix § 9 .§ 2 ). Table 8 tests the leakage differences of Table 1, seven KAU seeds against seven baseline seeds, with Welch’s t t t U U U
Section 3 places the retrained oracle at zero leakage, so the width of that zero is the oracle’s own variation across retraining seeds. Table 9 measures it. We retrain the oracle twice more per backbone with the recipe of Appendix § 9 .§ 1 , under retraining seeds 2 and 3. Each retrained oracle receives the update of Table 1 at every method’s reported update configuration for the seven unlearning seeds. Every run is read at the same per-seed peak epoch as Table 1 . The table reports the oracle’s own rise in forget-MRR under the update at the three oracle seeds. It also reports each method’s leakage recomputed against each oracle seed and each method’s own rise over its seven seeds. The oracle’s rise varies across retraining seeds by a standard deviation of 0.0036 to 0.0043 on TransE, 0.0032 to 0.0042 on TransH and 0.0018 to 0.0031 on RotatE. Its retained MRR at release varies by 0.0017, 0.0024 and 0.0025. Recomputed against each oracle seed, KAU’s leakage stays the smallest of the three methods on every backbone, and its reduction over GraphDPO stays between 44% and 67%. The reductions of Table 1 hold whichever oracle seed is the reference. KAU’s leakage in Table 1 is 5.0, 5.0 and 7.7 times the largest oracle-seed standard deviation on TransE, TransH and RotatE. It is a rise beyond the oracle and not seed variation of the reference. In the last column, every method’s rise exceeds the oracle’s at every oracle seed on every backbone.
Table 9. The retrained oracle at three retraining seeds on FB15k-237. Each oracle receives the update of Table 1 at every method’s reported update configuration for the seven unlearning seeds and is read at the same peak epochs. Oracle rise is the oracle’s own gain in forget-MRR under the update, mean over the seven update samples, at oracle seeds 1, 2 and 3. Leak is each method’s leakage against each oracle seed. Method rise is the method’s own gain, mean ± \pm ± M R M_R M R
CoDEx-L
CoDEx-L is run on TransE, TransH and RotatE under the protocol of this appendix, with the splits of Appendix C.1 and the update grid of Appendix C.3. Table 10 gives link prediction at release, with Gold the gold model of § 5 . Table 11 gives the seed spread and the tests behind the CoDEx-L block of Table 1 .
Table 10: Link prediction at release on CoDEx-L with TransE, TransH and RotatE: filtered MRR on the forget, retain and test evaluation sets. Original and Gold are single checkpoints. Method rows are mean ± \pm ± M F M_F M F M R M_R M R M T M_T M T
Table 10.
Table 11: Seed spread and significance of the CoDEx-L block of Table 1. Cells give mean ± \pm ± t t t U U U
Table 11.
The ordering of Table 1 holds on a second graph with over five times the entities and under a third of the relations, on all three backbones. KAU attains the lowest excess recovery, leakage and relative excess recovery on every backbone. Its leakage is 59%, 50% and 82% below GraphDPO’s on TransE, TransH and RotatE. Its retained MRR exceeds GraphDPO’s by 0.032, 0.044 and 0.103. On TransE it is 0.018 below the gold model’s, where GraphDPO and ZeroFisher lose 0.050 and 0.092, and KAU’s forget-MRR at release is within 0.002 of the gold model’s. On TransE all three methods are read at one update configuration, the one that leaks most against each of them on the selection half. On every backbone every KAU seed leaks less than every GraphDPO seed. Both tests find KAU’s leakage below ZeroFisher’s at the 5% level on every backbone.
Additional results
This appendix holds the measurements that the main text uses in summary. The first is the leakage across the 48 update configurations, and the second reads the update built from never-trained edges alone. The next two attribute the TransE result between the forgetting term and the ancillaries, and the recovery between parameter blocks. The next two are the calibration of the anticipated response as a ranking and the relation of forgetting depth to leakage and retained utility. The definitions and settings behind the ablation tables of § 5 follow, and a note on evaluating the anticipated score at the shifted rows closes the appendix. Leakage is Leak of equation (18) , in MRR points, and RER of equation (19) is leakage as a share of the erased knowledge.
Leakage across update configurations
§ 5 runs 48 update configurations per dataset and backbone, shared by every method. Each configuration is one draw of the update of § 3 , the continued training of § 5 , run on retained triples together with the never-trained triples B B B § 5 , receives every configuration with identical data and settings. Table 1 reports each method under the configuration that leaks most against it on the selection half of the probe, read on the report half at the epoch of peak leakage. Table 12 shows what lies behind that selected cell on TransE. The grid is that of Appendix § 9 .§ 3 , and every configuration runs at three screening seeds. A configuration’s leakage is the mean over those seeds of the leakage at each seed’s peak epoch. Each cell of the table is the largest such value over the configurations of its group. The last row gives each method under its own configuration in Table 1 , over seven unlearning seeds. It can therefore lie outside the three-seed range of the rows above it, as it does for ZeroFisher, whose seed spread is the largest (Table 7 ).
Table 7. Seed spread of Table 1 on FB15k-237: mean ± \pm ± Table 1 prints the ratio of seed means.
Table 12. Leakage on FB15k-237 with TransE by group of update configurations. Each cell is the largest leakage over the configurations of the group, where a configuration’s leakage is the mean over the three screening seeds of the leakage at that seed’s peak epoch. The last column is the ratio of KAU’s cell to GraphDPO’s. The last row gives each method under its own configuration in Table 1, over seven seeds.
The table is read down each column. KAU leaks less than GraphDPO and less than ZeroFisher in every one of the 48 configurations. Its leakage is 0.47 to 0.58 of GraphDPO’s in every group. Leakage is flat along every axis. GraphDPO’s group maxima span 0.0425 to 0.0470, and KAU’s span 0.0215 to 0.0249. The worst configuration therefore sets the scale, and no axis moves KAU from the bottom of the ordering. KAU’s place below both baselines in Table 1 is not a property of one configuration. The configuration reported in Table 1 is chosen by the selection of Appendix § 9 .§ 3 , which reads leakage over the run on the selection half, whereas this table reads peak leakage on the report half; the two readings need not pick the same configuration, and under either KAU is lowest in every group.
The never-trained-edge update
Table 13 reads one update outside the 48 configurations on FB15k-237 with TransE, beside the standard update, over the seven unlearning seeds of Table 1 . Each update is applied to the released checkpoint of every method and to the retrained oracle. ExRec, Leak and RER are read at the epoch of peak leakage as in Table 1 . The standard update is the configuration of Table 14 . It draws 3,000 edges from the never-trained set B B B 10 − 4 10^{-4} 1 0 − 4 B B B
Table 14. Block attribution of the rise in forget-MRR under the update, FB15k-237 with TransE, one update configuration and one unlearning seed. Released is the forget-MRR of the released model. Each further column gives the rise in forget-MRR of the hybrid that takes that block alone from the updated model, and the every-parameter column gives the rise of the updated model itself. Each model is read at its own epoch of peak leakage.
The never-trained-only update holds only edges that no model has ever trained on. This is the channel the unlearner can model only through stand-ins (§ 4.1 ). Under it GraphDPO keeps 68 percent of its leakage and ZeroFisher 79 percent. Removing the retained channel therefore does not remove the baselines’ leakage. The residual they leave on the involved rows is restored by any true edge at those rows, as § 4.4 says. KAU keeps 42 percent of its leakage. Its leakage is 0.33 of GraphDPO’s under this update, against 0.54 under the standard one. This is what the stand-in channel of § 4.1 predicts, together with the observation of § 4.6 that the retained span misses these directions. At the unlearning seed of Table 14 , the retrained oracle’s own rise ranges from +0.022 to +0.041 under the standard update. Under the never-trained-only update it falls to a range of +0.011 to +0.015. The ratio between the methods is the reading.
Running the standard update for longer changes the leakage little. Over 40 epochs, KAU’s leakage is 0.0217 against 0.0215 at 20 epochs, and GraphDPO’s is 0.0412 against 0.0402. ZeroFisher’s is unchanged at 0.0697. The peak-epoch reading of § 5 therefore captures nearly all the leakage a longer update produces, and KAU still leaks about half as much as GraphDPO.
The forgetting term against the ancillaries
KAU runs its anticipated forgetting loss with two ancillaries, the score-preservation term of equation (9) and the norm retraction of Appendix § 8 .§ 4 . The TransE result therefore has to be attributed among the three. The rows of Table 16 , Table 18 and Table 17 that change one of them at a time settle the attribution. Every such row except the relational anchor and the row without a forgetting term is released at KAU’s forgetting depth, so the rows compare leakage at equal forgetting. § 4.4 predicts the pattern they show. Its first control is the residual the edit leaves on the known edges, which Proposition A.2 ties to the score-preservation term. Without that term the update pulls the raised retained edges back and drags the forgotten facts with them. The row without a score anchor in Table 16 shows exactly this. Its leakage rises by almost half and its retained utility falls by 0.007, the lowest utility among KAU’s variants. The relational anchor of Table 17 holds pairwise distances rather than scores, so it leaves the residual free. It leaks the most of all KAU’s variants except the rows without the anticipated response or with a damped response, although it forgets the deepest. What matters on the known channel is therefore the score residual and not the geometry of the rows, as the first control says. The second control is where the forgetting is placed. The plain forgetting loss of Table 18 , which is KAU without the anticipated response, leaks more than the anticipated loss at the same depth. The anticipated term therefore lowers leakage on its own and not through a deeper release.
The same rows test the two statements about the filter. § 4.6 reads subspace methods as hard thresholds of the survival filter, and Corollary A.2 places null-space projection at its zero threshold. The retained-span projection of Table 18 , the hard threshold without stand-ins, leaks more than KAU at the same depth. Adding the projector on top of the anticipated loss, the projector row of Table 16 , raises leakage instead of lowering it. The hard threshold therefore adds nothing that the soft weights of the filter do not already provide, and it removes directions that the update would have left alone (Remark A.1). § 4.5 keeps the norm retraction because norm inflation could mimic resistance on TransE and TransH (Appendix § 8 .§ 4 ). The row without retraction in Table 17 leaks almost the same as the full method at the same utility, so the low leakage does not rest on norm control. The anticipated term is what lowers leakage. The score anchor holds utility while that term acts, and the retraction is a safeguard rather than a source of the result. One reading note applies at unequal depth. The excess recovery of the relational anchor barely moves, because a deeper release enlarges the denominator of equation (16) . Leakage in MRR points is therefore the column to compare there.
Which parameters the update restores
The unlearner edits only the rows of the involved entities, and the update restores the forgotten facts through the same rows. To read off which block carries the recovery we build hybrid models. A hybrid model takes one parameter block from the updated model and every other block from the released model, and the forget-MRR is evaluated on it. Table 14 gives the result on TransE for KAU, GraphDPO, ZeroFisher and the retrained oracle. All four face one update configuration with one unlearning seed, and each model is read at its own epoch of peak leakage. Forget-MRR is measured on the 500-edge report half of the held-out forget probe. The blocks are the involved rows, the relation rows and the entity rows the edit never touched. The involved rows are the endpoint rows of the forgotten facts, 11,412 of the 14,541 entities. The involved rows alone reproduce 95 to 105 percent of every model’s full rise. The relation rows reproduce at most 5.4 percent of the rise for the three unlearners and 9.5 percent for the oracle. The other entity rows move the forget-MRR by at most 0.0014. Each hybrid replaces one block at a time, so the three rises need not add up to the full rise, and two rows exceed 100 percent. Over the seven seeds of Table 1 , the involved rows reproduce 94 to 105 percent of the rise for KAU, GraphDPO and the oracle, and 91 to 105 for ZeroFisher. A forgotten fact therefore relearns through its own two endpoint rows, for an edited model and for the retrained oracle alike. This is the premise of Section 3 and of the anticipated response.
The anticipated response as a per-fact ranking
The objective uses the response to order the forgotten facts by how much the update would restore them, so we evaluate it as a ranking. We take KAU’s released TransE checkpoint and its updated checkpoint at the epoch of peak leakage under one update configuration and one unlearning seed. The predicted change of a forgotten fact’s score is the response at the released checkpoint, averaged over 32 draws. The realized change is the fact’s score at release minus its score after the update, so a positive change is a recovery. Table 15 compares the two over the n = 1,000 n = 1{,}000 n = 1 , 000
Table 15. The anticipated response as a per-fact ranking on KAU’s released TransE checkpoint on FB15k-237, under one update configuration and one unlearning seed. Per-fact correlation between the predicted and the realized change of the forgotten facts’ scores under the update, at the epoch of peak leakage, for the three ways of computing the response. The last two columns give the mean predicted and the mean realized change, a positive change being a recovery. n = 1,000 n = 1{,}000 n = 1 , 000
The joint response with exact evaluation reaches a Pearson correlation of 0.53 and a Spearman correlation of 0.21 per fact. Its quintiles of predicted recovery are monotone in realized recovery, from +0.003 in the lowest quintile to +0.459 in the highest. This is the ranking property the objective uses. The per-entity block solve lowers the Pearson correlation to 0.30. A fact whose two endpoints are both edited therefore has to be solved once, jointly, for the prediction to be right. First-order evaluation ranks the facts worse, at a Spearman correlation of 0.13, although its Pearson correlation of 0.61 is higher. Over the seven unlearning seeds of Table 1 , the joint response has median Pearson and Spearman correlations of 0.50 and 0.23. At every one of those seeds it has a higher Pearson correlation than the per-entity block solve and a higher Spearman correlation than first-order evaluation. First-order evaluation matches the level of the change, with a mean predicted change of +0.145 against a realized +0.159. The exactly evaluated response predicts the ranking and not the level, with a mean predicted change of −0.009. The target t f t_f t f § 4.3 states, and the response supplies the ranking. Table 16 places the joint solve with exact evaluation first in leakage as well. First-order evaluation raises RER from 19.38 to 29.07, and the per-entity block solve raises it to 30.50.
Leakage and retained utility against forgetting depth
Leakage depends on how deeply a method forgets at release, so Figure 3 in § 5 plots RER against forgetting depth. Depth is the forgetting rate FR, the forget-MRR drop at release as a percentage of the retrained oracle’s. Each method is released at three depths by varying only its budget knob, under one update configuration per backbone. Figure 3 shows means over three unlearning seeds. The rung nearest each of the three bands, 40 to 60, 60 to 85 and 85 to 110 percent, is shown. On TransE, from the shallowest to the deepest band the mean RER rises by about 59 points for ZeroFisher, 50 for GraphDPO and 15 for KAU. In the deepest band it is about 131 for ZeroFisher, 77 for GraphDPO and 26 for KAU. The mean ordering of the three methods holds in every band on every backbone. The baselines’ RER grows with depth more than twice as fast as KAU’s, so the gap widens toward the deepest band.
The figure is the reason every row of Table 16 and Table 18 is released at KAU’s forgetting depth. A method released deeper earns part of its leakage from that depth alone, so leakage is compared at equal FR.
Forgetting deeper does not cost KAU retained utility. Figure 5 gives the retained MRR at release of the same releases as Figure 3 , as a percentage of the gold model’s. KAU keeps more than 94 percent of the gold model’s retained MRR in every band on every backbone, and its retention rises slightly with depth. The baselines pay for depth in retained utility. From the shallowest to the deepest band, GraphDPO, the stronger baseline, loses 4.7, 5.1 and 13.6 points on TransE, TransH and RotatE and ends at 89.8, 88.0 and 70.8 percent, and ZeroFisher loses 6.7, 7.0 and 13.8 points. At every depth KAU therefore both leaks less and retains more.
Figure 5. Retained MRR at release against forgetting depth on FB15k-237, as a percentage of the gold model’s retained MRR, for the releases of Figure 3. Points average three unlearning seeds and bars span the seeds; the dashed line at 100 is the gold model. KAU keeps more than 94% of the gold model’s retained MRR at every depth, whereas both baselines lose retained utility as they forget deeper.
Figure 6 follows the relearning epoch by epoch on RotatE, under the update configuration of Figure 3 and at three unlearning seeds. ZeroFisher’s RER peaks within the first five epochs, and GraphDPO’s keeps rising until the last epochs. In every band and at every seed, KAU’s peak RER stays below 15, whereas the lowest peak of either baseline is 36.
Figure 6. RER along the update on FB15k-237 with RotatE, by forgetting-rate band at release, under the update configuration of Figure 3 . Each cell is the mean RER over three unlearning seeds at that epoch, and the number after each row is the mean over seeds of each seed’s peak RER. An RER of zero is the retrained oracle’s own recovery. The three panels share one colour scale.
Ablation details
Table 16 and 18 are run in one ablation setting. Every variant starts from KAU’s forgetting budget and keeps the retained pass, per-fact targets and release rule at KAU’s selected TransE hyperparameters. The score-preservation weight is β = 0.3 \beta= 0.3 β = 0.3 Table 3 . All rows, including KAU, are released within a fixed band of forgetting rates, so that leakage is compared at equal forgetting, which is why KAU’s values in these tables differ from those of Table 1 . All rows face one update configuration of Table 1 with three unlearning seeds and are read at the epoch of peak leakage on the report half. A variant that forgets less than KAU at its budget is given a larger forgetting budget, set from its forgetting rate at release alone, so that it falls within the band. Figure 7 shows the leakage of every row of Table 16 and 18 with its spread over the three seeds.
Figure 7. Leakage of every row of Table 16 and Table 18 on FB15k-237 with TransE, in the ablation setting of those tables. The upper panel holds the rows of Table 16 and the lower panel those of Table 18 . Markers are means over three unlearning seeds, and whiskers span one standard deviation over the seeds. The shaded band is KAU’s mean plus or minus one standard deviation. Rows are sorted by leakage within each table.
Variants of KAU. No anticipated response sets the response to zero, so that the forgetting loss acts on the current score. Response damped raises the relative ridge from 10 − 3 10^{-3} 1 0 − 3 10 3 10^{3} 1 0 3 First-order evaluation replaces the score at the shifted rows by its linearisation around the current rows. Per-entity block solve solves the response separately for each entity’s block instead of jointly. It therefore counts the residual of a drawn edge between two involved entities once at each endpoint (Lemma A.4). Signed residual takes the residual of every drawn edge with its sign, crediting the update with restoring lowered edges as well as raised ones. No pessimistic composition applies the loss to the anticipated score alone rather than to the smaller of the current and anticipated scores. Per-relation gate scales each edge’s residual by its margin-violation probability; it binds on 4% of the modelled update edges. No unseen channel and no known channel remove, respectively, the stand-in edges and the retained neighbours from the draw. No best-of-Q Q Q keeps the first plausible stand-in candidate instead of the best of four. Hinge of the expected draw applies the loss to the response of the expected draw, with inclusion probabilities as weights, instead of averaging the loss over sampled draws. Ordered k max k_{\max} k m a x keeps the first k max k_{\max} k m a x ρ k n = 1 \rho_{\mathrm{kn}}=1 ρ kn = 1 k max = 16 k_{\max}=16 k m a x = 16 Q = 1 Q=1 Q = 1 No score anchor sets the score-preservation weight to zero. Relational anchor holds pairwise distances between rows instead of scores; it
released deeper than the gold model. No norm retraction omits the rescaling of edited rows, projector added on top applies the retained-span projector to KAU’s update, and no forgetting term runs the retained pass alone; it forgets less than half of what the gold model forgets and cannot be brought to KAU’s depth. Every other forgetting rate lies within 9 points of KAU’s. Table 17 gives the variants that Table 16 omits.
Alternative forgetting objectives. Each alternative in Table 18 replaces KAU’s forgetting step and keeps everything else. The setting of each objective’s own hyperparameters is given in brackets. Plain forgetting loss is the variant of Table 16 without the anticipated response. Retained-span projection projects the forgetting gradient on each edited entity row off the span of the score gradients of that entity’s retained facts [9 , 27 , 74 ] , with projectors rebuilt every five epochs (ridge 10 − 2 10^{-2} 1 0 − 2 sharpness-aware rows follow Fan et al. [17 ] : SAM-RS averages the forgetting gradient over Gaussian perturbations of the edited rows (ρ = 10 − 4 \rho=10^{-4} ρ = 1 0 − 4 ρ = 3 × 10 − 5 \rho=3\times10^{-5} ρ = 3 × 1 0 − 5 ω = 10 − 6 \omega=10^{-6} ω = 1 0 − 6 ρ = 10 − 2 \rho=10^{-2} ρ = 1 0 − 2 0.97 0.97 0.97 ρ = 10 − 2 \rho=10^{-2} ρ = 1 0 − 2 Weight-distance regularisation subtracts a multiple of the mean squared displacement of the edited rows from the original model [49 ] (γ = 10 \gamma=10 γ = 10 Connectivity-based fine-tuning adds, for the retained and the forgetting loss, a barrier term at the midpoint between the current and the original rows [40 ] (ω = 10 − 3 \omega=10^{-3} ω = 1 0 − 3 TAR-style unrolled copies the entity table, runs Adam steps of the update’s own loss on the retained facts of the current draw, and evaluates the forgetting loss at the displaced rows [55 ] . Booster adds a penalty on the reduction of the retained loss that one normalised gradient step would obtain [29 ] (α = 10 − 2 \alpha=10^{-2} α = 1 0 − 2 NTK scrubbing is a one-shot edit [21 ] : for each deleted fact its two endpoint rows are moved along the component of the fact’s score gradient orthogonal to the span of the retained facts’ gradients until the fact reaches its target to first order (ϵ = 0.32 \epsilon=0.32 ϵ = 0.32 Weight distortion adds isotropic Gaussian noise to the edited rows (σ = 10 − 2 \sigma= 10^{-2} σ = 1 0 − 2 [49 ] .
The forgetting rates at release lie between 88 and 100 percent of the gold model’s, against 93 for KAU.
Why exact evaluation on piecewise-linear scores
The anticipated score is computed by adding the response to the rows and calling the score function again, rather than by adding the first-order term ϕ f T Δ θ \phi_f^{\mathsf{T}} \Delta\theta ϕ f T Δ θ § 10 .§ 5 measures the consequence, which is that the exactly evaluated response ranks facts by realized recovery better than the linear one.
On an L 1 L_1 L 1 x = e ˉ h + w ˉ r − e ˉ t x = \bar{e}_h + \bar{w}_r - \bar{e}_t x = e ˉ h + w ˉ r − e ˉ t d x = ∥ x ∥ 1 d_x = \lVert x \rVert_1 d x = ∥ x ∥ 1 D D D Lemma A.5 , applied coordinate by coordinate, reads
∣ x j + D j ∣ − ∣ x j ∣ = sign ( x j ) D j + 2 ( ∣ D j ∣ − ∣ x j ∣ ) + 1 [ sign ( D j ) ≠ sign ( x j ) ] . (20) \lvert x_j + D_j \rvert- \lvert x_j \rvert= \operatorname{sign}(x_j)D_j + 2(\lvert D_j \rvert- \lvert x_j \rvert) + \mathbf{1}\left[\operatorname{sign}(D_j) \ne\operatorname{sign}(x_j)\right]. \tag*{(20)} ∣ x j + D j ∣ − ∣ x j ∣ = sign ( x j ) D j + 2 (∣ D j ∣ − ∣ x j ∣) + 1 [ sign ( D j ) = sign ( x j ) ] . (20) Up to the normalization’s second-order term, the first term is what a first-order evaluation sees. The second is non-negative and is present only in the coordinates where the displacement opposes the residual and exceeds it in size, that is, where the coordinate crosses zero. Whether it matters is a question about two scales, the size of a coordinate ∣ x j ∣ \lvert x_j \rvert ∣ x j ∣ ∣ D j ∣ \lvert D_j \rvert ∣ D j ∣
Extended related work
This appendix gives the full related work that Section 2 summarizes. It places KAU among the relearning-robust unlearning methods and the unlearners for graphs. Table 19 records, for each study, the update it resists or measures and the object its objective reasons about. It also records whether that object couples retained to forgotten data, whether it computes what the update’s data do to the forgotten items, and how the study is evaluated. Appendix § 11 .§ 1 states what the table shows, and Appendix § 11 .§ 2 states the scope of this paper relative to these studies. Appendices § 11 .§ 3 , § 11 .§ 4 , § 11 .§ 5 and § 11 .§ 6 expand Section 2. They cover unlearning in knowledge graphs and graph networks, benign relearning, the relearning-robust methods and the tangent-kernel response. Appendices § 11 .7 and § 11 .8 place the closest methods and the remaining studies one at a time.
What the table shows
No knowledge-graph or GNN unlearner has been evaluated for recovery of the forgotten facts under continued training. GraphDPO, ZeroFisher, Schema and MetaEU report the released model’s forget and retained ranking and no training after the edit (Liu et al., 2026; Xiao et al., 2025a;b; Xu et al., 2025). GNNDelete, GIF and the OpenGU benchmark report membership or ranking readouts of the released model and no continued training [11 , 62 , 16 ] . Projector fine-tunes after its edit, as a check that fine-tuning from the unlearned solution is cheaper than retraining, and reads utility from that fine-tune [12 ] .
Almost no relearning-robust unlearning method reports its gap to an identically fine-tuned retrained model. TAR compares against an undefended model and a random baseline, MUDMAN against the unedited model after the same relearning, MCU against the original model and RepSelect against the base model [55 , 51 , 65 , 52 ] . Meta-unlearning, CIR, SAM, ILU, the spectral method of Rosati et al. [45 ] , GU and UNSC report no retrained reference under the fine-tune [19 , 17 , 58 , 74 , 9 ] (Sondej and Yang 2025). FRAG fine-tunes a retrained model identically but ranks methods by their own score change rather than by their distance to it [10 ] . Siddiqui et al. [49 ] , Lee et al. [36 ] and Dehghani et al. [14 ] use the reference, with a reference that does not move under the fine-tune, a fine-tune on forget data, and a head-only audit with a frozen extractor respectively. The reference matters here because the retrained oracle itself gains forget-MRR under the update on FB15k-237 with TransE Figure 2 , so an absolute post-update score cannot separate a leak from legitimate learning.
No prior method writes in closed form what the update’s data do to each forgotten item. The update enters as a simulation, an assumption, or a data-free proxy. TAR back-propagates the entropy of one fixed forget batch through a simulated fine-tune with a straight-through estimator [55 ] . Meta-unlearning unrolls a fine-tune on a subset of the forget data, MUDMAN interleaves a first-order fine-tune on the forget set, and RepSelect fits a LoRA fine-tune on the forget set and assumes the update’s weight change is proportional to the accumulated gradient [19 , 51 , 52 ] . MCU assumes the relearning distribution shares its dominant eigenstructure with the forget representation, FRAG reads channel activation statistics and needs no relearning run, and CIR rests on the hypothesis that broken representations are repaired [65 , 10 ] (Sondej and Yang 2025). SAM perturbs along the unlearner’s own forget gradient, ILU reduces each environment to one stationarity scalar, Siddiqui et al. [49 ] use a weight distance and Rosati et al. [45 ] a spectrum [17 , 58 ] . None of these is closed form, none is per fact, and none uses a relation among examples.
Coupling between retained and forgotten data is absent or a single aggregate quantity. Meta-unlearning reduces it to one inner product of whole-set gradients, MUDMAN to a per-coordinate sign test, GU to a one-step entanglement norm, and FRAG to a channel-support ratio [19 , 51 , 74 , 10 ] . TAR evaluates the retain loss at the weights before the simulated fine-tune, SAM and ILU add retain terms, the retain data of MCU enter neither its principal components nor its projector, RepSelect needs no retain set, and the retain step of CIR is optional [55 , 17 , 58 , 65 , 52 ] (Sondej and Yang 2025). Golatkar et al. [21 ] alone carry pairwise couplings, through the tangent kernel between forget and retain samples, and they spend them on computing the scrubbing edit, after which the analysis ends. A knowledge graph needs the pairwise object, because an entity row’s retained gradient aggregates over every incident edge, so no scalar and no sign mask can say which neighbour edge restores which fact.
Projection off the retained span cancels the edit where the forgotten and the retained gradients share rows. The appendix of GU records that the projected step vanishes when the forget gradient lies in the retain tangent space [74 ] . Adam-NSCL states that zero singular values of the feature covariance cannot be guaranteed, and GPM reports that most of the gradient space is constrained after a handful of dissimilar tasks [59 , 47 ] . On a knowledge graph a forgotten triple’s gradient shares its rows with every retained neighbour, so this case is the entity of high degree. That is why the operator of Theorem A.1 is ridge-shrunk rather than a projector, and why the loss acts on the anticipated score rather than on the update direction. It is also why the retained-span projection, which approaches the second limit of Corollary A.3 as its ridge vanishes, leaks more than KAU at matched forgetting depth on TransE, 0.0158 against 0.0111 forget-MRR Table 18 .
Benign relearning is measured by several methods and modelled by none of the unrolled or subspace methods. Meta-unlearning states that self-destruction is meant to occur only under harmful fine-tuning and confirms that it does not occur on the benign set [19 ] . MUDMAN, RepSelect, MCU, CIR and UNDO fine-tune on forget-domain data, and TAR includes retain-only fine-tunes in its sampled set but optimizes only their effect on the fixed forget batch [51 , 52 , 65 , 36 , 55 , 64 ] (Sondej and Yang 2025). ILU trains on a benign fine-tune and FRAG evaluates one, so benign relearning is modelled there, through a global stationarity scalar and through channel support, never through the response of specific retained examples [58 , 10 ] .
Resistance is often bought with utility or with self-destruction. TAR lowers retained accuracy and accepts a low post-update retained accuracy by design, and meta-unlearning makes the retained knowledge self-destruct under the fine-tune [55 , 19 ] . Siddiqui et al. [49 ] find that the methods best at resisting relearning are those with the lowest test accuracy. The utility drop of FRP exceeds that of the unlearners it is compared with, and UNDO pays in general capability [10 , 36 ] . KAU keeps the retained utility within 0.01 of the oracle’s on TransE, 0.2839 against 0.2932, where GraphDPO and ZeroFisher lose 0.03 and 0.06 (Table 5 ).
The robustness of a method that samples fine-tunes is tied to the sampled distribution. TAR reports sensitivity to parameter-efficient fine-tunes and to learning rates outside its sampled set and closes each hole by adding the offending fine-tune to that set, and meta-unlearning weakens against malicious fine-tuning as its number of inner steps grows [55 , 19 ] . KAU also draws from a class, but the draw is over the data of a benign recipe and the response to a draw is computed in closed form to first order, not sampled as a trajectory.
A method that only slows relearning is provably undone. Rosati et al. [45 ] prove that a fine-tune designed against the method restores fast convergence at a cost linear in model size, and their sweep finds no earlier method that withstands standard fine-tuning once the learning rate varies. KAU relocates the edit rather than slowing convergence, and the results read each method under the configuration that leaks most against it on the selection half, at the epoch where its leakage peaks (§ 5 ).
Curvature and norm-ball proxies do not describe the update on a graph. The perturbation ball of SAM is small on the scale of the weights, its own results show its unlearning efficacy falling as the number of forget samples grows, and its mechanism, a bound on Hessian-vector norms, says nothing about which rows two triples share [17 ] .
Scope relative to these studies
The relearning-robust unlearning methods for language and diffusion models handle deep networks with no closed-form kernel, and several of them face fine-tunes that adapt to the method. The closed form of Lemma 1 holds for any differentiable score. It is explicit in the rows and cheap enough for every step because the score depends on three parameter rows, which a deep encoder does not offer. Our update is a benign recipe whose 48 configurations are fixed in advance and shared by every method. Each method is reported under the one that leaks most against it on the selection half of the probe (§ 5 ).
Several of these methods face fine-tunes that hold forgotten data. A fine-tune that includes forgotten edges re-inserts the data, the retrained oracle learns them too, and the gap then measures relearning speed against the oracle, which is the question of Lee et al. [36 ] .
Several methods are evaluated under multi-step trajectories, unseen update types, and the worst case over learning rates, epochs and seeds. TAR simulates a multi-step fine-tune with momentum optimizers, and ILU fine-tunes to convergence and holds on unseen downstream tasks. Four studies report the maximum over rates, epochs, seeds or a suite of fine-tunes [13 , 36 , 43 , 8 ] . Here the response is the linearized response of the whole run of the update under frozen features (Appendix § 7 .§ 4 ), and Figure 2 shows each model’s forget-MRR along the update, so the reader sees where the linearization stops predicting. The never-trained-edge update is the unseen case, and an update outside the class, on edges that share no entity and no relation row with a forgotten fact, has zero first-order coupling to that fact.
Several studies compare more unlearners and more checkpoints. Siddiqui et al. [49 ] cover many unlearners across datasets and architectures, Che et al. [8 ] many checkpoints, and OpenGU many graph unlearners [16 ] . This paper compares two published knowledge-graph unlearners, GraphDPO and ZeroFisher, three relearning-resistant add-ons on GraphDPO (Table 2 ), and the alternative forgetting objectives of Table 18 , among them the retained-span projection. The projector of that row approaches, as its ridge vanishes, the zero-ridge limit of the per-entity survival filter with every retained edge drawn and no stand-ins (Proposition A.1 and Theorem A.1). It is the per-entity counterpart of the threshold at level zero in Corollary A.2, and its step direction is the matching limit of Corollary A.3.
Siddiqui et al. [49 ] find that data unseen during training relearn less than seen data, and Appendix § 10 .§ 2 reads every method under an update built from never-trained edges alone (Table 13 ). An unseen true edge lands on the same shared rows as a seen one with a larger residual, because the edit never saw it.
Table 13. The never-trained-edge update on FB15k-237 with TransE, means over seven unlearning seeds. Each row applies one update to the released checkpoint of every method and to the retrained oracle. ExRec, Leak and RER are read at the epoch of peak leakage as in Table 1 . The standard update is the configuration of Table 14 , and the other lies outside the grid. Columns follow equations (17) –(19) .
FRAG gives a predictor of relearning that needs no relearning run [10 ] . The anticipated post-update score of KAU is such a predictor, computed per fact, and it ranks forgotten facts by their realized recovery. Its per-fact Pearson correlation with that recovery is 0.53, and its Spearman correlation is 0.21 (Appendix § 10 .§ 5 ).
GU projects in the optimizer’s own metric and Adam-NSCL guarantees plasticity for the later task [74 , 59 ] . The response here is Euclidean, and a degree-dependent ridge for Adam is stated as a hypothesis in Appendix § 7 .12.
Golatkar et al. [21 ] bound what a reader of the scrubbed weights can extract, and GNNDelete, OpenGU, Projector and UNSC audit by membership inference [11 , 16 , 12 , 9 ] . The metric here is a ranking gap against the updated oracle, and a membership readout on a released embedding is a separate question.
GraphDPO and GNNDelete handle sequential requests, GraphDPO runs on bilinear backbones as well, and ZeroFisher and Schema delete entities and relations [39 , 11 , 63 b] . KAU is defined per request for any score that depends on three rows, and a new request reruns it with the new forget set.
ZeroFisher, RepSelect, CIR and the spectral method edit in seconds to minutes [64 , 52 , 45 ] (Sondej and Yang 2025). A KAU step costs one linear solve over all involved rows and no simulated fine-tune (Appendix § 8 .10).
Meta-unlearning uses self-destruction as a deterrent and the spectral method uses slowing [19 , 45 ] . The goal here is equivalence to the oracle under benign use, so the released model must remain fine-tunable at a retained utility close to the oracle’s, which rules out both.
Lee et al. [36 ] show that a model matched to the oracle’s outputs relearns faster than the oracle. That corroborates the reading that a pointwise anchor to a reference, such as the distillation of GraphDPO to the frozen original, confers no persistence, and it is why the score-preservation term of KAU holds the scores of retained edges rather than the rows (Proposition A.2).
Unlearning in knowledge graphs and graph networks
Exact unlearning retrains the model on the retained data [6 , 5 ] . Approximate unlearning edits the released model instead. One branch takes a single step that approximates the effect of removing the forgotten examples, with the inverse Hessian or its Fisher approximation [35 , 22 , 30 , 48 , 20 ] . The other optimizes an objective for a few steps on the forgotten examples, sometimes with retained ones [32 , 73 ] .
The object of the edit depends on the model. In the translational and rotational backbones we study (§ 3 ), the trainable parameters are the entity and relation tables. Their score function has no weights of its own [4 , 60 , 53 ] . A row edit changes the scores of the facts at that row alone, so the change and its cost can be confined to the neighbourhood of the deletion. A graph neural network instead computes every node’s representation from shared encoder weights by message passing. An edit to those weights changes every representation, so the collateral change, and the recomputation needed to control it, grow with the graph. Knowledge-graph unlearners therefore edit the tables themselves, and they differ in how much of the tables they update.
Liu et al. [39 ] state the task as an update of the two tables, and their method GraphDPO updates both tables. It trains a preference objective that prefers a reconstructed alternative over each forgotten triple, with the original model as reference. It also replays the retained triples adjacent to the forgotten ones. ZeroFisher [64 ] applies an influence update in which a Fisher matrix replaces the Hessian and zeroth-order estimates replace the gradients. It iterates that update for a tuned number of steps (Appendix § 9 .§ 2 ). It restricts the update to the rows of the local neighbours of the forgotten edges, because the cost of the full update grows with the size of the graph. Schema [63 ] re-embeds the two-hop neighbourhood of the deleted entities so that it matches a subgraph with the same schema and without the deleted facts. MetaEU [66 ] meta-learns a shared generator that regenerates the rows of the forgotten entities from their relations and neighbours.
Graph-neural-network unlearners edit the encoder or its output representations. GNNDelete inserts a deletion operator on the node representations of the affected subgraph and freezes the encoder [11 ] . GIF applies an influence update to the encoder weights with a term for the affected neighbours [62 ] . Projector projects the weights of a linear encoder off the deleted node features [12 ] , and OpenGU benchmarks such methods [16 ] .
These knowledge-graph and graph-network unlearners use graph structure as the scope of the edit or as a preservation term for neighbours. None has a term that computes what training on those neighbours does to the forgotten score. They report the ranking the released model gives before any fine-tune (Appendix § 11 .§ 1 ). We extend that reading and ask what the edit is worth once training resumes.
Benign relearning and the update model
An unlearned model gives back what it was asked to forget once training resumes. In language models, fine-tuning on data that contains none of the forgotten answers restores them [28 , 41 , 72 ] . Hu et al. [28 ] are the origin of benign relearning and of the reading that unlearning may obfuscate rather than delete. We transplant that setting to knowledge-graph embeddings, score it against a retrained model that receives the same fine-tune, and replace an informal correlation between forgotten and retained data with a closed-form account of the linearized response of the fine-tune. Deeb and Roger [13 ] show that fine-tuning on an accessible subset of the forget set restores held-out forgotten facts, and they name the absence of a reliable reference as the open problem. Our update holds no forgotten fact at all, and the reference is the retrained model after the same update.
Recovery grows as the fine-tune proceeds, so evaluations read the worst point over its steps and learning rates [13 , 36 ] . Others read the worst case over seeds, configurations and update recipes [43 , 8 ] . Section 5 follows both, reading the epoch of peak leakage and the worst update configuration, but averages over seeds.
Siddiqui et al. [49 ] establish the reading we adopt. They show that retain-only fine-tuning restores forget accuracy for most vision unlearners while a retrained model stays robust, they define tamper resistance as the requirement that the relearned unlearner not beat the relearned retrained model, which is the leakage of equation (1) read against the oracle’s zero here, and they report that unseen data relearn less. Two things differ on a knowledge graph. The retrained model itself recovers under the update (Figure 2 ), so the reference is not a fixed point. And an update built only from never-trained edges is read for every method in Appendix § 10 .§ 2 (Table 13 ).
Yoon et al. [72 ] attribute benign relearning in language models to syntactic alignment between the relearning data and the forgotten targets, and they defend by paraphrasing the forget set. A triple cannot be paraphrased, and the alignment between a forgotten fact and its retained neighbours is exact, which removes the data-side remedy and forces a storage-side one. Suriyakumar et al. [54 ] show the same failure in diffusion models, where fine-tuning on concepts disjoint from the erased one resurrects it, and they lower-bound the leaked gradient mass by the overlap of the two spans. We sharpen that observation into an objective in which the edit is chosen against the overlap rather than measured after the fact.
Dehghani et al. [14 ] recover forgotten classes with no forget, retain or auxiliary data, by probing the representation space and updating the head alone, and they measure excess recoverability relative to a retrained model under an identical audit. We follow that convention and report the leakage beyond the retrained oracle in MRR points and as a share of the erased knowledge, beside the forgetting at release, because a method can buy one with the other (§ 5 ).
Relearning-robust unlearning methods
Three families anticipate the update, and they differ in whether they simulate it, replace it by a proxy, or choose the subspace the edit occupies. Appendix § 11 .§ 1 sorts the same methods by how the update enters their objective, as a simulation, an assumption or a data-free proxy.
Unrolled methods anticipate the update by simulation. They simulate the update inside the objective and evaluate the forgetting loss at the simulated weights. Meta-unlearning takes the gradient through the simulation exactly [19 ] , and TAR takes it by a straight-through estimator (Tamrisa et al., 2025). ResAlign does similarly, taking the gradient implicitly through a proximal model of the simulation’s end point [37 ] . MUDMD does not differentiate through the simulation. It evaluates the forgetting gradient at a simulated copy and applies it to the original weights [51 ] . KAU replaces the simulation by the closed-form linearized response of the update for a shallow relational kernel.
Proxy methods replace the update by a cheaper quantity that does not describe the update itself. SAM penalizes the sharpness of the forgetting loss under weight perturbations over a finite ball [17 ] . ILU penalizes the variation of the loss across auxiliary datasets, a stationarity penalty with one scalar per dataset [58 ] . Siddiqui et al. [49 ] regularize a weight-space distance to the original model. Rosati et al. [45 ] control the weight spectrum and show that a fine-tune designed against any method only slows recovery undoes it. That result, detailed in Appendix § 11 .§ 1 , is why we report the gap along the fine-tune and not only at its end. Relearning-speed measures [36 , 57 ] are the unpaired version of that reading.
Subspace methods, the third family, choose where the edit lives. Retained-span projection places the edit off the span of the retained gradients to protect utility [21 , 9 , 74 ] . Slow-direction methods place the edit in directions that an update restores slowly. MCU and CIR take those directions from the principal components of the forget set’s representations and activations respectively [65 ] (Sondej and Yang 2025). RepSelect takes them from the weight gradient that a low-rank fine-tune on the forget set accumulates [52 ] . FRAG places the edit on weights whose input channels the retained data barely activate [10 ] .
Appendix E.6 traces the retained-span projector to continual learning and discusses MCU, and Appendix E.7 discusses FRAG and RepSelect.
These methods are built for deep networks. Each reads its subspace or its proxy off the network’s weights and activations, or runs one simulated update. None of these quantities says which training example moved which parameter. A deep model does not expose that attribution in closed form. Carried over to a knowledge-graph embedding, they leave its structure unused. An unrolled method returns the rows after one simulated update and no expression for which edge moved which row. A proxy method reads sharpness, weight distance or spectrum off the whole table, and those quantities say nothing about which edges drive which rows. A projection method projects off the retained-gradient span over all rows rather than off the span of the update’s edges at the shared rows. KAU instead writes the update’s effect on each forgotten fact in closed form, as a function of drawn edges the update may train on, and differentiates through it. Appendix E.7 reads both projection families through the survival filter of § 4.6 , the slow-direction ones on a spectrum estimated from the forget or retained data.
The tangent-kernel response and its origin
The function KAU differentiates through is the linearized response of training, and it can be built up from one gradient step. Take one gradient step on one example. To first order, the model’s output on a second example moves in proportion to the inner product of the two examples’ output gradients. That inner product is the tangent kernel [31 ] , and it says how much training on one example moves the prediction for another. Over a run of small steps the same rule holds at every step, with the kernel held at the current parameters. To first order the total change in any output is then the solution of a ridge-regularized linear system in that kernel (§ 4.2 ). The ridge term stands in for the finite length of the run. In a knowledge-graph embedding a triple’s score depends on three rows. The kernel between two triples is then an explicit expression in the rows of the two triples, and it is zero unless they share an entity or a relation. The kernel therefore names, for each forgotten fact, which trained edges move it and through which rows. That is the attribution the methods of Appendix E.5 lack. The effect of the update on a forgotten fact can then be written down as a linear system in that kernel rather than simulated.
The linearized cross-task response we differentiate through is not ours. Doan et al. [15 ] and Bennani et al. [3 ] derive it for continual learning, where one phase of training moves the function on an earlier phase’s data through the tangent kernel. Both use it to bound the resulting interference. Hidekel and Raviv [26 ] give a recent function-space account of the same motion. Malladi et al. [42 ] describe the fine-tuning of a pretrained model by the same kernel. Li et al. [37 ] differentiate a forgetting loss through a proximal model of a simulated fine-tune, after Rajeswaran et al. [44 ] . What is new here is the use we make of it. The second phase is the downstream fine-tune, and the residual that drives it on retained edges is created by the unlearning edit instead of being given by the data. The resulting closed form is placed inside an objective the unlearner minimizes over a class of draws.
Golatkar et al. [21 ] run the same kernel algebra in the opposite direction. They derive a one-shot scrubbing update from the linearized dynamics, project the forgetting gradient off the span of the retained gradients, add Fisher-shaped noise, and bound what a reader of the scrubbed weights can extract. Their kernel couples each forget sample to each retain sample pairwise, and that coupling is spent on computing the edit. Their analysis ends at the scrubbed weights, and their relearning readout fine-tunes on the complete data, forget set included. Ours begins with the benign fine-tune after release. We use the same algebra with the roles inverted, so that the kernel predicts the update instead of computing the edit. Corollary A.3 identifies their projector, restricted to one entity row, with the zero-ridge limit of our operator once the unseen channel is switched off. Read through the survival filter of Corollary A.2, a projector introduced to protect utility also marks the edits that continued training on retained data cannot undo to first order.
The projector off the span of earlier data has a second origin in continual learning. GPM keeps a new task’s gradient off the activation bases of past tasks and Adam-NSCL keeps it in the approximate null space of their feature covariance [47 , 59 ] . Both are optimizers of the later phase, so their invariance holds while they control the update, and the unlearners that reuse the construction [9 , 74 ] protect the retained loss from the edit.
Xiao et al. [65 ] give the closest statement about which components a fine-tune restores. Under an isotropic-kernel linearization, an edit placed in a high-variance component of the representation is reversed at a rate proportional to that variance, which is what their minor-component method exploits. The isotropic kernel drops exactly the off-diagonal blocks that carry the coupling in an embedding model, where the kernel between two triples is nonzero only when they share a row. Our ridge σ v \sigma_v σ v
Methods closest in design
Chen et al. [10 ] argue that robustness is governed by where an update lives rather than by how far it moves, and they give a score computed per checkpoint that needs no relearning run. Their pruning rule places the edit on weights that the retain data barely activate, so that a retain-only fine-tune leaves them inert. In a knowledge graph the rows a forgotten fact uses are the rows its retained neighbours use, so no row is inert under a retain-only update. The placement question then has to be asked inside the span of an entity’s edges rather than across channels. For a shallow embedding model that question can be made exact, because the span of the update’s data at an entity is a closed-form graph-local tangent space. The response goes one step further by evaluating the score at the shifted rows instead of along the tangent.
Sondej et al. [52 ] confine the edit to the low-variance complement of the forget gradient’s principal subspace and summarize the principle as selectivity rather than update strength. We share the idea of storing suppression outside the subspace a later fine-tune reaches. We define that subspace by drawn edges the update may train on, through a kernel available in closed form. In the linearized model the anticipated loss is the plain forgetting objective on the part of the edit that survives the update (Corollary A.1). Projection onto the complement is the zero-ridge threshold of that survival filter, a consequence instead of a starting point (Corollary A.2).
Yin et al. [71 ] calibrate a one-sided loss against a reference model’s margins with a budget-bounded certificate. Our loss is one-sided in the same way and is applied to the anticipated post-update score, and its per-fact targets are computed from quantiles of corrupted variants under the original model, so it needs no access to the retrained model.
These three, together with the retained-span methods above, share one object with us and use it differently. A null space enters prior work in three roles. It is a fixed layer operator that completes an ill-posed inverse ([70 , 18 ] ). It is the null space of retained features or gradients that keeps a later update off earlier data in continual-learning optimizers ([47 , 59 ] ) and that protects utility from the unlearning edit ([21 , 9 , 27 , 74 ] ). It is the low-variance part of the forget representation that a fine-tune restores slowly ([65 , 52 ] (Sondej and Yang 2025)). Ours is the complement of the span of the update’s data, chosen for persistence. In the linearized model it is the set of edits the update leaves untouched (Proposition A.1). Read through the survival filter, the second role is its hard threshold at level zero, restricted to the involved entities’ rows, when the draw is exactly their retained edges. The third has the form of a hard threshold at a positive level, taken on a proxy spectrum (Corollary A.2). In the linearized model under a uniform ridge, KAU’s gradient instead weights each direction by its surviving fraction, computed from the spectrum of its own update draws. Unseen edges in the update can move edits that retained-span projection preserves, whereas KAU’s draws include stand-ins for those edges (§ 4.1 ). Where the forgotten gradient lies inside the retained span, a hard projector removes the whole edit, which the appendix of GU records as a local trade-off ([74 ] ). On a graph that is the entity of high degree. There the cap k max k_{\max} k m a x § 4.2 ).
Remaining placements
Three further threads touch the mechanism. The image of an alignment edit that is pulled back toward its origin is due to Ji et al. [33 ] . Arora et al. [2 ] and Heo et al. [24 ] study how a growing row norm shrinks an effective learning rate. The retraction rule of Appendix § 8 .§ 4 removes this effect. Studies of when an unlearned model is reversible ([23 , 7 , 67 ] ) ask the same question at the level of the loss landscape.
