Knowledge graph reasoning

Overview

Knowledge graph reasoning asks whether a relation r holds between two entities h and t that are both in the graph but not connected by an edge 2303.13948 §5.5. The survey names two task types: single-hop prediction, where one element of a triple is predicted from the other two, and multi-hop reasoning over logical queries 2303.13948 §5.5. It treats reasoning as the last of five technical challenges for knowledge graphs, after embedding, acquisition, completion and fusion 2303.13948 §2.2. A benchmark paper gives a concrete multi-hop case: each question comes with the Wikidata triples that lead to its answer 2011.01060 §2.1. A 2024 survey sorts the same field by query type instead of by method family: one missing fact, a logical combination of conditions, a question in natural language, or a multi-turn conversation 2412.10390 §1 §2.8. The variants below use both framings.

Variants

The survey groups reasoning methods into three families: logic rule-based, distributed-representation-based and neural-network-based 2303.13948 §5.5. It does not describe any single method in enough detail to implement, and it gives no hyperparameters for any of them 2303.13948 §5.5. The survey card Knowledge Graphs: Opportunities and Challenges is the source for the taxonomy. The benchmark card 2WikiMultiHopQA is the source for the rule-based question generator and the evaluation numbers. Four method cards add concrete methods that the survey does not describe in enough detail to implement: GraIL for inductive link prediction, QA-GNN for question answering, CronKGQA for questions about when a fact held, and TG-LLM for reasoning over a timeline written from text. The 2024 survey Neural-Symbolic Reasoning over Knowledge Graphs is the source for the complex-query and natural-language families below. It proposes no method and reports no experiments 2412.10390 §1. SAKE adds a different kind of method: a language model trained with reinforcement learning to call graph lookup tools while it answers.

Logic rule-based

Reasoning from rules over the graph. The survey lists this family without describing a rule language, a rule-mining procedure or a result 2303.13948 §5.5. The benchmark paper shows one concrete use of rules: its inference questions are built from 28 logical rules over Wikidata relations, checked by hand from rules mined with AMIE 2011.01060 §3.2 app. A.3. Only relations with a single value per entity are used, so each question has one answer 2011.01060 app. A.3. The paper uses the rules to generate questions and does not evaluate rule-based reasoning as a method. It also notes that several rules can be false in some cases, and checks each new triple against Wikidata before use 2011.01060 app. A.3.

Distributed-representation-based

Entities and relations are embedded as vectors and a score for each candidate triple is computed from them 2303.13948 §5.1. The survey's scoring functions for this family are the ones listed under knowledge graph embeddings 2303.13948 §5.1. Single-hop prediction in this family is the same operation as completion: rank candidates for the missing element of a triple 2303.13948 §5.3 2303.13948 §5.5.

Neural-network-based

Reasoning with a neural network over the graph structure. The survey lists this family for reasoning 2303.13948 §5.5 but describes its models, R-GCN and ConvKB among them, under knowledge graph embeddings 2303.13948 §5.1.3. Their reported link prediction results on FB15K and WN18RR are in 2303.13948 tab. 3. The R-GCN equation printed in the survey does not show a relation-dependent weight, so check the original paper before implementing eq. 4.

Inductive subgraph scoring (GraIL)

Scores a candidate triple (u, r, v) from the subgraph around u and v. It uses no entity embeddings and no node features, so it can score entities that were not in training 1911.06962 §3.1. The method assumes the local neighbourhood of the candidate contains the evidence needed to decide it 1911.06962 §3.1. Each node is labelled with its distances to u and to v, and a relation-aware GNN with edge attention scores the subgraph 1911.06962 §3.1. The inductive splits were built for this test: the training and test graphs share the relation set but no entities 1911.06962 §4.1 app. F. Author-reported: best inductive AUC-PR in all 12 columns against RuleN, Neural-LP and DRUM tab. 1, and best Hits@10 in 10 of 12 tab. 2. Hits@10 ranks each positive against 50 sampled negatives 1911.06962 §4.1, so the number depends on the sampler. Using the union of the two neighbourhoods instead of their intersection lowers FB15k-237 v3 from 91.68 to 84.25 AUC-PR 1911.06962 tab. 7. Most of the cost is in extracting subgraphs, not in the network 1911.06962 §3.4. In the transductive setting, ensembles with embedding models give small gains on two of three datasets 1911.06962 §4.2 tab. 3 tab. 4 tab. 5; the paper reports no significance tests 1911.06962 §4.2.

Multi-hop reasoning over paths

