Hybrid Graph Neural Network and Large Language Model Framework for Robust Knowledge Graph Question Answering via Retrieval-Augmented Generation

The paper presents a hybrid KGQA pipeline in which a GNN prunes and ranks a candidate subgraph, a lightweight training-free heuristic (GNN attention + degree centrality) scores the shortest reasoning paths between seed entities and candidates, and the top paths are verbalized as text and handed to a small (7-8B) open-source LLM inside a single-pass RAG loop.

Problem Statement

KGQA requires both fluent natural-language understanding and verifiable multi-hop reasoning over structured graphs, but LLMs alone hallucinate facts on multi-hop chains while GNNs alone cannot produce human-readable answers. The paper targets this gap with a grounded, auditable, and compute-light pipeline that avoids fine-tuning and heavy multi-call LLM prompting, making it practical for academic and resource-constrained settings.

Key Novelty

A training-free 'entity-priority' path-scoring function that fuses GNN attention weights with graph degree centrality to rank candidate reasoning paths in milliseconds
An end-to-end integration of GNN-based subgraph pruning/candidate ranking with shortest-path extraction, verbalization, and a small open-source LLM within a single RAG call per question
Emphasis on auditability: the model surfaces a short list of human-readable graph paths as its 'reasoning trace' rather than an opaque answer
Design explicitly optimized for low-resource deployment (single mid-range GPU, ~1 LLM call/question) rather than raw accuracy maximization

Evaluation Highlights

Hits@1 improves by roughly 4-5 percentage points on the harder question subset of ComplexWebQuestions when adding the entity-priority scoring step
Competitive or superior results versus recent baselines on WebQuestionsSP and ComplexWebQuestions, with the largest gains on multi-entity and three-or-more-hop queries
Efficiency claims: about one LLM call per question and inference feasible on a single mid-range GPU

Signal Assessment

3/10 The GNN-retrieval-plus-LLM-verbalization pipeline closely follows an existing hybrid RAG paradigm already explored in prior GNN+LLM KGQA work; the genuine new contribution is a small, training-free path-scoring heuristic, making this a useful but incremental engineering refinement rather than a fundamentally new approach.

Methodology

Identify seed entities in the input question and use a GNN to prune a small candidate subgraph around them
Rank candidate answer entities using GNN-based scoring over the pruned subgraph
Extract shortest paths between seed entities and top-ranked candidates, then score each path with a lightweight function combining GNN attention and degree centrality
Verbalize the highest-scoring surviving paths into plain-English sentences as retrieved evidence
Feed the verbalized paths into a 7-8B open-source LLM in a single RAG call to generate the final natural-language answer

System Components

GNN Subgraph Pruner & Candidate Ranker

Restricts the search space to a small neighborhood around seed entities and ranks likely answer entities using learned graph representations

Shortest-Path Extractor

Computes shortest paths in the pruned subgraph between seed entities and top-ranked candidate answers

Entity-Priority Path Scorer

Training-free, millisecond-latency function combining GNN attention weights with node degree centrality to rank/filter candidate reasoning paths

Path Verbalizer

Converts the surviving graph paths into plain-English natural-language sentences to serve as retrieved context

Open-Source LLM Reader (7-8B)

Consumes the verbalized paths as RAG context and generates the final answer in a single inference call

Results

Metric/Benchmark	Baseline	This Paper	Delta
Hits@1, hard multi-hop subset (ComplexWebQuestions)	GNN/LLM pipeline without entity-priority scoring	With entity-priority scoring	+4-5 percentage points
Hits@1 (WebQuestionsSP)	Recent baseline systems	Competitive to superior	Qualitative gain
Hits@1, multi-entity / 3+ hop queries (ComplexWebQuestions)	Recent baseline systems	Largest reported gains	Qualitative gain
Inference cost per question	Multiple LLM calls (typical multi-step prompting)	~1 LLM call, single mid-range GPU	Lower latency/compute

Key Takeaways

A GNN-based structured retriever combined with lightweight, training-free path scoring can meaningfully boost multi-hop KGQA accuracy without any additional model training
Small open-source LLMs (7-8B) can achieve competitive KGQA performance when paired with strong graph-grounded retrieval, reducing dependence on large proprietary models
Verbalized shortest-path evidence offers a simple, auditable interpretability mechanism that fits naturally into agentic RAG pipelines
The single-GPU, one-LLM-call design pattern is a practical template for deploying graph-grounded RAG systems in academic or resource-constrained environments

Abstract

Knowledge graphs (KGs) hold facts about the world as connected triples, and they have become a backbone for any system that needs to reason over linked information. The task of Knowledge Graph Question Answering (KGQA) is to map a natural-language question onto the right entity, or set of entities, somewhere inside such a graph. Two communities have been pulling at this problem from opposite ends. Large language models (LLMs) read a question fluently but tend to invent facts and stumble on multi-hop chains they cannot verify. Graph neural networks (GNNs), on the other side, are good at walking through neighbourhoods and weighing relations, but cannot phrase an answer the way a person would. In this work, we describe a practical hybrid that places the two inside a retrieval- augmented generation (RAG) loop. A GNN first prunes a small subgraph around the question's seed entities and ranks candidate answers; we then extract shortest paths between the seeds and the top candidates, score each path with a lightweight function that combines GNN attention with degree centrality, and finally verbalise the surviving paths into plain-English sentences before passing them to a 7-8B open-source LLM. The proposed entity-priority scoring step is training-free and runs in milliseconds, yet it lifts Hits@1 by roughly 4-5 percentage points on the harder questions of ComplexWebQuestions. Experiments on WebQuestionsSP and ComplexWebQuestions show competitive or superior results against recent baselines, with the largest gains on multi-entity and three-or-more hop queries. The pipeline uses about one LLM call per question, runs comfortably on a single mid-range GPU, and exposes its reasoning as a short list of human-readable paths that anyone can audit. We argue that this combination of grounded retrieval, lightweight path scoring, and modest model size makes the approach particularly suited to academic and resourceconstrained settings.