GraphTOP: Graph Topology-Oriented Prompting for Graph Neural Networks

We thank the reviewer for providing valuable comments. We hope our point-by-point responses can fully address all your concerns.

• W1&Q1: How does GraphTOP perform on synthetic datasets? When scaling to larger graphs (exceeding 100,000 nodes), can it maintain a reasonable balance between model effectiveness and computational efficiency?
• A1: Thanks for bringing this up. We conduct experiments on a synthetic graph based on the CSBM and provide the results under SimGRACE and LP-GPPT as follows.

Additionally, we conduct experiments on ogbn-arxiv with ~170K nodes and provide the results under GraphCL and LP-GraphPrompt as follows.

• W2&Q2: The proof in Section 5.2 regarding edge rewiring's effect on inter-class distance expansion relies on linear additivity assumptions. While the authors have noted potential issues under nonlinear conditions with dynamic edge weights, could supplementary theoretical or experimental analysis be provided for nonlinear GCNs (e.g., GAT)?
• A2: Thanks for bringing this up. Our theoretical analysis follows classical studies [1, 2] analyzing linear separability under GNNs using linear GCNs because GCNs are the most popular GNNs in graph learning. We will analyze other complex GNNs (e.g., GAT) in our future work.

• Q3: The selection of parameters $\lambda_1$ and $\lambda_2$ shows significant impact on results. Could more robust optimization strategies be proposed?
• A3: Thanks for bringing this up. In our experiments, we conduct grid search on different values of $\lambda_1$ and $\lambda_2$. Their optimal values could vary across datasets and pre-training methods. More robust optimization strategies, such as Bayesian Optimization and Hyperband [3] , could be used for hyperparameter selection.

[1] Ma, Yao, et al. Is Homophily a Necessity for Graph Neural Networks? ICLR 2022.
[2] Baranwal, Aseem, Kimon Fountoulakis, and Aukosh Jagannath. Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization. ICML 2021.
[3] Li, Liam, et al. Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization. JMLR 2018.

We thank the reviewer for providing constructive comments. We hope our point-by-point responses can fully address all your concerns.

• C1&Q1: Assuming that the topological challenge is reasonable enough, in many graphs (such as chemical molecules and transportation networks), the existence of edges is determined a priori, and modifying the adjacency matrix may introduce unreasonable pseudo-structures.
• R1: Thanks for pointing out this insightful question. We agree that topology-oriented prompting will learn the modified adjacency matrix involving pseudo-structures. However, we would like to emphasize that the goal of topology-oriented prompting is to enhance model utility of a pre-trained GNN model for downstream tasks. As a result, the modified adjacency matrix will be more suitable for the pre-trained GNN model, although it may be different from the original one. Similarly, the modified node features by feature-oriented prompting may also include pseudo-features (e.g., the age feature is modified to a negative value). We thank the reviewer for bringing up how to understand the modified data by prompting methods, which is very intriguing but has not been well investigated yet. We think it is also an open question in other fields, i.e., the meaning of prompt tokens in NLP [1] and the meaning of prompt patches in CV [2].

• C2: The experimental tasks are single and all focus on node classification.
• R2: Thanks for pointing it out. We would like to clarify that this paper mainly focuses on node classification as the downstream task. As indicated in Appendix D, the proposed method can be extended to graph-level tasks, which are kept as our future work.

• C3&Q2: Some similar methods may be considered as baselines to compare, or for moderate discussion to distinguish them, such as Graph Structure Learning methods.
• R3: Thanks for bringing this up. We agree that graph structure learning also learns to modify graph structures. However, graph structure learning follows an end-to-end manner by training GNN models via supervised learning. This assumption is fundamentally different from graph prompting where GNN models are pre-trained via unsupervised learning and kept frozen during adaptation. Therefore, we argue that graph structure learning methods are not appropriate baselines in the experiments.

• C4&Q3: Regarding the experiments with different numbers of shots, some comparisons are missing, and the experiments in the appendix did not control the pre-training method to remain consistent.
• R4: Thanks for bringing this up. We would like to clarify that the experiments with different numbers of shots do not aim to compare the performance of one graph prompting method with different numbers of shots. Instead, we are comparing the performance of different graph prompting methods in the same condition (the same pre-trained GNN model and the same number of shots). We use different pre-training strategies here because we hope to provide results in more conditions.

[1] Zhou, Kaiyang, et al. Learning to Prompt for Vision-Language Models. IJCV 2022.
[2] Jia, Menglin, et al. Visual Prompt Tuning. ECCV 2022.

Dear Reviewer JEMG,

Thanks a lot for your reply. We would like to respectfully argue that there might be a misunderstanding in your concern about potential violations of domain priors by graph prompting. We provide the following explanation to clarify this.

We first would like to make a clear statement that mainstream prompting methods are indeed designed for learning to modify the input data that does not exist in practice, even though the modified data may violate domain priors.

