K-Paths: Reasoning over Graph Paths for Drug Repurposing and Drug Interaction Prediction

• URL: http://arxiv.org/abs/2502.13344v3
• Date: Wed, 28 May 2025 23:21:27 GMT
• Title: 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,
• Abstract summary: K-Paths is a model-agnostic retrieval framework that extracts structured, diverse, and biologically meaningful multi-hop paths from dense biomedical knowledge graphs.<n>These paths enable the prediction of unobserved drug-drug and drug-disease interactions.<n>Experiments show that K-Paths improves zero-shot reasoning across state-of-the-art language models.
• Score: 21.72997408572975
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Biomedical knowledge graphs (KGs) encode rich, structured information critical for drug discovery tasks, but extracting meaningful insights from large-scale KGs remains challenging due to their complex structure. Existing biomedical subgraph retrieval methods are tailored for graph neural networks (GNNs), limiting compatibility with other paradigms, including large language models (LLMs). We introduce K-Paths, a model-agnostic retrieval framework that extracts structured, diverse, and biologically meaningful multi-hop paths from dense biomedical KGs. These paths enable the prediction of unobserved drug-drug and drug-disease interactions, including those involving entities not seen during training, thus supporting inductive reasoning. K-Paths is training-free and employs 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. These paths serve as concise, interpretable reasoning chains that can be directly integrated with LLMs or GNNs to improve generalization, accuracy, and enable explainable inference. Experiments on benchmark datasets show that K-Paths improves zero-shot reasoning across state-of-the-art LLMs. For instance, Tx-Gemma 27B improves by 19.8 and 4.0 F1 points on interaction severity prediction and drug repurposing tasks, respectively. Llama 70B achieves gains of 8.5 and 6.2 points on the same tasks. K-Paths also boosts the training efficiency of EmerGNN, a state-of-the-art GNN, by reducing the KG size by 90% while maintaining predictive performance. Beyond efficiency, K-Paths bridges the gap between KGs and LLMs, enabling scalable and explainable LLM-augmented scientific discovery. We release our code and the retrieved paths as a benchmark for inductive reasoning.

Related papers

• MuCoS: Efficient Drug Target Discovery via Multi Context Aware Sampling in Knowledge Graphs [0.0]
  Multi Context Aware Sampling (MuCoS) is a novel framework that prioritizes high-density neighbours to capture salient structural patterns. Experiments on the KEGG50k dataset demonstrate that MuCoS outperforms state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-03-11T06:08:42Z)
• eXpath: Explaining Knowledge Graph Link Prediction with Ontological Closed Path Rules [12.802269132505364]
  Link prediction (LP) is crucial for Knowledge Graphs (KG) completion but commonly suffers from interpretability issues.<n>We propose to explain LP models in KG with path-based explanations.
  arXiv  Detail & Related papers  (2024-12-06T08:33:49Z)
• Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models [92.71304585906624]
  Large language models (LLMs) struggle with faithful reasoning due to knowledge gaps and hallucinations.<n>We introduce graph-constrained reasoning (GCR), a novel framework that bridges structured knowledge in KGs with unstructured reasoning in LLMs.<n>GCR achieves state-of-the-art performance and exhibits strong zero-shot generalizability to unseen KGs without additional training.
  arXiv  Detail & Related papers  (2024-10-16T22:55:17Z)
• Tree-of-Traversals: A Zero-Shot Reasoning Algorithm for Augmenting Black-box Language Models with Knowledge Graphs [72.89652710634051]
  Knowledge graphs (KGs) complement Large Language Models (LLMs) by providing reliable, structured, domain-specific, and up-to-date external knowledge. We introduce Tree-of-Traversals, a novel zero-shot reasoning algorithm that enables augmentation of black-box LLMs with one or more KGs.
  arXiv  Detail & Related papers  (2024-07-31T06:01:24Z)
