💬 NLP

Topology-Aware Reasoning over Incomplete Knowledge Graph with Graph-Based Soft Prompting

This paper proposes GraSP, a novel graph-based soft prompting framework that leverages Graph Neural Networks to encode structural subgraphs for subgraph-level reasoning, thereby mitigating the impact of incomplete knowledge graphs and achieving state-of-the-art performance in multi-hop Knowledge Base Question Answering through a cost-effective two-stage generation paradigm.

Original authors: Shuai Wang, Xixi Wang, Yinan Yu

Published 2026-04-15

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Shuai Wang, Xixi Wang, Yinan Yu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a mystery, like a detective trying to figure out what language people speak in the town where a specific newspaper is sold. You have a giant, digital map of the world (a Knowledge Graph) that connects facts like "Newspaper X is sold in City Y" and "City Y speaks Language Z."

However, this map is incomplete. Some roads are missing. Maybe the map doesn't have a direct line connecting "Newspaper X" to "City Y."

The Problem: The "Follow-the-Roads" Detective

Most current AI detectives (Large Language Models) try to solve this by strictly following the existing roads on the map.

Step 1: Start at "Newspaper X."
Step 2: Look for a road to the next clue.
The Problem: If the road is missing (because the map is incomplete), the detective gets stuck. They can't see the connection, so they give up or guess wrong (hallucinate).

Some other methods try to fix this by reading a written description of the map. But reading a long list of facts ("A is connected to B, B is connected to C...") is like trying to understand a city's layout by reading a phone book. You lose the big picture of how everything fits together.

The Solution: GraSP (The "Intuitive Map Reader")

The authors of this paper propose a new method called GraSP. Instead of just following roads or reading lists, GraSP uses a special tool called a Graph Neural Network (GNN) to look at the shape of the neighborhood around the clue.

Here is how it works, using a creative analogy:

1. The "Subgraph" (Looking at the Neighborhood)

Instead of just looking at the missing road, GraSP looks at the entire neighborhood around the newspaper.

The Analogy: Imagine you are looking for a friend's house, but the street sign is missing. Instead of giving up, you look at the houses nearby. You see a bakery, a school, and a park. Even if you don't see the direct path to your friend's house, you notice that the bakery is owned by a group that operates in the same city as your friend.
The Tech: The GNN scans this local "neighborhood" (subgraph) and finds these hidden, indirect connections. It realizes that even without the direct road, the pattern of the neighborhood suggests the newspaper is likely in that city.

2. The "Soft Prompt" (The Whispered Hint)

Once the GNN understands the neighborhood's shape, it doesn't write a long report. Instead, it creates a "Soft Prompt."

The Analogy: Think of this as a whispered hint or a "feeling" passed directly into the detective's brain. It's not a sentence you can read; it's a mathematical nudge that says, "Hey, pay attention to this specific area of the map; the clues are hiding here."
This allows the AI to "feel" the missing connections without needing the actual road to be there.

3. The Two-Stage Team (The Intern and the Expert)

To save time and money, GraSP uses a two-person team:

The Intern (Lightweight LLM): First, a small, fast AI looks at the "whispered hint" and the map. Its job is just to say, "Okay, I think the answer is in Cyprus. Let's focus there." It filters out the noise.
The Expert (Powerful LLM): Then, a much smarter, more expensive AI takes that specific focus and writes the final answer: "The newspaper is in Cyprus, so the languages are Greek and Turkish."

Why is this better?

It's Robust: If a road is missing on the map, the "neighborhood pattern" still gives enough clues to solve the mystery. It doesn't break when the data is incomplete.
It's Efficient: By using the "Intern" to do the heavy lifting of finding the right clues, the "Expert" doesn't have to read the whole encyclopedia. This saves a lot of computing power.
It's Smarter: It understands the structure of the world, not just the words.

In a Nutshell

GraSP is like a detective who doesn't just follow a map; they understand the vibe of the neighborhood. Even if a street is blocked, they can look at the surrounding buildings, get a "gut feeling" (soft prompt) about where to go, and use a smart team to solve the case quickly and accurately. This makes them much better at solving puzzles when the map is broken or missing pieces.

1. Problem Statement

The paper addresses the challenge of Knowledge Base Question Answering (KBQA), specifically focusing on multi-hop reasoning over incomplete Knowledge Graphs (KGs).

The Limitation of Current Methods: Most existing multi-hop KBQA approaches rely on explicit edge traversal (node-to-node reasoning). They assume that if an answer exists, there is a direct path of connected edges in the KG.
The Core Issue: Real-world KGs are often incomplete (missing edges). When a critical edge is missing, the reasoning chain breaks, causing the model to fail.
The Hallucination Problem: Large Language Models (LLMs) alone are prone to hallucinations in knowledge-intensive tasks. While grounding LLMs in KGs helps, rigid traversal methods are fragile when the graph structure is imperfect.
Existing Alternatives: Some methods convert subgraphs into text descriptions to hedge against missing edges. However, this "graph-to-text" transformation often obscures the underlying structural topology and introduces semantic noise, preventing the model from discerning implicit correlations between disconnected entities.