Let's consider representative graph prompting methods, e.g., All-in-one [1] and GPF [2]. When we apply them to graph data (e.g., molecular graphs), they will yield atoms and molecules that do not exist in the real world. For example, All-in-one [1] generates prompted graphs by learning extra prompt nodes added to the original graphs. Typically, each prompt node cannot be mapped to a specific atom. Therefore, the prompted graph by graph prompting methods [1, 2] cannot represent a real chemical molecule (i.e., domain priors).

Moreover, we can get the same conclusion in classic prompting methods from NLP [3] and CV [4]. For example, CoOp [3] learns extra prompt tokens that are concatenated with the original tokens. While the original tokens represent specific words, the prompt tokens are not able be mapped to words in natural language. As a result, CoOp [3] will generate the modified sentences that are not linguistically reasonable or consistent with domain priors in natural language.

In a nutshell, we believe that your concern about violating domain priors should not be viewed as a weakness of our method. We hope our clarification can fully address your concern. We are happy to provide more explanation if you have any further questions.

Best,
Submission9678 Authors

[1] Sun, Xiangguo, et al. All in one: Multi-task prompting for graph neural networks. KDD 2023.
[2] Fang, Taoran, et al. Universal Prompt Tuning for Graph Neural Networks. NeurIPS 2023.
[3] Zhou, Kaiyang, et al. Learning to Prompt for Vision-Language Models. IJCV 2022.
[4] Jia, Menglin, et al. Visual Prompt Tuning. ECCV 2022.

Dear Reviewer JEMG,

As the discussion period is ending within 19 hours, we are eager to know whether your concern has been addressed. We think there might be a misunderstanding on how we understand prompt tuning. We look forward to your feedback and are more than happy to answer any further questions.

Best,
Submission9678 Authors

We thank the reviewer for providing valuable comments. We hope our point-by-point responses can fully address all your concerns.

• W1: Missing related work - This work (https://arxiv.org/pdf/2503.00750) is graph prompting from edge perspective and should be somewhat related.
• R1: Thanks for bringing our attention to this excellent work. We will include it in the revised version of our paper.

• W2: Writing could be improved - the current writing is not easy-to-follow, the paper is presented in a dense and notation-heavy manner, adding some illustrative figure could help.
• R2: Thanks for pointing it out. We will try to add some illustrative figures to make the paper more readable.

• Q1: Is this topology-based prompt compatible with existing feature-based prompt? any chance they could be combined to make further improvement?
• A1: Thanks for bringing this up. Yes, they are compatible and could be combined. It is definitely a promising scheme to combine them for further improvement. We will explore this in our future work.

• Q2: Is there any visualized example to illustrate a subgraph before/after re-wiring?
• A2: Thanks for pointing it out. Since we are not allowed to provide figures during rebuttal, we will try to perform the case study in the revised version of our paper.

We thank the reviewer for providing valuable comments. We hope our point-by-point responses can fully address all your concerns.

• W1: It has been shown that a standard GNN (such as that in Eq. 1) cannot solve link prediction tasks (Zhang et al 2021). Therefore, using a standard GNN for "pre-training, adaptation" when pre-training is link prediction is not ideal, as it will not be able to perform the pre-training task well. I think you either should not consider link prediction as pre-training task (either remove it from the paper or move it to the appendix clarifying why theoretically is not a good strategy given the model) or change the GNN model, as shown in Bevilacqua et al., 2025.

• R1: Thanks for bringing this up. We would like to argue that designing effective pre-training strategies for training powerful GNNs is still an ongoing probelm in graph learning. Although choosing a better pre-training strategy can yield more powerful GNN models, it is outside the scope of this study: we are aiming to obtain the best performance on downstream tasks given a pre-trained GNN model no matter how it is pre-trained. While link prediction may not be the best pre-training strategy, many graph prompting methods [1, 2, 3] adopt link prediction as their pre-training strategies. Additionally, one recent study [4] discusses when to use link prediction or contrastive learning for pre-training. We will discuss this in the revised version of our paper.

• W2: The evaluation section is weak. The considered datasets are small and outdated. I would recommend to include the ogb datasets (arxiv, proteins, products).
• R2: Thanks for bringing this up. We conduct experiments on ogbn-arxiv and provide the results under GraphCL and LP-GraphPrompt as follows.

• Q1: Please connect your subgraph-constrained topology-oriented prompting with the line of work of Subgraph GNNs, which also represents related work. See for instance Southern et al., 2025 and all works therein.

• A1: Thanks for bringing this up. We will include related works of subgraph GNNs in the revised version of our paper.

[1] Liu, Zemin, et al. GraphPrompt: Unifying Pre-Training and Downstream Tasks for Graph Neural Networks. WWW 2023.
[2] Yu, Xingtong, et al. Generalized Graph Prompt: Toward a Unification of Pre-Training and Downstream Tasks on Graphs. TKDE 2024.
[3] Sun, Mingchen, et al. GPPT: Graph Pre-training and Prompt Tuning to Generalize Graph Neural Networks. KDD 2022.
[4] Yu, Xingtong, et al. Non-Homophilic Graph Pre-Training and Prompt Learning. KDD 2025.