PaperlayerView exact revision on arXiv

Source-linked AI summary

AdaPath: Query-Adaptive Path-Finding via Path-Bank for Multi-Hop Implicit Biomedical KGQA

Jun Hyeong Kim, Dongki Kim, Yinhua Piao, Sung Ju Hwang

arXiv:2608.30556v1cs.AI

TL;DR

Biomedical KGQA challenges path-finding because queries omit intermediate reasoning, allow multiple valid pathways, and operate over dense graphs. AdaPath retrieves query-adaptive meta-paths from Path-Bank to provide cues and prune traversal, while BioStrat-QA stratifies query difficulty by surface exposure. Across three biomedical KGQA benchmarks, AdaPath consistently outperforms baselines, although its reliability is bounded by LLM scoring, matching paths, graph coverage, and synthetic benchmark construction.

  • Problem

    Biomedical KGQA lacks explicit intermediate cues, permits multiple valid reasoning pathways, and requires navigating densely connected graphs.

  • Method

    AdaPath retrieves query-adaptive meta-paths from a Path-Bank reflecting query semantics and biomedical KG structure, then uses them to prune candidate expansion.

  • Results

    AdaPath consistently outperforms baselines across BioStrat-QA, STaRK-Prime, and MedDDx, particularly on multi-hop queries with limited intermediate cues.

  • Takeaways & Limitations

    BioStrat-QA enables systematic measurement of path-finding robustness across explicit, implicit, and bare queries and depths up to three hops.

  • Takeaways & Limitations

    AdaPath depends on LLM per-hop scoring and inferred hop length and answer type, falls back to unguided traversal without matching meta-paths, and is limited by graph coverage and synthetic benchmarks.

Abstract

from arXiv · show

Path-finding over knowledge graphs has become an effective way to ground LLM reasoning on multi-hop questions. However, biomedical QA introduces two distinct challenges that general-domain methods are not designed for: (i) queries do not expose intermediate reasoning and can be answered through multiple valid pathways, and (ii) biomedical knowledge graphs are densely connected, so path-finding methods easily take wrong turns. To address these challenges, we propose AdaPath, a path-finding framework that retrieves query-adaptive meta-paths from Path-Bank, which captures both query semantics and biomedical knowledge graph structure. AdaPath provides the missing cues in biomedical queries while effectively pruning dense knowledge graph neighborhoods during multi-hop reasoning. We further release BioStrat-QA, a biomedical KGQA benchmark that stratifies multi-hop queries by how much intermediate reasoning they expose. Across biomedical KGQA benchmarks, AdaPath consistently outperforms baselines, sustaining meaningful path-finding even when multi-hop queries expose less surface information. The source code is available at https://github.com/Jun-Hyeong-Kim/AdaPath.

1 Introduction

Biomedical KGQA requires multi-hop causal reasoning, but biomedical queries often omit intermediate cues and admit multiple candidate pathways. AdaPath addresses these difficulties with query-adaptive meta-path guidance, while BioStrat-QA evaluates robustness as surface cues decrease.

  • Motivation: Multiple valid biomedical pathways can connect the same entities, making the most relevant intermediate path difficult to identify.The paper illustrates this challenge with multiple mechanism chains between Metformin and type-2 diabetes.
  • Motivation: Biomedical questions require traversing multi-hop causal chains rather than retrieving independent facts.The Metformin example requires tracing drug, protein-level, and downstream-effect relations.
  • Motivation: Biomedical queries often state the goal without exposing the intermediate relations needed for path-finding.This leaves guidance cues hidden compared with general-domain queries that directly express traversal relations.
  • Approach: AdaPath retrieves query-adaptive meta-paths from Path-Bank to supply missing cues and prune candidate expansion in dense biomedical graphs.The meta-paths encode query semantics and graph structure, guiding traversal toward biologically plausible directions.
  • Benchmark: BioStrat-QA stratifies multi-hop queries into explicit, implicit, and bare levels while extending reasoning depth up to three hops.This design measures path-finding robustness as intermediate surface cues decrease.
  • Results: AdaPath consistently outperforms baselines across BioStrat-QA, STaRK-Prime, and MedDDx, especially on multi-hop queries with limited intermediate cues.Path-level analyses show retrieval of both ground-truth-aligned paths and semantically related alternatives.