Answers that need a chain of facts, for example a question that links two hops through an intermediate entity. The survey cites multi-hop relation reasoning as the knowledge-graph technique behind two question-answering systems, MHPGM and EmbedKGQA 2303.13948 tab. 1. In recommenders, path generation from user-item interactions is listed for KPRN 2303.13948 tab. 1. The survey reports that most multi-hop reasoning work runs on graphs of about 63K entities and 592K relations 2303.13948 §5.5, which is small next to the large academic and industrial graphs it lists 2303.13948 §4.2.

Evaluating multi-hop chains (2WikiMultiHopQA)

The benchmark has about 193k English questions in four types: comparison, inference, compositional and bridge-comparison 2011.01060 §2.2 tab. 2. Inference questions follow the logic-rule pattern above; the inference type has 7,478 examples 2011.01060 tab. 2. Each sample has a question, a context of 10 paragraphs, supporting sentences, an answer and evidence triples 2011.01060 §2.1 §3.2.

The benchmark scores the answer, the supporting sentences and the evidence triples, and a joint score that requires all three 2011.01060 §2.1 eq. 1. Its baseline is a HotpotQA-style reading model with one added block that predicts evidence triples 2011.01060 §5.2. On the test split it reaches 43.93 answer F1, 65.26 supporting-fact F1, 14.94 evidence F1 and 5.41 joint F1 2011.01060 tab. 5. On 100 test samples, human annotators reach 75.63 evidence F1 on average, against 16.74 for the model 2011.01060 tab. 7. The same multi-hop model scores lower on this benchmark than on HotpotQA: 26.76 joint F1 against 40.52 2011.01060 tab. 4.

The evidence scores show that a correct answer does not mean the chain of facts was found. On the test split the baseline's evidence F1 is 2.85 for inference questions and 17.65 for compositional ones 2011.01060 tab. 6.

Language model with a knowledge-graph subgraph (QA-GNN)

For multiple-choice questions, a pretrained language model (RoBERTa-large, or SapBERT for medical questions) is combined with a ConceptNet subgraph. The subgraph holds the question's topic entities and their 2-hop neighbours, cut to the top 200 nodes by relevance 2104.06378 §3 §4.2. The language model scores how relevant each node is to the question and answer text 2104.06378 §3.2 eq. 1. The question and answer are added as one extra node, linked to the question and answer entities, and five attention GNN layers pass messages over the graph 2104.06378 §3.1 §3.3. Author-reported: 73.41% on the CommonsenseQA in-house test, against 68.69% for RoBERTa-large alone and 71.11% for MHGRN 2104.06378 tab. 3. On OpenBookQA test with RoBERTa-large it reports 67.80% against 64.80% 2104.06378 tab. 5. On CommonsenseQA questions with negation it reports 58.8% against 54.2% for RoBERTa 2104.06378 tab. 10. The cost is about 20 hours on two RTX 2080 Ti for CommonsenseQA, with a model of about 360M parameters 2104.06378 §4.3 §4.5. The released code computes the relevance scores differently from eq. 1 and uses other settings the paper leaves open, so reproducing the numbers needs the card's Paper vs code section.

Temporal question answering over a knowledge graph (CronKGQA)

Adds the time at which a fact held. A pretrained language model encodes the question, and two projections of that encoding give an entity query and a time query 2106.01515 §5 fig. 1. Every entity is scored from the question's subject and time, and every year from the subject and object, with a temporal embedding model (TComplEx) 2106.01515 §4.2 eq. 4 eq. 5. The entities and times in the question must be given as input; entity linking is assumed to be solved 2106.01515 §3.2. The authors built CronQuestions, about 410k question-answer pairs from templates and paraphrases over a timed Wikidata graph, split 350,000 / 30,000 / 30,000 2106.01515 §3.2 tab. 4. Author-reported: Hits@1 0.647 overall, against 0.288 for the best baseline 2106.01515 tab. 5. Simple questions reach 0.987 and complex ones 0.392 tab. 5. For time answers, TComplEx embeddings give 0.549 Hits@1 and ComplEx embeddings give 0.057 2106.01515 tab. 7. The paper does not say which split Table 5 reports 2106.01515 tab. 5.

Temporal graph reasoning with an LLM (TG-LLM)

The graph here is not a knowledge graph. A fine-tuned Llama 2 13B first writes an ordered timeline of the events in a story, with the start and end of each event as separate entries 2401.06853 §3.1. A second adapter reads that timeline, some computed time gaps and the question, then writes a chain of thought and an answer 2401.06853 §3 fig. 1. The reasoning adapter is trained on chains of thought chosen by a contrastive score, and on graph perturbations: renamed entities, shifted years, dropped irrelevant facts and swapped relation names 2401.06853 §3.2.1 §3.2.2. The training data, TGQA, is synthetic: stories written by GPT-3.5 from subgraphs of YAGO11k 2401.06853 §2. Author-reported: on TGQA, exact match rises from 0.646 for the chain-of-thought baseline to 0.797 for the full model [arxiv:2401.06853 tab. 5], against 0.821 for GPT-4 with chain of thought and 0.772 for GPT-4 with a standard prompt tab. 4. Human raters find fewer temporal-graph errors after training: 0.05 for the full model against 0.10 for in-context learning 2401.06853 tab. 3.

