Beyond Explicit Edges: Robust Reasoning over Noisy and Sparse Knowledge Graphs
This addresses a key limitation in GraphRAG systems for real-world applications where knowledge graphs are often incomplete or noisy, though it appears to be an incremental improvement over existing methods.
The paper tackles the problem of reasoning over noisy and sparse knowledge graphs by introducing INSES, a dynamic framework that combines LLM-guided navigation and embedding-based similarity expansion to recover hidden links. It consistently outperforms state-of-the-art baselines, achieving accuracy improvements of 5%, 10%, and 27% on different KG construction methods in the MINE benchmark.
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. INSES consistently outperforms SOTA RAG and GraphRAG baselines across multiple benchmarks. Notably, on the MINE benchmark, it demonstrates superior robustness across KGs constructed by varying methods (KGGEN, GraphRAG, OpenIE), improving accuracy by 5%, 10%, and 27%, respectively.