acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Multi-label node classification, Heterophilic graph, Link prediction, Prompt learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_yXgsOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper handles the problem of multilabel node classification in heterophilous graphs. It proposes 2 techniques: casting node classification as link prediction to a label-specific virtual node and pairwise prompting (which uses representations based on each label's affinity and repulsion computed over the training nodes). The proposed method combining these 2 techniques is named PHeLP. Some theoretical properties of PHeLP are investigated, and empirical evaluation is performed on 6 datasets.

Critical strengths

The paper is fairly well-written and easy to follow.

Critical weaknesses

Positioning. The paper targets specifically the setting of heterophilous graphs and makes the following claim: "heterophily challenges conventional message-passing GNNs". However, it has been shown many times in prior literature that it is actually not the case and classic message-passing GNNs perform perfectly fine on heterophilous graphs, typically outperforming heterophily-specific models [1-6]. Thus, it is not clear that any specialized methods are needed for handling node classification in heterophilous graphs. Further, [3] and especially [5] demonstrate that modified versions of classic GNNs with improved architectures (added skip connections, normalizations, dropout) strongly outperform both GNNs without these improvements and heterophily-specific models. Such improved GNNs need to be used as baselines over weaker models used in this work.

Novelty. The contributions of the paper consist of two techniques: casting node classification as link prediction and pairwise prompting. However, the first of these techniques - treating node classification as link prediction - does not seem to be specific to either heterophilous or multi-label graphs - it can be used for node classification in any graph. And it is not novel: casting node classification as link prediction to virtual nodes is very common and was used, for example, in some early attempts to create graph foundation models [7, 8], although I suspect it is even older than that. Which leaves pairwise prompting as the only novel contribution of the paper. While the idea behind pairwise prompting is somewhat interesting, it is very simple and empirical gains from it are not that impressive, which means this idea is not enough to be the sole contribution of a paper at ICLR.

Potential leakage. The paper creates features for virtual class nodes using GPT-5.5, SciBERT, and PubMedBERT. However, these models were pretrained on large datasets (especially GPT) which likely included the source data of node classification datasets being used such as DBLP (including the node labels). This means that there is a possibility of data leakage. Such leakage caused by using LLMs to create features for node classification datasets has been discussed in [9].

[1] Is homophily a necessity for graph neural networks? (ICLR 2022)

[2] Revisiting heterophily for graph neural networks (NeurIPS 2022)

[3] A critical look at the evaluation of GNNs under heterophily: Are we really making progress? (ICLR 2023)

[4] Characterizing Graph Datasets for Node Classification: Homophily–Heterophily Dichotomy and Beyond (NeurIPS 2023)

[5] Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification (NeurIPS 2024)

[6] Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning (ICLR 2026)

[7] OpenGraph: Towards Open Graph Foundation Models (EMNLP 2024)

[8] AnyGraph: Graph Foundation Model in the Wild (arxiv preprint 2024)

[9] Harnessing Explanations: LLM-to-LM Interpreter for Enhanced Text-Attributed Graph Representation Learning (ICLR 2024)

Questions for authors

Can the authors address the issues raised in weaknesses?

4 comments
AuthorsOpenReview ↗

Author Response (Part 1/2)

Dear reviewer yXgs,

We sincerely appreciate your time and effort in evaluating our paper.

We are grateful to the reviewer for the positive remarks on the following aspects:

  • Clear and easy-to-follow presentation.
  • Interesting pairwise prompting idea.

In the rebuttal, we have provided the following clarifications and additional results.

Q1: Positioning.

A1: We agree that well-tuned classical GNNs can perform strongly on heterophilous graphs [1–6]. As Zhao et al. (Multi-label Node Classification On Graph-Structured Data) note, homophily has different semantics in multi-label graphs. PHeLP addresses label-dependent heterophily in MLNC, where the same neighborhood can play different predictive roles for different candidate labels.

Following [5], we tune GCN, GAT, and GraphSAGE with residual connections, LayerNorm, and dropout. The corresponding PHeLP variants directly adopt the same tuned backbone configurations. PHeLP consistently improves performance across the evaluated datasets and backbones, supporting its benefit beyond backbone tuning. The selected backbone configurations and corresponding performance comparisons are provided in Appendix A.3.2 (Tabs. 8 and 9, respectively).

DatasetBackboneGNN AUCPHeLP AUCGNN APPHeLP AP
PCGGCN64.71 ± 0.2465.00 ± 0.9525.74 ± 0.8226.37 ± 0.51
GAT64.03 ± 1.2265.47 ± 0.4025.52 ± 1.1425.75 ± 0.54
GraphSAGE63.03 ± 1.6164.51 ± 0.9322.10 ± 0.7024.62 ± 0.45
BlogCatGCN73.08 ± 0.3973.17 ± 0.6119.44 ± 0.4619.59 ± 0.39
GAT72.62 ± 0.4173.39 ± 0.3618.40 ± 0.2319.16 ± 0.42
GraphSAGE73.02 ± 0.4873.96 ± 0.9017.83 ± 0.1819.71 ± 0.22
HumLocGCN75.87 ± 0.3477.50 ± 0.5024.22 ± 0.5527.30 ± 0.37
GAT76.85 ± 0.5079.48 ± 0.2026.74 ± 0.4630.53 ± 0.68
GraphSAGE76.54 ± 0.2476.82 ± 0.4126.28 ± 0.2326.30 ± 0.29
EukLocGCN75.99 ± 0.2079.06 ± 1.6615.10 ± 0.2218.71 ± 2.01
GAT76.88 ± 0.3279.20 ± 0.4116.37 ± 0.4320.42 ± 0.42
GraphSAGE77.03 ± 0.5277.51 ± 0.2216.21 ± 0.3316.77 ± 0.10
DBLPGCN96.53 ± 0.0697.53 ± 0.0394.69 ± 0.2795.00 ± 0.08
GAT96.59 ± 0.1897.61 ± 0.0994.63 ± 0.3695.08 ± 0.18
GraphSAGE96.64 ± 0.1697.75 ± 0.0294.86 ± 0.3695.31 ± 0.12

[1] Ma et al., Is Homophily a Necessity for Graph Neural Networks?, ICLR 2022.

[2] Luan et al., Revisiting Heterophily for Graph Neural Networks, NeurIPS 2022.

[3] Platonov et al., A Critical Look at the Evaluation of GNNs Under Heterophily: Are We Really Making Progress?, ICLR 2023.

[4] Platonov et al., Characterizing Graph Datasets for Node Classification: Homophily–Heterophily Dichotomy and Beyond, NeurIPS 2023.

[5] Luo et al., Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification, NeurIPS 2024.

[6] Arnaiz-Rodríguez and Errica, Oversmoothing, Oversquashing, Heterophily, Long-Range, and More: Demystifying Common Beliefs in Graph Machine Learning, ICLR 2026.

AuthorsOpenReview ↗

Author Response (Part 2/2)

Q2: Novelty.

A2: We appreciate your interest in pairwise prompting design and the opportunity to clarify the contributions of PHeLP.

  • Relation-aware heterogeneous data–label link prediction. OpenGraph [7] pretrains a link predictor on data--data edges. During inference, it augments the target graph with class nodes and uses the pretrained predictor to infer links between unlabeled data nodes and candidate class nodes, enabling cross-graph zero-shot classification. AnyGraph [8] further introduces competence-based graph expert routing, and scores node--class associations through embedding inner products, adapting to cross-graph distribution shifts. PHeLP constructs a heterogeneous graph containing data-data, data-label, and label-label relations during the training phase. It learns the representation of nodes and labels through relation-specific propagation and directly uses positive and negative node-label pairs for supervised training and optimizing. These differences change how candidate associations are represented, adapted, and supervised—not simply whether class nodes are introduced.

  • Heterophily-aware pairwise prompting. Its key contribution is to distinguish shared neighborhood relations from their pair-specific predictive effects. Global affinity and repulsion relations characterize which neighboring labels are over- or under-represented for a candidate label, but their predictive relevance depends on the target node's local observed-label composition. PHeLP independently groups labels according to their affinity and repulsion relations to learn shared prompts for two complementary branches. Pair-conditioned gates adapt these prompts to individual node–label pairs, while matching the target node's local observed-label composition with each candidate label's affinity and repulsion relations determines the relative contributions of the two branches (Eqs. 5–9). Together, these designs enable relational knowledge to be shared across labels while preserving the distinct predictive roles of the same neighborhood for different node–label pairs. Theorem 2 establishes sufficient conditions for a prediction-risk advantage over uniform fusion, while the Statistics-MLP comparison (Appendix A.3.5, Tab. 12) and Uniform ablation (Fig. 5(a)) provide complementary empirical support.

MethodHumLocPCGBlogCatEukLocDBLP
Statistics-MLP75.09±0.7259.80±1.3172.80±0.9373.60±1.1796.18±0.11
Single-branch76.22±0.4562.28±1.2464.25±10.7576.12±0.7395.75±0.22
Affinity-only75.85±0.1862.40±0.9064.27±10.7276.30±1.0495.81±0.18
Repulsion-only75.89±0.8662.68±0.8764.36±10.8574.88±1.7795.74±0.18
Full PHeLP77.01±0.7264.74±0.8774.29±0.4776.56±0.2596.74±0.17

[7] Xia et al., OpenGraph: Towards Open Graph Foundation Models, Findings of EMNLP 2024.

[8] Xia and Huang, AnyGraph: Graph Foundation Model in the Wild, Findings of ACL 2026.

Q3: Potential leakage.

A3: Thanks for raising this important concern.

  • TAPE [9] prompts an LLM with node texts to generate node predictions on classes. PHeLP prompts an LLM with class names and general domain information to generate class descriptions (Tab. 3), which PLMs encode as label-node features. No node-level data or supervision, such as held-out node–label associations, is provided to these language models.
  • Data–label edges, label–label relations, and neighborhood label statistics are constructed exclusively from observed training labels. Semantic label–label relations, when used, are derived from label descriptions without access to held-out node–label associations.
  • Appendix A.3.7 (Tab. 16) reports the effect of label semantics, including configurations with and without LLM-derived label features.

[9] He et al., Harnessing Explanations: LLM-to-LM Interpreter for Enhanced Text-Attributed Graph Representation Learning, ICLR 2024.

We hope these results and clarifications address the reviewer's concerns.

Thank you once again for your time and valuable suggestions.

Best regards,

The authors of submission 26213

I appreciate the author's rebuttal, especially additional experiments with stronger baselines, and increase my score.

AuthorsOpenReview ↗

Thank You for Your Positive Feedback

Dear Reviewer yXgs,

We are truly delighted by your positive feedback and sincerely appreciate your reconsideration and score increase.

We are especially grateful for your recognition of our additional experiments with stronger baselines. Your constructive suggestions have been invaluable in strengthening our work.

Thank you once again for your time, thoughtful consideration, and encouragement!

Best regards,

The Authors of Submission 26213

Reviewer_3qiCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes PHeLP, a prompt-enhanced link prediction framework for multi-label node classification on heterophilic graphs. It reformulates multi-label classification as heterogeneous data–label link prediction and introduces affinity- and repulsion-based prompting to capture label-dependent neighborhood relations. Although the experimental results are competitive, the methodological novelty is limited, and the theoretical and experimental justifications remain insufficient.

Critical strengths
  1. Meaningful Research Problem. The paper addresses multi-label node classification on heterophilic graphs, where the same neighborhood may play different predictive roles for different candidate labels. This is a relevant problem that deserves further investigation.
  2. Comprehensive Experimental Evaluation. The paper evaluates the proposed framework on six benchmark datasets, covering different GNN backbones, node-split and label-split settings, ablation studies, and efficiency analysis. The results demonstrate competitive performance across multiple settings.
Critical weaknesses
  1. Limited Methodological Novelty. The proposed framework largely combines existing techniques, including heterogeneous graph representation learning, label correlation modeling, learnable prompts, gating mechanisms, and adaptive fusion. In particular, the affinity and repulsion scores are essentially positive and negative deviations of conditional label frequencies from their marginal frequencies. The paper does not sufficiently distinguish its core contributions from existing label-aware graph learning methods.
  2. Insufficient Theoretical Justification. Theorem 1 establishes improved distinguishability under the heterogeneous formulation, but greater distinguishability does not necessarily imply better classification performance. Theorem 2 relies on a strong margin assumption that effectively requires the affinity-based matching weights to possess substantial discriminative ability, without establishing when this assumption holds. Theorem 3 inherits these limitations, leaving the practical significance of the theoretical results unclear.
  3. Insufficient Experimental Justification. The experiments lack important comparisons with simpler alternatives, such as conventional GNNs with learnable label embeddings and pairwise predictors, or MLP-based fusion of neighborhood statistics. Moreover, most datasets exhibit relatively low proportions of multi-label nodes, while DBLP is highly homophilic. These limitations weaken the empirical support for the claimed advantages in strongly heterophilic multi-label settings.
Questions for authors

Q1. Necessity of Heterogeneous Graph Construction.

Why is it necessary to introduce label nodes and construct a heterogeneous graph? Could comparable performance be achieved using a conventional GNN with learnable label embeddings and a pairwise predictor? Additionally, how does the proposed framework address potential information mixing caused by high-degree label nodes?

Q2. Necessity of the Prompting Mechanism.

What advantages does the proposed prompting mechanism offer over directly incorporating affinity, repulsion, and neighborhood label distributions into an MLP-based predictor? Since affinity and repulsion are derived from the positive and negative parts of the same association matrix, why are two separate prompting branches necessary?

Q3. Theoretical Significance of Theorem 1.

Theorem 1 establishes that heterogeneous graph construction can distinguish nodes that conventional GNNs cannot. However, increased distinguishability does not necessarily improve prediction accuracy. Under what conditions can this improvement in distinguishability lead to lower classification risk?

Q4. Validity of the Assumption in Theorem 2.

Theorem 2 assumes that affinity-based matching weights satisfy a strong margin condition. Can the authors theoretically justify this assumption based on graph heterophily or label distribution properties, rather than assuming that the matching weights already possess sufficient discriminative ability?

Q5. Representativeness of Benchmark Datasets.

Given that DBLP is highly homophilic and most benchmark datasets contain relatively few genuinely multi-label nodes, could the authors provide additional evaluations on datasets exhibiting both strong heterophily and substantial multi-label characteristics?

Q6. Contribution of Individual Components.

Could the authors provide more fine-grained ablation studies independently examining data–label edges, label–label edges, affinity and repulsion modeling, prompt grouping, and pairwise gating? This would help clarify which components are primarily responsible for the performance improvements.

6 comments
AuthorsOpenReview ↗

Author Response (Part 1/5)

Dear reviewer 3qic,

We sincerely thank you for the careful assessment and the specific, constructive questions.

We appreciate your recognition of the following strengths of our work:

  1. Meaningful Research Problem.
  2. Comprehensive Experimental Evaluation.

In the rebuttal, we have provided the following clarifications and additional results.

W1: Limited Methodological Novelty.

R1: In the Label-Aware Graph Learning methods,

  • CorGCN [1] emphasizes correlation-aware graph decomposition.
  • LIP [2] propagates label influences to guide learning.
  • GraphPrompt [3] applies task-specific prompts to subgraph readout, adapting aggregated representations rather than individual node--label interactions.
  • PSP [4] introduces learnable node--prototype connections to refine class prototypes on heterophilic graphs, using structural prompts for prototype construction rather than pair-specific affinity and repulsion matching.
  • OFA [5] constructs query-centered prompt graphs and predicts from class-node representations, organizing class information through task-specific prompt connections rather than explicitly encoding inter-label dependencies.
  • GPPT [6] separately constructs class-specific task tokens and GNN-derived structure tokens, then matches them using an edge predictor pretrained on data--data links, treating class tokens as matching prototypes rather than graph nodes participating in message passing.
  • OpenGraph [7] pretrains a link predictor on data--data edges. During inference, it augments the target graph with class nodes and uses the pretrained predictor to infer links between unlabeled data nodes and candidate class nodes, enabling cross-graph zero-shot classification.
  • AnyGraph [8] further introduces competence-based graph expert routing, and scores node--class associations through embedding inner products, adapting to cross-graph distribution shifts.

The methodological contribution of PHeLP lies in enhancing relation-aware heterogeneous data–label link prediction with heterophily-aware pairwise prompting. Firstly, PHeLP constructs a heterogeneous graph containing data-data, data-label, and label-label relations during the training phase. It learns the representation of nodes and labels through relation-specific propagation and directly uses positive and negative node-label pairs for supervised training. Secondly, PHeLP groups labels separately according to their affinity and repulsion relations to learn shared prompts. It adapts these prompts to individual node–label pairs through pair-conditioned gates and determines the contributions of the two branches through candidate-label-specific matching with local observed-label composition. Together, these designs enable relational knowledge to be shared across labels while preserving the distinct predictive roles of the same neighborhood for different node–label pairs.

[1] Bei et al., Correlation-Aware Graph Convolutional Networks for Multi-Label Node Classification, KDD 2025.

[2] Sun et al., Multi-Label Node Classification with Label Influence Propagation, ICLR 2025.

[3] Liu et al., GraphPrompt: Unifying Pre-Training and Downstream Tasks for Graph Neural Networks, WWW 2023.

[4] Ge et al., PSP: Pre-Training and Structure Prompt Tuning for Graph Neural Networks, ECML PKDD 2024.

[5] Liu et al., One For All: Towards Training One Graph Model For All Classification Tasks, ICLR 2024.

[6] Sun et al., GPPT: Graph Pre-training and Prompt Tuning to Generalize Graph Neural Networks, KDD 2022.

[7] Xia et al., OpenGraph: Towards Open Graph Foundation Models, Findings of EMNLP 2024.

[8] Xia and Huang, AnyGraph: Graph Foundation Model in the Wild, Findings of ACL 2026.

AuthorsOpenReview ↗

Author Response (Part 2/5)

W2: Insufficient Theoretical Justification.

R2: The original manuscript already provides mathematical justifications for these results in Appendix A.1. We clarify the key conditions below.

1. Theorem 1. Theorem 1 establishes a distinguishability advantage. Corollary 4 and its stochastic-label extension further show that when node–label pair types with identical data-node-only contexts have different conditional label probabilities (p1≠p2p_1\neq p_2), both occur with positive probability, and their distinct heterogeneous representations allow the predictor to realize these probabilities, the attainable BCE risk is strictly reduced (inf⁡θhetRhet<inf⁡θdirRdir\inf_{\theta_{\mathrm{het}}}\mathfrak{R}_{\mathrm{het}} < \inf_{\theta_{\mathrm{dir}}}\mathfrak{R}_{\mathrm{dir}}; Appendix A.1.1).

2. Theorem 2. Rather than presupposing discriminative matching weights, Appendix A.1.2 derives explicit sufficient conditions for the matching-margin assumption from label-conditional neighborhood distributions. Under the assumptions in Appendix A.1.2, nonzero positive and negative deviations (δ+≠0\boldsymbol{\delta}_{+}\neq\mathbf{0} and δ−≠0\boldsymbol{\delta}_{-}\neq\mathbf{0}) yield a positive population matching gap Γ>0\Gamma>0. When relation-estimation error and neighborhood variation satisfy κ<η\kappa < \eta and υc<(η−κ)2\upsilon_c < (\eta-\kappa)^2, where η=dmin⁡Γ/8\eta=d_{\min}\Gamma/8, the midpoint threshold guarantees a margin γc=Γ/4\gamma_c=\Gamma/4 with violation probability at most υc/(η−κ)2\upsilon_c/(\eta-\kappa)^2.

3. Theorem 3. Under Theorem 2's conditions, positive additional label-predictive information I(Yic;hic∣Xc)>0I(Y_{ic};\mathbf{h}_{ic}\mid X_c)>0 and the entropy-gap condition Ψ(εc,γc)<H(Yic∣Xc,hic)\Psi(\varepsilon_c,\gamma_c)<H(Y_{ic}\mid X_c,\mathbf{h}_{ic}) guarantee strictly lower attainable BCE risk than both data-node-only prediction and uniform fusion (Eq. 13).

We have highlighted these key conditions and their risk implications in Section 3.5 of the revised manuscript. We have also added empirical matching-margin diagnostics across six datasets (Appendix A.3.9, Figs. 9–10), demonstrating the discriminative behavior of the matching weights. The Full–Uniform ablation (Fig. 5a) further supports the predictive benefit of pair-specific matching.

W3: Insufficient Experimental Justification.

R3: We address these concerns through controlled comparisons with GNN + LabelEmb + Pair (A1; Appendix A.3.5, Tab. 13) and Stats-MLP (A2; Appendix A.3.5, Tab. 12), demonstrating PHeLP's advantages beyond simpler label-aware prediction and direct statistical fusion. We further evaluate PPI (Edge-H: 34.14%; multi-label ratio: 96.08%), where PHeLP outperforms all compared baselines (A5; Appendix A.3.1, Tabs. 6–7), providing direct evidence of its effectiveness in settings combining heterophily with substantial multi-label characteristics.

AuthorsOpenReview ↗

Author Response (Part 3/5)

Q1: Necessity of Heterogeneous Graph Construction.

A1: Thanks for the important concerns.

1)Necessity Heterogeneous Graph Construction. Two nodes may be indistinguishable to a conventional GNN on the original attributed graph but different label-related information through their neighbors' observed label associations. In GNN + LabelEmb + Pair, these nodes receive identical GNN representations. Since the same candidate label also has the same learnable embedding, their predictions are identical, even when the observed associations provide different predictive information. In contrast, PHeLP incorporates observed data–label associations and label-label relations into message passing, allowing such differences to influence node representations and predictions. Theorem 1 establishes this distinguishability advantage, while Corollary 4 provides an explicit case where it leads to lower attainable BCE risk.