2 Related Work

Retrieval-augmented biomedical QA methods supply external evidence, while path-finding methods explicitly traverse knowledge graphs to construct multi-hop reasoning chains. Existing approaches differ in how much they exploit graph structure and how they guide or verify traversal.

  • Retrieval-Augmented QA: Retrieval-augmented generation grounds LLM reasoning by injecting external knowledge into prompts.Fact-retrieval methods commonly provide query-matching triples or short paths as evidence.
  • Retrieval-Augmented QA: Chain-of-Knowledge retrieves evidence chains across heterogeneous sources without exploiting explicit graph structure.Its sources include knowledge graphs, Wikipedia, and tables.
  • Biomedical QA: KGARevion has an LLM generate candidate triples, verify them against the biomedical KG, and revise the chain.This combines generation with graph-based checking for biomedical QA.
  • Path-Finding Methods: Path-finding methods traverse knowledge graphs hop by hop, giving LLMs structured evidence paths rather than local triples.StructGPT expands single-hop neighborhoods, while Think-on-Graph performs LLM-guided beam search.
  • Biomedical Benchmarks: STaRK-Prime benchmarks biomedical retrieval over PrimeKG using mostly shallow-hop queries with reasonably explicit phrasing.This positions it as a biomedical KGQA benchmark with limited coverage of implicit multi-hop reasoning.

3 Method

AdaPath constructs a Path-Bank of query- and structure-aware meta-paths, then retrieves relevant paths to guide pruning during biomedical KG traversal. BioStrat-QA evaluates path-finding across explicit, implicit, and bare multi-hop queries with decreasing surface exposure of intermediate reasoning.

  • Path-Bank Construction: AdaPath constructs a Path-Bank by mining typed meta-paths from training queries that encode reusable cues and biomedical KG structure.The construction uses query-conditioned edge weighting, bidirectional Personalized PageRank, and hop-stratified path registration.
  • Path-Bank Construction: Query-conditioned edge weighting combines endpoint and relation similarities to align mined paths with each training query.The similarity is based on normalized BM25 scores over biomedical KG node and relation descriptions, with β trading off relation and endpoint terms.
  • Path-Bank Construction: Bidirectional Personalized PageRank identifies a corridor subgraph structurally central to both topic and answer entities, from which multi-hop paths are extracted and binned by hop length.The top-K corridor nodes support extraction of top-n cost-minimizing paths using Yen’s k-shortest-paths algorithm.
  • Query-Adaptive Meta-Path Guided Path-Finding: At inference, AdaPath retrieves query-adaptive meta-paths from similar training queries and uses matched relation-type transitions to guide BFS from the test query’s topic entity.Filtering also uses inferred answer type, hop length, and walk realizability before traversal.
  • Query-Adaptive Meta-Path Guided Path-Finding: Guided BFS keeps neighbors matching retrieved relation and node-type transitions, then narrows candidates with sentence-BERT similarity and depth-specific LLM scoring.Final assembled paths are passed to the LLM with the test query to ground the answer.
  • BIOSTRAT-QA: BioStrat-QA stratifies shared-path queries as Explicit, Implicit, or Bare according to how much intermediate reasoning appears on the surface.The benchmark extends PrimeKG-based templates across single-hop, two-hop, and three-hop settings to evaluate path-finding as cues decrease.

4 Experiments

