Source-linked AI summary
Matched Excess-Outranker Regularization for Candidate-Set Interference in Continual Knowledge Graph Embedding
Hao Ren, Junbin Gao, Jiaojiao Jiang
TL;DR
Continual KGE can lose historical rank because graph growth adds candidates, even without old-entity forgetting. The paper introduces MEOR to penalize only excess newcomer pressure against structurally matched old references. Across ENTITY–ComplEx and FBInc settings, MEOR improves historical ranking while satisfying preservation criteria.
Problem
Candidate admission expands every compatible query’s candidate universe, creating historical rank loss that existing catastrophic-forgetting-focused continual KGE objectives do not directly regulate.
Method
MEOR compares smooth answer-relative newcomer pressure with score-blind, structurally matched old references and applies a one-sided penalty only to excess competition.
Results
MEOR improves historical current-universe MRR by 0.0057 over replay and reduces candidate-set interference by 0.0055 on ENTITY–ComplEx, while improving MRR in all ten reported FBInc settings.
Takeaways & Limitations
Candidate admission is a distinct source of continual rank loss that can be controlled without replacing the embedding architecture or continual learner.
Takeaways & Limitations
The empirical claim is limited to the reported streams, backbones, hosts, and fixed aggregation and matching settings; large admission batches also increase exact cohort-scoring cost.
Abstract
from arXiv · showhide
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.
1 Introduction
Continual KGE must address candidate-set interference: newly admitted entities can demote historical answers without changing old-entity ordering. MEOR regulates excess newcomer competition while preserving the host learner’s ability to learn new facts.
- Motivation: Candidate-set interference occurs when admitted entities enter historical queries’ candidate universes and displace established answers despite unchanged old-entity ordering.It is distinct from catastrophic forgetting and can be isolated by comparing old- and current-universe rankings at a fixed checkpoint.
- Method: MEOR measures smooth answer-relative newcomer pressure and compares it with score-blind, structurally matched old-candidate pressure.Matching uses prediction role, degree, and incident relation-role structure rather than model scores.
- Method: A one-sided squared-hinge penalty acts only when newcomer pressure exceeds the matched old reference.Newcomers below the reference receive no penalty, while the host objective continues governing new-fact learning.
- Results: 0.0057 higher historical current-universe MRR and 0.0055 lower candidate-set interference were obtained over replay across eight ENTITY–ComplEx paired runs.The corresponding one-sided 95% lower bounds were 0.0052 and 0.0051.
- Results: MEOR improved historical ranking over persistent calibration, MMR, and UOR, while direct ablations supported all four reference-construction and aggregation components.The components were smooth tail aggregation, structural matching, query-specific assignment, and old-reference centering.
- Results: Across ten FBInc-S and FBInc-L stream, backbone, and host combinations, MEOR improved historical current-universe MRR with every paired 95% confidence interval excluding zero.Every newcomer-acquisition bound remained within the preservation margin.
2 Related Work
Related work frames continual KGE as incremental representation learning focused mainly on catastrophic forgetting. The paper identifies candidate-set interference as a separate rank-loss mechanism caused by expanding candidate universes and an unmet intervention target.
- KGE background: KGE link prediction ranks candidate entities using learned triple scores, with filtered evaluation removing other known correct answers.The resulting rank depends on both the score function and the candidate-universe construction.
- Continual versus temporal KGE: Continual KGE updates representations as facts, entities, or relations arrive, whereas temporal KGE treats time as semantic information in prediction.Continual graph states may reflect acquisition, benchmark construction, or deployment rather than validity intervals.
- Existing approaches: Existing continual KGE methods use replay, regularization, distillation, selective updates, reconstruction, transfer, and modular adaptation to retain prior knowledge while incorporating updates.Despite architectural differences, these methods share the stability–plasticity objective.
- Candidate-set interference: Candidate-set interference demotes historical answers when new entities become eligible competitors, even if answer scores and old-entity ordering remain unchanged.The loss arises from additional competitors rather than failure to rank established entities.
- Candidate-set interference: A same-checkpoint comparison of old- and current-universe evaluation isolates rank loss attributable to admitted candidates, unlike catastrophic forgetting caused by model updating.Old-candidate evaluation can therefore overstate continual performance.
- Intervention gap: Current-universe evaluation exposes the problem, but reviewed continual objectives do not directly regulate admitted entities’ ranking pressure on historical answers.This intervention gap motivates treating candidate competition as an explicit learning target within the fixed continual KGE process.
3 Continual KGE Problem Formulation
The formulation models cumulative graph growth, defines scoring and historical rank under old and current candidate universes, and separates query roles and evaluation endpoints. Candidate expansion is assessed as a distinct loss while old-universe ranking and newcomer acquisition serve as preservation objectives.
- 3.1 Graph Growth and Candidate Admission: A cumulative graph snapshot Gᵤ contains entities Eᵤ, relations Rᵤ, and observed triples Fᵤ⊆Eᵤ×Rᵤ×Eᵤ.The graph state represents information observed through snapshot u.
- 3.1 Graph Growth and Candidate Admission: Queries mask either the head or tail entity, with evaluated update indices U and prediction modes D specifying the experimental scope.The missing endpoint d identifies whether head or tail prediction is used.
- 3.1 Graph Growth and Candidate Admission: At each update, the model assigns higher scores to candidates it prefers, and the formulation is independent of embedding architecture.Method and training-realization indices distinguish learning procedures and paired runs.
- 3.2 Historical Rank Loss Under Candidate Growth: Historical queries use the same model state and filtering rule over candidate sets drawn from Eᵤ−1 and Eᵤ.The answer is retained while newly introduced candidates appear only through candidate expansion.
- 3.2 Historical Rank Loss Under Candidate Growth: Ranks are induced by candidate scores and a fixed tie rule, allowing old- and current-universe ranks to be compared for the same historical occurrence.The ordering relation determines which candidates precede the answer.
- 3.2 Historical Rank Loss Under Candidate Growth: The rank identity isolates loss attributable to newly admitted candidates even when old-entity ordering is unchanged, without assuming unchanged representations.Current-universe evaluation reveals interference that old-candidate evaluation cannot measure.
- 3.3 Query Roles and Evaluation Objectives: Historical, target-newcomer, and query-newcomer occurrences represent distinct learning requirements and are evaluated separately.Target newcomers have new answers; query newcomers have new query entities but old answers.
- 3.3 Query Roles and Evaluation Objectives: Current-universe historical MRR is the primary utility outcome, old-universe historical MRR is a preservation outcome, and candidate-expansion loss is not sufficient alone to establish useful ranking.Endpoints require nonempty predefined query sets, with equal weighting across cells and within-cell queries.
4 Matched Excess-Outranker Regularization
MEOR measures newcomer competition relative to historical answers, compares it with score-blind structurally matched old references, and penalizes only excess pressure while retaining the host objective. Its construction uses query-local normalization, matched reference cohorts, and a mean-level one-sided squared hinge.
- Answer-Relative Newcomer Competition: MEOR uses a smooth, answer-relative newcomer competition measure because raw outranker counts are discontinuous and unnormalized gaps are not comparable across queries.The aggregate normalizes score gaps to the local score scale and smoothly combines the above-answer tail.
- Score-Blind Matched References: The newcomer aggregate is compared with old candidates matched by prediction mode, degree, and incident relation-role structure using score-blind nested keys.Matching falls back from the finest structural key to coarser keys when necessary, selecting the first nonempty old-entity cell.
- Score-Blind Matched References: Matched reference identifiers are fixed independently of model scores and shared across paired methods, reducing observable cohort imbalance without treating references as causal counterfactuals.The method constructs J matched draws and scores those candidates with each model.
- Matched Excess Objective: The complete refinement objective adds λLMeor to the host learner's objective while retaining its positive learning signal for newly admitted entities.When the eligible replay batch is empty, LMeor is defined as zero.
- Matched Excess Objective: MEOR adds a one-sided squared-hinge penalty after averaging matched-reference pressure, so equal mean pressure incurs no penalty and positive excess receives increasing penalty.The squared hinge has zero value and gradient at the boundary; hinging each draw separately would impose pressure even when the means match.
- Interpretation and Computational Cost: Computational cost increases with admission-batch size because the complete newcomer cohort and every reference cohort are scored; approximate cohort scoring is outside the study's scope.This is the stated computational boundary of the method.
5 Experiments and Results
The experiments evaluate MEOR’s ranking benefit, mechanism, preservation, and transfer across entity-growth streams, embedding models, and continual-learning hosts. MEOR consistently improves historical current-universe ranking while reducing candidate-set interference and satisfying the stated preservation criteria.
- Experimental setting: The evaluation uses four five-snapshot entity-growth streams and filtered head and tail prediction after every update.The primary comparison is ENTITY with ComplEx; FBInc-S and FBInc-L support transfer analysis, while WN-CKGE marks an applicability boundary rather than a positive efficacy setting.
- Primary results: At 0.0887, MEOR attains the highest historical current-universe MRR in the primary ENTITY–ComplEx setting.It also records the highest old-universe MRR and lowest candidate-set interference, whereas persistent calibration attains the highest newcomer-acquisition metric but lower current-universe MRR.
- Primary results: MEOR’s historical current-universe MRR gains over replay, persistent calibration, MMR, and UOR are 0.0057, 0.0071, 0.0051, and 0.0045, respectively.The corresponding one-sided lower bounds are 0.0052, 0.0065, 0.0047, and 0.0030.
- Primary results: Against replay, the 0.0057 current-universe MRR gain combines a 0.0002 old-universe change with a 0.0055 reduction in candidate-set interference.The analogous decomposition is reported against MMR and UOR, and every interference-reduction lower bound is positive.
- Preservation: MEOR satisfies preservation criteria: old-universe lower bounds remain above −0.005, and newcomer acquisition improves against replay, MMR, and UOR.Newcomer-acquisition gains are 0.0015, 0.0020, and 0.0017, while persistent calibration retains a mean advantage of 0.0038 and remains within the preservation margin.
- Ablations: All four MEOR components contribute positively, with smooth tail aggregation yielding the largest matched-ablation gain: 0.0051 with a 0.0047 lower bound.Structural matching, old-reference centering, and query-specific assignment contribute 0.0045, 0.0011, and 0.0008, respectively; every ablation has a positive interference-reduction lower bound.
- Transfer: Adding MEOR improves historical current-universe MRR in all ten transfer settings, with every paired 95% confidence interval excluding zero.The study applies MEOR within named hosts and across the reported streams, backbones, and embedding models rather than replacing the continual KGE architecture.
- Transfer: Transfer newcomer-acquisition effects range from −0.0001 to −0.0015, while every lower bound remains above the −0.005 preservation margin.The combined transfer results therefore report improved historical current-universe ranking under the stated newcomer-preservation criterion.
6 Limitations
MEOR’s scope is limited to entity-growth streams where newly admitted entities create excess competition, and its effectiveness depends on available structural matching information. The reported empirical boundary covers specific streams, hosts, backbones, and fixed matching settings.
- Applicability boundary: WN-CKGE documents an inactive applicability regime rather than a positive efficacy comparison.Meor and MMR had zero active records among 64 calibration records, so their regularization terms contributed neither loss nor gradient there.
- Scope: Relation-only or fact-only updates can still alter established representations without creating the entity-candidate expansion Meor targets.Meor complements replay, distillation, and parameter-stability methods rather than replacing them.
- Reference construction: Reference quality is bounded by the structural resolution available for matching.Sparse structural cells require coarser fallbacks, while structural signatures do not form a causal counterfactual.
- Empirical scope: The empirical claim is limited to ENTITY, FBInc-S, and FBInc-L, reported backbones, hosts, and fixed aggregation and matching settings.Other prediction tasks require candidate and reference definitions appropriate to their ranking spaces.
- Computational boundary: Exact cohort scoring becomes more costly as admitted entities and matched draws increase, so very large admission batches require efficient batching or approximation.
7 Conclusion
The paper identifies candidate-set interference as a distinct form of continual rank loss and addresses it with a host-level regularizer that suppresses only excess newcomer competition. Experiments show improved historical ranking across ENTITY–ComplEx and ten FBInc settings without redesigning the underlying learner or embedding architecture.
- Conclusion: Candidate-set interference lowers historical-answer rank when entity vocabulary growth adds candidates, even if old-entity ordering is preserved.A same-checkpoint rank decomposition separates admission-induced competition from parameter forgetting.
- Conclusion: MEOR compares answer-relative newcomer competition with score-blind, structurally matched old references using a one-sided objective.The host loss continues learning legitimate new knowledge.
- Conclusion: 0.0057 higher historical current-universe MRR and 0.0055 lower candidate-set interference were observed on ENTITY–ComplEx versus replay.MEOR also satisfied preservation criteria and outperformed persistent calibration, MMR, and UOR.
- Conclusion: All ten reported FBInc-S and FBInc-L stream, host, and backbone combinations improved historical current-universe MRR with paired confidence intervals excluding zero.Every newcomer-acquisition bound remained within the preservation margin.
- Conclusion: Candidate-set interference is presented as a distinct and controllable source of historical rank loss addressable without replacing the embedding architecture or continual learner.
Ethical Considerations
The paper uses established benchmarks without human participants or new personal-data collection, but knowledge-graph applications can reproduce inaccurate, sensitive, or biased information. Deployments therefore require auditing and safeguards, especially for consequential decisions.
- Ethical considerations: The study involves no human participants or collection of new personal data, limiting its direct ethical risk.
- Ethical considerations: Knowledge graphs and link prediction can reproduce inaccurate, outdated, sensitive, or socially biased information or infer unrecorded associations.
- Ethical considerations: Improper configuration could favor established entities and delay recognition of legitimate new facts or underrepresented entities.The one-sided intervention and newcomer-acquisition criterion reduce this risk but do not replace dataset and deployment auditing.
- Ethical considerations: Applications involving people or consequential decisions should examine subgroup ranking, verify provenance, restrict sensitive predictions, support correction and removal, and retain human oversight.The method should not be the sole basis for high-stakes decisions.