We further compare PHeLP with GNN + LabelEmb + Pair, which uses a conventional two-layer GNN, learnable label embeddings, and the same pair encoder and predictor. The better performance of PHeLP in the Table below, combined with A6, can demonstrate the effectiveness of heterogeneous representation learning (Appendix A.3.5, Tab. 13).

DatasetMethodMacro AUCMacro AP
DBLPGNN + LabelEmb + Pair95.32 ± 0.0991.62 ± 0.17
PHeLP96.74 ± 0.1793.43 ± 0.44
HumLocGNN + LabelEmb + Pair74.30 ± 1.7025.11 ± 0.75
PHeLP77.01 ± 0.7228.60 ± 0.94
EukLocGNN + LabelEmb + Pair76.05 ± 0.9214.72 ± 0.67
PHeLP76.56 ± 0.2515.90 ± 0.22
BlogCatGNN + LabelEmb + Pair52.52 ± 0.794.42 ± 0.15
PHeLP74.29 ± 0.4718.71 ± 0.69
PCGGNN + LabelEmb + Pair58.94 ± 1.1319.69 ± 0.80
PHeLP64.74 ± 0.8724.12 ± 0.70

2) High-degree label nodes may cause hub-induced representation homogenization. Beyond conventional measures such as normalization, shallow propagation, and skip connections, PHeLP uses normalized aggregation, shallow propagation, and skip connections, together with relation-specific transformations. Predictions additionally depend on the node–label pair representation and matching between local observed-label composition and the candidate label’s affinity and repulsion relations (Eqs. 7–9). These pair-specific inputs allow predictions to differ even when shared label nodes provide similar messages. High-degree label selection criteria are provided in Tab. 14, with the corresponding performance results reported in Tab. 15 (Appendix A.3.5).