2. Methodology: GraSP Framework

The authors propose GraSP (Graph-based Soft Prompting), a framework that shifts the reasoning paradigm from node-level path traversal to subgraph-level reasoning. The method consists of three main components:

A. Subgraph Extraction

Instead of blindly expanding neighbors, the system uses a relevance-based retrieval strategy:

Topic Identification: Starts with a topic entity identified from the question.
Iterative Retrieval: Encodes the question and candidate entities using a BERT-based encoder. It calculates cosine similarity to select the top- $k$ most relevant neighbors.
Expansion: This process is repeated iteratively up to $l$ hops (typically 2 hops) to construct a question-relevant subgraph.

B. Graph-Based Soft Prompting (The Core Innovation)

To preserve structural information without converting the graph to text, GraSP uses a Graph Neural Network (GNN):

Encoding: An $l$ -layer Graph Attention Network (GAT) encodes the extracted subgraph. It uses message-passing mechanisms to capture complex dependencies between entities, even if they are not directly connected.
Soft Prompt Generation: The resulting entity embeddings are passed through a lightweight Feed-Forward Network (FFN) to map them into continuous soft prompt vectors.
Integration: These soft prompts are concatenated with the question and instruction context to form the input for the LLM. This allows the LLM to "see" the global structural context of the subgraph rather than just isolated facts.

C. Two-Stage Reasoning and Answering

To balance performance and computational cost, the framework employs a two-stage LLM pipeline:

Stage 1 (Selection): A lightweight LLM (e.g., 0.6B–8B parameters) processes the soft prompts to identify the most relevant entities and relations. It also decides if the current information is sufficient to answer the question. If not, it selects an intermediate entity to continue the reasoning loop.
Stage 2 (Generation): A powerful LLM (e.g., GPT-5.2 or similar) receives the selected entities and relations (as natural language evidence) to generate the final, high-quality answer.
- Note: The lightweight model can be fine-tuned, while the powerful generator model remains frozen (off-the-shelf), reducing training costs.

3. Key Contributions

Subgraph-Level Reasoning Paradigm: The paper introduces a novel approach that encodes structural subgraphs into soft prompts using GNNs. This allows the model to infer missing relations by leveraging implicit topological patterns (e.g., convergent paths) rather than relying solely on explicit edges.
Two-Stage Efficiency: The proposed framework decouples reasoning (entity selection) from answer generation. This significantly reduces computational costs by using a small, potentially fine-tuned model for the heavy lifting of search/reasoning, while reserving large, expensive models only for the final generation.
Robustness to Incompleteness: By utilizing the surrounding structural context via GNNs, the method is less sensitive to missing edges compared to traditional traversal-based methods.

4. Experimental Results

The authors evaluated GraSP on four standard multi-hop KBQA benchmarks: ComplexWebQuestions (CWQ), WebQuestionsSP (WebQSP), WebQuestions, and GrailQA.

State-of-the-Art Performance: GraSP achieved the best results on three out of four datasets (CWQ, WebQSP, WebQuestions), outperforming strong baselines like ToG, KBQA-o1, KG-Agent, and LMP.
Robustness to Missing Edges: In experiments where edges were randomly removed (simulating 5%–25% incompleteness), GraSP showed the slowest performance degradation.
- Example: On CWQ, GraSP's performance dropped by only 10.8 points under high incompleteness, whereas baselines like ToG and KBQA-o1 dropped by 18.2 and 17.2 points, respectively.
Ablation Studies:
- Removing the soft prompt caused a significant performance drop, proving the necessity of structured knowledge.
- Graph-based soft prompts outperformed Text-based soft prompts, confirming that GNNs encode structural information more effectively than simple text linearization.
- 2-hop subgraphs were found to be the optimal balance between structural expressiveness and noise; 1-hop was insufficient, and 3-hop introduced too much noise.
Efficiency: GraSP required fewer LLM calls and less runtime compared to baselines, particularly due to the two-stage design which minimizes calls to large models.

5. Significance and Impact

Bridging the Gap: GraSP effectively bridges the gap between the structural reasoning capabilities of GNNs and the generative/semantic capabilities of LLMs.
Practicality: The framework is highly practical because it does not require fine-tuning the massive, expensive LLMs used for generation. It can integrate seamlessly with any off-the-shelf closed-source LLM.
Handling Real-World Data: By addressing the "incompleteness" problem inherent in real-world knowledge graphs, this method makes KBQA systems more reliable for practical applications where data is rarely perfect.
Future Direction: The paper highlights that while effective, the use of continuous soft prompts reduces interpretability (the "black box" nature of how structural signals influence decisions), pointing to a future research direction for making these structural cues more transparent.