PaperlayerView exact revision on arXiv

Source-linked AI summary

MindMap: Knowledge Graph Prompting Sparks Graph of Thoughts in Large Language Models

Yilin Wen, Zifeng Wang, Jimeng Sun

arXiv:2308.09729v5cs.AIcs.CLcs.LG

TL;DR

LLMs have difficulty incorporating new knowledge, avoiding hallucinations, and explaining their reasoning. MindMap uses knowledge-graph prompting to combine retrieved and implicit knowledge while eliciting graph-based reasoning, achieving empirical gains over vanilla LLMs and retrieval-augmented methods across three question-answering datasets.

  • Problem

    Pre-trained LLMs have outdated knowledge, are costly or risky to update, and can generate plausible but incorrect outputs in high-stakes settings.

  • Method

    MindMap prompts LLMs to comprehend knowledge-graph inputs, aggregate evidence subgraphs, and combine retrieved external knowledge with implicit knowledge in a reasoning mind map.

  • Results

    Across three question-answering datasets, MindMap achieves empirical gains over vanilla LLMs and retrieval-augmented generation methods and remains robust to mismatched retrieval knowledge.

  • Takeaways & Limitations

    MindMap supports reliable and transparent LLM inference by representing answer rationales and reasoning processes in graphs.

  • Takeaways & Limitations

    Knowledge-graph errors, outdated or partial information, integration complexity, and possible excessive dependence on KGs may influence LLM outputs, especially for intricate medical queries.

Abstract

from arXiv · show

Large language models (LLMs) have achieved remarkable performance in natural language understanding and generation tasks. However, they often suffer from limitations such as difficulty in incorporating new knowledge, generating hallucinations, and explaining their reasoning process. To address these challenges, we propose a novel prompting pipeline, named \method, that leverages knowledge graphs (KGs) to enhance LLMs' inference and transparency. Our method enables LLMs to comprehend KG inputs and infer with a combination of implicit and external knowledge. Moreover, our method elicits the mind map of LLMs, which reveals their reasoning pathways based on the ontology of knowledge. We evaluate our method on diverse question \& answering tasks, especially in medical domains, and show significant improvements over baselines. We also introduce a new hallucination evaluation benchmark and analyze the effects of different components of our method. Our results demonstrate the effectiveness and robustness of our method in merging knowledge from LLMs and KGs for combined inference. To reproduce our results and extend the framework further, we make our codebase available at https://github.com/wyl-willing/MindMap.

1 Introduction

LLMs face challenges with outdated knowledge, hallucinations, and limited transparency, while prior KG prompting often treats graph inputs as plain text. MindMap addresses these issues by eliciting graph-based reasoning that combines retrieved KG facts with implicit LLM knowledge.

  • Motivation: Outdated knowledge makes pretrained LLMs inflexible, while fine-tuning can be costly or risk catastrophic forgetting.The paper identifies both data and training-pipeline costs and the risk associated with continual fine-tuning.
  • Motivation: Hallucinated outputs are plausible but wrong, creating serious concerns for high-stakes applications such as medical diagnosis.
  • Motivation: LLMs lack transparency because their knowledge is implicit in parameters and their deep-neural-network inference process is difficult to interpret.
  • Motivation: Prior KG prompting methods often treat KG triples as plain text, ignoring graphical structure and making responses difficult to validate and vulnerable to hallucinations.
  • Approach: MindMap prompts LLMs to consolidate KG facts and implicit knowledge, discover patterns, and reason over a mind map for evidence-grounded generation.The method is presented as a plug-and-play approach for graph-of-thoughts reasoning and is evaluated across three datasets.

2 Related Work

Related work has explored retrieval augmentation, chain- and tree-based reasoning, and KG integration, but these approaches commonly use documents or plain-text facts and focus on narrower graph tasks. MindMap instead prompts fixed LLMs to reason over graph inputs while combining implicit and explicit knowledge.

  • Retrieval-Augmented Generation: Retrieval-augmented generation dynamically adds evidence, but lengthy documents can exceed context limits and information in the middle may be missed.
  • Reasoning with LLMs: Chain- and tree-of-thought prompting elicit intermediate reasoning steps but focus on implicit LLM knowledge rather than joint reasoning with external graph knowledge.
  • Knowledge Graph Augmented LLM: KG research has integrated graph information through attention, graph encoders, graph neural networks, and interactions between text tokens and KG entities.
  • Knowledge Graph Augmented LLM: Prompting methods for KG tasks can comprehend graph inputs, yet they often target entity linking, graph mining, or KG question answering and translate retrieved facts into plain text.

3 Method