DatasetMethodMacro AUC (%)Macro AP (%)
DBLPGNN + LabelEmb + Pair97.38 ± 0.0196.28 ± 0.06
Full PHeLP97.82 ± 0.0596.81 ± 0.12
HumLocGNN + LabelEmb + Pair80.47 ± 0.3453.11 ± 0.94
Full PHeLP82.70 ± 0.4656.94 ± 0.52
EukLocGNN + LabelEmb + Pair76.54 ± 0.2132.27 ± 0.89
Full PHeLP77.55 ± 0.1834.30 ± 0.33
BlogCatGNN + LabelEmb + Pair77.89 ± 0.4137.25 ± 0.90
Full PHeLP78.71 ± 0.5738.59 ± 1.19
PCGGNN + LabelEmb + Pair57.90 ± 0.5130.96 ± 0.37
Full PHeLP63.52 ± 0.4437.58 ± 0.42
Reviewer_uxPyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies multi-label node classification on heterophilic graphs and proposes PHeLP, a prompt-enhanced link prediction framework. The method constructs a heterogeneous graph containing data nodes and label nodes, transforming the classification task into data–label link prediction. It estimates label-dependent affinity and repulsion relations using observed training labels and the neighborhood structure of the data graph, separately adjusts a shared node–label pair representation through two types of group prompts, and adaptively fuses the predictions of the two branches using node–label pair-specific matching weights. The paper provides a theoretical analysis of distinguishability and the attainable population prediction risk, and conducts experimental evaluations on six datasets under both node-split and label-split protocols.

