Matched Excess-Outranker Regularization for Candidate-Set Interference in Continual Knowledge Graph Embedding

Hao Ren; Junbin Gao; Jiaojiao Jiang

cs.AIAug 25, 2026

Matched Excess-Outranker Regularization for Candidate-Set Interference in Continual Knowledge Graph Embedding

Authors: Hao Ren, Junbin Gao, Jiaojiao Jiang

Organizations: University of New South Wales Sydney, NSW, Australia · The University of Sydney Sydney, NSW, Australia

Abstract

Continual knowledge graph embedding updates entity and relation representations as a graph grows. Existing methods primarily address catastrophic forgetting, but entity admission also changes the candidate universe of every compatible query. A historical answer can therefore lose rank even when its score and its ordering among old entities are preserved. We formalize this effect as candidate-set interference and introduce Matched Excess-Outranker Regularization (MEOR), a host-level objective that compares smooth answer-relative newcomer pressure with score-blind, structurally matched old references. Its one-sided penalty acts only when newcomer competition exceeds the matched reference, preserving the host learner's signal for legitimate new entities. Across eight paired runs on ENTITY-ComplEx, MEOR improves historical current-universe mean reciprocal rank (MRR) by 0.0057 over replay and reduces candidate-set interference by 0.0055, with one-sided 95% lower bounds of 0.0052 and 0.0051, respectively. It satisfies the preservation criteria for old-universe ranking and newcomer acquisition and improves historical current-universe MRR over persistent calibration, matched maximum regularizer (MMR), and unmatched old regularizer (UOR). Direct ablations support each component of its reference construction and aggregation. Adding MEOR also improves historical ranking in all ten reported FBInc-S and FBInc-L host and backbone settings, with every paired 95% confidence interval excluding zero. These results establish candidate admission as a distinct source of continual rank loss and show that it can be controlled without replacing the underlying embedding architecture or continual learner.

Figures & tables

Figure 1. Cumulative evolution of a continual knowledge graph across three snapshots. Dark orange nodes and red edges mark new knowledge, while light orange nodes and black edges show retained knowledge.

Figure 2. Candidate-set interference and the query-specific computation of Meor . The upper-left panel compares a historical query under old and expanded candidate universes, where the answer loses rank while old candidates retain their relative order. The upper-right panel contrasts newcomer competition with a matched-old reference. The lower panel traces a replay occurrence through score-blind structural matching, answer-relative gaps, smooth aggregation, and the one-sided Meor penalty combined with the host loss.

Dataset	Snapshot 0			Snapshot 1			Snapshot 2			Snapshot 3			Snapshot 4
	$\|\mathcal{E}\|$	$\|\mathcal{R}\|$	Facts	$\|\mathcal{E}\|$	$\|\mathcal{R}\|$	Facts	$\|\mathcal{E}\|$	$\|\mathcal{R}\|$	Facts	$\|\mathcal{E}\|$	$\|\mathcal{R}\|$	Facts	$\|\mathcal{E}\|$	$\|\mathcal{R}\|$	Facts
ENTITY	$2{,}909$	$233$	$46{,}388$	$5{,}817$	$236$	$72{,}111$	$8{,}725$	$236$	$73{,}785$	$11{,}633$	$237$	$70{,}506$	$14{,}541$	$237$	$47{,}326$
FBInc-S	$2{,}909$	$233$	$46{,}388$	$2{,}919$	$233$	$235$	$2{,}930$	$233$	$152$	$2{,}940$	$233$	$180$	$2{,}950$	$233$	$239$
FBInc-L	$2{,}909$	$233$	$46{,}388$	$3{,}010$	$233$	$3{,}110$	$3{,}110$	$234$	$2{,}736$	$3{,}211$	$234$	$2{,}908$	$3{,}312$	$234$	$3{,}105$
WN-CKGE	$24{,}567$	$11$	$55{,}801$	$28{,}660$	$11$	$9{,}300$	$32{,}754$	$11$	$9{,}300$	$36{,}848$	$11$	$9{,}300$	$40{,}943$	$11$	$9{,}302$

Table 1. Dataset statistics. Entity and relation counts are cumulative; Facts is the number of triples introduced at each snapshot.

