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

Hang Gao; Dimitris N. Metaxas

cs.CLMar 14, 2026

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

Authors: Hang Gao, Dimitris N. Metaxas

Organizations: Department of Computer Science, Rutgers University, Piscataway, New Jersey, USA.

Abstract

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 .

Figures & tables

Method	Entity Nodes Generated by Different Methods
KGGEN	[”adult”, ”adulthood”, ”antennae”, ”appearance”, ”appreciation”, ”balance”, ”beauty”, ”biodiversity”, ”birds”, ”body”, ”butterfly”, ”camouflage”, ”caterpillar”, …, ”food”, ”food source” , ”host plants”, ”life cycle”, ”lifespan” , ”plant populations”, ”plants” , …]
GraphRAG	[”egg stage”, ”birds”, ”adult butterflies” , ”nectar”, ”insects”, ”pupa”, ”host plants”, ”larva stage”, ”chrysalis”, ”metamorphosis”, ”female butterflies” , ”pollination”, ”reptiles”, ”butterflies” , ”caterpillar”, ”butterfly” , …]
OpenIE	[”They”, ”egg to larva”, ”specific host plants”, ”journey filled”, ”third stage”, ”butterfly ’s life cycle”, ”lifespan ranging from few days to weeks”, ”Life Cycle” , ”changes”, ”laid”, ”twigs”, ”Next time”, ”to prepare for stage of its life cycle”, …, ”short lifespan ranging”, ”lifespan ranging from days”, ”prepare for stage of its life cycle”, ”lifespan ranging from days to weeks”, ”life cycle” , …]

Table 1: Entity Nodes Generated by Different Methods

Figure 1: An example of INSES workflow. Solid edges denote explicit relations; dashed edges denote dynamically added similarity edges. Nodes/edges with green background aid answering query. LLM maps query entities (“Greenwood Laboratory School” and “The Poor Boob”) to initial nodes, picks relevant triples while pruning noise, and uses similarity expansion to recover latent links (e.g., “Springfield” → “Springfield Illinois”). Navigation and pruning discard spurious edges, while expansion reveals critical connections, together enabling more reliable multi-hop reasoning.

	Baseline methods	Musique		2Wiki		HotpotQA
	Baseline methods	EM	LLM Judge	EM	LLM Judge	EM	LLM Judge
LLM only	GLM-4 (Direct)	0.15	0.18	0.32	0.36	0.41	0.49
LLM only	GLM-4 (Few-shot CoT)	0.24	0.27	0.38	0.46	0.51	0.57
Text-based	Naïve RAG (Top-5)	0.31	0.29	0.39	0.43	0.62	0.71
	Naïve RAG (Top-10)	0.33	0.37	0.41	0.44	0.67	0.77
	HyDE	0.21	0.31	0.45	0.46	0.57	0.63

Table 2: Performance comparison among baselines and INSES on three benchmark datasets in terms of EM and LLM Judge.

INSES	Musique		2Wiki		HotpotQA
	EM	LLM Judge	EM	LLM Judge	EM	LLM Judge
GLM-4 (Direct)	0.15	0.18	0.32	0.36	0.41	0.49
GPT-4o (Direct)	0.28	0.35	0.54	0.57	0.49	0.65
Naïve RAG (Top-5)	0.31	0.29	0.39	0.43	0.62	0.71
w/ LLM Navigator	0.32	0.35	0.57	0.51	0.53	0.62
w/ LLM Navigator + Similarity Enhance	0.44	0.45	0.63	0.61	0.58	0.69

Table 3: Ablation study on three datasets.

Figure 2: Proportion of queries routed to Naïve RAG vs. INSES across three datasets.

Figure 3: Quantitative comparison of knowledge graph topologies generated by GraphRAG, KGGEN, and OpenIE on the MINE dataset (averaged over 100 articles). The significant variance in node/edge counts and graph density underscores the heterogeneity of real-world KGs, necessitating the adaptive navigation and dynamic expansion capabilities of INSES to handle both sparsity and noise.

Figure 4: Kernel density distributions of query accuracy comparision across KGs constructed by three distinct methods. Dashed lines denote the mean accuracy for each distribution.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

LLM Extract Entities Prompt
Your task is to extract several entities from the given query, so they can be used to search a knowledge graph for clues relevant to answering the query.
Return only the entities you extract, separated by commas, with no other text.
Query: {query}

Appendix

Table 4: LLM Extract Entities Prompt

LLM Navigation Prompt
Your task is to provide support for complex queries and multi-hop reasoning in the knowledge graph. Based on the following query, the visited nodes and the selected triplets, as well as the current nodes and their adjacent triplets, select the triplet numbers (separated by commas) from the adjacent triplets of the current nodes that help answer the query.
Selection criteria: Select the triplets that are most relevant to the query and most likely to help answer it.
Then determine:
1. Based on the visited nodes, the selected triplets, and the triplets you just selected, is this information sufficient to answer the query?
2. If so, answer ”sufficient”;
3. If not, answer ”insufficient”;

