- 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
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.
| Method | HumLoc | PCG | BlogCat | EukLoc | DBLP |
|---|---|---|---|---|---|
| Statistics-MLP | 75.09±0.72 | 59.80±1.31 | 72.80±0.93 | 73.60±1.17 | 96.18±0.11 |
| Single-branch | 76.22±0.45 | 62.28±1.24 | 64.25±10.75 | 76.12±0.73 | 95.75±0.22 |
| Affinity-only | 75.85±0.18 | 62.40±0.90 | 64.27±10.72 | 76.30±1.04 | 95.81±0.18 |
| Repulsion-only | 75.89±0.86 | 62.68±0.87 | 64.36±10.85 | 74.88±1.77 | 95.74±0.18 |
| Full PHeLP | 77.01±0.72 | 64.74±0.87 | 74.29±0.47 | 76.56±0.25 | 96.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.
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
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:
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).
[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.