Recall@K

Recall@K is defined as the fraction of all relevant items in a ground truth set that appear in the top-K ranked results returned by a system. The formula is:

Recall@K = (Number of relevant items in top-K results) / (Total number of relevant items in the ground truth)

• A value of 1.0 indicates all relevant items were found within the top K.
• A value of 0.0 indicates none were found.
• It is agnostic to the order of the relevant items within the top K; their mere presence is sufficient.

In knowledge graph quality assessment, Recall@K functions as a coverage metric for retrieval systems. It answers the critical question: "How much of the known, correct information does my system successfully surface?"

• High Recall@K is essential for applications where missing a relevant fact is costly, such as diagnostic support or legal discovery.
• It directly measures the completeness of retrieval, complementing precision metrics that measure purity.
• For a knowledge graph completion task (e.g., link prediction), it evaluates how well the model identifies true missing links among its top-K predictions.

The parameter K determines the scope of evaluation and is application-dependent. Its setting reflects real-world user behavior and system constraints.

• Small K (e.g., 1, 5, 10): Simulates scenarios where users only examine the first few results (e.g., a chatbot's immediate reply, a search engine's first page). Demands high ranking accuracy.
• Large K (e.g., 100, 1000): Assesses the system's ability to act as a comprehensive recall engine for downstream batch processing or analytics. Less sensitive to ranking errors.
• K >= Total Relevant Items: When K equals or exceeds the total number of relevant items, Recall@K converges to 1.0 if the system retrieves all of them, regardless of rank.

Recall@K and Precision@K form the fundamental duality of retrieval evaluation. They measure complementary aspects:

• Recall@K: Measures coverage of the ground truth. "Did I find all the right answers?"
• Precision@K: Measures purity of the results. "Are the answers I found correct?"

Trade-off: Optimizing for one often negatively impacts the other. A system can achieve Recall@5 = 1.0 by returning every item in the database (poor precision). It can achieve Precision@5 = 1.0 by returning only a few, ultra-confident results (poor recall). The F1-Score@K harmonizes these two metrics into a single score.

In Retrieval-Augmented Generation (RAG) architectures built on knowledge graphs, Recall@K is a pivotal metric for the retrieval component.

• It evaluates the graph traversal or semantic search system that fetches context for the Large Language Model (LLM).
• High Recall@K ensures the LLM is grounded with all necessary factual context, reducing the risk of omissions that lead to hallucinations or incomplete answers.
• The metric is used to tune parameters like embedding models, similarity thresholds, and graph hop limits to maximize the retrieval of relevant subgraphs or entity neighborhoods.

While essential, Recall@K has limitations that must be accounted for in rigorous evaluation:

• Dependence on Ground Truth: The metric is only as good as the gold standard dataset. Incomplete or biased ground truth invalidates the score.
• Ignores Ranking Quality: It does not reward a system for ranking the most relevant item first. Mean Reciprocal Rank (MRR) or Normalized Discounted Cumulative Gain (NDCG) are used alongside it to assess ranking.
• Static Snapshot: Traditional Recall@K measures performance at a single point in time. Drift detection requires monitoring Recall@K over time as the knowledge graph and query distributions evolve.
• Computational Cost: For very large graphs, calculating recall against a complete ground truth can be expensive, often requiring sampled evaluation.

Recall@K is the primary metric for assessing the completeness of a knowledge graph's semantic search or SPARQL endpoint. It answers: "Does the system retrieve all known relevant facts for a query?"

• Use Case: A pharmaceutical company queries its research graph for "all known side effects of Drug X." A high Recall@10 ensures the top 10 results contain nearly all documented side effects, critical for regulatory compliance and safety reviews.
• Benchmarking: Teams run a suite of test queries against a gold standard dataset. A low Recall@K indicates poor schema alignment, insufficient indexing, or weak entity linking.

In knowledge graph completion (KGC), models like TransE or ComplEx predict missing links (e.g., (Company, acquires, ?)). Recall@K evaluates these link prediction algorithms.

• Mechanism: For each test triple, the model ranks all possible candidate entities. Recall@K measures if the correct entity appears in the top-K ranked candidates.
• Example: Predicting the headquartersLocation for 10,000 companies. Recall@100 = 0.95 means for 95% of companies, the true city is found within the top 100 model predictions. This is vital for automated graph population pipelines.

In Retrieval-Augmented Generation (RAG), a knowledge graph serves as the deterministic factual source. Recall@K audits the retrieval stage before the LLM generates an answer.

• Critical for Hallucination Prevention: Low recall means relevant grounding facts are missing from the context sent to the LLM, increasing the risk of fabrication.
• Process: For a set of Q&A pairs, the system retrieves subgraphs for each question. Recall@K is calculated by checking if the subgraphs contain the facts needed to deduce the gold-standard answer. High recall is non-negotiable for enterprise explainable AI.

