Graph Transformer with Disease Subgraph Positional Encoding for Improved Comorbidity Prediction

Basic Information

• Paper ID: 2503.03046
• Title: Graph Transformer with Disease Subgraph Positional Encoding for Improved Comorbidity Prediction
• Authors: Xihan Qin, Li Liao (University of Delaware)
• Classification: cs.LG (Machine Learning)
• Paper Link: https://arxiv.org/abs/2503.03046
• Code Link: https://github.com/xihan-qin/TSPE-GraphTransformer

Abstract

This study addresses the disease comorbidity prediction problem by proposing a Graph Transformer method with subgraph positional encoding (TSPE). The approach leverages Human Interactome (HI) data and employs Transformer attention mechanisms combined with a novel Subgraph Positional Encoding (SPE) to capture inter-node interactions and disease associations. Experiments on clinical benchmark datasets RR0 and RR1 demonstrate that TSPE achieves improvements of up to 28.24% in ROC AUC and 4.93% in accuracy compared to existing state-of-the-art methods.

Research Background and Motivation

Problem Definition

1. Core Problem: Disease comorbidity prediction, i.e., predicting the likelihood of multiple diseases occurring simultaneously in the same patient
2. Significance: Comorbidity significantly affects disease management, treatment strategies, and prognostic outcomes, particularly in pandemics such as COVID-19, where specific comorbidities lead to more severe outcomes
3. Limitations of Existing Methods:
   • Traditional methods such as geodesic embedding (GE) have limited performance
   • The current state-of-the-art method BSE, while introducing supervised selection mechanisms, still relies on traditional SVM classifiers
   • The Graph Transformer proposed by Dwivedi et al. uses Laplacian Positional Encoding (LPE) that lacks disease-specific information

Research Motivation

Building on the emphasis of BSE research on node connectivity and disease associations, this work explores leveraging Transformer attention mechanisms and specially designed subgraph positional encoding to improve comorbidity prediction performance.

Core Contributions

1. Proposes TSPE Framework: First application of Transformer architecture to disease comorbidity prediction, designing an encoder-decoder structure suitable for graph data
2. Innovative Subgraph Positional Encoding (SPE): Combines clustering information from Laplacian Positional Encoding (LPE) with disease label information from Graph Positional Encoding (GPE)
3. Significant Performance Improvements: Substantially outperforms existing state-of-the-art methods on both benchmark datasets
4. Comprehensive Ablation Studies: Validates the effectiveness of different positional encoding methods

Methodology Details

Task Definition

• Input: Two disease subgraphs (protein node sets) from the Human Interactome graph
• Output: Binary classification result determining whether two diseases exhibit comorbidity
• Constraints: Positive and negative samples defined based on clinical relative risk (RR) values

Model Architecture

Overall Framework

TSPE adopts an encoder-decoder architecture:

• Encoder: Processes node embeddings of disease A
• Decoder: Processes node embeddings of disease B and learns inter-disease relationships through cross-attention
• Classification Layer: Converts decoder output to binary classification results

Key Technical Components

1. Node Embedding Generation Node embeddings are generated using Node2Vec with parameters p=1, q=1 (balanced random walk) and window size of 2.

2. Subgraph Positional Encoding (SPE) SPE = (M + LPE), GPE, where:

• M: Node embedding matrix
• LPE: Laplacian Positional Encoding, capturing graph clustering information
• GPE: Graph Positional Encoding, capturing disease label information

3. GPE Computation Process

Z = AW                    # (11) GEE embedding calculation
Z = UΣV^T                 # (12) Singular Value Decomposition
GPE = U_d                 # (13) Select top d left singular vectors

4. Classification Mechanism

s = softmax(||X||²₂,axis=1)     # (6) Compute score vector
y_cand = Σ(X·diag(s))_j         # (8) Weighted summation
y_pred = σ(Wy_cand + b)         # (9) Final prediction

Technical Innovations

1. Unified Attention Mechanism: Uses unmasked multi-head attention, enabling the model to attend to all nodes within subgraphs
2. Disease-Specific Positional Encoding: GPE directly leverages disease label information, providing more targeted encoding than traditional LPE
3. Multi-Level Information Fusion: SPE simultaneously captures graph topology (LPE) and biological significance (GPE)

