Technical Summary: Generalized Rank-based Evaluation for Knowledge Graph Completion

Problem Statement

Knowledge Graph Completion (KGC) aims to infer missing facts from observed knowledge graphs (KGs), a task critical for applications ranging from drug discovery to retrieval-augmented generation. Despite the proliferation of KGC models, the evaluation of these models remains underexplored. Current rank-based evaluation metrics (e.g., Mean Reciprocal Rank [MRR], Hits@K) suffer from two primary limitations:

1. Lack of Predictive Sharpness Control: Existing metrics implicitly assume a fixed level of strictness in penalizing inaccurate predictions. They often fail to distinguish between models that excel at top-ranked predictions versus those that provide consistently high-quality predictions across a broader range of ranks.
2. Popularity-Bias Sensitivity: Real-world KGs follow power-law distributions where a few entities and relations appear frequently. Standard metrics tend to overestimate models that perform well on these high-popularity triples while underestimating models that generalize better to rare, low-popularity entities and relations, which are often crucial for applications like discovering novel drug interactions.

Furthermore, under the Open-World Assumption (OWA)—where the absence of a triple does not imply falsity—existing metrics struggle to consistently estimate a model's intrinsic performance, often yielding inconsistent rankings when evaluated on incomplete subsets of facts compared to a complete (Closed-World) setting.

Methodology: The PROBE Framework

The authors propose PROBE (Predictive shaRpness and pOpularity-Bias robustness aware Evaluation), a generalized evaluation framework designed to address these gaps. PROBE decomposes the evaluation process into three stages: Prediction, Transformation, and Aggregation.

1. Rank Transformer (RT) for Predictive Sharpness

To control the degree of strictness in penalizing predictions, PROBE introduces a rank transformation function $f(r, \alpha)$ that converts the rank $r$ of a correct entity into a score.

• Mechanism: The function is defined as $f(r, \alpha) = 1/r^\alpha$, where $\alpha$ is a tunable parameter controlling predictive sharpness.
• Behavior:
  • High $\alpha$ imposes heavy penalties on lower ranks, emphasizing top-ranked predictions (high sharpness).
  • Low $\alpha$ reduces the penalty for moderately ranked predictions, allowing models with stable performance across a wider rank range to score higher.
• Refinement: To ensure distinguishability and a fixed range $[0, 1]$, the authors apply an affine transformation to rescale scores based on the candidate set size $|E_i|$, ensuring the worst prediction maps to 0 and the best to 1.

2. Rank Aggregator (RA) for Popularity-Bias Robustness

To mitigate popularity bias, PROBE assigns weights to test triples based on their popularity.

• Triple-Level Popularity: Unlike previous works that consider only entity frequency, PROBE measures popularity at the triple level by combining:
  • Entity Popularity ($\delta(e)$): The frequency of the target entity.
  • Entity-Conditioned Relation Popularity ($\delta(r|e)$): The frequency of the specific relation given the entity.
• Weighting Mechanism: The weight $w_t$ for a triple is calculated as the product of weights derived from entity and relation popularity, controlled by a parameter $\beta$.
  • $\beta > 0$: Assigns higher weights to low-popularity triples and lower weights to high-popularity ones, enhancing robustness to bias.
  • $\beta = 0$: Reduces to a standard unweighted average (equivalent to existing metrics).
• Final Score: The final PROBE score is the weighted average of the transformed scores: $PROBE = \sum w_i \cdot c_i$.

3. Geometric Interpretation

The framework interprets the evaluation as an inner product in an $n$-dimensional space. The rank transformer defines the geometry of the score space (controlled by $\alpha$), while the rank aggregator defines the evaluation direction (controlled by $\beta$). This allows the metric to flexibly align with different application requirements.

Key Contributions

1. New Perspectives: The paper identifies and formalizes two overlooked perspectives in KGC evaluation: predictive sharpness and popularity-bias robustness.
2. Generalized Framework: PROBE is proposed as a unified framework that subsumes existing metrics (e.g., MRR, Hits@K) as special cases under specific parameter configurations ($\alpha=1, \beta=0$).
3. Theoretical Analysis: The authors define six key properties for reliable KGC evaluation:
   • Fixed optimum and fixed pessimum.
   • Anti-monotonicity.
   • Candidate-size awareness.
   • Sharpness awareness.
   • Popularity awareness.
     The paper proves that PROBE satisfies all six properties, whereas existing metrics satisfy only a subset.
4. Open-World Consistency: Theoretical analysis demonstrates that PROBE better preserves the relative performance of models between Closed-World (CWA) and Open-World (OWA) settings compared to existing metrics, providing a more reliable estimate of intrinsic model performance.

Experimental Results

The authors conducted extensive experiments using six KGC models (including RotatE, ComplEx, TuckER, pLogicNet, RNNLogic) across six real-world KGs (FB15k-237, WN18RR, YAGO3-10, Family, UMLS, Kinship).

• Impact of Predictive Sharpness ($\alpha$): Varying $\alpha$ significantly altered the relative rankings of models. Models like RNNLogic, which excel at top-ranked predictions, were favored under high sharpness ($\alpha=1$), while models like HousE, which maintain stable performance across ranks 3–100, were favored under lower sharpness ($\alpha \le 0$).
• Impact of Popularity-Bias Robustness ($\beta$): Increasing $\beta$ shifted the preference toward models robust to rare facts. For instance, TuckER performed well on popular triples but degraded on rare ones, whereas pLogicNet and ComplEx maintained stability, becoming top performers under high $\beta$.
• Comprehensiveness: No single model dominated across all datasets and parameter settings, highlighting that the "best" model depends on the specific evaluation perspective required by the application.
• Reliability under OWA: In experiments simulating incomplete knowledge graphs, PROBE consistently preserved the relative rankings of models compared to their performance on complete graphs (CWA). In contrast, metrics like MRR and p-MRR showed significant rank instability and score divergence when moving from CWA to OWA.

Significance and Claims

The paper claims that existing rank-based metrics are insufficient for a comprehensive evaluation of KGC models because they implicitly assume fixed evaluation perspectives that may not align with real-world application needs. By introducing PROBE, the authors provide a flexible, principled framework that:

• Allows practitioners to tune evaluation strictness and bias robustness according to specific domain requirements (e.g., high sharpness for safety-critical drug discovery vs. robustness for exploratory recommendation).
• Offers a theoretically grounded metric that reliably estimates intrinsic model performance even when the underlying knowledge graph is incomplete.
• Reveals that model superiority is context-dependent, urging the community to move beyond single-metric evaluations toward perspective-aware assessment.