Method	$H_{\mathrm{cur}}\uparrow$	$H_{\mathrm{old}}\uparrow$	$D_{\mathrm{MCI}}\downarrow$	$A_{\mathrm{TN}}\uparrow$
Replay	$0.0830$	$0.1199$	$0.0369$	$0.1700$
Persistent calibration	$0.0816$	–	–	$0.1753$
MMR	$0.0836$	$0.1200$	$0.0364$	$0.1695$
UOR	$0.0842$	$0.1200$	$0.0358$	$0.1698$
Meor	$0.0887$	$0.1201$	$0.0314$	$0.1715$

Table 2. Absolute endpoint performance of Meor and mechanism-matched controls in the primary ENTITY–ComplEx setting.

Comparator	Mean	LB	Mean	LB	Mean	LB	Mean	LB	W/T/L
	$\Delta H_{\mathrm{cur}}\uparrow$		$\Delta H_{\mathrm{old}}\uparrow$		$D_{\mathrm{MCI}}$ reduction $\uparrow$		$\Delta A_{\mathrm{TN}}\uparrow$
Replay	$0.0057$	$0.0052$	$0.0002$	$-0.0001$	$0.0055$	$0.0051$	$0.0015$	$0.0008$	$8/0/0$
Persistent calibration	$0.0071$	$0.0065$	–	–	–	–	$-0.0038$	$-0.0043$	$8/0/0$
MMR	$0.0051$	$0.0047$	$0.0001$	$-0.0003$	$0.0050$	$0.0049$	$0.0020$	$0.0015$	$8/0/0$
UOR	$0.0045$	$0.0030$	$0.0001$	$-0.0011$	$0.0044$	$0.0041$	$0.0017$	$0.0012$	$7/0/1$

Table 3. Paired effects of Meor relative to mechanism-matched controls on ENTITY–ComplEx across eight paired training realizations.

Isolated property	Comparator	$\Delta H_{\mathrm{cur}}\uparrow$		$D_{\mathrm{MCI}}$ reduction $\uparrow$		$\Delta A_{\mathrm{TN}}\uparrow$
		Mean	LB	Mean	LB	Mean	LB
Smooth tail aggregation	MMR (maximum)	$0.0051$	$0.0047$	$0.0050$	$0.0049$	$0.0020$	$0.0015$
Structural matching	UOR (role-only references)	$0.0045$	$0.0030$	$0.0044$	$0.0041$	$0.0017$	$0.0012$
Query-specific assignment	Shuffled matched references	$0.0008$	$0.0005$	$0.0007$	$0.0002$	$0.0002$	$-0.0002$
Old-reference centering	Uncentered smooth penalty	$0.0011$	$0.0006$	$0.0009$	$0.0003$	$0.0003$	$-0.0002$

Table 4. Direct ablations of Meor ’s reference construction and aggregation on ENTITY–ComplEx.

Dataset	Host family	Host–backbone	$\Delta H_{\mathrm{cur}}\uparrow$	Paired 95% CI	W/T/L	$\Delta A_{\mathrm{TN}}\uparrow$	$\Delta A_{\mathrm{TN}}$ LB
FBInc-S	Replay	ComplEx	$0.0026$	$[0.0017,0.0043]$	$8/0/0$	$-0.0004$	$-0.0011$
FBInc-S	Replay	DistMult	$0.0022$	$[0.0010,0.0034]$	$7/1/0$	$-0.0002$	$-0.0008$
FBInc-S	Replay	TransE	$0.0020$	$[0.0009,0.0031]$	$7/1/0$	$-0.0001$	$-0.0006$
FBInc-S	Source-Bound	LKGE–TransE	$0.0023$	$[0.0011,0.0035]$	$7/0/1$	$-0.0012$	$-0.0024$
FBInc-S	Source-Bound	IncDE–TransE	$0.0029$	$[0.0016,0.0042]$	$8/0/0$	$-0.0010$	$-0.0021$
FBInc-L	Replay	ComplEx	$0.0026$	$[0.0019,0.0045]$	$8/0/0$	$-0.0008$	$-0.0016$

Table 5. Paired effects of adding Meor to replay hosts and source-bound continual-learning adapters on FBInc-S and FBInc-L.

KG Embedding

Knowledge graph embedding (KGE) represents entities and relations as vectors or structured geometric objects for prediction and reasoning.

See all 56 papers

Apr 21, 2026

Revisiting Catastrophic Forgetting in Continual Knowledge Graph Embedding