MindMap builds evidence-grounded reasoning by mining and aggregating knowledge-graph subgraphs, then prompting an LLM to combine the resulting mind map with its implicit knowledge. The pipeline produces both an answer and an explicit reasoning pathway.

  • 3 Method: MindMap uses three stages: evidence graph mining, evidence graph aggregation, and LLM reasoning on the resulting mind map.The final stage combines the reasoning graph with the LLM’s implicit knowledge to generate an answer and explain the reasoning process.
  • Evidence graph mining: The pipeline identifies query entities with an LLM, matches them to knowledge-graph entities using BERT similarity, and forms the entity set Vq.The matched entities are used to construct evidence subgraphs in the next step.
  • Evidence graph mining: Evidence subgraphs are built through path-based exploration of up to k hops and neighbor-based one-hop expansion around query-related nodes.New intermediate nodes are added from bridging paths before pruning manages information overhead and preserves diversity.
  • Evidence graph aggregation: MindMap converts entity-chain representations into natural-language descriptions and prompts the LLM to consolidate diverse evidence subgraphs into a unified reasoning graph Gm.The unified graph provides a holistic external augmented input for final generation.
  • LLM reasoning on the mind map: The final prompt combines a system instruction, question, evidence graphs, graph-of-thought instructions, and exemplars to produce an answer, inference process, and mind map.The graph-of-thought instruction guides the LLM to comprehend and enhance the input, construct a mind map, and index its knowledge sources.
  • Synergistic inference: Unlike approaches that merely rephrase retrieved facts, MindMap combines evidence graphs with the LLM’s own knowledge for language understanding, knowledge reasoning, and knowledge enhancement.The paper highlights this combination as particularly valuable when external knowledge is inaccurate.

4 Experiments

MindMap was evaluated on three medical question-answering datasets using semantic, GPT-4-based, accuracy, and hallucination measures. It generally outperformed retrieval and vanilla-LLM baselines by combining external KG evidence with implicit knowledge, including under mismatched or incomplete retrieval.

  • Datasets and setup: MindMap was evaluated on GenMedGPT-5k, CMCQA, and ExplainCPE, covering medical dialogues, long multi-round reasoning, and multiple-choice pharmacist-exam questions.The evaluation compared vanilla GPT-3.5/GPT-4, tree-of-thought, BM25, text-embedding, and KG-retrieval baselines.
  • GenMedGPT-5k: MindMap significantly outperformed other methods on GPT-4 ranking and hallucination quantification for GenMedGPT-5k, with an average GPT-4 ranking of 1.8725 and low hallucination scores.BERTScore differences were small, whereas GPT-4 ranking and hallucination measures better separated the methods.
  • CMCQA: On CMCQA, MindMap ranked favorably against most baselines and outperformed retrieval-based methods in pairwise comparisons, despite limited KG coverage of required facts.Its performance gap was narrower than on GenMedGPT-5k, but combining external and implicit knowledge remained advantageous for lengthy, complex dialogues.
  • ExplainCPE: On ExplainCPE, MindMap achieved superior accuracy, while directly adding mismatched retrieved knowledge sometimes reduced performance below vanilla GPT-3.5.The results attribute these errors to misleading external knowledge and show the importance of integrating, rather than blindly inserting, retrieved facts.
  • Ablation and evidence construction: MindMap improved hallucination quantification over Neighbor-only and Path-only variants, with neighbor-based evidence more effective for factual accuracy and path-based evidence useful for relevant external information.Path-based methods struggled with multi-hop medication and test recommendations.
  • Question-type analysis: Across question types, MindMap excelled on knowledge-intensive drug questions, matched retrieval methods on disease questions, and matched GPT-3.5 on general-knowledge questions.These results support combining external KG evidence with the LLM’s implicit knowledge when KG fact coverage varies.

5 Conclusion

The paper concludes that KG prompting enables LLMs to comprehend graph inputs and combine retrieved external knowledge with implicit knowledge. MindMap further represents reasoning and answers as explanatory graphs, showing gains over vanilla and retrieval-augmented methods while remaining robust to mismatched retrieval knowledge.

  • MindMap enables LLMs to comprehend KG inputs and infer using both implicit knowledge and retrieved external knowledge.
  • MindMap elicits reasoning and answers as graphs that provide rationales for the inference process.
  • Experiments on three question-answering datasets showed empirical gains over vanilla LLMs and retrieval-augmented generation methods.
  • The method was reported to be robust to mismatched retrieval knowledge, supporting the paper’s aim of reliable and transparent LLM inference in production.

A Construction of Datasets

The paper evaluates MindMap on three medical question-answering datasets covering patient consultations, clinical dialogues, and pharmacist-examination questions. Each dataset is sampled into a test set for evaluation.

  • GenMedGPT-5k: GenMedGPT-5k contains generated patient dialogues grounded on a disease database, covering diagnosis, symptoms, treatments, and medical tests.The test set contains 714 sampled dialogues.
  • CMCQA: CMCQA contains Chinese multi-round patient-doctor dialogues spanning 45 clinical departments, converted into one-round question-answer pairs.The test set contains 468 sampled examples.
  • ExplainCPE: ExplainCPE is a five-way Chinese National Licensed Pharmacist Examination dataset requiring reasoning across drug, disease, scenario, mathematical, and general knowledge.The evaluation uses 400 samples related to disease diagnosis and treatment recommendations.

