Enrich-on-Graph: Query-Graph Alignment for Complex Reasoning with LLM Enriching

Large Language Models (LLMs) struggle with factual errors and hallucinations in knowledge-intensive tasks like Knowledge Graph Question Answering (KGQA) due to a semantic gap between structured knowledge graphs and unstructured queries. This paper proposes Enrich-on-Graph (EoG), a flexible framework that leverages LLMs' prior knowledge to enrich KGs, effectively bridging this semantic gap to enable precise and robust reasoning while maintaining low computational costs and scalability.

The gist

EoG enables efficient evidence extraction from KGs for precise and robust reasoning by generating a query-aligned graph (G∗) that aligns the semantics between vanilla KGs (G) and queries (q), thereby maximizing the mutual information MI(q, G).

Semantic Gap Analysis and Optimization Objective

The core challenge addressed is the Semantic Gap between Queries and Knowledge Graphs, which stems from focus mismatch—where irrelevant graph focuses clash with query focus—and structure mismatch—where rigid KG structures conflict with linguistic query structures. The paper states that The semantic gap between the vanilla KG and the query stems from focus mismatch and structure mismatch. To solve this, the goal is to find an optimized graph G∗ by maximizing the expected posterior probability:

G∗ = argmax G EP(q,G) [P (Mθ, qG)]

This optimization is mathematically equivalent to maximizing the mutual information (MI) between q and G.

The Enrich-on-Graph Framework

EoG is a flexible three-stage framework designed to align semantics:

1. Parsing: This stage involves parsing the query and graph to enable effective alignment, where LLMs convert natural language queries into new forms (Q) and transform triples into graph queries (QG), constructing quadruples G4 = (qe, es, r, eo).

2. Pruning: This stage addresses focus mismatch by proposing focus-aware multi-channel pruning. It masks the head entity, tail entity, and both (MASK3(t) = (?, r, ?)) to create three recall channels: (e1, r, MASK), (MASK, r, e2), and (MASK, r, MASK). The final score of a triple combines scores across all recall channels.

3. Enriching: This stage resolves structure mismatch by leveraging LLMs with parametric knowledge as a prior to enrich the graph. It uses Similarity, Symmetry, and Transitivity properties to enhance reasoning paths; for instance, symmetry generates a reversed triple (e2, r2, e1), and transitivity combines relationships into a new relationship r3.

Graph Quality Evaluation Metrics

To verify the optimization objective, three graph quality metrics are introduced:

1. Relevance (Sa(q, G)): Measures structural relevance by calculating Sa(q, G) = Σ t∈G sim (vq, vt), where vq and vt are embeddings of the query and triple t.

2. Semantic Richness (Se(G)): Assesses feature properties by using Se(G) = Σ t∈G KGC (t+), where KGC is a semantic scoring model like KG-BERT, evaluating the completeness score of triples in the semantic space.

3. Redundancy (S d(G)): Measures redundancy by calculating S d(G) = Σ Gsub∈G X rj1∈Gsub(r) X rj2∈Gsub(r) sim vrj1, vrj2, where Gsub extracts subgraphs with the same head and tail entities.

Experimental Results and Efficiency

Extensive experiments on WebQSP (simple/two-hop reasoning) and CWQ (complex 2-4 hop reasoning) demonstrate EoG's superiority. EoG achieves state-of-the-art performance by generating high-quality KGs. For instance, on the CWQ dataset, EoG improves Hits@1 by 13.1% and F1 by 15.8% compared to RoG (RoR). Furthermore, the framework is computationally efficient; EoG requires only 4 LLM calls per query, which is significantly fewer than methods like ToG or DoG, leading to a reduction in token usage by up to 83.6% compared to ToG. The combination of Prune and Enrich modules further enhances performance, showing that the combined approach achieves superior results across all metrics.

Conclusion

EoG successfully bridges the semantic gap by leveraging LLMs as priors to generate query-aligned graphs, simplifying reasoning complexity while ensuring scalability and adaptability across different KGQA methods. The framework proves that maximizing MI(q, G) through this mechanism leads to higher graph quality metrics (Relevance and Semantic Richness), validating its effectiveness in achieving state-of-the-art results.

Here are the specific improvements that can be made to AI systems by implementing the Enrich-on-Graph (EoG) framework, along with what those improved systems can achieve:

The implementation of the Enrich-on-Graph (EoG) framework fundamentally shifts LLM reasoning from relying solely on noisy, vanilla Knowledge Graphs (KGs) to leveraging query-aligned, semantically enriched graphs. This leads to the following specific enhancements:

1. [[Bridging Semantic Gaps via Query-Aligned Graph Generation]]

The system will generate an optimal graph structure (G∗) that is explicitly aligned with the logical form of a complex natural language query (q).

The improved AI system can:

• Perform precise, multi-hop reasoning by eliminating structure mismatch (e.g., reducing 4-hop paths to 2-hop or direct relations) and focus mismatch (filtering out irrelevant entities like birthdays or education from the KG).

• Achieve superior accuracy in Knowledge Graph Question Answering (KGQA) tasks, especially those requiring complex reasoning paths, as demonstrated by the significant performance gains over baselines like RoG and ToG.

2. [[Context-Aware Noise Mitigation via Focus-Aware Multi-Channel Pruning]]

The system will employ a Three Masking Channels pruning strategy that considers global query focuses (compound queries) and local focuses (unit queries).

The improved AI system can:

• Significantly reduce the injection of noise and factual errors during the retrieval phase by selectively masking entities, relations, and both in a triple to capture different semantic aspects of the query.

• Improve answer coverage while maintaining high precision by ensuring that retrieved subgraphs are highly relevant to both the global intent and specific local constraints of the question.

3. [[Semantic Augmentation via Structure-Driven Knowledge Enriching]]

The system will use LLMs as an external knowledge source to enrich the pruned graph (Gp) using structural, symmetry, and transitivity properties, and feature attributes (ontologies).

The improved AI system can:

• Resolve entity ambiguity by generating query-related ontologies (e.g., determining if an entity is a Political Figure or a specific President).

• Simplify complex reasoning paths by using structural properties to derive new, semantically enhanced triples that bypass long, convoluted chains of reasoning (e.g., condensing 3-hop paths into direct relations).

• Correct factual errors by using symmetry and transitivity to infer missing relationships that are logically implied by the query context.

4. [[Theoretical Validation and Robustness via Quality Metrics]]

The system will incorporate three theoretically validated graph quality metrics—Relevance, Semantic Richness, and Redundancy—as optimization objectives for the graph generation process.

The improved AI system can:

• Be self-aware of its own output quality, iteratively optimizing the enriched graph to maximize Relevance (query-triple similarity), Semantic Richness (ontological completeness), and minimize Redundancy (avoiding repetitive triples).

• Achieve state-of-the-art performance across diverse KGQA datasets by ensuring the generated knowledge is not only relevant but also semantically dense and concise.

5. [[Enhanced Computational Efficiency]]

The framework is designed to be computationally efficient, requiring only a low number of LLM calls (e.g., 4 per query) and drastically reducing token usage compared to iterative reasoning methods like ToG or DoG.

The improved AI system can:

• Operate efficiently on large-scale KGs (billions of triples) without incurring prohibitive computational costs, making complex reasoning scalable and practical for real-world applications.

In summary, the EoG framework transforms LLM KGQA from a trial-and-error process into a structured, high-fidelity pipeline that guarantees:

1. Higher accuracy in complex factual retrieval (up to 15.8% improvement on CWQ).

2. Reduced reliance on hallucination by grounding reasoning in query-aligned structure.

3. Scalability and low operational cost for enterprise KG applications.