Appendix

Table 5: LLM Navigation Prompt

LLM Answer Question With Retrieved Triplets Prompt
You are a helpful assistant that provides accurate and concise answers based on the provided knowledge graph information.
Please answer the following query: {query}
The following information is extracted from a knowledge graph, which contains entities, relationships, and relevant text:
{context}
Your response must be in JSON format with two fields:
1. ”reasoning”: Your step-by-step reasoning process based on the knowledge graph information. Explain how the entities and relationships help answer the query.

Appendix

Table 6: LLM Answer Question With Retrieved Triples Prompt

Dimension	Text RAG	Graph-based RAG
Data form & indexing	Chunk raw text and retrieve via dense vectors; preserves original wording and details	Extract entities/relations or community structure to build a graph, then retrieve by graph and aggregate subgraphs/communities
Retrieval characteristics	Strong at in-place factual recall via semantic similarity; sensitive to type words and relation templates; well-suited to short-chain reasoning	Connects evidence across segments via explicit structure; better for long chains/hierarchical reasoning and thematic/context integration
Strengths (tasks)	Single-hop and $\leq$ 2-hop factual QA with rich details; pulling key snippets across documents	Multi-hop ( $\geq$ 3) and long-range reasoning; contextual summarization/thematic synthesis; structured evidence integration
Generation trade-offs	Higher context relevance and lower noise; more focused coverage in creative/synthesis tasks	Broader evidence recall and coverage, but more redundancy; typical trade-off: coverage $\uparrow$ vs. relevance $\downarrow$ in creative tasks
Efficiency & cost	Low build/query cost; shorter prompts	Higher graph construction cost; retrieval/aggregation tends to inflate prompt length, increasing cost (varies by implementation)
Implementation variants	Classic dense retrieval with optional reranking, HyDE, hybrid (sparse+dense) retrieval	KG-style triple retrieval, community-based global/local retrieval, mixed nodes (concepts/passages), etc.

Appendix

Table 7: Text RAG vs. Graph-based RAG: comparison of pipeline, capabilities, and costs

LLM Router Prompt
You are a strict binary classifier of question complexity for QA routing. Return EXACTLY one token: True or False. No punctuation. No explanation.
Definition:
- ”True” ONLY if the question is exceptionally complex and strictly requires $\geq 3$ distinct reasoning hops.
- ”False” if it can be answered with 1-2 hops, involves basic aggregations, or if you are unsure.
- DEFAULT RULE: When in doubt or if the complexity is borderline, strictly output False.
Examples:

Appendix

Table 8: LLM Router Prompt

Iteration	The relevant status of each iteration
Query	Who was the spouse of a leading speaker against slavery and publisher of an antislavery newspaper?
Entities	[’leading speaker against slavery’, ’antislavery newspaper’ , ’spouse’, ’publisher’]
$V_{init}$	[’Opponent of slavery’, ’Anti-slavery newspaper’ , ’Husband and wife’, ’Newspaper publisher’]
iter=0	$V_{current}$ : [’Opponent of slavery’, ’Anti-slavery newspaper’ , ’Husband and wife’, ’Newspaper publisher’]. $T_{new\_selected}$ : [’Thomas spottswood hinde $\rightarrow$ Occupation $\rightarrow$ Opponent of slavery’, ’The north star $\rightarrow$ Is $\rightarrow$ Anti-slavery newspaper’ , ’Enos bronson $\rightarrow$ Was $\rightarrow$ Newspaper publisher’]. $V_{candidate}$ : [’Thomas spottswood hinde’, ’The north star’ , ’Enos bronson’]
iter=1	$V_{current}$ : [’Thomas spottswood hinde’, ’The north star’ , ’Enos bronson’]. $T_{new\_selected}$ : [ ’The north star $\rightarrow$ Published by $\rightarrow$ Frederick douglass’ ]. $V_{candidate}$ : [ ’Frederick douglass’ ]
iter=2	$V_{current}$ : [ ’Frederick douglass’ ]. $T_{new\_selected}$ : [ ’The north star $\rightarrow$ Published by $\rightarrow$ Frederick douglass’ ]. $V_{candidate}$ : [ ]

Appendix

Table 9: Search without similarity expansion