Knowledge Graph Embeddings (KGEs) support a wide range of downstream tasks over Knowledge Graphs (KGs). In practice, KGs evolve as new entities and facts are added, motivating Continual Knowledge Graph Embedding (CKGE) methods that update embeddings over time. Current CKGE approaches address catastrophic forgetting (i.e., the performance degradation on previously learned tasks) primarily by limiting changes to existing embeddings. However, we show that this view is incomplete. When new entities are introduced, their embeddings can interfere with previously learned ones, causing the model to predict them in place of previously correct answers. This phenomenon, which we call entity interference, has been largely overlooked and is not accounted for in current CKGE evaluation protocols. As a result, the assessment of catastrophic forgetting becomes misleading, and CKGE methods performance is systematically overestimated. To address this issue, we introduce a corrected CKGE evaluation protocol that accounts for entity interference. Through experiments on multiple benchmarks, we show that ignoring this effect can lead to performance overestimation of up to 25%, particularly in scenarios with significant entity growth. We further analyze how different CKGE methods and KGE models are affected by the different sources of forgetting, and introduce a catastrophic forgetting metric tailored to CKGE.

Gerard Pons, Carlos Escolano, Besim Bilalli +1

Data-intensive Technologies and Knowledge Systems (DTAK), Department of Service and Information System Engineering, Universitat Politècnica de Catalunya, Barcelona, 08034, Catalonia, Spain · Intelligent Data Science and Artificial Intelligence Research Center (IDEAI), Department of Computer Science, Universitat Politècnica de Catalunya, Barcelona, 08034, Catalonia, Spain

Graph Representation Learning KG Embedding Graph Embedding KG Completion Catastrophic Forgetting

Ask PDF

Oct 22, 2026

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

Approximate unlearning answers a deletion request on a knowledge-graph embedding by editing entity embeddings instead of retraining from scratch. These embeddings keep being updated as new facts arrive. Under this ordinary continued training, forgotten facts recover more than in the exact-unlearning baseline, a model retrained without them and given the same continued training. We trace this relearning to entity embeddings shared by forgotten and new facts. To our knowledge, this is the first study of relearning in knowledge-graph embeddings. Relearning-robust methods developed for deep networks do not account for the graph structure underlying this recovery. We propose Kernel-Anticipated Unlearning (KAU), which uses the tangent kernel to model how continued training changes forgotten facts' scores through these shared parameters. KAU expresses this first-order response in closed form and differentiates through it inside the forgetting loss. The objective steers edits toward directions that continued training reverses less. We compare KAU with state-of-the-art knowledge-graph unlearners and relearning-robust methods under identical continued training, measuring leakage beyond the exact-unlearning baseline. Across three backbones, KAU reduces the strongest knowledge-graph unlearner's leakage by 46-63% on FB15k-237 and 50-82% on CoDEx-L, at higher retained utility.

Parnian Fazel, Mohammad M Maheri, Hamed Haddadi

Imperial College London · University of Oxford

Machine Unlearning Graph Unlearning KG Embedding

Ask PDF

Sep 10, 2026

When Successful Knowledge Graph Edits Displace Correct Answers: Rank-Level Locality beyond Parameter Support

Editing a knowledge graph embedding (KGE) model to promote a desired answer can displace correct answers from the returned list. Locality tests based only on facts that reuse the edited parameter can miss this ranking effect. We introduce a common rank-displacement audit at three scopes: facts supported by the edited parameter, other correct answers to the target query, and correct answers across queries with the same relation. We also derive dimensional and geometric conditions for an update to improve the target while exactly preserving selected scores. On FB15k-237 with DistMult and ComplEx, direct promotion always moves the target into the top ten, but does so without damage in only 23.0--23.2% of edits. Strict preservation causes no measured damage, yet succeeds in only 1.3--1.4%. Support-regularized entity editing gives the highest joint success, 36.3--37.7%, while rank-truncated preservation reaches 32.8--34.7% and reduces the mean number of displaced answers from about 14 to 1.2. Experiments across dimensions, scorers, ranking conventions, and a learned editor show that locality depends on both the protected scope and the editing mechanism. KGE editing should therefore report correction success together with the incidence and severity of rank displacement.

Yi-Cheng Lai, Jerry Wang, Hsin-Ling Hsu +3

Institute of Information Science, Academia Sinica Taipei, Taiwan · University of Illinois Urbana-Champaign Urbana, IL, USA · National Chengchi University Taipei, Taiwan

Knowledge Editing KG Embedding

Ask PDF

Abstract

KG Embedding

Explore similar work

Revisiting Catastrophic Forgetting in Continual Knowledge Graph Embedding

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

When Successful Knowledge Graph Edits Displace Correct Answers: Rank-Level Locality beyond Parameter Support