Complex logical queries (tree-form and EFO-1)

Answers a query that combines conditions with conjunction, disjunction, negation and existential variables, not a single fact or a chain of lookups. The 2024 survey splits these queries into two families, tree-form and EFO-1, and notes that neither family contains the other 2412.10390 §4.1. Tree-form queries are built from a projection, complement, intersection and union, and their neural solvers embed each term and implement the operators as differentiable functions 2412.10390 §4.2.1. Boxes make intersection a box intersection, while union needs a rewrite into disjunctive normal form 2412.10390 §4.2.1. EFO-1 queries are solved as a graph, for example by message passing over the query graph 2412.10390 §4.2.2.

Neural-symbolic solvers search for variable assignments that satisfy the query. A link predictor turns each triple into a fuzzy truth value between 0 and 1, and the search runs as beam search on acyclic query graphs, backtracking on acyclic queries, or a method that also covers cyclic graphs 2412.10390 §4.3. Some of these solvers relax the search into embedding space for gradient-based optimisation, and one learns its link predictor from search feedback 2412.10390 §4.3. The survey gives no results for any of them 2412.10390 §1.

Natural-language questions and LLM combinations

Answers a question written in English by retrieving a subgraph around candidate answers, ranking answers by embedding similarity, or ranking candidate query graphs and generating the correct one 2412.10390 §5.1. In multi-turn dialogue, the user's reformulations serve as feedback for reinforcement-learning agents that walk the graph 2412.10390 §5.2. The survey's question-answering side is covered on the knowledge base question answering page.

For language models, the survey lists three ways to combine them with a graph. The graph can supply facts to the model, as in QA-GNN, GreaseLM and retrieval with a knowledge graph 2412.10390 §6.1. The model can walk the graph from topic entities, scoring neighbours and moving on when the current node lacks the answer 2412.10390 §6.2. Or the two can be trained together with a shared objective 2412.10390 §6.3. The survey gives one example for each and does not compare them 2412.10390 §6.

Agentic reinforcement learning with graph tools (SAKE)

The language model is the reasoner, and the graph is reached through two deterministic tools rather than a learned scorer. In a three-turn rollout the model names entities in the question, the first tool returns for each entity a group of the entity and its most similar graph concepts, and the model keeps the groups it needs. The second tool returns the graph triplets that link two kept groups, and the model then reasons by analogy over those triplets and writes an answer 2505.15062 §3.1 §3.2 eq. 6 eq. 7. The tools have no trainable parameters, and tool output is excluded from the training loss 2505.15062 §3.1 alg. 1.

The policy is trained end-to-end with GRPO from an instruction-tuned base model, with no supervised stage 2505.15062 §3.4 §3.5. The reward adds a format term, which checks that the closing tags are present, to an exact-match term on the answer 2505.15062 §3.5 eq. 9 eq. 10 eq. 11. The paper does not state the clipping range or the KL weight 2505.15062 §3.4 eq. 8. Author-reported: a Qwen2.5-7B model reaches a weighted average of 75.4 on UMLS question answering, against 70.1 for GPT-3.5-Turbo with GIVE, and 81.3 on CommonsenseQA 2505.15062 tab. 1. The paper's token counts per question are 639 to 1,156 for SAKE, against 7,010 to 19,461 for ToG and GIVE 2505.15062 tab. 2. The UMLS knowledge graph has 135 nodes and 5,877 triplets, which is small next to the ConceptNet graph used for CommonsenseQA 2505.15062 §4.1. The UMLS test set is 224 questions, so one question moves the weighted average by about 0.45 points 2505.15062 §4.1 tab. 1. The released code differs from the paper in several places, including the group construction and the tool-call trigger; see the card's Paper vs code section before reproducing numbers.

When to use which

The survey does not compare reasoning methods on a common benchmark, and it gives no latency, memory or data-volume figures for reasoning. The table therefore chooses by task. Its entries are what the cited sources state, not results measured here.

Implementation sketch

The survey gives no algorithm for reasoning. The first sketch covers only the single-hop case, which the survey defines as ranking candidates for a missing element 2303.13948 §5.5. Scoring is left as a parameter because the survey does not fix one scoring function for this use 2303.13948 §5.1. The second sketch is the input step of the inductive variant. It builds the labelled subgraph for one candidate; the scoring GNN is in the GraIL card. Multi-hop reasoning is not specified here.