Iteration	The relevant status of each iteration
Query	Who was the spouse of a leading speaker against slavery and publisher of an antislavery newspaper?
Entities	[’leading speaker against slavery’, ’antislavery newspaper’, ’spouse’, ’publisher’]
$V_{init}$	[’Opponent of slavery’, ’Anti-slavery newspaper’, ’Husband and wife’, ’Newspaper publisher’]
iter=0	$V_{current}$ : [’Opponent of slavery’, ’Anti-slavery newspaper’, ’Husband and wife’, ’Newspaper publisher’]. $T_{new\_selected}$ : [’Thomas spottswood hinde $\rightarrow$ Occupation $\rightarrow$ Opponent of slavery’, ’The north star $\rightarrow$ Is $\rightarrow$ Anti-slavery newspaper’, ’Enos bronson $\rightarrow$ Was $\rightarrow$ Newspaper publisher’]. $V_{candidate}$ : [’Thomas spottswood hinde’, ’The north star’, ’Enos bronson’]. $V_{sim}$ : [’Pro-slavery southerner’, ’Liberty party paper’, ’Husbands and wives’, ’Newspaper of record’]
iter=1	$V_{current}$ : [’Thomas spottswood hinde’, ’The north star’, ’Enos bronson’, ’Pro-slavery southerner’, ’Liberty party paper’, ’Husbands and wives’, ’Newspaper of record’]. $T_{new\_selected}$ : [’The north star $\rightarrow$ Published by $\rightarrow$ Frederick douglass’]. $V_{candidate}$ : [’Frederick douglass’]. $V_{sim}$ : [’Newspaper editor’, ’The toronto star’, ’Opponent of slavery’, ’Federalist party’, ’Husband and wife’, ”Country’s newspaper of record”]
iter=2	$V_{current}$ : [ ’Frederick douglass’ , ’Newspaper editor’, ’The toronto star’, ’Federalist party’, ”Country’s newspaper of record”]. $T_{new\_selected}$ : [’The north star $\rightarrow$ Published by $\rightarrow$ Frederick douglass’]. $V_{candidate}$ : [ ]. $V_{sim}$ : [ ’Frederick douglass memorial and historical association’ , ’Weekly newspaper’, ’Federalists’, ’Newspaper of record’]

Appendix

Table 10: Search with similarity expansion

LLM only (Direct) Prompt
You are a helpful assistant that answers questions based on your own knowledge.
Question: {question}
Please provide your response in the following JSON format:
”answer”: ”Your final answer”

Appendix

Table 11: LLM only (Direct) Prompt

LLM only (Few-shot CoT) Prompt
You are a helpful assistant that answers questions based on your own knowledge. Below are several examples of chain of thought. You can refer to these examples to think about the question and give the correct answer.
Your answer must be returned in JSON format with two fields: ”reasoning” and ”answer”. The ”reasoning” field should contain your step-by-step reasoning process, and the ”answer” field should contain the final answer. The ”answer” field should be as concise as possible and should not contain unnecessary explanations.
Examples of Chain of Thought: Q: What language is primarily spoken in the country whose capital is Madrid?
A: First, the country whose capital is Madrid is Spain. Second, the primary language of Spain is Spanish. The answer is {Spanish}.
Q: Who painted The Starry Night and famously cut off part of his ear?
A: First, The Starry Night was painted by Vincent van Gogh. Second, the artist who cut off part of his ear is Vincent van Gogh. The answer is {Vincent van Gogh}.

Appendix

Table 12: LLM only (Few-shot CoT) Prompt

Naïve RAG Prompt
You are a helpful assistant that provides accurate and concise answers based on the provided context.
Please answer the following query: {query}
Context information is below:
{context} Your response must be in JSON format with three fields:
1. ”reasoning”: Your step-by-step reasoning process based on the context.
2. ”answer”: The final answer to the query, as concise as possible without unnecessary explanations.

Appendix

Table 13: Naïve RAG Prompt

LLM as a judge Prompt
You are an expert evaluator. Your task is to determine if the predicted answer is semantically equivalent to the ground truth answer for the given question.
Question: {question}
Ground Truth Answer: {ground_truth}
Predicted Answer: {prediction}
Instructions: - Compare the predicted answer and the ground truth answer in the context of the question.
- They are considered equivalent if they convey the same meaning, even if the wording is different.

Appendix

Table 14: Implementation Details of LLM as a judge in Section 4.5 and 4.6

LLM as a judge Prompt
You are an evaluator that checks if the Correct Answer can be deduced from the information in the Context.” Context:
{context} Correct Answer:
{correct_answer} Task: Determine whether the Context contains the information stated in the Correct Answer. Respond with ”1” if yes, and ”0” if no. Do not provide any explanation, just the number.

Appendix

Table 15: Implementation Details of LLM as a judge in Section 4.8

Explore similar work

Aug 16, 2026

Noesis: Bidirectional Graph-RAG with Adaptive Parallelism and Cross-Knowledge-Base Semantic Discovery

