Reranking Answers of Large Language Models with Knowledge Graphs

AI summary

Overview

Research area: Natural Language Processing / Knowledge Graph Question Answering (KGQA) — specifically, using graph structure mined from Wikidata to rerank candidate answers produced by large language models.

Technical level: Advanced. The paper assumes familiarity with large language models, beam search decoding, knowledge graph triples and shortest-path traversal, sentence-embedding models, and learning-to-rank regressors.

Scope (one sentence): The paper proposes a pipeline that, for every LLM-generated answer candidate to a factoid question, extracts a Wikidata subgraph connecting question entities to that candidate, converts the subgraph into graph, text, and graph-to-text features, and feeds those features to rerankers that try to lift the correct answer to the top position.

What This Paper Is About

Large language models often answer factoid questions incorrectly at top-1, yet the correct answer frequently appears somewhere among the many alternative answers the model generates. The authors ask whether the "space" in a knowledge graph between the entities in a question and a candidate answer — represented as a subgraph of shortest paths — contains enough signal to pick out the correct candidate. Their goal is to build and systematically compare rerankers that use these subgraphs, evaluated on Wikidata-backed question answering with the Mintaka dataset.

Key Contributions

1. A subgraph-based reranking formulation of KGQA. The problem is recast as a ranking problem over an LLM-generated answer pool rather than top-1 answer selection, with a scoring function over a dynamically constructed subgraph of shortest paths between question entities and each candidate answer.

2. A systematic feature catalogue and comparison. The authors enumerate the main feature types derivable from mined subgraphs — graph statistics (nodes/edges, cycles, bridges, average shortest path, density, Katz centrality, PageRank), question–answer text embeddings, and three Graph2Text linearizations (Deterministic, T5, GAP) — and compare rerankers of increasing complexity: cosine-similarity semantic ranking, majority vote/self-consistency, linear regression, logistic regression, CatBoost, and a neural ranker with a regression head.

3. A public web application for graph exploration, including subgraph visualization and automatic graph-to-text generation describing the mined subgraph, so a user can inspect why one candidate answer is preferred over another.

4. Released artefacts: source code on GitHub (s-nlp/kbqa) and a published dataset of subgraphs plus base-model answer candidates for the Mintaka train, validation, and test splits.

The authors also list the differences from their earlier paper: reformulating KGQA as ranking instead of top-1 answering, running in-depth experiments over feature combinations, adding graph-to-natural-text features, and adding visualization and graph-to-text to the demo.

Main Findings

• Top-1 accuracy understates LLM capability. Figure 1 plots the Hit@N metric for 1 ≤ N ≤ 40 on the full Mintaka dataset using Mistral, Mixtral, T5-Large-SSM and T5-XL-SSM with Diverse Beam Search, and motivates the paper by showing that the correct answer is often present in the top 10–40 alternative generations even when the top-1 prediction is wrong.

• MRR above Hits@1 for a tuned model. The fine-tuned T5-XL-SSM model is reported to achieve higher Mean Reciprocal Rank than Hits@1, which the authors interpret as headroom that reranking can exploit.

• Beam diversity is a prerequisite. Classical beam search outputs minor variations of a single sequence, giving too few unique candidates; Diverse Beam Search (with its diversity penalty and dissimilarity term weighted by λ_g) is adopted specifically to generate a sufficiently varied answer pool.

• Question text must accompany the subgraph. The authors state that, per their earlier ablation study, relying purely on subgraphs without the question inside the text representation is ineffective, which is why question–answer concatenations and question-conditioned Graph2Text sequences are included.

• Complexity hypothesis for graph features. The working hypothesis is that subgraphs attached to correct answers are less "complex" than those attached to incorrect candidates, which is why the graph features are chosen to convey subgraph complexity.

• Reranking is claimed to help, but the numbers are not in the provided text. The authors state that their study "consistently improves the Hit@N metric" with various features and models, and that the earlier rudimentary text linearization approach already achieved state-of-the-art Hits@1. However, the supplied content is truncated at the start of Section 4.1, so the actual reranking scores, per-model Hits@1 values, and ablation tables are not reported here. No accuracy figures should be attributed to this summary.