Experimental Setup

Datasets

• Source: Human Interactome dataset from Menche et al.
• Scale: 13,460 protein nodes, 153 disease subgraphs, 10,743 disease pairs
• Dataset Partition:
  • RR0: RR > 0 as positive samples (82.6% positive samples)
  • RR1: RR > 1 as positive samples (58.4% positive samples)

Evaluation Metrics

• Primary Metric: ROC AUC (suitable for imbalanced datasets)
• Secondary Metric: Accuracy

Comparison Methods

• Node2Vec + SVM
• BSE + Node2Vec + SVM (current state-of-the-art method)

Implementation Details

Experimental Results

Main Results

RR0 Dataset:

RR1 Dataset:

Ablation Studies

Testing different positional encoding methods on the RR1 dataset:

Experimental Findings

1. Significant Performance Improvements: TSPE achieves 28.24% improvement in ROC AUC over BSE_SVM on RR0 and 15.40% on RR1
2. Importance of Positional Encoding: SPE outperforms LPE, demonstrating the value of disease label information
3. Effectiveness of Attention Mechanism: Transformer architecture substantially outperforms traditional SVM classifiers

Related Work

Main Research Directions

1. Network-Based Methods: Predicting disease relationships using protein interaction networks
2. Graph Embedding Methods: Such as geodesic embedding (GE) and Biologically Supervised Embedding (BSE)
3. Graph Transformers: General Graph Transformer framework proposed by Dwivedi et al.

Advantages of This Work

1. Architectural Innovation: First application of Transformer to disease comorbidity prediction
2. Encoding Improvements: Proposed SPE is better suited for biomedical tasks than standard LPE
3. Performance Breakthrough: Substantially surpasses existing state-of-the-art methods

Conclusions and Discussion

Main Conclusions

1. TSPE successfully adapts Transformer architecture to disease comorbidity prediction
2. Subgraph Positional Encoding SPE effectively combines topological and biological information
3. Attention mechanisms effectively capture complex relationships between protein nodes

Limitations

1. Data Dependency: Requires disease label information to utilize SPE
2. Computational Complexity: Transformer architecture incurs higher computational overhead compared to traditional methods
3. Interpretability: The biological significance of attention weights requires further investigation

Future Directions

1. Adaptation to other subgraph relationship prediction tasks
2. Exploration of additional types of positional encoding methods
3. Enhancement of model interpretability

In-Depth Evaluation

Strengths

1. Strong Methodological Innovation: First successful application of Transformer to disease comorbidity prediction
2. Clear Technical Contributions: SPE positional encoding is well-designed and effectively fuses multiple information sources
3. Comprehensive Experimental Design: Includes sufficient comparative experiments and ablation studies
4. Significant Performance Improvements: Achieves substantial improvements on both benchmark datasets

Weaknesses

1. Insufficient Theoretical Analysis: Lacks in-depth theoretical analysis of why Transformer is effective for this task
2. Computational Efficiency Not Discussed: Training time and inference efficiency comparisons are not reported
3. Limited Biological Validation: Lacks biological significance validation of prediction results

Impact

1. Academic Value: Provides new insights for Graph Transformer applications in biomedical domains
2. Practical Value: Can be directly applied to clinical decision support systems
3. Reproducibility: Complete code implementation is provided

Applicable Scenarios

1. Disease risk assessment and personalized medicine
2. Drug repurposing and adverse effect prediction
3. Other graph-based biomedical prediction tasks

References

1. Menche et al. "Uncovering disease-disease relationships through the incomplete interactome." Science (2015)
2. Dwivedi & Bresson. "A generalization of transformer networks to graphs." AAAI Workshop (2021)
3. Grover & Leskovec. "node2vec: Scalable feature learning for networks." KDD (2016)

Overall Assessment: This is a high-quality research paper that successfully introduces Transformer architecture to disease comorbidity prediction. The proposed SPE positional encoding method demonstrates clear biological motivation and technical innovation. The experimental results are impressive and provide valuable references for related research.