Efok Cqa Eval

efok-cqa-eval

$\text{EFO}_{k}$-CQA: Towards Knowledge Graph Complex Query Answering beyond Set Operation — Yin et al. (2023) (arXiv:2307.13701, 2023)

What this evaluates

Evaluates knowledge graph complex query answering models on existential first-order (EFO) queries with multiple free variables and complex structures (cycles, multi-hop), testing their ability to handle combinatorially hard queries beyond simple set operations.

Datasets

• EFO_k-CQA — total 741; splits: test (-1); repo https://github.com/HKUST-KnowComp/EFOK-CQA

Metrics

• MRR (primary) — range: percent
  • Mean Reciprocal Rank: the average of 1/rank for the first correct answer across all queries.
• HIT@10 — range: percent
  • Percentage of queries where the correct answer entity appears in the top-10 predictions.
• Marginal score — range: percent
  • Average MRR computed independently for each free variable in multi-variable queries. Only computable when every free variable has a marginal hard answer.
• Multiply score — range: percent
  • Product of the per-variable HIT@10 scores for all free variables in a query.
• Joint score — range: percent
  • Exact match accuracy where the predicted answer sets for all free variables simultaneously match the ground truth sets.

Input / output format

Input: A complex existential first-order logic query over a knowledge graph, defined by its graph structure (e.g., SDAG, Multi, Cyclic) and a specified number of constant entities.

Output: A ranked list of candidate entities for each free variable in the query.

Scoring recipe

def evaluate(query, predictions, gold):
    if query.num_free_vars == 1:
        ranks = [1 + predictions[var].index(g) for g in gold[var]]
        mrr = sum(1/r for r in ranks) / len(ranks)
        hit10 = sum(1 for r in ranks if r <= 10) / len(ranks)
        return mrr, hit10
    else:
        marginal = sum(compute_mrr(gold[v], predictions[v]) for v in query.free_vars) / len(query.free_vars)
        multiply = 1.0
        for v in query.free_vars:
            hit = sum(1 for r in [1 + predictions[v].index(g) for g in gold[v]] if r <= 10) / len(gold[v])
            multiply *= hit
        joint = 1.0 if all(set(predictions[v]) == set(gold[v]) for v in query.free_vars) else 0.0
        return marginal, multiply, joint

Common pitfalls

• Marginal metrics cannot be computed for queries where some free variables lack marginal hard answers; models must report Multiply/Joint scores instead.
• Joint scores are significantly lower than marginal/multiply scores, highlighting a gap in handling complex query semantics rather than simple per-variable accuracy.
• Performance trends differ across knowledge graphs (FB15k-237 vs FB15k vs NELL), with larger graphs sometimes yielding better results due to distribution shifts.

Evidence (verbatim from paper)

We note that though in some breakdowns, the marginal score is over 90 percent, almost close to 100 percent, the joint score is pretty slow, which further corroborates our findings that joint metric is significantly harder and more challenging in Section 5.3.

Citation

@misc{yin2023efokcqa,
  title={$\text{EFO}_{k}$-CQA: Towards Knowledge Graph Complex Query Answering beyond Set Operation},
  author={Yin et al. (2023)},
  year={2023},
  note={arXiv:2307.13701}
}

• arXiv: 2307.13701