Retrieval-Augmented Generation over knowledge graphs (Graph-RAG) has emerged as a powerful paradigm for grounding large language models in domain-specific corpora. However, existing systems face persistent limitations: (1) static chunking fragments long documents, losing cross-section semantic connections; (2) ingestion pipelines do not scale adaptively; and (3) multi-domain deployments require either a monolithic knowledge base that dilutes retrieval precision or manual user routing. We present Noesis, a decoupled Graph-RAG architecture addressing these limitations through four algorithms: (a) Bidirectional Graph Traversal with a Graph-Feedback Context Resolver simulating human reading with degrading memory; (b) an AIMD Concurrency Controller adapted from TCP congestion control, achieving 23x speedup with zero OOM events; (c) Moesis, domain-aware selective quantization for MoE models achieving 6.3x speedup on 12 GB consumer GPUs; and (d) Mesh, cross-KB semantic routing with runtime structural discovery enabling small on-premises models to perform multi-hop cross-domain reasoning. On HotpotQA (1,000 questions), Noesis achieves 59.5 EM / 74.7 F1, surpassing GraphRAG by +27.8 EM while using a 35B on-premises model for graph construction rather than GPT-4o. Source text verification on a 193-page document confirms 90% precision on long-range causal edges inaccessible to chunk-independent extraction.

Nicola Cogotti

Alpha Cogs

Graph Retrieval-Augmented Generation Graph-Based Retrieval LLM Inference Acceleration

Ask PDF

Sep 11, 2026

Cognition on Graph: Navigating Massive Knowledge Space via Cognitive Cycles and Bidirectional Graph-Text Synergy

Retrieval-Augmented Generation (RAG) has empowered Large Language Models (LLMs) to tackle knowledge-intensive tasks. However, navigating global, heterogeneous knowledge bases (large-scale knowledge graphs and text corpora) for complex reasoning remains a challenge. Existing methods typically employ reactive, graph-driven exploration strategies, which blindly follow graph topology without adapting to the question context or evolving exploration progress, and lack deep bidirectional synergy between graph and text. To address these limitations, we propose CoG (Cognition on Graph), a cognitive-inspired, training-free framework for adaptive knowledge exploration. Drawing inspiration from human problem-solving, CoG performs a continuous plan-explore-reflect cycle, where it proactively formulates investigation plans, performs dual-source retrieval, and dynamically reflects on progress to adjust strategies. Crucially, it establishes deep bidirectional synergy between structured graph and unstructured text, where entities extracted from text dynamically guide graph exploration to bridge knowledge gaps. Extensive experiments on seven multi-hop QA benchmarks demonstrate that CoG significantly outperforms state-of-the-art methods while achieving superior exploration efficiency. Our code and datasets are available at https://github.com/zhougengxian/CoG.

Gengxian Zhou, Jian Xu, Zichen Tang +3

Beijing University of Posts and Telecommunications · Zhongguancun Academy, Beijing · MAIS, Institute of Automation, Chinese Academy of Sciences +1

Multi-Hop QA Retrieval-Augmented Generation Graph Retrieval-Augmented Generation Agentic RAG Knowledge Graph Question Answering

Ask PDF

Feb 24, 2026

HELP: HyperNode Expansion and Logical Path-Guided Evidence Localization for Accurate and Efficient GraphRAG

Large Language Models (LLMs) often struggle with inherent knowledge boundaries and hallucinations, limiting their reliability in knowledge-intensive tasks. While Retrieval-Augmented Generation (RAG) mitigates these issues, it frequently overlooks structural interdependencies essential for multi-hop reasoning. Graph-based RAG approaches attempt to bridge this gap, yet they typically face trade-offs between accuracy and efficiency due to challenges such as costly graph traversals and semantic noise in LLM-generated summaries. In this paper, we propose HyperNode Expansion and Logical Path-Guided Evidence Localization strategies for GraphRAG (HELP), a novel framework designed to balance accuracy with practical efficiency through two core strategies: 1) HyperNode Expansion, which iteratively chains knowledge triplets into coherent reasoning paths abstracted as HyperNodes to capture complex structural dependencies and ensure retrieval accuracy; and 2) Logical Path-Guided Evidence Localization, which leverages precomputed graph-text correlations to map these paths directly to the corpus for superior efficiency. HELP avoids expensive random walks and semantic distortion, preserving knowledge integrity while drastically reducing retrieval latency. Extensive experiments demonstrate that HELP achieves competitive performance across multiple simple and multi-hop QA benchmarks and up to a 28.8

\times

speedup over leading Graph-based RAG baselines.

Yuqi Huang, Ning Liao, Kai Yang +4

Shanghai Jiao Tong University, China.

Graph Retrieval-Augmented Generation Graph-Based Retrieval LLM Reasoning with Graphs Multi-Hop QA

Ask PDF