Mixture of Structural-and-Textual Retrieval over Text-rich Graph Knowledge Bases

Yongjia Lei, Haoyu Han, Ryan A. Rossi, Franck Dernoncourt, Nedim Lipka, Mahantesh M. Halappanavar, Jiliang Tang, Yu Wang

Introduction

Text-rich Graph Knowledge Bases (TG-KBs) represent a sophisticated class of data structures where nodes are associated with detailed textual documents and edges define complex structural relationships. Examples include academic citation networks (linking papers, authors, and institutions) and e-commerce platforms (linking products, categories, and brands). Despite the wealth of information available, retrieving relevant entities from TG-KBs remains a significant challenge. Current methodologies often treat textual and structural signals in isolation: textual retrievers (e.g., BM25 or dense embeddings) ignore the graph topology, while structural retrievers (e.g., Graph Neural Networks) struggle to incorporate the nuances of long-form text.

This paper introduces MoR (Mixture of Structural-and-Textual Retrieval), a framework designed to harmonize these two modalities. MoR employs a "Planning-Reasoning-Organizing" pipeline that dynamically interleaves graph traversal with textual matching, ultimately reranking candidates based on their specific traversal trajectories.

The MoR Framework

The MoR architecture is divided into three distinct stages designed to maximize both accuracy and computational efficiency.

1. Planning: Textual Graph Generation

Traditional retrieval methods often rely on rigid heuristics or expensive, step-by-step Large Language Model (LLM) prompting. MoR departs from this by using a fine-tuned LLM to generate a "planning graph" in a single pass. This graph serves as a logical roadmap for the query, outlining the necessary reasoning paths (e.g., Institution → Author → Paper) and specifying textual constraints for each node type.

2. Reasoning: Mixed Traversal

Guided by the planning graph, MoR executes a layer-wise breadth-first search. This stage is characterized by "Mixed Traversal," where the system interleaves two types of operations:

  • Structural Traversal: Fetching neighbors based on predefined entity types and edge relationships.
  • Textual Matching: Retrieving nodes based on their semantic similarity to the query’s textual restrictions.

By merging the outputs of both operations at each step, the framework allows structural logic and textual context to mutually reinforce the search process.

3. Organizing: Structure-aware Reranking

To refine the candidate list into a final Top-K selection, MoR introduces a novel reranker. Unlike standard models that only evaluate the final retrieved node, MoR scores candidates based on their entire traversal trajectory. This trajectory includes:

  • Textual Fingerprints: The sequence of similarity scores accumulated along the path.
  • Structural Fingerprints: Metadata regarding node categories.
  • Traversal Identifiers: Indicators of whether a specific step was driven by text or structure.

Experimental Evaluation

The authors evaluated MoR using the STaRK benchmark, focusing on three diverse TG-KBs:

  • Amazon: An e-commerce graph containing products, brands, and categories.
  • MAG (Microsoft Academic Graph): A scholarly network of papers, authors, and institutions.
  • Prime: A biomedical knowledge graph linking diseases, drugs, and proteins.

Performance and Efficiency

MoR demonstrated state-of-the-art accuracy, achieving an average Mean Reciprocal Rank (MRR) of 58.77. This significantly outperformed pure textual methods like BM25 (36.68), pure structural methods like QAGNN (27.20), and the previous leading hybrid baseline, MFAR* (54.53).

Beyond accuracy, MoR proved highly scalable. By parallelizing reasoning paths and minimizing LLM calls during the traversal phase, the system maintains low latency. For instance, 1-hop queries in the MAG dataset are processed in approximately 0.289 seconds, while complex 3-hop queries take roughly 1.233 seconds.

Key Insights

  • Adaptive Modality Preference: MoR automatically adjusts its reliance on text versus structure based on the dataset. In the MAG dataset, over 95% of correct answers were derived via structural retrieval. In contrast, the Amazon dataset saw a higher contribution from textual matching, reflecting the text-heavy nature of product descriptions and reviews.
  • The Power of Trajectories: Ablation studies confirmed that reranking based on the full traversal path is superior to reranking based solely on the destination node. This is particularly evident in highly structured graphs like MAG, where the "logical path" to an answer is a strong indicator of relevance.
  • Downstream Impact: When the retrieved contexts were used to feed a GPT-4o model for question answering, MoR’s retrieval quality led to a 64.0% win rate over BM25-based retrieval on the MAG dataset.

Limitations and Future Work

While MoR represents a significant advancement, challenges remain in highly specialized domains. In the Prime (biomedicine) dataset, the model's performance was constrained by the complexity of medical terminology, suggesting a need for domain-specific fine-tuning. Additionally, the current implementation only reranks candidates at the final stage. Future iterations may explore "intermediate routing" to prune unproductive paths earlier in the traversal process and methods to aggregate features from multiple trajectories leading to the same candidate.

Conclusion

MoR provides a robust framework for retrieval over Text-rich Graph Knowledge Bases by treating structure and text as complementary signals. Through its unique planning and trajectory-aware reranking, it achieves a new standard for accuracy and efficiency in complex information retrieval tasks.

Summary updated

BibTeX
@inproceedings{lei2025mixture,
  author = {Yongjia Lei and Haoyu Han and Ryan A. Rossi and Franck Dernoncourt and Nedim Lipka and Mahantesh M. Halappanavar and Jiliang Tang and Yu Wang},
  title = {{Mixture of Structural-and-Textual Retrieval over Text-rich Graph Knowledge Bases}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2025},
}
Figure