Critical strengths

1.Tables 1 and 2 show that PHeLP is competitive on six datasets. Ablation experiments further support the effectiveness of the prompt module and pairwise matching weights, providing evidence for the value of the complete method. 2.The paper provides a reasonable modeling of label-dependent neighborhood information. By treating data–label pairs as prediction instances, the method offers a targeted solution to the problem that the same neighborhood plays different roles for different candidate labels.

Critical weaknesses

1.The risk conclusion of Theorem 2 relies on the matching margin assumption, but the experiments do not directly report the empirical satisfaction of this assumption on real data. Therefore, it is difficult to judge to what extent this theoretical condition can explain the actual performance improvement. 2. Some comparisons and implementation details are insufficiently explained , such as how label groups are formed, which affects the accurate reproduction of the method.

Questions for authors

1.The risk conclusion of Theorem 2 relies on the matching margin assumption. Is this assumption empirically supported on the datasets used? Can the authors provide a corresponding analysis? 2. Table 2 contains only four of the twelve baseline methods evaluated in Table 1. What was the criterion for selecting these baseline methods for label split evaluation? 3. The paper groups labels separately based on the cosine similarity of affinity and repulsion relation profiles. Can the authors further explain how the label groups are determined from these similarities, and how the number of groups is obtained? In addition, how are the Emb/Rel configurations for each dataset in the main experiments determined?