B Implementation of Knowledge Graph

MindMap uses two medical knowledge graphs as external knowledge sources, each constructed for specific evaluation datasets and containing domain entities and relationships.

  • EMCKG: EMCKG is built from a disease database for GenMedGPT-5k inference, covering diseases, symptoms, drug recommendations, and test recommendations.Its relationships include possible_disease, need_medical_test, need_medication, and has_symptom.
  • EMCKG: EMCKG contains 1122 nodes and 5802 triples.
  • CMCKG: CMCKG is built from QASystemOnMedicalKG for KG-augmented inference on CMCQA and ExplainCPE.It includes diseases, symptoms, syndromes, recommendation drugs, recommendation tests, recommendation foods, and forbidden foods.
  • CMCKG: CMCKG contains 62282 nodes, 12 relationships, and 506490 triples.

C Implementation of Baselines

The evaluation compares MindMap with direct LLMs, document-retrieval systems, KG retrieval, and tree-of-thought reasoning, while detailing prompts and evidence-graph construction procedures.

  • Baseline methods: The baselines include GPT-3.5 and GPT-4, BM25 document retrieval with GPT-3.5, text-embedding retrieval with GPT-3.5, KG retrieval with GPT-3.5, and tree-of-thought.
  • Retrieval baselines: BM25 and embedding baselines retrieve document contexts, whereas KG retrieval finds shortest paths between question entities before prompting GPT-3.5.The document baselines convert KG knowledge into natural-language documents; KG retrieval uses the same preliminary entity-recognition process as MindMap.
  • MindMap comparison: MindMap differs from KG retrieval by reasoning over multiple evidence sub-graphs with multithought and backtracking evidence sources.
  • Prompt and graph construction: The evidence-graph pipeline recognizes query entities, aggregates graph nodes and edges into natural-language sentences, and guides LLM reasoning through prompts.The final prompt includes system instructions, the question, evidence graphs, graph-of-thought instructions, and exemplars.
  • Evidence-graph exploration: Path-based exploration connects query entities through intermediary paths, while neighbor-based exploration expands query nodes and semantically related neighbors.Path exploration uses bounded hops and assembles disconnected segments; neighbor exploration adds one-hop triples and may expand relevant neighbors further.

F In-depth Analysis

The in-depth analysis examines MindMap examples across GenMedGPT-5k, CMCQA, and ExplainCPE, focusing on factual robustness, evidence aggregation, visualization, and task coverage.

  • GenMedGPT-5k: Figure 6 compares MindMap and baseline responses with a reference response and GPT-4 factual-correctness preferences on a GenMedGPT-5k example.The example focuses on handling mismatched facts.
  • GenMedGPT-5k: Figure 7 presents responses, a generated mind map, and GPT-4 preferences for factual correctness and disease-fact matching on another GenMedGPT-5k example.The example is used to illustrate evidence-graph aggregation.
  • CMCQA: Figure 8 shows a CMCQA question, summary answer, inference process, and generated mind map to visualize MindMap’s final output.
  • ExplainCPE: Figure 4 evaluates MindMap and baselines across six ExplainCPE questions representing three question types.

G Pairwise Ranking Evaluation

The pairwise ranking evaluation asks raters to compare answers across overall quality and factual correctness, including diagnosis and drug recommendation. For CMCQA, an added instruction forces a preference when references may lack facts.

  • Evaluation axes: Raters compare answer pairs for diversity and integrity, total factual correctness, disease diagnosis, and drug recommendation.Each axis uses reference outputs to determine which response is the better match.
  • Factual correctness: The total factual correctness axis covers disease diagnosis, drug, and test recommendations against the reference output.The instruction asks which response better matches the reference facts.
  • CMCQA adjustment: For CMCQA, raters are instructed to choose “1” or “0” rather than defaulting to a tie when the reference label may contain no facts.The added instruction addresses pairwise ranking cases where the reference is derived from an actual dialogue answer.

H Limitations and Potential Risks

The paper’s integration of knowledge graphs and language models carries risks from biased or incomplete graph information, integration complexity, dependence on graph availability, and difficult-to-interpret mind maps.

  • Knowledge quality: Knowledge graphs may contain outdated, partial, biased, or erroneous information that influences language-model outputs.The passage identifies replication of existing graph biases and errors as a concern, particularly when graphs derive from pre-existing data sources.
  • Integration complexity: Complex KG–LLM integration may produce unexpected errors or logical inconsistencies for intricate or vague medical queries.The concern is especially important in medical settings where precision is paramount.
  • Availability: Dependence on knowledge graphs could hinder performance when graphs are unavailable or lack relevant information.The risk concerns scenarios in which the external knowledge source cannot be accessed or is incomplete.
  • Interpretability: Mind maps may be difficult to interpret when their visual representations are complex or obscure.Reduced clarity could make it difficult for users to understand how conclusions were reached.
Loading 2308.09729v5…