# K-Paths: Reasoning over Graph Paths for Drug Repurposing and Drug Interaction Prediction
**Authors:** Tassallah Abdullahi, Ioanna Gemou, Nihal V. Nayak, Ghulam Murtaza, Stephen H. Bach, Carsten Eickhoff, Ritambhara Singh
**arXiv:** [2502.13344](https://arxiv.org/abs/2502.13344)
**Date:** 2025-02-18
**Summary page:** https://www.summarizepaper.com/en/paper/2502.13344v3/
## Key points
- Biomedical knowledge graphs (KGs) are crucial for encoding rich and structured information in drug discovery.
- Extracting meaningful insights from large-scale KGs is challenging due to their complex structure.
- K-Paths is a novel model-agnostic retrieval framework designed to extract structured, diverse, and biologically meaningful multi-hop paths from dense biomedical KGs.
- K-Paths enables the prediction of unobserved interactions between drugs and diseases, supporting inductive reasoning by including unseen entities during training.
- The framework utilizes a diversity-aware adaptation of Yen's algorithm to extract the K shortest loopless paths between entities in a query, prioritizing biologically relevant and relationally diverse connections.
- Extracted paths from K-Paths can be integrated with both large language models (LLMs) and graph neural networks (GNNs) to enhance generalization, accuracy, and explainable inference capabilities.
- Experimental results show that K-Paths improves zero-shot reasoning across state-of-the-art LLMs, with significant improvements on tasks related to predicting interaction severity and drug repurposing.
- K-Paths enhances the training efficiency of EmerGNN—a leading GNN—by reducing the size of the KG while maintaining predictive performance levels.
- The framework serves as a bridge between KGs and LLMs, enabling scalable and explainable scientific discovery augmented by LLMs.
- Authors have made their code available along with retrieved paths as a benchmark resource for further research in inductive reasoning within drug discovery.
## Summary
In the realm of drug discovery, biomedical knowledge graphs (KGs) play a crucial role in encoding rich and structured information. However, extracting meaningful insights from these large-scale KGs poses a significant challenge due to their complex structure. Existing methods for retrieving biomedical subgraphs are typically tailored for graph neural networks (GNNs), which limits their compatibility with other paradigms such as large language models (LLMs). To address this limitation, a novel model-agnostic retrieval framework called K-Paths has been introduced.
K-Paths is designed to extract structured, diverse, and biologically meaningful multi-hop paths from dense biomedical KGs. These paths enable the prediction of unobserved interactions between drugs, as well as between drugs and diseases. Importantly, K-Paths supports inductive reasoning by including entities that were not seen during training. This training-free framework utilizes a diversity-aware adaptation of Yen's algorithm to extract the K shortest loopless paths between entities in a query. It prioritizes biologically relevant and relationally diverse connections, thereby generating concise and interpretable reasoning chains.
The extracted paths from K-Paths can be seamlessly integrated with both LLMs and GNNs to enhance generalization, accuracy, and explainable inference capabilities. Experimental results on benchmark datasets demonstrate the effectiveness of K-Paths in improving zero-shot reasoning across state-of-the-art LLMs.
For instance,Tx-Gemma 27B shows improvements of 19.8 and 4.0 F1 points on tasks related to predicting interaction severity and drug repurposing respectively, while Llama 70B achieves gains of 8.5 and 6.2 points on the same tasks.
Moreover,K-Paths enhances the training efficiency of EmerGNN—a leading GNN—by significantly reducing the size of the KG while maintaining predictive performance levels. Beyond efficiency gains, K-Paths serves as a bridge between KGs and LLMs, enabling scalable and explainable scientific discovery augmented by LLMs.
To facilitate further research in inductive reasoning within the domain of drug discovery, the authors have made their code available along with retrieved paths as a benchmark resource for the community. This innovative approach holds promise for advancing drug discovery efforts through enhanced reasoning capabilities facilitated by structured path extraction from biomedical KGs.