3 comments
AuthorsOpenReview ↗

Author Response (Part 1/2)

Dear reviewer uxPy,

We sincerely appreciate your time and effort in evaluating our paper.

We are grateful to the reviewers for recognizing the value of our work in the following aspects:

  • Reasonable modeling & targeted solution.
  • Strong Empirical Evidence.

In the rebuttal, we have provided the following clarifications and additional results.

Q1: Empirical Support for the Matching-Margin Assumption.

A1: We directly evaluate the matching-margin condition in Theorem 2 using the matching weights in Eq. 7. For each label, we measure the fraction of test node–label pairs satisfying $ (2Y_{ic}-1)(\alpha_{ic}^{\mathrm{aff}}-\tau_c)\geq\gamma $.

Appendix A.3.9 (Figs. 9–10) reports overall, positive-pair, and negative-pair satisfaction across multiple margin levels under validation-balanced and class-conditional midpoint thresholds. Each label-specific threshold remains fixed across margin levels. The table below reports validation-balanced results at $ \gamma=0.05 $, with satisfaction rates macro-averaged over evaluable labels. Here, $ \Delta_\alpha $ denotes the macro-averaged positive-minus-negative difference in affinity matching weights, while Affinity AUC measures their ability to distinguish positive and negative pairs.

DatasetMargin satisfaction ↑Positive ↑Negative ↑$ \Delta_\alpha $ ↑Affinity AUC ↑
DBLP84.16 ± 0.2182.72 ± 0.3883.68 ± 0.480.584 ± 0.00292.75 ± 0.09
BlogCat56.35 ± 2.8350.36 ± 3.4156.23 ± 2.890.126 ± 0.00965.54 ± 0.45
Delve86.18 ± 0.4859.63 ± 0.6786.38 ± 0.490.296 ± 0.00273.57 ± 0.17
PCG33.53 ± 2.6575.89 ± 5.4327.46 ± 4.850.065 ± 0.00858.55 ± 0.83
HumLoc65.1752.2866.020.16167.87
EukLoc45.1967.0544.410.10159.97