• Graph2Text quality varies visibly by method. Table 2 shows worked examples where the T5 and GAP linearizations of the same subgraph produce different, and in some cases factually different, narratives (for example, one example's GAP output states that two people "are both men" where the T5 output states they "are both females").

Methodology in Plain English

1. Generate many candidate answers. Instead of taking only the model's single best answer, the researchers let four tuned language models (Mistral, Mixtral, T5-Large-SSM, T5-XL-SSM) produce a pool of answers per question using Diverse Beam Search, which deliberately makes the beams differ from one another.

2. Find the entities in the question. Where a dataset does not annotate question entities, an LLM (GPT-OSS-120B) extracts the entity surface forms and the Wikidata Search API is used to map each to a Wikidata ID, taking the top search result.

3. Build a subgraph per candidate. For each candidate answer, the system computes the shortest paths in Wikidata from every question entity to that candidate, collects all the distinct nodes on those paths, and then keeps every edge that exists in Wikidata between those nodes. The result is a small induced subgraph specific to that question–candidate pair.

4. Turn each subgraph into features. Three families are used: numerical graph statistics; a plain string joining question and answer with a semicolon, embedded with the MPNet sentence transformer (all-mpnet-base-v2); and natural-language descriptions of the subgraph produced three ways — a deterministic linearization that unrolls the labelled adjacency matrix row by row, a T5 model adapted on WebNLG 2.0, and the GAP BART-based graph-aware model, also trained on WebNLG 2.0.

5. Rank the candidates. Baseline rankers are cosine similarity over MPNet embeddings and majority vote over the beam outputs. Learn-to-rank models — ordinary least squares linear regression scoring 1/0 for correct/incorrect, L2-regularized logistic regression, CatBoost regression, and a transformer with an added regression head over MPNet embeddings — are trained on the feature sets and used to sort candidates; graph features are excluded from the neural ranker because there is no straightforward way to combine numeric features with it.

6. Evaluate on a filtered Mintaka. Mintaka provides 20,000 question–answer pairs annotated with Wikidata entities and, as the paper describes, eight question types; the listed examples cover Count, Comparative, Superlative, Ordinal, Multi-hop, Intersection, Difference, Yes/No, and Generic. Yes/No and Count questions are excluded from the reranking experiments because their answers ("yes"/"no" and numbers) have no corresponding Wikidata entities, so no meaningful question–answer subgraph exists. The authors note the full pipeline could still handle them via the question-type classifier from their earlier work.

Why This Matters

Impact on research. The paper reframes KGQA evaluation from top-1 accuracy to ranking over a generated candidate pool, and it provides an unusually explicit inventory of what can be extracted from question–answer subgraphs, together with a like-for-like comparison of classical graph features, embedding-based similarity, and neural graph-to-text representations. Publishing the subgraph dataset and candidate pools makes reranking experiments on Mintaka reproducible in a way that raw benchmark scores alone are not.

Real-world applications:

• Enterprise and assistant question answering over internal knowledge bases, where a candidate answer can be checked against a curated structured store before being shown to a user.
• Fact verification and hallucination mitigation, since the mined subgraph supplies an inspectable path of relationships supporting or undermining a claim.
• Explainable search and analytics interfaces, where a visualization of the entity path plus a generated sentence justifies why an answer was surfaced.
• Domain knowledge bases in medicine, finance, or government open data, where structured sources already exist and the bottleneck is picking the right candidate rather than generating text.

Industry relevance. The approach is a post-processing layer: it sits on top of any fine-tuned or prompted LLM and needs no retraining of the generator, so it can be added to existing retrieval and assistant stacks. The cost is in graph traversal and feature extraction, which the authors explicitly flag as resource-intensive.

Future Directions

• Handling non-entity answers. Yes/No and Count questions were excluded; extending subgraph reranking to numeric and boolean answers, possibly via the question-type classifier the authors mention, is an open problem.
• Reducing subgraph extraction cost. The authors note that subgraph extraction requires substantial computational resources and refer to hardware details in an appendix, implying scalability of shortest-path mining over large knowledge graphs is unresolved.
• Better graph-to-text supervision. The Graph2Text models are adapted on WebNLG 2.0, whose statistics the paper reports (2,730 entities, 354 relations, 81,927 triples; 623,902 total text tokens, 8,075 unique; 60% entity coverage), and Table 2 shows outputs that sometimes contradict the graph — improving faithfulness of generated subgraph narratives is a clear next step.
• Portability beyond Wikidata. The pipeline is demonstrated on Wikidata only; whether the same feature sets transfer to other Semantic Web sources such as DBpedia is left untested here.

Target Audience

Researchers and graduate students working on knowledge graph question answering, retrieval-augmented and graph-grounded generation, and learning-to-rank for NLP; engineers building assistants over structured enterprise or open knowledge bases who want a reranking layer on top of an existing LLM; and Semantic Web practitioners interested in how RDF-style graph structure can be operationalized as features for neural pipelines. Readers should already be comfortable with LLM decoding strategies and graph algorithms, since the paper's core argument is about feature and ranker design rather than introductory concepts.

Authors’ abstract

Answering natural language questions over knowledge graph data is challenging due to the vast number of facts, which can be difficult to process and navigate. One potential solution for this issue is to use mined subgraphs related to the query, although this process still requires extracting these subgraphs. This research presents a solution for extracting subgraphs related to entity candidates from a question-and-answer set, which can be obtained by inferring a large language model by calculating the shortest paths between entities. The proposed approaches detail various features that can be extracted from the subgraphs and reranking models to select the most probable answers from a list of candidates. Experiments were conducted on Wikidata to evaluate the effectiveness of the proposed approaches. This involved enumerating all the main feature types that can be extracted from mined subgraphs and a detailed analysis of the proposed features and reranking method combinations. In addition, a public web application that provides a useful web tool for studying the graph space between question and answer entities has been developed to work with subgraphs. This includes visualization of the extracted subgraph and automatic generation of natural language text to describe it.