Fast Think-on-Graph: Wider, Deeper and Faster Reasoning of Large Language Model on Knowledge Graph

Xujian Liang, Zhaoquan Gu

TL;DR

This paper introduces Fast Think-on-Graph (FastToG), a novel approach to enhance Large Language Models (LLMs) with knowledge graphs (KGs) for more accurate and efficient reasoning. FastToG leverages community detection within KGs to enable LLMs to "think" in terms of interconnected groups of nodes, leading to improved performance and explainability.

What Problem Does This Paper Address?

Large Language Models (LLMs) often struggle with factual accuracy and can "hallucinate" information. Retrieval-Augmented Generation (RAG) aims to mitigate this by retrieving relevant external information. Graph Retrieval Augmented Generation (GRAG) further enhances RAG by integrating Knowledge Graphs (KGs) to provide structured information. However, existing GRAG methods face limitations: simple approaches fail to capture complex relationships within KGs, while more sophisticated methods can be computationally expensive, especially with dense graphs. This paper addresses the challenge of making GRAG more efficient and effective by enabling LLMs to reason over KGs in a more structured and scalable way, specifically by focusing on "communities" of nodes rather than individual entities or simple paths.

Methods

The core innovation of FastToG is its "community-by-community" reasoning approach. Instead of processing individual nodes or simple paths, FastToG first uses community detection algorithms to group related nodes within a KG. This allows LLMs to capture deeper correlations and reason over more meaningful clusters of information.

Key methodological components include:

  • Community Detection on Subgraph: FastToG first retrieves a local subgraph around a query's entities and then applies community detection algorithms (like Louvain) to partition this subgraph into communities.
  • Two-Stage Community Pruning: To manage computational cost and improve retrieval efficiency, FastToG employs a two-stage pruning process:
  • Modularity-based Coarse-Pruning: This stage uses a modularity metric to filter out communities with low internal connectivity, preserving structural information.
  • LLMs-based Fine-Pruning: In this stage, the LLM itself is prompted to select the most relevant communities from the pruned set, leveraging its understanding of the query.
  • Community-to-Text Conversion: Since LLMs are trained on text, the graph structures of communities need to be converted into a textual format. FastToG proposes two methods:
  • Triple-to-Text (T2T): Directly converts KG triples into text.
  • Graph-to-Text (G2T): Uses a fine-tuned language model (like T5-base) to generate more human-readable and summarized textual representations of communities, aiming to reduce redundancy and improve clarity.

Datasets

FastToG was evaluated on several real-world datasets commonly used for knowledge graph question answering and reasoning tasks:

  • Multi-hop KBQA: CWQ (Complex WebQuestions), WebQSP (WebQuestionsSP), QALD (Question Answering over Linked Data).
  • Slot Filling: Zero-Shot RE (Zero-Shot Relation Extraction), TREX (Text REasoning EXperiment).
  • Common-Sense Reasoning: Creak.

The paper also mentions using Wikidata (version 20240101) as the source KG, containing 84.6 million entities and 303.6 million relationships. For fine-tuning the Graph2Text module, they used the WebNLG dataset and synthetic data generated by GPT-4.

Key Insights and Ideas

  • "Thinking" in Communities: The central idea that LLMs can reason more effectively by processing information in terms of "communities" of nodes, rather than isolated entities or simple paths, is a significant shift. This allows for capturing broader contextual relationships.
  • Efficiency through Pruning: The two-stage pruning mechanism (modularity-based coarse pruning followed by LLM-based fine-pruning) is crucial for balancing accuracy and computational cost, especially in dense KGs.
  • Graph-to-Text for Better Input: The development of Graph2Text (G2T) as a method to convert KG communities into natural language offers a more nuanced and potentially less redundant input for LLMs compared to simple triple-to-text conversion.
  • Trade-off in Community Size: The study highlights that simply increasing the size of communities doesn't always lead to better accuracy; there's an optimal range where accuracy is maximized, suggesting that very large communities can introduce noise.

Key Results

FastToG demonstrated significant improvements across several metrics:

  • Higher Accuracy: FastToG consistently outperformed previous GRAG methods (including n-w and n-d variants) across various datasets, with the G2T version showing particular strength. For instance, Ours(g2t) surpassed n-d 1-w (ToG) by 4.4% on one dataset and 5.9% on another.
  • Faster Reasoning: By reasoning with communities, FastToG effectively shortened reasoning chains, reducing the number of calls to LLMs and thus improving efficiency. The paper shows that increasing the "MaxSize" of communities (beyond 1) significantly reduces the average depth of reasoning chains.
  • Better Explainability: The case study on the "Central America" query illustrated how reasoning with communities provides a clearer and more intuitive path to the answer compared to node-based reasoning.
  • Pruning Effectiveness: Modularity-based coarse pruning was shown to outperform random pruning, indicating the importance of preserving structural information during the selection of candidate communities.

Limitations and Future Work

  • Hallucination in G2T: The paper acknowledges that while G2T generally improves accuracy, the underlying language models used for G2T can still introduce hallucinations. They observed that the proportion of hallucinations increases with larger community sizes, which can negatively impact reasoning.
  • Community Size Optimization: While FastToG shows benefits from larger community sizes (up to 4), the accuracy starts to decrease beyond that, suggesting that further research is needed to optimize community size selection.
  • Future Directions: The authors suggest several avenues for future work:
  • Incorporating semantics and syntax into community detection.
  • Developing multi-level hierarchical communities for enhanced retrieval.
  • Improving community-to-text conversion techniques.

Summary updated

Abstract

Graph Retrieval Augmented Generation (GRAG) is a novel paradigm that takes the naive RAG system a step further by integrating graph information, such as knowledge graph (KGs), into large-scale language models (LLMs) to mitigate hallucination. However, existing GRAG still encounter limitations: 1) simple paradigms usually fail with the complex problems due to the narrow and shallow correlations capture from KGs 2) methods of strong coupling with KGs tend to be high computation cost and time consuming if the graph is dense. In this paper, we propose the Fast Think-on-Graph (FastToG), an innovative paradigm for enabling LLMs to think ``community by community" within KGs. To do this, FastToG employs community detection for deeper correlation capture and two stages community pruning - coarse and fine pruning for faster retrieval. Furthermore, we also develop two Community-to-Text methods to convert the graph structure of communities into textual form for better understanding by LLMs. Experimental results demonstrate the effectiveness of FastToG, showcasing higher accuracy, faster reasoning, and better explainability compared to the previous works.
BibTeX
@inproceedings{liang2025fast,
  author = {Xujian Liang and Zhaoquan Gu},
  title = {{Fast Think-on-Graph: Wider, Deeper and Faster Reasoning of Large Language Model on Knowledge Graph}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i23.34635},
}
Figure