Positive Δα\Delta_\alpha and Affinity AUC above 50% across all six datasets can support directional separation. The satisfaction curves directly quantify the empirical coverage of the matching-margin condition, while the Full–Uniform ablation (Fig. 5(a)) demonstrates the predictive benefit of pair-specific matching. Appendix A.1.2 further derives sufficient conditions for this matching behavior.

Q2: Baseline Selection for Label-Split Evaluation.

A2: Tab. 2 presents strong representatives of two relevant method families: CorGCN and LIP-GCN for MLNC, and H2GCN and GPR-GNN for heterophily-oriented learning. These four methods are included in the main text due to space constraints. Appendix A.3.3 (Tab. 10) reports the whole label-split results for all twelve baselines under the same evaluation protocol. PHeLP's performance advantage is maintained in this complete comparison.

DatasetBest BaselineMacro AUCBest PHeLP VariantMacro AUC
DBLPGPR-GNN96.96 ± 0.07PHeLP-GPRGNN97.68 ± 0.21
BlogCatGPR-GNN74.20 ± 0.69PHeLP-GPRGNN75.16 ± 0.42
DelveGPR-GNN98.54 ± 0.04PHeLP-GPRGNN98.68 ± 0.12
PCGLIP-GCN63.60 ± 0.68PHeLP-GraphConv63.91 ± 0.32
HumLocVariMul74.86 ± 1.87PHeLP-GraphConv79.90 ± 1.95
EukLocVariMul76.39 ± 1.56PHeLP-GraphConv77.81 ± 1.29
AuthorsOpenReview ↗