Experiments evaluate AdaPath across biomedical KGQA datasets, query information levels, hop depths, path quality, traversal depth, and Path-Bank ablations. AdaPath consistently outperforms baselines, especially when multi-hop queries expose limited intermediate information.

  • Datasets and setup: AdaPath is evaluated on BIOSTRAT-QA, STaRK-Prime, and MedDDx using Llama and Qwen instruction-tuned backbones, with exact match or accuracy as appropriate.Path-finding baselines share topic links, the biomedical KG, backbone, and a three-hop search limit.
  • Main results: AdaPath consistently outperforms retrieval and path-finding baselines across BIOSTRAT-QA information levels and hop depths.Path-finding baselines degrade sharply on multi-hop queries with low surface information, while AdaPath remains robust on implicit and bare queries.
  • Main results: AdaPath also outperforms baselines on STaRK-Prime and MedDDx, generalizing across synthesized and human-generated queries and MedDDx difficulty levels.The same improvement trend is retained with smaller Llama-3.1-8B and Qwen-2.5-7B backbones.
  • Path analysis: Path-level analysis measures exact triplet recovery with Recall and semantic mechanism alignment with Context Relevance, reflecting that multiple biological pathways can support one answer.Context Relevance is scored by GPT-4o-mini as an LLM judge.
  • Depth analysis: AdaPath reaches the highest hit rate at every depth across query types, whereas PoG and ToG-2 drop sharply after initially reaching reasonable entities.The depth-level result is reported for three-hop BIOSTRAT-QA queries on Llama-3.1-70B, with a similar pattern on two-hop queries.
  • Ablation study: Both removing Path-Bank and removing meta-path guidance lowers performance relative to AdaPath, with the gap widening as hop depth increases.On bare queries, replacing Path-Bank with LLM-generated meta-paths performs worse than unguided traversal, supporting the quality of Path-Bank selection.

5 Conclusion

The paper presents AdaPath and BIOSTRAT-QA to address implicit intermediate reasoning and dense biomedical graph traversal. Analyses attribute AdaPath’s advantage to query-specific path retrieval optimized for each query.

  • 5 Conclusion: AdaPath uses query-adaptive meta-paths from Path-Bank that reflect query semantics and biomedical KG structure, while BIOSTRAT-QA stratifies queries by exposed intermediate reasoning.The benchmark supports systematic evaluation of multi-hop path-finding under differing surface information.
  • 5 Conclusion: Path- and depth-level analyses indicate that AdaPath’s advantage originates in path-finding, where retrieved paths are quantitatively and qualitatively optimized for each query.This conclusion links the framework’s performance to its retrieved path quality.

Limitations

AdaPath’s effectiveness is bounded by backbone quality, available meta-paths, graph coverage, and benchmark construction. The authors also caution that mechanistic paths should not replace expert judgment.

  • Limitations: Weaker backbones can make noisier next-hop decisions that propagate across hops and degrade longer reasoning chains.AdaPath relies on LLM scoring after meta-path filtering, and queries without matching meta-paths fall back to unguided traversal.
  • Limitations: Path-finding is difficult for queries requiring node or relation types absent from the underlying graph, including recently approved drugs or newly characterised mechanisms.The reachable answer space is bounded by what the graph encodes.
  • Limitations: The benchmarks share a common synthetic construction procedure, so validation on independently collected biomedical QA remains future work.This limits the evidence for performance beyond the current benchmark construction setting.
  • Limitations: Mechanistically grounded AdaPath paths may invite over-trust and should not substitute for expert judgment.The caution applies to interpreting the system’s answers in biomedical settings.

A.1 Dataset Statistics

