Beyond Explicit Edges: Robust Reasoning over Noisy and Sparse Knowledge Graphs

GraphRAG is increasingly adopted for converting unstructured corpora into graph structures to enable multi-hop reasoning. However, standard graph algorithms rely heavily on static connectivity and explicit edges, often failing in real-world scenarios where Knowledge Graphs (KGs) are noisy, sparse, or incomplete. To address this limitation, we introduce INSES (Intelligent Navigation and Similarity Enhanced Search), a dynamic framework designed to reason beyond explicit edges. INSES couples LLM-guided navigation, which prunes noise and steers exploration, with embedding-based similarity expansion to recover hidden links and bridge semantic gaps. Recognizing the computational cost of graph reasoning, we complement INSES with a lightweight router that delegates simple queries to Naïve RAG and escalates complex cases to INSES, balancing efficiency with reasoning depth. Experimental results show that INSES performs favorably compared to established RAG and GraphRAG baselines on multiple benchmarks. In particular, on the MINE benchmark, it exhibits notable robustness and adaptability across KGs constructed by varying methods. Our code and data are publicly available at https://github.com/hanggao-gh/INSES.

Large language models are often asked to answer questions that require connecting multiple pieces of information. A common way to help them is to organize documents into a knowledge graph, where facts are represented as connected entities. However, real-world knowledge graphs are often messy: important links may be missing, similar entities may be split apart, and some extracted connections may be noisy. As a result, a system that only follows existing graph edges can easily get stuck or follow the wrong path. We introduce INSES, a framework that helps models reason beyond the explicit edges in a knowledge graph. Instead of treating the graph as fixed, INSES dynamically searches for useful hidden connections by combining two ideas: a language model guides the search toward relevant facts, while embedding similarity helps find related entities that are not directly connected. We also add a lightweight router that sends simple questions to standard text retrieval and reserves graph-based reasoning for harder multi-step questions. This work matters because it makes retrieval-augmented AI systems more reliable when their external knowledge sources are incomplete or noisy. By repairing reasoning paths during inference rather than permanently changing the graph, INSES can improve multi-hop question answering while keeping the system efficient and adaptable.