Author Response (Part 2/2)

Q3: Label Grouping and Emb./Rel. Configuration Selection.

A3: Thank you for pointing this out. We clarify both aspects below.

1) Label grouping. We independently apply relation-guided greedy grouping to affinity and repulsion profiles. Each branch uses G=min⁡(K,C)G=\min(K,C) groups, where CC is the number of classes and K=5K=5 is the default group budget, fixed across datasets. The GG most frequent training labels initialize separate groups. Each remaining label is assigned to the group maximizing its average cosine similarity to existing members, with deterministic penalties for group size and group index. Similarities involving zero relation profiles are set to zero. The complete procedure is provided in Algorithm 2 (Appendix A.2.1):

Algorithm 2: Relation-Guided Label Grouping

Input: Training-label matrix Ytr\mathbf{Y}^{\mathrm{tr}}, relation profiles scr\mathbf{s}_c^r for each label cc and branch rr (affinity or repulsion), and group budget K=5K=5.

Output: Branch-specific group assignments grp⁡r(c)\operatorname{grp}_r(c) for all labels.

Step 1: Initialization

  • Set G←min⁡(K,C)G\gets\min(K,C).
  • Compute training-label frequencies nc←∑iYictrn_c\gets\sum_i Y_{ic}^{\mathrm{tr}} for each label cc.
  • Sort labels by decreasing ncn_c (ties by label index) to obtain order\mathrm{order}.
  • Set λs←10−6\lambda_s\gets10^{-6} and λg←10−9\lambda_g\gets10^{-9}.

Step 2: Relation-Guided Greedy Grouping

Repeat the following procedure independently for affinity and repulsion.

  • Compute the relation-profile cosine similarity matrix Simr\mathbf{Sim}^r.
  • Set Simcdr=0\mathrm{Sim}_{cd}^r=0 if c=dc=d or either profile is zero.
  • Initialize each group Cgr\mathcal{C}_g^r with label order[g+1]\mathrm{order}[g+1], for g=0,…,G−1g=0,\ldots,G-1.

