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

TL;DR

This paper introduces MoR, a novel retrieval framework that intelligently combines textual and structural information from Text-rich Graph Knowledge Bases (TG-KBs). By planning query logic, reasoning through mixed textual and structural traversals, and organizing results with a structure-aware reranker, MoR significantly outperforms existing methods, demonstrating the power of harmonizing these two knowledge types.

What Problem Does This Paper Address?

Answering complex questions often requires understanding information that is both written out (textual) and interconnected in a structured way (like in a knowledge graph). Text-rich Graph Knowledge Bases (TG-KBs) store this dual nature of information, making them valuable for applications like question answering and information retrieval. However, existing methods tend to retrieve textual and structural information separately, or they might over-rely on one type, missing out on how they can mutually reinforce each other. Some methods even discard structural information after initial aggregation, which is a loss of valuable reasoning signals. This paper aims to bridge this gap by proposing a unified approach that leverages both textual and structural knowledge effectively.

Methods

The proposed method, MoR (Mixture Of Structural-and-Textual Retrieval), operates in three stages:

  1. Planning: MoR first generates a "textual planning graph." This graph outlines the logical steps and entity types needed to answer a query, essentially creating a roadmap for retrieval. This is done by an LLM that predicts tokens sequentially, avoiding repeated LLM calls.
  2. Reasoning: Using the planning graph, MoR performs a "mixed traversal." This involves simultaneously fetching related entities based on the graph's structure (structural traversal) and matching textual descriptions (textual matching). These two retrieval types inform each other iteratively, creating a synergistic effect.
  3. Organizing: Finally, a "structure-aware reranker" organizes the candidates obtained from the reasoning stage. It uses features derived from the entire traversal trajectory (textual fingerprint, structural fingerprint, and traversal identifier) to rank the candidates, prioritizing those whose paths best align with the query's logic.

Datasets

The authors evaluate MoR on three Text-rich Graph Knowledge Bases (TG-KBs) from the STaRK benchmark:

  • Amazon: E-commerce products, with nodes representing products, categories, colors, and brands.
  • MAG: Academic papers, with nodes for papers, authors, institutions, and fields of study.
  • Prime: Biomedical domain, focusing on entities like diseases, genes/proteins, and drugs.

Key Insights and Ideas

  • Synergy is Key: The most significant insight is that simply retrieving textual or structural information in isolation is suboptimal. Their mutual reinforcement, as achieved by MoR, leads to superior performance.
  • Planning as a Foundation: Generating a logical plan (the textual planning graph) before retrieval is crucial. It guides the subsequent reasoning process and ensures that retrieval aligns with the query's underlying intent.
  • Trajectory Matters for Reranking: The entire path taken during retrieval (the trajectory) provides valuable signals for reranking. This is more effective than just considering the final candidate or a single step.
  • Dataset-Specific Adaptability: MoR's performance and the importance of its components (textual vs. structural retrieval) vary across datasets, highlighting its adaptive nature. For instance, MAG benefits more from structural signals than Amazon.

Key Results

  • MoR consistently outperforms hybrid, textual, and structural retrieval baselines across all three datasets (Amazon, MAG, Prime).
  • On average, MoR achieves the best performance, ranking first on MAG and second on Amazon/Prime.
  • The planning module generates accurate planning graphs for a high percentage of queries (e.g., 88.85% on MAG, 70.03% on Amazon).
  • Ablation studies show that removing any of MoR's three core modules (Planning, Reasoning, Organizing) leads to a significant performance drop, underscoring the importance of each component.
  • The structure-aware reranker, particularly when considering the full trajectory, significantly improves performance, especially on datasets like MAG where structural signals are more critical.

Limitations and Future Work

  • Domain-Specific Knowledge: MoR, like other baselines, struggles with highly specialized domains (e.g., biomedical) due to a lack of deep domain knowledge. Future work could integrate such knowledge.
  • Reranking at Every Layer: The current reranking happens at the final layer. Applying it at intermediate layers could further refine the retrieval process.
  • Multi-Trajectory Integration: The reranker currently uses the most informative trajectory. Future work could explore integrating information from all traversed paths for more comprehensive reranking.
  • Query Patterns: MoR's performance can decline on queries with repeated entity types (e.g., "Product → Product"), suggesting areas for improvement in handling ambiguity.

Summary updated

Abstract

Text-rich Graph Knowledge Bases (TG-KBs) have become increasingly crucial for answering queries by providing textual and structural knowledge. However, current retrieval methods often retrieve these two types of knowledge in isolation without considering their mutual reinforcement and some hybrid methods even bypass structural retrieval entirely after neighboring aggregation. To fill in this gap, we propose a Mixture of Structural-and-Textual Retrieval (MoR) to retrieve these two types of knowledge via a Planning-Reasoning-Organizing framework. In the Planning stage, MoR generates textual planning graphs delineating the logic for answering queries. Following planning graphs, in the Reasoning stage, MoR interweaves structural traversal and textual matching to obtain candidates from TG-KBs. In the Organizing stage, MoR further reranks fetched candidates based on their structural trajectory. Extensive experiments demonstrate the superiority of MoR in harmonizing structural and textual retrieval with insights, including uneven retrieving performance across different query logics and the benefits of integrating structural trajectories for candidate reranking. Our code is available at https://github.com/Yoega/MoR.
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