Document Type

Thesis - Open Access

Award Date

2025

Degree Name

Master of Science (MS)

Department / School

Electrical Engineering and Computer Science

First Advisor

Chulwoo Pack

Abstract

Graph-based Retrieval-Augmented Generation (GraphRAG) enhances large language models (LLMs) by grounding their reasoning in structured knowledge graphs, making them more reliable for multi-hop reasoning and factual QA. A central mechanism in Think-on-Graph systems such as ToG[14] and FastToG[7] is community detection, which groups locally related nodes into compact subgraphs so that LLMs can reason over focused, information-rich neighborhoods instead of traversing the entire graph. However, these methods rely purely on structural connectivity, often scattering semantically related entities across different communities and weakening the evidence provided to the LLM. We propose Semantic Think-on-Graph (SemToG), a semantic-aware extension of FastToG[7] that integrates node and relation embeddings directly into community detection through relation-query similarity, entity relevance, hop-aware propagation, and answer-type intent. By combining structural connectivity with semantic alignment, SemToG constructs query-relevant communities that deliver more coherent evidence for LLM reasoning. We evaluate SemToG on six benchmark datasets : CWQ [15], WebQSP[19], QALD[12],ZSRE[13], TREx [3], and Creak [10]-measuring answer accuracy and reasoning steps. SemToG achieves consistent gains of 2-5% accuracy over FastToG[7] while requiring fewer community-expansion steps, demonstrating improved retrieval precision, semantic consistency, and computational efficiency. These results highlight the significance of incorporating semantic-aware community formation into GraphRAG pipelines and point toward more robust and contextually aligned knowledge-grounded LLM systems.

Publisher

South Dakota State University

Download

Share

COinS
 

Rights Statement

In Copyright