PHeLP: Prompt-Enhanced Link Prediction for Multi-Label Node Classification on Heterophilic Graphs

Heterophily complicates multi-label node classification because the same neighborhood can play different predictive roles for different candidate labels. Existing heterophily-oriented methods are largely designed for single-label classification, while conventional multi-label methods remain limited in distinguishing label-dependent neighborhood relations under heterophily. To address this challenge, we propose PHeLP, a prompt-enhanced link prediction framework for multi-label node classification on heterophilic graphs. First, to explicitly capture node–label relations, we formulate the task as heterogeneous data–label link prediction, making each candidate data–label pair an explicit prediction instance and allowing graph structure, observed training associations, and label dependencies to jointly inform prediction. Second, to distinguish the predictive roles of the same neighborhood across candidate labels, we introduce a heterophily-aware pairwise prompting mechanism. PHeLP captures affinity and repulsion as complementary neighborhood patterns and uses affinity and repulsion prompts to refine a shared pair representation in separate branches. Matching the target node's local observed-label composition to the candidate label's affinity and repulsion patterns then determines how the branch predictions are adaptively combined. Theoretical analysis indicates that PHeLP can enhance distinguishability and reduce prediction risk. Extensive experiments on multi-label graph benchmarks demonstrate the effectiveness and robustness of PHeLP across node-split and label-split settings.