# Rank every entity as the tail of the query (head, relation, ?)
def rank_tails(head, relation, entities, score):
    # score(h, r, t): plausibility of the triple, from a trained model
    scored = [(score(head, relation, t), t) for t in entities]
    # highest plausibility first
    return [t for _, t in sorted(scored, reverse=True)]

# Labelled enclosing subgraph for a candidate (u, r, v)  [arxiv:1911.06962 §3.1]
def enclosing_subgraph(triples, u, v, k):
    # k-hop undirected neighbourhood of each target  [§3.1]
    near_u = within_hops(triples, u, k)
    near_v = within_hops(triples, v, k)
    # keep nodes close to both targets (intersection)  [§3.1]
    nodes = (near_u & near_v) | {u, v}
    # the two targets have fixed labels  [§3.1]
    labels = {u: (0, 1), v: (1, 0)}
    for n in nodes - {u, v}:
        # distance to each target, not passing through the other  [§3.1]
        d_u = dist_avoiding(triples, n, u, avoid=v)
        d_v = dist_avoiding(triples, n, v, avoid=u)
        # drop nodes farther than k from either target  [§3.1]
        if d_u <= k and d_v <= k:
            labels[n] = (d_u, d_v)
    return labels

Contradictions

None known between papers. The cards measure different things on different benchmarks: inductive splits 1911.06962 tab. 1, CommonsenseQA and OpenBookQA 2104.06378 tab. 3, and 2WikiMultiHopQA [arxiv:2011.01060 tab. 5]. Add CronQuestions 2106.01515 tab. 5 and TGQA 2401.06853 tab. 4 to that list. Their numbers are not comparable. The survey's advantage claims for knowledge-graph systems are argued qualitatively and not measured 2303.13948 §3. The benchmark measures the evidence chain of one text baseline at 14.94 evidence F1 2011.01060 tab. 5, which is a measurement of one system, not of knowledge-graph explanations in general. The 2024 survey reports no numbers, so it adds no entries to these comparisons 2412.10390 §1.

SAKE's results are on UMLS question answering 2505.15062 tab. 1 and on a 246-question CommonsenseQA subset over ConceptNet 2505.15062 tab. 3. Its CommonsenseQA score of 81.3 and QA-GNN's 73.41 are from different test sets and backbones, so they are not comparable 2104.06378 tab. 3. SAKE's numbers are also not comparable with the inductive scores above.

Two papers disagree with their own tables. TG-LLM's text says the 13B model is comparable to or better than GPT-4 on all datasets 2401.06853 §4.3. Its Table 4 shows GPT-4 with a standard prompt ahead on TimeQA easy and on both TempReason levels, and GPT-4 with chain of thought ahead on TGQA [arxiv:2401.06853 tab. 4]. CronKGQA's text says every model except EmbedKGQA does best on time-join questions 2106.01515 §6.3, but its Table 6 shows the two Entities-as-Experts variants scoring higher on before/after and first/last questions than on time join 2106.01515 tab. 6.

SAKE's text says it improves every benchmark on both model sizes without exception 2505.15062 §4.1. Its Table 1 shows 80.0 on ProcessBank for SAKE at 7B, against 82.5 for GraphRAG and ToG 2505.15062 tab. 1.

Papers

• Inductive Relation Prediction by Subgraph Reasoning: GraIL, a 2019 inductive link predictor that scores a candidate from its labelled enclosing subgraph; the source for the inductive variant and its numbers.
• QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering: a 2021 method that joins a pretrained LM with a ConceptNet subgraph for multiple-choice QA; the source for the LM-plus-subgraph variant.
• 2WikiMultiHopQA: a 2020 multi-hop QA benchmark with evidence triples from Wikidata; the source for the rule-based question generator and the evaluation numbers on this page.
• Knowledge Graphs: Opportunities and Challenges: a 2023 survey whose §5.5 gives the reasoning taxonomy and task types used on this page.
• Question Answering Over Temporal Knowledge Graphs: a 2021 method and dataset for questions about when facts held; the source for the CronKGQA variant.
• Large Language Models Can Learn Temporal Reasoning: a 2024 two-step LoRA pipeline that writes a timeline from a story and reasons over it; the source for the TG-LLM variant.
• Neural-Symbolic Reasoning over Knowledge Graphs: A Survey from a Query Perspective: a 2024 survey that organises reasoning by query type and has no experiments; the source for the complex-query and natural-language sections.
• SAKE: Structured Agentic Knowledge Extrapolation for Complex LLM Reasoning via Reinforcement Learning: a 2025 method that trains a Qwen2.5 model with GRPO to call two knowledge-graph tools; the source for the agentic variant and its numbers.