• Augmentation is AUtO-Net: Augmentation-Driven Contrastive Multiview Learning for Medical Image Segmentation [3.1002416427168304]
  This thesis focuses on retinal blood vessel segmentation tasks. It provides an extensive literature review of deep learning-based medical image segmentation approaches. It proposes a novel efficient, simple multiview learning framework.
  arXiv  Detail & Related papers  (2023-11-02T06:31:08Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  Heterogeneous Graph Neural Networks (HGNNs) are powerful tools for deep learning on heterogeneous graphs. Recent pre-computation-based HGNNs use one-time message passing to transform a heterogeneous graph into regular-shaped tensors. We propose a hybrid pre-computation-based HGNN, named Random Projection Heterogeneous Graph Neural Network (RpHGNN)
  arXiv  Detail & Related papers  (2023-10-23T01:25:44Z)
• Meta-Path-based Probabilistic Soft Logic for Drug-Target Interaction Prediction [36.08294497336554]
  Drug-target interaction (DTI) prediction aims at predicting whether a drug will be bounded to a target. Most of the recently proposed methods use single drug-drug similarity and target-target similarity information for DTI prediction. We propose a network-based drug-target interaction prediction approach.
  arXiv  Detail & Related papers  (2023-06-25T02:30:38Z)
• Normalizing Flow-based Neural Process for Few-Shot Knowledge Graph Completion [69.55700751102376]
  Few-shot knowledge graph completion (FKGC) aims to predict missing facts for unseen relations with few-shot associated facts. Existing FKGC methods are based on metric learning or meta-learning, which often suffer from the out-of-distribution and overfitting problems. In this paper, we propose a normalizing flow-based neural process for few-shot knowledge graph completion (NP-FKGC)
  arXiv  Detail & Related papers  (2023-04-17T11:42:28Z)
• Enhancing Embedding Representations of Biomedical Data using Logic Knowledge [6.295638112781736]
  In this paper, we exploit logic rules to enhance the embedding representations of knowledge graph models on the PharmKG dataset. An R2N uses the available logic rules to build a neural architecture that reasons over KGE latent representations. In the experiments, we show that our approach is able to significantly improve the current state-of-the-art on the PharmKG dataset.
  arXiv  Detail & Related papers  (2023-03-23T13:38:21Z)
• Walk-and-Relate: A Random-Walk-based Algorithm for Representation Learning on Sparse Knowledge Graphs [5.444459446244819]
  We propose an efficient method to augment the number of triplets to address the problem of data sparsity. We also provide approaches to accurately and efficiently filter out informative metapaths from the possible set of metapaths. The proposed approaches are model-agnostic, and the augmented training dataset can be used with any KG embedding approach out of the box.
  arXiv  Detail & Related papers  (2022-09-19T05:35:23Z)
• Neural Networks for Local Search and Crossover in Vehicle Routing: A Possible Overkill? [10.882329986831087]
  We investigate the use of predictions from graph neural networks (GNNs) in the form of heatmaps to improve the Hybrid Genetic Search (HGS) We show that exploiting more sophisticated strategies using measures of node relatedness can significantly enhance performance. However, contrary to initial expectations, we also observed that heatmaps did not present significant advantages over simpler distance measures.
  arXiv  Detail & Related papers  (2022-09-09T22:08:17Z)
• Explainable Sparse Knowledge Graph Completion via High-order Graph Reasoning Network [111.67744771462873]
  This paper proposes a novel explainable model for sparse Knowledge Graphs (KGs) It combines high-order reasoning into a graph convolutional network, namely HoGRN. It can not only improve the generalization ability to mitigate the information insufficiency issue but also provide interpretability.
  arXiv  Detail & Related papers  (2022-07-14T10:16:56Z)
• Scientific Language Models for Biomedical Knowledge Base Completion: An Empirical Study [62.376800537374024]
  We study scientific LMs for KG completion, exploring whether we can tap into their latent knowledge to enhance biomedical link prediction. We integrate the LM-based models with KG embedding models, using a router method that learns to assign each input example to either type of model and provides a substantial boost in performance.
  arXiv  Detail & Related papers  (2021-06-17T17:55:33Z)
• Path-based knowledge reasoning with textual semantic information for medical knowledge graph completion [20.929596842568994]
  Medical knowledge graphs (KGs) are often significantly incomplete, so it necessitating a demand for medical knowledge graph completion (MedKGC) MedKGC can find new facts based on the exited knowledge in the KGs. This paper proposes two novel path-based reasoning methods to solve the sparsity issues of entity and path respectively.
  arXiv  Detail & Related papers  (2021-05-27T11:45:59Z)
• Cyclic Label Propagation for Graph Semi-supervised Learning [52.102251202186025]
  We introduce a novel framework for graph semi-supervised learning called CycProp. CycProp integrates GNNs into the process of label propagation in a cyclic and mutually reinforcing manner. In particular, our proposed CycProp updates the node embeddings learned by GNN module with the augmented information by label propagation.
  arXiv  Detail & Related papers  (2020-11-24T02:55:40Z)
• SumGNN: Multi-typed Drug Interaction Prediction via Efficient Knowledge Graph Summarization [64.56399911605286]
  We propose SumGNN: knowledge summarization graph neural network, which is enabled by a subgraph extraction module. SumGNN outperforms the best baseline by up to 5.54%, and the performance gain is particularly significant in low data relation types.
  arXiv  Detail & Related papers  (2020-10-04T00:14:57Z)
• GCN for HIN via Implicit Utilization of Attention and Meta-paths [104.24467864133942]
  Heterogeneous information network (HIN) embedding aims to map the structure and semantic information in a HIN to distributed representations. We propose a novel neural network method via implicitly utilizing attention and meta-paths. We first use the multi-layer graph convolutional network (GCN) framework, which performs a discriminative aggregation at each layer. We then give an effective relaxation and improvement via introducing a new propagation operation which can be separated from aggregation.
  arXiv  Detail & Related papers  (2020-07-06T11:09:40Z)
• A Trainable Optimal Transport Embedding for Feature Aggregation and its Relationship to Attention [96.77554122595578]
  We introduce a parametrized representation of fixed size, which embeds and then aggregates elements from a given input set according to the optimal transport plan between the set and a trainable reference. Our approach scales to large datasets and allows end-to-end training of the reference, while also providing a simple unsupervised learning mechanism with small computational cost.
  arXiv  Detail & Related papers  (2020-06-22T08:35:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.