BIOSTRAT-QA contains controlled multi-hop biomedical queries generated from shared evidence paths and grouped by explicit, implicit, and bare surface information. Its templates and prompts progressively withhold intermediate reasoning details.

  • A.1 Dataset Statistics: BIOSTRAT-QA contains 4,568 queries across train, development, and test splits, covering one-, two-, and three-hop reasoning over PrimeKG.Each record has explicit, implicit, and bare formulations over the same topic and answer entities.
  • A.1 Dataset Statistics: The dataset uses 60 hand-crafted metapath templates: 18 one-hop, 30 two-hop, and 12 three-hop patterns.Most are single-topic chains, while some use junction patterns with shared intermediate or answer nodes.
  • A.1 Dataset Statistics: Three separate GPT-5.4 calls generate explicit, implicit, and bare questions from each evidence path without information leakage across formulations.The implicit level receives a name-free pathway summary for two- and three-hop paths.
  • Pathway summaries: Pathway summaries paraphrase intermediate and answer descriptions without naming those nodes, producing a natural biomedical explanation of the topic-to-answer relationship.This summary stage is skipped for one-hop paths, which use a hand-written relation-level description.
  • Explicit queries: Explicit queries expose intermediate node names and relation labels while withholding the answer entity name.They are generated from the full evidence path.
  • Implicit queries: Implicit queries withhold intermediate names and relation labels, instead using relation descriptions or a name-free pathway summary.The generated question must reflect the pathway without naming intermediate or answer entities.
  • Bare queries: Bare queries reveal no path details and require generic linking phrases rather than specific relation verbs or mechanism details.The answer entity name is also withheld.

B Results on Small Backbones

On smaller backbones, AdaPath retains its improvement pattern over baselines while evaluation combines benchmark QA accuracy with path-recovery and traversal metrics.

  • Small-backbone results: AdaPath retains its improvement over baselines on Llama-3.1-8B and Qwen-2.5-7B.Performance levels shift with backbone scale, but the improvement pattern observed with larger backbones remains.
  • Evaluation setup: BIOSTRAT-QA reports EM (%) per information-level and hop-depth cell, with Overall averaging all nine cells.The benchmark covers three information levels and three hop depths in the small-backbone results.
  • Evaluation metrics: Exact Match credits predictions matching any recorded ground-truth answer name after case and whitespace normalization.BIOSTRAT-QA uses multi-answer expansion so semantically equivalent answer entities receive credit.
  • Evaluation metrics: MedDDx accuracy counts a prediction correct when it matches either the ground-truth option letter or its entity name.This metric is used for the multiple-choice MedDDx queries.
  • Path-level evaluation: Path recovery uses per-depth triplet recall, while Context Relevance judges whether retrieved paths form a query-aligned biomedical mechanism.Recall compares retrieved triplets with the ground-truth evidence path; Context Relevance complements exact matching when valid alternatives exist.
  • Depth-level traversal: On 2-hop BIOSTRAT-QA queries, AdaPath sustains answer-depth hit rates across Explicit, Implicit, and Bare formulations, unlike sharply declining baselines.The figure reports the fraction of explored entity sets containing the reference node at each depth, with independent subplot y-axes.

F Meta-Path Retrieval Quality

AdaPath retrieves meta-path schemas that support both reference-path recovery and traversable alternatives, with retrieval remaining useful as query surface cues decrease.

  • Meta-path representation: Path-Bank stores type-level meta-path schemas, so one schema can instantiate many entity-level paths without revealing disjoint test paths.BIOSTRAT-QA shares meta-paths across splits while keeping entity-level paths disjoint.
  • BIOSTRAT-QA retrieval: Reference meta-path recovery declines moderately as surface cues disappear, while retrieved alternatives remain traversable at a nearly constant rate.Together with Context Relevance, these results indicate that AdaPath supplies usable reasoning schemas rather than only one reference path.
  • BIOSTRAT-QA retrieval: Table 11 measures ground-truth meta-path recovery and ranking, alternative traversability after exact matches are excluded, and downstream QA accuracy.R@k and MRR assess recovery and ranking; Trav.† evaluates alternatives that remain walkable to the answer.
  • External datasets: STaRK-Prime and MedDDx lack released reference paths, so their analysis measures traversability over the whole retrieved pool rather than exact-match-excluded alternatives.Their template pool reaches at most two hops, making these measurements not directly comparable to Table 11.
  • Cross-formulation robustness: Under query-formulation mismatch, Recall@5 decreases moderately, QA accuracy remains above the strongest baseline, and at least roughly half of alternatives remain traversable.The result supports retrieval of usable alternatives rather than only the schema that generated the query.

