KGCRR: An Effective Metric-Driven Knowledge Graph Completion Framework by Designing a Novel Upper Bound Function with Adaptive Approximation to Reciprocal Rank

Kuan Xu, Kuo Yang, Jian Liu, Xiangkui Lu, Jun Wu, Xuezhong ZhouAAAI 2025 · DOI

TL;DR

This paper introduces KGCRR, a novel framework for Knowledge Graph Completion (KGC) that addresses the critical inconsistency between KGC evaluation metrics (like Reciprocal Rank) and common optimization objectives. By proposing a new upper bound function called CRR, which adaptively approximates Reciprocal Rank, KGCRR significantly improves KGC performance, achieving an average MRR improvement of 19.06% across benchmark datasets.

What Problem Does This Paper Address?

Knowledge Graphs (KGs) are powerful tools for information retrieval and decision-making, but they often suffer from missing information. Knowledge Graph Completion (KGC) aims to fill these gaps by predicting missing links (triples). A key metric for evaluating KGC performance is the Reciprocal Rank (RR), which measures how high the ground-truth item is ranked among all possible candidates. However, existing KGC methods often optimize objective functions (like Log-Likelihood or margin-based losses) that are not directly aligned with RR. This misalignment can lead to sub-optimal performance, where models might achieve low loss but fail to improve the crucial ranking metric. While directly optimizing RR is challenging due to gradient vanishing issues, existing upper bounds like "Rank loss" also have limitations, particularly in emphasizing top-ranked items.

Methods

The core contribution of this paper is the CRR (Close to Reciprocal Rank) loss function. CRR is designed as a novel upper bound to the RR loss, aiming for a closer approximation than existing methods. Key features of CRR include:

  • Adaptive Approximation: CRR uses a sigmoid function with two parameters:
  • Temperature ($\tau$): Smooths the sigmoid, similar to existing approaches.
  • Pressure ($p$): A new parameter that controls the shift of the sigmoid. Increasing $p$ forces the sigmoid to more closely approximate the indicator function when scores are negative, thereby improving the approximation to RR, especially for highly scored ground-truth items.
  • Transformation Function: A log function is applied to the CRR loss to further enhance its sensitivity to top-ranking positions, aligning with the emphasis of the RR metric.
  • Theoretical Guarantees: The authors theoretically prove that CRR is indeed an upper bound to RR and that increasing the pressure parameter $p$ narrows the gap between CRR and RR, leading to better optimization. They also demonstrate that CRR mitigates the gradient vanishing issues associated with directly optimizing RR.
  • Plug-and-Play: CRR is designed to be a drop-in replacement for existing loss functions in various KGE models.

Datasets

The proposed KGCRR framework was evaluated on two widely used KGC benchmark datasets:

  • FB15k-237: A subset of Freebase, known for its challenging link prediction task.
  • WN18RR: A subset of WordNet, also a standard for KGC evaluation.

Key Insights and Ideas

  • Metric-Objective Mismatch is Real: The paper clearly illustrates the inconsistency between common KGC loss functions and the RR metric, showing how optimizing for one doesn't guarantee improvement in the other.
  • The Power of "Pressure": The introduction of the "pressure" parameter ($p$) in the sigmoid function is a novel and effective way to adaptively approximate the indicator function, which is crucial for improving RR optimization.
  • Top-Rank Sensitivity Matters: The RR metric heavily favors correctly ranking the ground-truth item at the very top. CRR, with its adaptive approximation and transformation function, explicitly addresses this by being more sensitive to top-ranking positions than standard losses.
  • CRR is a General Improvement: The framework's plug-and-play nature means it can boost the performance of various existing KGE models without requiring fundamental architectural changes.

Key Results

  • Significant MRR Improvement: KGCRR achieved an average improvement of 19.06% in Mean Reciprocal Rank (MRR) across experiments on FB15k-237 and WN18RR.
  • Superiority over Baselines: CRR consistently outperformed margin-based and Log-Likelihood losses on both datasets, showing an average MRR improvement of 26.49% and 32.31% respectively on FB15k-237.
  • Better Approximation to RR: The paper demonstrates that CRR has a higher Pearson correlation coefficient with RR compared to other losses, indicating a better alignment.
  • Faster Convergence: Experiments showed that CRR leads to more rapid convergence compared to RR loss and other baseline losses, likely due to its better gradient properties.

Limitations and Future Work

  • Parameter Sensitivity: While the "pressure" parameter ($p$) is key to CRR's effectiveness, the paper notes that its impact is sensitive, and an optimal value needs to be found. Overly large values of $p$ can lead to performance degradation, possibly due to a new gradient vanishing issue.
  • Dataset Dependency: The degree of improvement from CRR can vary across datasets. The paper suggests that datasets with fewer candidate entities might benefit more, as CRR can more effectively rank the ground-truth items.
  • Future Directions: The authors suggest exploring more flexible objective functions for KGC and investigating different transformation functions beyond the log function to further enhance CRR's capabilities.

Summary updated

BibTeX
@inproceedings{xu2025kgcrr,
  author = {Kuan Xu and Kuo Yang and Jian Liu and Xiangkui Lu and Jun Wu and Xuezhong Zhou},
  title = {{KGCRR: An Effective Metric-Driven Knowledge Graph Completion Framework by Designing a Novel Upper Bound Function with Adaptive Approximation to Reciprocal Rank}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i12.33410},
}
Figure