For each remaining label, indexed by j=G+1,…,Cj=G+1,\ldots,C:

  • Select c←order[j]c\gets\mathrm{order}[j].
  • For each group g=0,…,G−1g=0,\ldots,G-1, compute the average similarity avg⁡gr←∑d∈CgrSimcdr∣Cgr∣\operatorname{avg}_g^r\gets\frac{\sum_{d\in\mathcal{C}_g^r}\mathrm{Sim}_{cd}^r}{|\mathcal{C}_g^r|}.
  • Compute the assignment score score⁡gr←avg⁡gr−λs∣Cgr∣−λgg\operatorname{score}_g^r\gets\operatorname{avg}_g^r-\lambda_s|\mathcal{C}_g^r|-\lambda_g g.
  • Select g∗←min⁡(arg⁡max⁡gscore⁡gr)g^*\gets\min(\arg\max_g\operatorname{score}_g^r).
  • Add label cc to the selected group Cg∗r\mathcal{C}_{g^*}^r.

After processing all labels, record grp⁡r(c)←g\operatorname{grp}_r(c)\gets g for each label cc assigned to group gg.

Step 3: Return

Return the recorded group assignments for both affinity and repulsion branches.

2) Emb. and Rel. configurations. We select the Emb./Rel. configurations based on validation Macro AUC. The selected configurations are Rel. for DBLP, Emb. for HumLoc, and Emb.+Rel. for EukLoc. The corresponding results are reported in Appendix A.3.7 (Table 16).

We hope these results and clarifications address your concerns.

Thank you again for your time and thoughtful consideration.

Best regards,

The authors of submission 26213

Dear Reviewer,

I hope this message finds you well. As the discussion period ends in less than three days, I wanted to ensure we have addressed all your concerns satisfactorily. If there are any additional points or feedback you'd like us to consider, please let us know. Your insights are invaluable to us, and we're eager to address any remaining issues to improve our work.

Thank you for your time and effort in reviewing our paper.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Author Final Remarks

Dear Reviewers, ACs, SACs, and PCs,

We sincerely appreciate your time and effort in evaluating our paper.


We are grateful to the reviewers for recognizing the value of our work in the following aspects:

  • Meaningful Problem (Reviewer 3qiC): Addressing the important challenge of label-dependent heterophily in multi-label node classification.

  • Targeted Methodology (Reviewers uxPy, yXgs): Providing a reasonable modeling approach and an interesting pairwise prompting design.

  • Strong Empirical Evidence (Reviewers uxPy, 3qiC): Demonstrating competitive performance through comprehensive evaluations and ablation studies.


In the rebuttal, we have provided the following clarifications and additional results.

Clarifications on Paper Details

  • Methodological Novelty (Reviewers 3qiC(W1), yXgs(W2)): Clarifying PHeLP's positioning, distinctive contributions, and key differences from existing methods.
  • Theoretical Justification (Reviewers 3qiC(W2, Q3–Q4), uxPy(W1, Q1)): Clarifying the risk implications of Theorem 1 and the theoretical justification for Theorem 2.
  • Implementation Details (Reviewers uxPy(W2, Q3), yXgs(W3)): Clarifying label grouping, semantic configurations, and safeguards against label leakage.

Additional Experimental Results

  • New Dataset (Reviewer 3qiC(W3, Q5)): Demonstrating PHeLP's effectiveness on PPI, which combines strong heterophily with substantial multi-label characteristics.
  • New Baselines (Reviewer yXgs(W1)): Demonstrating consistent improvements over well-tuned classical GNNs.
  • Expanded Label-split Evaluation (Reviewer uxPy(Q2)): Demonstrating PHeLP's advantages against the complete set of twelve baselines.
  • Fine-grained Ablation Studies (Reviewers 3qiC(W3, Q1–Q2, Q6), yXgs(W2)): Demonstrating the effectiveness of individual components and design choices.
  • High-degree Label Analysis (Reviewer 3qiC(Q1)): Demonstrating PHeLP's effectiveness on high-degree label nodes.
  • Matching-margin Diagnostics (Reviewers uxPy(W1, Q1), 3qiC(W2, Q4)): Providing empirical support for the matching-margin assumption.

We greatly appreciate the reviewers' valuable suggestions, which have undoubtedly strengthened this work. We have incorporated the reviewers' valuable suggestions into the revised manuscript and will continue to refine it based on further feedback.

We respectfully request your feedback again and sincerely invite you to review our responses to the other reviewers as well. We have dedicated over 60 hours to preparing this rebuttal, and we truly hope our responses address your concerns. If you have any further questions or concerns, we would be glad to address them.


Thank you once again for your time and thoughtful consideration.

Best regards,

The Authors of Submission 26213

Dear Reviewers,

Thank you for your time and effort in reviewing this paper. The authors have posted responses to your reviews. If you have not yet done so, please read their responses and leave a follow-up comment visible to the authors, indicating which concerns have been addressed and which remain unresolved.

Please also update your review and rating if your assessment has changed. Your feedback will help the authors address any remaining questions during the discussion period.

Thank you!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.