H Robustness of Context Relevance

Context Relevance results remain robust across two LLM judges and repeated trials, with AdaPath ranked best under both evaluation settings.

  • Judge robustness: AdaPath is the best method under both GPT-4o-mini and Claude-Haiku-4.5 judges across both backbones.The same reasoning paths were rescored with three trials per judge.
  • Judge robustness: Run-to-run variation remains below half a point in the Context Relevance verification.Table 14 reports values as mean ± standard deviation over three trials, scaled by 100.

I Ablation Study on Path-Bank & Meta-Path

Ablations, efficiency tests, external-KG evaluation, and control-signal checks support the value of Path-Bank guidance, while identifying data and model-scope boundaries.

  • Ablation results: AdaPath leads both unguided ablations on every BIOSTRAT-QA cell, with the gap widening from one-hop to longer reasoning paths.The difference opens when unguided search must commit to intermediate entities before reaching the answer.
  • External-dataset ablations: AdaPath stays ahead of both ablations on STaRK-Prime splits and every MedDDx difficulty tier under both backbones.MedDDx tiers increase distractor similarity to the gold answer, so the guidance persists when answer options are harder to distinguish.
  • Construction efficiency: Corridor-restricted Yen search finishes in under ten CPU-minutes over 7,473 training queries, versus dozens of CPU-hours on the raw KG.Restricting search to the extracted corridor keeps runtime and memory nearly flat as KG size grows.
  • Online efficiency: AdaPath uses fewer LLM calls and tokens than ToG and PoG while running faster and achieving higher accuracy.StructGPT and ToG-2 are cheaper but explore less and perform below AdaPath in EM.
  • Statistical significance: 255 of 270 paired-bootstrap comparisons are significant, while nonsignificant cases occur in the smallest subsets with wider intervals.The point estimate remains positive in every remaining setting.
  • External-KG generalization: AdaPath is strongest at every information level on Hetionet, with a widening margin over path-finding baselines as cues disappear.This transfers query-adaptive Path-Bank retrieval to a KG independently built from PrimeKG.
  • Control-signal analysis: Control-signal oracle substitution changes performance by only a few points, indicating that inferred hop length and answer type are not bottlenecks.Hop prediction nevertheless decreases from Explicit to Bare queries as intermediate cues become scarcer.

O Case Studies

The case studies evaluate whether retrieved reasoning paths are biologically valid and relevant, then compare path recovery and answer accuracy across query formulations. ADAPATH maintains full-path recovery and correct answers as intermediate mechanism cues are removed, while ToG increasingly drifts or relies on recalled knowledge.

  • Expert Evaluation: Biomedical validity measures whether reasoning steps are biologically valid, while pathway relevance measures whether the traced pathway contributes to answering the question.The two dimensions are rated independently because biologically true statements may still fail to address the question.
  • Expert Evaluation: ADAPATH receives the highest expert ratings for both validity and relevance, whereas ToG scores below CoT on each dimension.The reported comparison indicates that ADAPATH’s retrieved paths were judged biologically sound and pertinent to the questions.
  • Expert Evaluation: Blinded evaluation asked nine biomedical experts to rate 10 anonymized reasoning cases on independent biomedical validity and pathway relevance scales.Each scale ranged from 1 to 5, separating biologically meaningful reasoning from reasoning that contributes to answering the specific question.
  • Path Recovery: ToG’s path-finding degrades as mechanism cues are removed, causing neighboring-path drift or dependence on prior knowledge for explicit and implicit queries.In the 3-hop cases, ToG recovers only one or none of the ground-truth triplets and fails on bare formulations when recalled cues disappear.
  • Path Recovery: Across 2-hop and 3-hop cases, ADAPATH recovers the ground-truth path under explicit, implicit, and bare query formulations.The case studies report complete recovery at both depths, including all three hops in the 3-hop examples.
Loading 2608.30556v1…