Entity resolution clusters records that refer to the same real-world entity. Recall@K assesses the clustering algorithm's ability to group all matching records together.

• Application: Resolving customer records from 50 source systems. The system proposes candidate clusters. Recall@5 = 0.98 means that for 98% of records, all true duplicate records are found within the top 5 proposed cluster matches.
• Ties to Identity Resolution Accuracy: This directly measures the completeness side of the resolution process, complementing precision-based metrics.

Knowledge graph embeddings (node2vec, TransR) project entities into a vector space. Recall@K evaluates the quality of nearest-neighbor searches in this space.

• Quality Signal: High Recall@K for "find similar products" or "recommend related research papers" indicates the embeddings successfully encode semantic and structural relationships.
• Diagnostic Tool: A drop in Recall@K over time can signal embedding drift, where the vector representations have degraded and no longer reflect the current graph's semantics, triggering model retraining.

Recall@K provides a data-driven method to identify and prioritize gaps in a knowledge graph.

• Workflow: 1. Define a target domain (e.g., "supply chain partners"). 2. Create a benchmark list of known entities/facts. 3. Measure Recall@K for queries related to this domain.
• Strategic Insight: A low Recall@K score for "all subsidiaries of Company Y" directly quantifies the completeness ratio gap. This informs ETL and semantic integration pipeline roadmaps, directing resources to the areas with the highest impact on retrieval utility.

Precision@K is the complementary metric to Recall@K. It measures the proportion of relevant results within the top-K retrieved items. While Recall@K asks "Did we find all the relevant items?", Precision@K asks "Are the items we found correct?"

• Formula: (Number of relevant items in top-K) / K.
• Trade-off: In retrieval systems, there is often an inverse relationship between precision and recall; tuning for higher recall can lower precision, and vice versa.
• Use Case: Critical for user-facing applications where presenting incorrect facts (low precision) damages trust, even if coverage (recall) is high.

Query Answerability is a higher-level, application-focused metric that assesses a knowledge graph's practical utility. It measures the system's capability to provide complete and accurate results for a defined set of representative queries.

• Scope: Goes beyond a single metric like Recall@K to evaluate end-to-end performance for real-world use cases.
• Benchmarking: Often evaluated using a Gold Standard set of questions and their verified answers.
• Components: A high answerability score requires good recall (to find all necessary facts), good precision (for those facts to be correct), and effective query execution.

A Gold Standard (or ground truth dataset) is a meticulously curated reference used to benchmark metrics like Recall@K and Precision@K. It consists of a set of queries and the complete, verified set of relevant entities or facts for each.

• Creation: Typically built by domain experts through manual annotation or derived from authoritative sources.
• Purpose: Provides the definitive "correct answers" against which system retrieval is measured. The calculation of Recall@K is meaningless without a gold standard to define what 'relevant' means.
• Challenge: Creating a comprehensive gold standard is expensive and time-consuming, but essential for reliable evaluation.

The Completeness Ratio is a broader structural metric that assesses what proportion of known or expected facts are present in the knowledge graph. Recall@K can be seen as a retrieval-oriented measure of completeness for a specific query.

• Domain-Level: Measures global coverage (e.g., "Does our biomedical KG contain 90% of known protein-protein interactions?").
• Schema-Level: Measures attribute population (e.g., "What percentage of Person entities have a birth date?").
• Relationship: A high global Completeness Ratio is a prerequisite for achieving high Recall@K across a wide range of queries.

Link Validity is the quality dimension that ensures the relationships (edges/predicates) between entities are semantically correct and factually accurate. It is a prerequisite for the precision of retrieved results.

• Impact on Recall@K: If a system retrieves a fact within the top-K results but the link is invalid (e.g., (Paris, capitalOf, Germany)), it harms Precision@K. However, Recall@K only cares if a valid relevant fact was retrieved.
• Assessment: Often validated via rule-based checks, statistical outliers, or manual sampling.
• Example: A high Recall@K score is misleading if many of the retrieved "relevant" triples suffer from low link validity.

Embedding Quality evaluates the vector representations of knowledge graph elements. High-quality embeddings are crucial for semantic search and link prediction models that power high Recall@K.

• Mechanism: Entities and relations are mapped to vectors such that their geometric relationships (distance, angle) reflect their semantic relationships.
• Direct Impact: Poor embeddings lead to poor retrieval; relevant entities won't be "close" in the vector space, causing them to be ranked outside the top-K, lowering recall.
• Evaluation: Measured by how well the embeddings perform on tasks like link prediction (using metrics like Hits@K, a variant of Recall@K) or entity clustering.