GraphTOP: Graph Topology-Oriented Prompting for Graph Neural Networks
Authors: Xingbo Fu
Zhenyu Lei
Zihan Chen
Binchi Zhang
Chuxu Zhang
Jundong Li
Venue: NeurIPS 2025 poster ()
Keywords: Graph Neural Networks
Prompt Learning
Primary area: deep_learning
TL;DR: A graph topology-oriented prompting framework

Abstract: Graph Neural Networks (GNNs) have revolutionized the field of graph learning by learning expressive graph representations from massive graph data.
As a common pattern to train powerful GNNs, the "pre-training, adaptation" scheme first pre-trains GNNs over unlabeled graph data and subsequently adapts them to specific downstream tasks. In the adaptation phase, graph prompting is an effective strategy that modifies input graph data with learnable prompts while keeping pre-trained GNN models frozen. Typically, existing graph prompting studies mainly focus on *feature-oriented* methods that apply graph prompts to node features or hidden representations. However, these studies often achieve suboptimal performance, as they consistently overlook the potential of *topology-oriented* prompting, which adapts pre-trained GNNs by modifying the graph topology. In this study, we conduct a pioneering investigation of graph prompting in terms of graph topology. We propose the first **Graph** **T**opology-**O**riented **P**rompting (GraphTOP) framework to effectively adapt pre-trained GNN models for downstream tasks. More specifically, we reformulate topology-oriented prompting as an edge rewiring problem within multi-hop local subgraphs and relax it into the continuous probability space through reparameterization while ensuring tight relaxation and preserving graph sparsity. Extensive experiments on five graph datasets under four pre-training strategies demonstrate that our proposed GraphTOP outshines six baselines on multiple node classification datasets. Our code is available at https://github.com/xbfu/GraphTOP.

GraphTOP: Graph Topology-Oriented Prompting for Graph Neural Networks
Xingbo Fu University of Virginia Charlottesville, VA, USA xf3av@virginia.cm edu
Zhenyu Lei University of Virginia Charlottesville, VA, USA vjd5zr@virginia.cm edu
Zihan Chen University of Virginia Charlottesville, VA, USA brf3rx@virginia.c edu
Binchi Zhang University of Virginia Charlottesville, VA, USA epb6guóvirginia. edu
Chuxu Zhang University of Connecticut Storts, CT, USA chuxu www.g@uconn.nn..... edu
Jundong Li University Virginia Charlotteswilll, VA, USA jundongövirginia edu
Abstract
Graph Neural Networks (GNNs) have revolutionized the field of graph learning by learning expressive graph representations from massive graph data. As a common pattern to train powerful GNNs, the "pre-training. adaptation" scheme first pre-trains GNNs over unlabeled graph data and subsequently adapts them specific downstream tasks. In the adaptation phase, graph prompting is an effective strategy that modifies input graph data with learnable prompts while keeping pre-trained GNN models frozen. Typically, existing graph prompting studies mainly focus on feature-orienter methods that apply graph prompts to node features hidden representations. However, these studies often achieve suboptimal performance. as they consistently overlook the potential of topology- oriented prompting, which adapts pre-trained GNNs by modifying the graph topology. In this study, we conduct pioneering investigation of graph prompting in terms of graph topology. We propose the first Graph Popology-Orientee Prompting (GraphTOP) framework to effectively adapt pre-trained GNN models for downstream tasks. More specifically, we reformulate topology-orienter prompting as an edge rewiring problem within multi-hop local subgraphs and relax it into the continuous probability space through reparameterization while ensuring tight relaxation and preserving graph sparsity. Extensive experiments on five graph datasets under four pre- pre-training strategies demonstrate that our proposed GraphTOP outshines six baselines on multiple node classification datasets. Our code is available httpt::///// :/ //t/t/gitttt tituu...... com/ xbfu/GraphTOP
Introduction
Graphs are ubiquitous in a wide range of real-world scenarios, such as social networks 45 knowledge graphs [41], traffic networks [32] and healthcare [ 77 To gain deep insights from tremendous graph data, numerous graph learning models have been developed in recent years. Among these efforts. Graph Neural Networks (GNNs)
23
33
38
46 are prevalent
tool for modeling graph data and have shown great prowess in different graph-related downstream tasks, including node classification 128 (56). link prediction [] 62). and graph classification 25 63 Traditionally, GNN models are trained in supervised manner. However, the supervised manner relies heavily sufficient labeled graph data, which may be infeasible in the real world. Furthermore, the trained GNN models cannot be well generalized to other downstream tasks, even on the same graph data. These two critical issues hinder further deployments of GNN models in practice.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

To address the above issues, the "pre-training adaptation" scheme has been widely adopted by a comuucopi of studies [ 13
57 8). Typically, they first train GNN models on pre-training tasks in an unsupervised manner, followed by adapting the pre-trained GNN models to specific downstream tasks. For instance, a GNN model can be pre-trained via link prediction and later adapted for node classification as the downstream task. During the adaptation phase, the goal is to bridge the objective gap between pre-training and downstream tasks. Inspired by recent prompt tuning approaches in natural language processing [21 588 and computer vision [18 48), graph prompting [9] has become an effective adaptation strategy to adapt pre-trained GNN models for downstream tasks by modifying the input graph data with trainable prompt vectors while keeping the pre-trained GNN models frozen. Generally, the existing graph prompting methods are feature- oriented they design and learn graph prompts mainly by applying them to node features [ 36 or
36 52
hidden representations 27 51 52
While the feature-oriented design is intuitive in graph prompting methods, they mostly overlook graph topology another essential component in graphs that fundamentally distinguishes graph data from image data and text data when designing graph prompts. Notably, graph representations are not only dependent on feature information but also determined by graph topology. Numerous efforts have demonstrated the significant impact of graph structures on graph-related tasks, particularly node classification 66 20 26, 37 55). Unfortunately. the potential of topology-oriens oriented prompting for tre-trained GNN models remains unexplored in existing studies. Therefore. it is natural to pose the question: How should we design a topology-orienes prompting framework to effectively adapt a pre-trained GNN model for downstream tasks?
To answer this question, we conduct the pioneering investigation of graph prompting in terms of graph topology. We propose GraphTOP the first Graph Topology-Orientes Prompting framework to adapt pre-trained GNN models for downstream tasks, particularly for node classification. In TraphTOP, we formulate topology-oriented prompting into the continuous probability space via reparameterization. To ensure computational feasibility in practice, we propose subgraph-constrainee topology-orientes prompting by restricting edge rewiring between each target node and other nodes within its multi-hop subgraphs. In the end, we design the optimization objective of GraphTOP to ensure tight relaxation and maintain graph sparsity. Our theoretical analysis indicates that topology-oriene GNN models for node classification. We conduct comprehensive experiments over five datasets under four pre-training strategies to evaluate the performance of our proposed method. The experimental results validate the superiority of GraphTOP against six baselines.
edge rewiring problem and relax it
prompting can effectively enhance the pre-trained
We summarize the main contributions as follows:
Problem formulation. We formulate and conduct an initial investigation of graph prompting
from the perspective of graph topology.
Algorithmic design. We propose GraphTOP, the first work adapt pre-trained GNN models by modifying graph topology of the input graph.
oriented prompting frame-
Theoretical analysis. We provide theoretical analysis to support that our design of topology- oriented prompting in GraphTOP can effectively enhance pre-trained GNN models for node classification.
Experimental evaluation. We conduct comprehensive experiments on five public datasets under four pre-training strategies. Experimental results validate the effectiveness of our proposed GraphTOP against six baselines for node classification.
2
Related works
2.1 Graph pre-training
Graph pre-training aims to train powerful GNN models over unlabeled graph data in a self-supervised fashion [44]. Generally, graph pre-training methods can be roughly categorized into two types:
contrast-based methods and generation- based methods. Contrast-based methods 33 39
45
49
54
are developed based on the concept of mutual information (MI) maximization, where the estimated
MI between different views of similar objects is maximized. For example, DGI [39] maximizes MI
between the local and global instance views. SimGRACE (55 constructs contrastive views from

---

the perturbed version of GNN models. Generation-bed based methods 14 27 33 35 focus on reconstructing specific information from graph data, such as graph structure and node features. For instance, GraphMAF [12] pre-trains GNN models by reconstructing masked node features. also adopt link prediction as the pre-training
Meanwhile, previous graph prompting studies 22 35 strategy.
2.2
Graph prompting
Graph prompting adapts pre- preitrained GNN models to close the objective gap between pre-training and downstream tasks. The intuition is to modify the input graph with learnable prompt vectors for downstream tasks without tuning the pre-trained GNN models. For example, GPPT 35 pre-trains a GNN model via link prediction and adapts it for node classification as the downstream task. It bridges the objective gap between link prediction and node classification by converting node classification to link prediction. GraphPrompt [27] and its variant GraphPrompt+ (50) design prompt vectors as feature weights and apply them to node (hidden) representations. GPF-plus [5] mainly focuses on graph classification as the downstream task and learns to manipulate the input graph by adding extra learnable prompt vectors to node features. All-in-one (36) unifies various downstream tasks as graph- level tasks and similarly designs prompt vectors to modify node features. MultiGPrompt [52] instead inserts prompt vectors into node representations at each hidden layer. ProNoG [51] investigates prompt design for non-homophilic graphs and learns prompt vectors feature weights based on subgraph representations. While the above graph prompting methods have demonstrated remarkable performance in adapting pre-trained GNN models, they are largely feature-oriented and consistently overlook the potential of ropology-oriented prompting design.
3 Preliminaries
3.1 Graph neural networks
An attributed graph can be denoted as G = E) where V = {ui, U2, ,0n] } is the set of n nodes and & C x V is the edge set. It can also be represented as G = (). Here, A E 10 1 denotes the adjacency matrix where dij = 1 iff uz) E E. X Raxds denotes the feature matrix where the i-th row æ; E IRd2 is the dz-dimensional feature vector of node i; E V. A (o:) denotes the set of node v, neighboring nodes. GNN models leverage node features and graph structure to learn a di dimeensioon representation vector h2 E Rdd for each target node i; E V. Generally, GNN models follow the gressage-passingg mechanism, in which the representation of node e; is iteratively updated by aggregating the representations from its neighboring nodes. More concretely, a GNN model I updates the representation of node us V at layer by
m AGGREGATE ({ ((n 0. E (w:))) A COMBINE (N (1( m
(I)
where h Rd denotes the di-dimensional representation of node at layer I, and we initialize h (0) x, AGGREGATE() (-) represents the aggregation operation extracting the neighboring infor- mation of node v,, and COMBINE()) (.) represents the combination operation integrating the previous representation of node and its neighboring information at layer l. The ultimate representation h; of node v after the final layer of the GNN model can be used for diverse downstream tasks. this study, we focus on node-level downstream tasks, particularly node classification, i.e., predicting the class label y/ of each target node G.
3.2 Graph prompting
In this study, we mainly center on graph prompting for node-level downstream tasks, e.g., node classification. Given a GNN model pre-trained by a pre-training task, graph prompting aims to adapt the pre-trained GNN model for node classification by learning graph transformation with trainable prompts to modify the input graph without tuning the pre-trained GNN model. Let fe- denote the pre-trained GNN model with parameters 0", Given the input graph G with labeled node list Vr. C V. the graph transformation ls transforms it to a prompted graph ς (g(l) where á contains learnable prompt parameters. By tuning the prompt parameters in Φ, the pre-trained GNN model fo- can generate suitable node representations for node classification through a trainable
3

---

classifier parameterized by w. Mathematically, we can train @ and w by optimizing the empirical loss minimization problem of graph prompting defined as
1
Σ e (ow ( (9)1) OVEV
min Lp (), 6,
= [VE
(2)
where ((:))) denotes the cross-entropy loss for node classification. The main goal of graph prompting figure out the optimal graph transformation bg for downstream tasks.
4 Methodology
In this section, we present GraphTOP - graph topology-oriente prompting framework that adapts pre-trained GNN models for node classification by learning modify graph topology while keeping the pre-trained GNN models frozen. We begin by formulating topology-oriented prompting as an edge rewiring problem. Then, we relax this problem into the continuous probability space via reparameterization and optimize the probabilities through a shared trainable projector. To reduce complexity, we restrict the edge rewiring problem multi-hop hop local subgraphs. Finally, we present the complete optimization objective in GraphTOP, designed to ensure tight relaxation and preserve graph sparsity.
4.1 Topology-orients prompting
Graph prompting learns to transform the input graph 9 = (A, X) to prompted one J. Ideally, the prompted graph & can generate informative node representations through the pre-trained GNN model fo- and is more suitable for downstream tasks, such as node classification. Unlike previous feature-oriented graph prompting studies [5] 33) that aim to transform the input graph with learnable prompt vectors applied to node features (i.e., X), topology-orientee
prompting designs learnable prompts manipulate graph topology (i.e., A). As a result, we will obtain the prompted graph ğ (S, X) with the prompted graph topology S (0,1)
To achieve this, we formulate topology-oriented prompting as an edge rewiring problem. Specifically, given each pair of nodes v; E V and t;j E V (u, # vyy) the goal is to obtain a learnable binary edge selector 8ij E S that determines whether an edge exists between them. other words, edge (v,, új) belongs to the prompted edge set iff stj 1. Mathematically, we can reformulate the problem of graph prompting in Equation (2) as
min Lp (S, w) 8,00
Σ V,EV,
e (sw (wo- (S,X))) .8), s.t. S E (0,1)=xm.
VE
(3)
4.2 Prompt reparameterization
Solving the problem in Equation (3) is challenging since the loss function is discrete with respect to binary edge selectors in S, making it intractable and difficult to apply in practice. In this study, propose to address this issue through edge rewiring reparameterization When treat the edge selectors S as binary random variables and reparameterize the problem in Equation (3) with respect to their distributions, it can be relaxed into expected loss minimization problem over the classifier weight and probability spaces, which is continuous. More concretely, we treat each edge selector Sij S as Bernoulli random variable following the Bernoulli distribution with probability Pij- During the forward pass, each edge selector stj is sampled from the Bernoulli distribution with probability Pig to be I and Piy be O. Let P represent the probability matrix. The problem of topology-oriented prompting in Equation 3 can be relaxed into the expected loss minimization problem
min (S P.
(S)(S,))) s.t. P E [0, 1
(4)
Therefore, we reformulate the edge rewiring problem as a continuous problem in Equation
However, solving the above problem via gradient descent remains challenging. The difficulty lies in computing the gradient of the expected loss with respect to the probability matrix P, as Bernoulli sampling is non-differentiable. To make the probability matrix trainable, we propose to reparameterize the Bernoulli sampling in graph prompting via Gumbel-Softmn reparameterization 30 59 60) Before introducing this, we first present the following theorem.

---

Theorem 1. Given two random variables G1 and G2 that follow the Gumbel distribution
Gumbel(0, 1). for any probability Pij E P. we have
Pr G1 - G2 + log
Pij
2 20 Pij-
(5)
Pij
The proof of Theorem D is provided in Appendix A
Recall that the probability that each edge selector Sij is equal to 1 is also Pij. Therefore, we can rewrite the expected loss function in Equation as
Ecg,o CP (1 (1(Gi-O
220 w
log
Inxn Inxn (
(6)
where I(-) is the indicator function, and Inxn is an n-by-n all-ones matrix. G, E R and G2 Ruxn are random matrices where each entry follows the Gumbel distribution Gumbel (0, 1).
Nevertheless, the rewritten expected loss discrete due to the indicator function. common solution to this issue is to approximate the expected loss by replacing the indicator function with sigmoid function. Specifically, the expected loss can be approximated as
G1
G2 + log (mxx--))
Eg, G2
Lp
(7)
7
where (-) is the element-wise sigmoid function, and T is the temperature annealing parameter that decreases linearly, facilitating the transition from probabilistic approximations to pear-deterministic outputs during training.
The final task is the computation of P. Instead of learning each individual probability in P as free parameters- - which is usually hard to train, we propose to obtain the probabilities through learnable projector shared by nodes. As the GNN model has been well pre-trained, informative node representations from the pre-trained GNN model as the input of the projector. Given the representation matrix H Raxd, where the i-th row h, is the representation vector of node us we obtain P through a learnable projector m based on H, i.e., P = m mH). Specifically, given two nodes U, and vy with their representations h; and hj. the projector computes the probability Piy by
consider using the
Piy = (Wa (ReLU (W1 (h: + h,)))),
(8)
where W and W2 are trainable weights in the projector m. Note that the projector will generate Pij Pjú. which consistent with undirected graphs. The integration strategy of h, and h2 in m can be altered (e.g., concatenation) to handle directed graphs. Therefore, the final problem of topology-oriente prompting can be formulated as
[1 - 82 + log Inxa
(II)
min Lp (b.w) 6.w
1
Σ REV.
é (6 (Lso (S,)))., where =
VV
Here, Φ (W1, Wo} represents the prompt parameters that we aim to learn. gi g2 R are two matrices where each entry is sampled from Gumbel (0, 1) per iteration. Since the representation matrix H is generated by the pre-trained GNN model and fixed during training, we can compute before the adaptation phase to avoid additional computational costs.
R and
4.3 Subgraph--onstrranne topology-orientee prompting
Although the above formulation is feasible to solve, it still poses challenges in scalability. Since we need to learn an edge selector for each node pair, the number learnable edge selectors grows overwhelmingly large as the number of nodes in the input graph increases. In GraphTOP, we propose subgraph-constrainned topology-orienter prompting to reduce the complexity. In most GNN architectures, the representation of target node through a pre-trained GNN model primarily depends on its local subgraph [23] [5]]. Motivated by this, we consider restricting learning edge selectors for edge rewiring to multi-hop local subgraph of each target node. More concretely, we first extract the p-hop subgraph G(v)) (A (A(x),, X(v))) for each target node v,. Here, X(v:) includes the feature vectors of node and other nodes within p steps of node ei. and A A(v:) indicates the
connection between these nodes extracted from the original adjacency matrix A. p is a pre-defined
hyperparameter. Typically, set p 2 to balance efficiency and effectiivneess. Then, the task is
5

---

to perform edge rewiring to obtain the prompted subgraph ((;)) = (S(e;). ((;)) based on ((v)). Nonetheless, the computation is still expensive we consider edge connections between each pair of nodes in (v;). Theoretically, the computational cost is approximately O (22),, where D represents the average node degree.
To further reduce the computational cost of edge rewiring, we propose to rewire edges only between the target node and other nodes in (vx)). In this way, we only need to consider how the target node connects to other nodes while keeping other edges in the original subgraph G (vx) intact. As a result, the computational cost will significantly decrease, reducing to (DP)). More specifically, For each pair of nodes 1/ and Uy in the subgraph ((ve), we can compute 5 S(e;) by
9r 92 + log 1-P3A
if (uy,
8yk
(10)
ajks
otherwise,
where 91 and 92 two values sampled from Gumbel 1). Therefore, the objective function in Equation (9) can be reformulated as
Cp(d,w)
Σ v.VV
l (aw (Ifo- (S(u)).((<)))) u.)
[V2l
(11)
4.4 Prompt optimization
While the problem of topology-orienter prompting becomes solvable through the relaxation in Section 4.2. simply solving the problem in Equation (IT) cannot guarantee the tightness of the relaxation. Typically, is unlikely to obtain every probability Pij converging to 0 or I after training. As result, Bernoulli sampling may cause significant fluctuations in graph topology during inference, resulting in unstable classification performance. Therefore, the goal here is to encourage deterministic probabilities (i.e., either 1) during training. To achieve this, introduce extra entropy- based regularization term (Ø) in the objective function. The intuition of this regularization term is to penalize high-entropy probabilities via entropy minimization [TO]. Mathematically, the regularization term (Ø) can be written as
[V (W
(x( [v.
Σ WEVE
e(vs)) PGEN((O)
Σ
where e (Pt)) Psy log + (1 Pis) log(1 - -Pt))
(12)
Here, (1;) represents the set of nodes within node ws's p-hop subgraph except node u.. By minimizing Cx, each probability Psj will be likely to converge to 0 or I after training, leading to deterministic graph topology for inference. As result, the relaxation in Equation ( becomes tight.
Meanwhile, the prompted graph may become overly dense, resulting in almost fully connected graph topology. Such prompted graphs are often impractical for most applications and incur high computational costs [2] 20 26). Therefore, it is important control how sparse the prompted graph is. To achieve this, we introduce another regularization term Cs(() to constrain the size of connected edges in the prompted graph. More specifically, the regularization term L.s()) (d) can be formulated as
EnjEN, Pi
(Ø) = [V2
Σ
(13)
W.
LEVL
where y is hyperparameter to control the size of connected edges for each node. Finally, we can write the overall objective function
min (o,w,) + L)() + AgCs(Ø),
(14)
where X₁ and X are two hyperparameters to balance different loss terms.
5 Analysis of GraphTOP
In this section, we present a comprehensive analysis of our proposed framework. The overall algorithm of GraphTOP can be found in Appendix B

---

5.1 Complexity analysis
Without loss of generality, we take a Kllayer GCN model as an example for complexity analysis. When we set p 2, the representation of each target node is computed based on its 2-hop local subgraph. When the average node degree is D. the expected number of nodes within its 2-hop local subgraph is O Accordingly, the expected number of edges within its 2-hop local subgraph is O(D)). We assume each layer of the GCN model has the same hidden size as the feature matrix, i.e., dz dh dy for simplicity. In this case, the time complexity of the GCN model is d + KD The extra cost in GraphTOP comes from the computation of the probabilities when generating the prompted graph. The time complexity for computing the probabilities is OfD + did Therefore, we can conclude that computing the probabilities in GraphTOP does not introduce significant additional computational costs compared with GNN models.
5.2 Theoretical analysis
In this subsection, we provide theoretical analysis of how topology-oriented prompting in our GraphTOP benefits pre-trained GNN models for node classification. Following previous graph learning studies 29 40). our analysis is similarly based on the contextual stochastic block model (CSBM) 4. Given random graph 9 generated by the CSBM with two node classes ei and c2, node 0/ has the feature vector æ; following Gaussian distribution n; ~ N( I) if it from class d1 otherwise, ~ (H2, I). Here, we assume μ * 122 The edges in G are generated following an intra-class probability p > 0 and an inter-class probability q > In other words, each pair of nodes will be linked through edge with probability p if they are from the same class; otherwise, the probability g. We denote a random graph generated by the CSBM as CSBM( M4 P, 4).
We aim to analyze how our edge rewiring design in opplogy-oriented oriented prompting improves linear separability under pre-trained GNN models. Here. we consider 2-layer linear GCN models (23 for simplicity. We are particularly interested in the expected Euclidean distance between node representations of the two classes after 2-layer GCN operations. Let Dist' and Dist denote the expected Euclidean distances with or without our edge rewiring design, respectively. In GraphTOP, we have the following theorem.
Theorem 2. Given a pre-trained 2-layer linear GCN model fø- and a random graph G ~ CSBM(H 1 P22 P. q). when p + q, there always exists edge rewiring in the prompted graph by Graph- TOP that satisfies
p+ 9 Dist pp q
Dist'
Dist.
(15)
The proof of Theorem can be found in Appendix Theorem iidicates that the expected distance between the two class centroids can be enlarged effectively when GraphTOP alters how every target node connects to the other nodes within its multi-hop hop local subgraph. Under this circumstance, the representations of nodes from the two classes more likely to be correctly classified. Therefore, we conclude that our edge rewiring design in Graph can theoretically enhance the classification performance of pre-trained GNN models.
Experiments
6.1 Experimental setup
Datasets We adopt five roal-world graph datasets from various domains to evaluate the performance of our framework. These datasets include Cora [47], PubMed [47], Amazon [31], Minesweeper [3],
and Flickr [53]. Detailed information about these datasets can be found in Appendix E.T
Pre-training strategies To evaluate the compatibility our framework with different pre- pre-training strategies, we conduct experiments under four representative pre-training strategies. More specifically. we adopt GraphCL [4] and SimGRACE (45 for contrast-based methods. As for generation-
methods, we follow two previous studies GPPT 35 and GraphPrompt [27 to pre-train GNN
models via link prediction. We term them IPPGPPT and L.-GrrapPrrompt, respectively. More information about these pre-training strategies can be found in Appendix E.2
7

---

Table I: Accuracy 5-shot node classification five datasets. The best-performing method is bolded, and the runner-up up is underlined.
Pre-training
Graph prompting
Cora
PubMed
Amazon
Minesweeper
Fllckr
strategies
methods
Linear Probe
55.69
67.30 26.20
23.19 23..11
67.59
29.31
GPPT
61.50
65.75 25.3..9
24.27 23.77
65. 65.44.8.90
21.01
ALL-in-one
52.33 1.455
22, 22.82..6000
63. 22.2.2.
21.57 24.64
GruphC1.
GraphPrompt
1:12:3222
21.71 21.71:29.93
61.19 13.50
21.9223.72
GraphPrompt+
58.91 13.12
66.26 25.75
23.83 22.50
61.66 61.64.6630
24.4324..2
ProNoG
60.01 17.00
68.17 1.882
23.26 23.26_2..4 2..42
65.48
26.17
GraphTOP
63 4..44.4..1
68 2.4.18
27.43
68. 2.14
30.93-19.07
Linear Probe
40.68
54.50
24.58 14.58:44.38
60.58
26.78
GPPT
11.83144.7
52.25
24.27
59. 09..6224.44
22.11
ALL-in-ooe
41.11+44.2
51.45 51.45+4.77
22.66-3.56
58.11+a.0.
21.50++4.49
SimGRACE
GraphPrompt
47.02-+3.s7
55.74+6.50
21.24-22.78
58. 38.72+4.37
19.72:44.54
GraphPrompt+
51.26114.00
55.93
25.07 =5.07
60.76 60.7616.75
20.79
ProNoG
12.44.12..9
55.11 5..9
22.53
2.
25. 44444445
GraphTOP
50.57 +2.91
16 6.
25.67 4.8.44
61.25
27. 27.70.6.00
Linear
24.40
42.26 22..0
25.50.4.11
63.22 (3.2228.11
23.7624.30
GPPT
32.08 27
44.75
23.0002..00
63.44.8.28
22.41
ALL-in-one
26.07 26.
41.11:4.02
21.1923.00
59.97 4.667
18. 18.0994..30
LP-OPPT
GraphPrompt
30. 30.14
44.72=6.65
21.88 2..8
61.73
19.72
GrapPrrmppt+
33.42.1.91
45.17:1.91
24.34
61.15
21.02::4:22
ProNoG
33.71
46.07 12.002
21.39
66.11 4.20
24.08g44.10
GraphTOP
33.97.2.44
46 46.5211.11
32.41
66 (6..67.6
25. 25.9511311
Lincar Probe
50.15
66.26
25.00
65.90= 7.30
23.75=#3.26
GPPT
52.13
63.1618.22
25.38_2.77
62.53 12.533...
24.1613.88
49.42.9.77
64.73
21.37
58. 17.44443
10.9.2
I.P. .r..happProopp
GraphPrompi
14
68 08.161...23
22.76_9.81
58,01.3. 20
21.15
GraphPromph+
52.19 2..22
62.19-26770
24.44:11.81
61.78 28.23.99
21.48:24.00
ProNoG
52.49 $5.48
67. 22.02
23.79 22.02
88
21.74
GraphTOP
53.4424.72
68. 68.1428.44
27.07 27.07=55.44 5.884
67. 87.09:28.44
25.03-g3.a4
Baselines We include five state-of-the-art graph prompting methods as the baselines of our ex-
periments, including GPPT (35), All-in-one (36), GraphPrompt [27), GraphPrompt+ (50), and ProNoG [51). Additionally, we also report the performance of tuning linear probes as the classifier based on node representations from pre-trained GNN models without any graph prompting methods
(termed Linear Probe). More information on these baselines can be found in Appendix E.3
Implementation details We use a 2-layer GCN as the GNN model for each graph prompting method. The hidden size is 128. All the experimental results are based on the 5-shot setting. Each method trained using the Adam optimizer [22 with learning rate of 0.005. The number of epochs is set to 500 for graph prompting. We set = 0.5 in our experiments. We conduct a grid search for A and A2. The reported performance the average result of five runs with different random seeds.
6.2 Effectiveness evaluation
We first evaluate the overall performance of method and other baselines. Table I reports the average accuracies on 5-shot node classification over five datasets under four pre-training strategies. According the results in the table, we first observe that Linear Probe can achieve competitive performance in some cases, although it only trains a classifier during the adaptation phase. For example, it outperforms several baselines on Flickr across four pre-training strategies. Additionally, we observe that ProNoG is strong baseline compared to other graph prompting methods. It achieves the runner-up position in some cases, such as four datasets under GPPT Finally, it noteworthy that GraphTOP achieves the best performance in most cases compared to other baselines. More consistently
specifically, GraphTOP outperforms other baselines achieves the best performance on Amazon and Flickr across all four pre-training strategies. These observations validate the effectiveness GraphTOP in modifying graph topology to adapt pre-trained GNN models for node classification.
out of 20 experiments.

---

GraphToP
GraphTOP
GraphTop
GraphTOP
Pubdee
Amazon
Minesweepe per
Flickr
0.6 (a) SimGRACE
(a) Cora under SimGRACE
(b) PubMed under LP-GPPT
(b) LP.GrrphPrompt
Figure/ I: The distribution curves of pij by Graph- Figure 2: The average edge densities of target nodes by GraphTOP with and without Lg.
TOP with and without LE.
6.3 Analysis of GraphTOP
Analysis of LE The loss term LE ensures tight relaxation of GraphTOP by encouraging each probability to converge to or 1. To evaluate the effectiveness of LF, we conduct experiments on the probability distribution by GraphTOP and its variant without LF. Figure Trigure[Tillsstnnn Iillustrates the distribution curves of Pij by GraphTOP with and without Lg. Based on the distribution curves, we observe that the probabilities are not centered around 0 or I without Lg. Instead, may obtain many probabilities around 0.5. In this case, tight relaxation cannot be guaranteed in our reparameterization. However, when we keep LE in the objective function, the probabilities more likely to be close to 0 or 1, which validates the motivation of our design in GraphTOP.
Analysis of Ls In the objective function of GraphTOP, Ls is designed to control the number of neighboring nodes for each target node by restricting the sparsity of a target node to the threshold (we set y 0.5 in our experiments). Typically, the edge densities should be forced to y by the loss term Ls. To validate the effectiveness of Ls. we conduct experiments evaluating the edge densities of target nodes when removing Ls. Vigure[iiluutratee GraphTOP with and without Ls. From these bar figures, we observe that the average edge densities are consistently very high when we remove Ls from the objective function. means that each target node connects to almost all other nodes within its local subgraph, leading to overly dense graph topology. When we retain Ls in the objective function, we observe that the average densities by GraphTOP decrease significantly toward 0.5, thereby ensuring the sparsity of the prompted graph. Therefore, we can conclude that the loss term Ls can effectively avoid overly dense prompted graphs.
the average edge densities of target nodes by
Efficiency analysis In Section we restrict edge rewiring within the p-hop local subgraph of each target node. To further reduce the complexity, we propose to rewire edges only between each target node and other nodes within its multi-hop subgraph. To evaluate the efficiency improvement by our design in GraphTOP, we conduct experiments on the running time of GraphTOP and its variant with edge rewiring between each pair of nodes within multi-hop subgraph (i.e., GraphTOP,, all all_nndss) T shows the running time of the two methods when p = and p = 3. From the results in the ta- ble, we can observe that GraphTOP, all nodes requires much more time compared with GraphTOP. For in- stance, GraphTOP.,, all nodes needs 651.22 1.122 seconds to finish each experiment when p = 2, which is about 2.97x longer than GraphTOP. Furthermore, when we set p = 3, GraphTOP, all nodes will be out of GPU memory our server. In contrast, the running time of GraphTOP does not increase significantly. We observe similar patterns other datasets. These observations strongly support our design in Graph- TOP by rewiring edges only between each target node with other nodes within its local subgraph.
Table 2: Running time (seconds) of Graph- TOP and its variant over three datasets when and p = (OOM: out of GPU memory).
p
GraphTOP
GruphTOP, all modes
36.52
Cora
53.08
0OM
218.61
651.22
Amazon
252.21
00M
77.51 51
113.37
Minesweeper
78.65
199.48
More experimental results Due to the page limit, more experimental results, including the influ- ence ê and X2, analysis of GPU memory usage, and performance with different numbers shots, provided in Appendix

---

7 Conclusion
In this study, we conduct a pioneering investigation into graph prompting from the perspective of graph topology. We propose GraphTOP - the first graph topology-oriente prompting framework that adapts pre-trained GNN models by modifying graph topology for downstream tasks, particularly node classification. Extensive experiments over five graph datasets validate the effectiveness of GraphTOP against six baselines under four pre-training strategies.
Acknowledgments and Disclosure of Funding
This work is supported in part by the National Science Foundation (NSF) under grants IIS-2006844, IIS-2144209, IIS-2223769, IIS-2331315, CNS-2154962. BCS-2228534, and CMMI-2411248 the Office Naval Research (ONR) under grant N000142412636, the Commonwealth Cyber Initiative (CCT) under grant VV-1Q25-004, and the iPRIME Fellowship Award UVA.
References
[1] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, 2020.
[2] Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. Advances in neural information processing systems, 2020.
[3] Limeng Cui, Haeseung Seo, Maryam Tabar, Fenglong Ma. Suhang Wang, and Dongwon Lee. Deterrent: Knowledge guided graph attention network for detecting healthcare misinformation. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, 2020.
[4] Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. Advances Neural Information Processing Systems, 2018.
[5] Taoran Fang, Yunchao Zhang, Yang Yang, Chumping Wang. and Lei Chen. Universal prompt tuning for graph neural networks. Advances in Neural Information Processing Systems, 2023.
[6] Bahare Fatemi, Layla El Asri, and Seyed Mehran Kazemi. Slaps: Self supe-suupo improves structure learning for graph neural networks. Advances in Neural Information Processing Systems, 2021.
[7] Xingbo Fu, Chen Chen, Yushun Dong, Anil Vullikanti, Eili Klein, Gregory Madden, and Jundong Li. Spatial-temporal networks for antibiogram pattern prediction. In 2023 IEEE 11th International Conference on Healthcare Informatics, 2023.
[8] Xingbo Fu, Yinhan He, and Jundong Li. Edge prompt tuning for graph neural networks. In International Conference on Learning Representations, 2025.
[9] Xingbo Fu, Zehong Wang, Zihan Chen, Jiazheng Li, Yaochen Zhu, Zhenyu Lei, Cong Shen, Yanfang Ye, Chuxu Zhang, and Jundong Li. Graph prompting for graph learning models: Recent advances and future directions. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2, 2025.
[10] Yves Grandvalet and Yoshua Bengio. Semi-supervised learning by entropy minimization. Advances neural information processing systems, 2004.
[11] Will Hamilton, Zhitao Ying, and Jure Leskovec.
Inductive representation learning on large graphs. In Advances in neural information processing systems, 2017.
[12] Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjie Wang, and Jie Tang. Graphmae: Self-supervised masked graph autoencoders. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.
10

---

[13] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-traime tre-training graph neural networks, In International Conference on Learning Representations, 2020.
[14] Ziniu Hu, Changjun Fan, Ting Chen, Kai-Wei Chang, and Yizhou Sun. Pre-training graph neural networks for generic structural feature extraction. arXiv preprint arXiv:1905, 13728, 2019.
[15] Renhong Huang, Jiarong Xu, Xin Jiang, Chenglu Pan, Zhiming Yang, Chunping Wang, and Yang Yang. Measuring task similarity and its implication in fine-tuning graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024.
[16] EunJeong Hwang, Veronika Thost, Shib Sankar Dasgupta, and Tengfei Ma. An analysis of virtual nodes in graph neural networks for link prediction. In The First Learning on Graphs Conference, 2022.
[17] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameteriizatio with cumbel-softmast In International Conference on Learning Representations, 2017.
[18] Menglin Jia, Luming Tang, Bor-Chun Chen, Claire Cardie, Serge Belongie, Bharath Hariharan, and Ser-Nam Lim. Visual prompt tuning. In European Conference on Computer Vision, 2022.
[19] Wei Jin, Tyler Derr, Haochen Liu, Yiqi Wang, Suhang Wang, Zitao Liu, and Jiliang Tang. Self-supervised learning on graphs: Deep insights and new direction. arXiv preprint arXiv:2006. 10141, 2020.
[20] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference knowledge discovery & data mining, 2020.
[21] Muhammad Uzair Khattak, Hanoona Rasheed, Muhammad Maaz, Salman Khan, and Fa- had Shahbaz Khan. Maple: Multi-moda prompt learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 19113-19122, 2023.
[22] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- tional Conference on Learning Representations, 2015.
[23] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017.
[24] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadch. and Ameet Talwalkar. Hy- perband: A novel basei approach to hyperparameter optimization. Journal of Machine Learning Research, 2018.
(25) Shuangli Li, Jingbo Zhou, Tong Xu, Dejing Dou, and Hui Xiong. Geomgel: Geometric graph contrastive learning for molecular property prediction. In Proceedings of the AAAI conference on artificial intelligence, 2022.
[26] Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan. Towards unsupervised deep graph structure learning. In Proceedings of the ACM Web Conference 2022, 2022.
[27] Zemin Liu, Xingtong Yu, Yuan Fang, and Xinming Zhang. Graphprompt: Unifying pre-training and downstream tasks for graph neural networks. In Proceedings of the ACM Web Conference 2023, 2023.
[28] Sitao Luan, Chenqing Hua, Minkai Xu, Qincheng Lu, Jiaqi Zhu, Xiao Men--Wnn& Chang, Jie Fu, Jure Leskovec, and Doina Precup. When do graph neural networks help with node classification? in- vestigating the homophily principle on node distinguishability. Advances in Neural Information Processing Systems, 2023.
[29] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. homophily a necessity for graph neural networks? In International Conference Learning Representations, 2022.
11

---

[30] Chris Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous re- laxation of discrete random variables. In International Conference on Learning Representations. 2017.
[31] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? In International Conference on Learning Representations, 2023.
[32] Jianzhong Qi, Zhuowei Zhao, Egemen Tanin, Tingru Cui, Neema Nassir, and Majid Sarvi. A graph and attentive multi-path convolutional network for traffic prediction. JEEE Transactions on Knowledge and Data Engineering. 2022.
[33] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint vrXiv:2006.10633 2020.
[34] Fan- Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. In International Conference on Learning Representations, 2020.
[35] Mingchen Sun, Kaixiong Zhou, Xin He, Ying Wang, and Xin Wang. Gppt: Graph pre-training and prompt tuning to generalize graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.
[36] Xiangguo Sun, Hong Cheng, Jia Li, Bo Liu, and Jihong Guan. All in one: Multi-task prompting for graph neural networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023.
[37] Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition- based multi-relational graph convolutional networks. In International Conference Learning Repre- sentations, 2020.
[38] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[39] Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2019.
[40] Junfu Wang, Yuanfang Guo, Liang Yang, and Yunhong Wang. Understanding heterophily for graph neural networks. In International Conference on Machine Learning, 2024.
[41] Yu Wang, Nedim Lipka, Ryan A Rossi, Alexa Siu, Ruiyi Zhang, and Tyler Derr. Knowl- edge graph prompting for multi-document question answering. Proceedings of the AAAI Conference Artificial Intelligence, 2024.
[42] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph enn for learning on point clouds. ACM Transactions on Graphics, 2019.
[43] Xuemei Wei, Yezheng Liu, Jianshan Sun, Yuanchun Jiang, Qifeng Tang, and Kun Yuan. Dual subgraph-based graph neural network for friendship prediction in location-based social networks. ACM Transactions on Knowledge Discovery from Data, 2023.
[44] Lirong Wu, Haitao Lin, Cheng Tan, Zhangyang Gao, and Stan Li. Self-supervised learning on graphs: Contrastive, generative, or predictive. IEEE Transactions on Knowledge and Data Engineering, 2021.
[45] Jun Xia, Lirong Wu, Jintao Chen, Bozhen Hu, and Stan Li. Simgrace: A simple framework for graph contrastive learning without data augmentation. In Proceedings of the ACM Web Conference 2022, 2022.
[46] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
12

---

[47] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi supervised learning with graph embeddings. In International conference on machine learning, 2016.
[48] Seungryong Yoo, Eunji Kim, Dahuin Jung, Jungbeom Lee, and Sungroh Yoon. Improving visual prompt tuning for self- supervised vision transformers. In International Conference on Machine Learning, 2023.
[49] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 2020.
[50] Xingtong Yu, Zhenghao Liu, Yuan Fang. Zemin Liu, Sihong Chen, and Xinming Zhang. Generalized graph prompt: Toward a unification of pre-training and downstream tasks on graphs. IEEE Transactions Knowledge and Data Engineering, 2024.
[51] Xingtong Yu, Jie Zhang, Yuan Fang, and Renhe Jiang, Non-homophilic graph pre-training and prompt learning. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2025.
[52] Xingtong Yu, Chang Zhou, Yuan Fang, and Xinming Zhang. Multigprompt for multi-task pre-training and prompting graphs. In Proceedings of the ACM on Web Conference 2024, 2024.
[53] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020.
[54] Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz, and Irwin King. Spectral feature augmen- tation for graph contrastive learning and beyond. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023.
[55] Zheng Zhang, Junxiang Wang, and Liang Zhao. Curriculum learning for graph neural networks: Which edges should we learn first. Advances in Newral Information Processing Systems, 2023.
[56] Tianxiang Zhao, Xiang Zhang, and Suhang Wang. Imbalanced node classification with synthetic over-sampling. IEEE Transactions on Knowledge and Data Engineering. 2024.
[57] WANG Zhili, DI Shimin, CHEN Lei, and ZHOU Xiaofang. Search to fine-tune pre-trained graph neural networks for graph-level tasks. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), 2024.
[58] Kaiyang Zhou, Jingkang Yang, Chen Change Loy, and Ziwei Liu. Learning to prompt for vision-language models. International Journal of Computer Vision, 2022.
[59] Xiao Zhou, Yong Lin, Weizhong Zhang, and Tong Zhang. Sparse invariant risk minimization. In International Conference on Machine Learning, 2022.
[60] Xiao Zhou, Weizhong Zhang, Hang Xu, and Tong Zhang. Effective sparsification of neural networks with global sparsity constraint. In Proceedings of the IEEE/CV Conference on Computer Vision and Pattern Recognition, 2021.
[61] Zhilun Zhou, Yu Liu, Jingtao Ding, Depeng Jin, and Yong Li. Hierarchical knowledge graph learning enabled socioeconomic indicator prediction in location-based social network. In Proceedings of the ACM Web Conference, 2023.
[62] Jing Zhu, Yuhang Zhou, Vassilis N Ioannidis, Shengyi Qian. Wei Ai, Xiang Song, and Danai Koutra. Pitfalls in link prediction with graph neural networks: Understanding the impact of target-link inclusion & better practices. Proceedings of the 17th ACM International Conference Web Search and Data Mining, 2024.
[63] Xiang Zhuang, Qiang Zhang, Keyan Ding, Yatao Bian. Xiao Wang, Jingsong Lv, Hongyang Chen, and Huajun Chen. Learning invariant molecular representation in latent discrete space. Advances in Neural Information Processing Systems, 2023.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The paper's contributions and scope are specified in the abstract and in- troduction, including problem formulation, algorithmic design, theoretical analysis, and experimental evaluation.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Please check Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiaatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: Please check Section 5.2 Section A and Section
C
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please check Section 6.1 and Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Please check our code is available at allttps://anonyyouus 4open / #/GraphTOP-9955 9678
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
oliccy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc/pbble pwwppppguuuiieeeeep hutpc///uuudess/deeuuuubiiis SroodeSubiissi. ssiniiolccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please check Section 6.1 6.1 and Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We reported the standard deviations the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please check Section E.4. We also evaluated time of execution and memory needed in the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttp:://euur/ htt.ti/iiii/////ooooooooo//o//oe
Answer: [Yes]
Justification:
We follow the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Please check Section
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The data and related techniques are explicitly cited in the paper.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy buctps://neure wwwparippps..coooeeeeeeeee for what should or should be described.
20

---

A Proof of Theorem 1
Theorem 1 Given two random variables G1 and G2 that follow the Gumbel distribution
Gumbel(0, 1), for any probability Pij E P. we have
Pij
Pr
G1
G2 + log
20 = Pij-
(16)
1 Pij
Proof. According to the definition of the Gumbel distribution, the probability density function of Gumbel (1,, 1) is
f(z; ()) (a-p)-e-(e-m))
(17)
The cumulative distribution function of Gumbel(p, 1) is
F(E; = - (F--))
(18)
Obviously, we have
Pij
Pr G1 G2 log
2 Pr ((log (pty + G1) (log -Pp) + G2) 20)
1 - Pij
(19)
Let 2 log (pt))
G1, 22 log (1 1 -Pis) + G2. We know
x Gumbel (pt)) 1), 22 Gumbel(log (1 pis),
(20)
Then, have
Pr (log (pij) + G1) (log (1 pij) + G2) 0)
Pr(x1
I2 2 20)
M122; (1 - Poj) (z); log (pis) (pis))dda )dr2drr
F(s1;log(1 -
+oo
(1) tog(1 e (21 (og(m))) to togtoey)) dai
(o) losll pij)) Log(P,) (et wuless)) dx
(21)
+00
(m) (lg-)))(p))))- (e hot (al(es)) dxy
+00
(w) -lg((p)))))) dx
Pij
22 dxi
-00
Pij
Pij
Therefore, we can conclude
Pij
G1 GG-22+ log
20 = Pij-
(22)
1 Pij
21

---

Algorithm GraphTOP
1: Input: Pre-trained GNN model for, initial Iw and lg. input graph 9, training node list VL. hyperparameters X1 and λ2, learning rate 7, training epochs E 2: Extract p-hop local subgraph ((v) for each node 0/ E VL
3: for e- to E do
4: Anneal temperature by max (0.97 x e/ 0.03,
5: for each v2 and its local subgraph G(v:) do
6: S(x:) (e4)
7:
for each node 2y E (,( do
8:
Compute Pij (W2 (ReLU (W1 (h4 hz))))
9:
Sample 91 and from Gumbel (0, 1)
+ log
Pg P-p
10:
8ij
7
11:
Compute e (pij) = Péj log + (1 - (1-p:s) log(1 - pis)
12:
end for
13:
end for
Compute (p(ó,w) 1
[V.. Em,e,
(gw (lfo- ((t)))(()))))))))) .)
15:
Compute (F(0) [Vr. Ener
Watrell EnjeNs E (pts))
Er,eNocu,) [N,(us]
16:
Compute Ls(Ø) [V2l Enev
17:
Update t (Vp((
Update Φ r V (Cr(o,w) +
- x=
19:
end for
B Overall Algorithm
The overall algorithm of GraphTOP is provided in Algorithm
C Proof of Theorem
Theorem 2 Given a pre-trained 2-layer linear GCN model Ja- and a random graph G ~
CSBM 11 P2.P. P.q). when p + q, there always exists edge rewiring the prompted graph by Graph- TOP that satisfies
p Dist.
Dist'
(23)
p-
Proof. According to the CSBM, suppose that the labels of a target node vy 's neighbors will be independently sampled from a neighborhood distribution De, = ptgg p+g or D = --ار و
p q if node o; is from class
if node is from class 229]
Without GraphTOP, the expected feature obtained from the first layer of the GCN operation will be
E., [h (1))
+
(24)
p+
for nodes from class e1 and
E h (1)
14
142
(25)
p+q
p
for nodes from class Here, we ignore the linear transformation in the weight matrices of the pre-trained GNN model, as it can be absorbed by the linear classifier.
Similarly, the expected feature obtained from the second layer of the GCN operation will be
Es, 1h (2)
P 9
Ec, [ (2) +
IEc, (1)
(26)
22

---

for nodes from class and
p p for nodes from class C2. When q. the nodes from the two classes are distinguishable from each other, i..,, Ee, h (2) + E,, [h (
Beg 1h [2)
p+q Rey [1
(27)
To evaluate the linear separability of linear classifiers, we calculate the expected distance Dist between the two classes and by
B hh [1 Bey [h [h!201]
Dist
p Beg (1) + 9 -P
Bey [h (1)
p ptg 9
p p+g
p- ạ
Beg 1h (1 - Beg 11c Bozlh(1) (1
(28)
ptq
p q
p- q
+ 9 9-2 p
p+q
p
p
(p g)
|| H2l
(p + q)²
Next, we consider the expected distance when rewiring edges with GraphTOP. Since GraphTOP only alters how every target node connects to the nodes within its 2-hop local subgraph, B,, [h] and E,2 (h [1] are still the expected features for nodes from class ej and C2. respectively. Let p' and q' denote intra-class and inter-class probabilities of edges between target node and other nodes after rewiring edges with GraphTOP, respectively. Then, the new expected feature from the second layer of the GCN operation will be
p' p' +
E hh (2)
Ec, (1 p' +
Ecg (1)
(29)
for nodes from class C1 and
d'
p' p' +
E (2)
E., (1
E,,, (1)
(30)
pf + q
for nodes from class C2. In this case, the new expected distance after rewiring edges with GraphTOP will be
Dist'
Ey (h
E' [2(
p' d
E,, [h 11+
o' r/ p' +
Eeg 166
p' + o
W -
Ez, 1h (2)
B.,, (1)
(31)
1/ +
pp' 1-4/ 4'1
M1 + 9 P
p p+d u2
1/ /+9
p+0 1
p //
1p 1p- gl
||| Mzl
1/ 4
p+1 4
Then we have
Dist' = 1p/ - g'l
p
Dist.
(32)
// g
With the loss term LE, each probability Ptş is forced to be 0 or 1. To ensure that the nodes from the two classes e₁ and 02 both have the probability of to connect intra-class nodes, we may compute
Psy in Equation ( to be I as long as i4 are vy are from the same class; otherwise, Ptj = 0. In this case, will have p' and q' = 0 for each target node in the prompted graph. Hence, we can get
p 9 Dist.
Dist'
(33)
p
23

---

Table 3: Basic information and statistics of graph datasets adopted in experiments.
Dataset
#(Nodes)
#(Edges)
#(Features)
Average degree
Homophily ratio #(Clasee))
Cora
2,708
10,556
1,433
3.90
0.810
PubMed
19,717
88,648
500
4.49
0.802
3
Amazon
24,492
93,050
300
3.80
0.380
Minesweeper
10,000
39,402
3.94
0.683
2
Flickr
89,250
899,756
500
10.08
0.319
D Extension to graph-level tasks
For graph-level tasks, such graph classification, can similarly model edge rewiring Bernoulli random variables. Since graphs in graph-level tasks are typically not very large (usually less than 10K nodes per graph), we do not need to restrict topology-oriented prompting instead apply to the whole graph. In this case, GraphTOP is simplified for graph-level tasks. We keep empirical evaluation of TraphTOPP on graph-level tasks our future work.
multi-hop subgraph but
E
More details about experimental setup
E.1
Datasets
We use five real-world graph datasets to evaluate the performance of GraphTOP. The statistics of these datasets can found Table
E.2 Pre-training strategies
We adopt four representative methods for pre-training GNN models in our experiments. These methods are also adopted by the previous graph prompting studies 27 35 36). The details of these pre-training strategies are listed here.
generates two perturbed views of graph using node dropping and edge perturbation. A GNN model encodes both views into representations, which are then mapped to a latent space using a nonlinear projection head. The contrastive loss is applied to maximize agreement between the two views, optimizing both the GNN model and the projection head.
GraphCL 49
SimGRACE 45 constructs perturbed version of the GNN model by adding Gaussian noise to its parameters. Given an input graph, the perturbed and the original GNN models generate representations that form positive pair for contrastive learning.
LP-GPPT [35] randomly masks a subset of edges in the input graph. The model learns predict whether given pair of nodes is connected. Negative samples are generated by selecting node pairs that are not linked in the original graph.
P--rrphPrompp (27) samples a connected neighbor as one positive node and an unlinked node as one negative node for each target node. The training objective is to maximize the similarity between connected node pairs while minimizing the similarity between unconnected pairs.
We would like to emphasize that designing effective pre-training strategies for training powerful GNNs remains ongoing challenge in graph learning. Many graph prompting methods 35 27 50 adopt link prediction as their pre-training strategies, while one recent study [51] discusses when to link prediction contrastive learning for pre-training. Although choosing better pre-training strategy can yield more powerful GNN models, it is outside the scope of this study: we aim to obtain the best performance on downstream tasks given pre-trained GNN model, regardless of its pre-training strategy.
E.3 Baselines
We six SOTA baselines in experiments. We provide the details of these baselines follows.

---

67.59
67.68
67.68
67.68 67.68
31.97
32.08
32.08
32.08
32.08
2 67.86
67.68
67.68
67.68 67.68
2
31.71
32.08
32.05
32.07
32.07
5 667.79 68.14
28
67.68
67.68
5
31.88
32.02
32.41
32.06
32.05
10 66.779
68.11
67.
67.83 68.01
10
31.96
32.13
32.39
31.82
32.32
20 67.79
20-67.79
68.18 68. 67.69 67.41
20
32.11
32.02
32.14
32.26 32.33
3
3
(a) PubMed under GraphCL
(b) Amazon under LP-GPPT
Figure 3: The average accuracies of GraphTOP with different values of X and X2.
Linear Probe only trains linear classifier during the adaptation phase without any graph prompting design.
GPPT [35] pre-trains a GNN model via edge masking and link prediction, coupled with a task-specific prompt module that reparameterizes downstream node classification into edge likelihood estimation.
All-in-one [36 reformulates node/edge tasks graph tasks via multi-hop subgraphs, using learnable prompt graphs with token vectors, tunable token structures, and -inturr-immllaitt- weighted insertion patterns. It aligns downstream tasks with graph-level pre-training via episodic meta-learning over multi-tass episodes.
GraphPrompt 27 bridges the gap between pre-training and downstream tasks through subgraph similarity calculations unified template, with learnable prompt updated during the adaptation phase to incorporate task-specific knowledge for tasks like node and graph classification.
GraphPrompt+ [50] extends GraphPrompt by introducing prompt vectors within each layer of the pre-trained GNN model, effectively capturing hierarchical information beyond the readout layer to enhance adaptation.
ProNoG [51]: ProNoG is a graph prompting framework for non-homophilic graphs. employs conditional network to generate node-specific prompts based on its multi-hop subgraph.
E.4 Hardware information
We run our experiments using server equipped with 512 GB of memory, 128 AMD EPYC 7543 32-core CPUs, and NVIDIA RTX A6000 GPUs, each of which has 48 GB of memory.
F
More experimental results
F1
Influence of X and Aa
The two hyperparameters X₁ and Ay balance different loss terms in the objective function of GraphTOP. To explore their influence on model utility, we conduct grid search for x and Ag. Other robust optimization strategies, such as Bayesian Optimization and Hyperband [24), can also be used for hyperparameter selection. F λ1 and Xu over PubMed under GraphCL and Amazon under LP-GPPT. According to the results, we observe that the performance of GraphTOP varies with different values of both \ and Ag. GraphTOP can obtain the best performance when we set \ = 2 and X = 5 or 10. Additionally, we also notice that the accuracies are not high but quite stable when X2 O. We conjecture that the probabilities are mostly driven toward values close by the loss term LF. leading to the same densely connected prompted graphs. When X2 > 0, however, the edge densities by GraphTOP are reduced. In this case, detrimental edges will be removed to enhance adaptation for pre-trained GNN models.
the accuracy results of GraphTOP with different values of
25

---

Table 4: GPU memory usage (GB) of GraphTOP and its variant when 2 and 3 (OOM: out of GPU memory).
Dataset
GraphTOP
GraphTOP all modes
2
0.44
6.41
Cora
0.69
OOM
2
0.24
13.41
PubMed
3
2.33
OOM
0.49
6.54
Amazon
3
0.58
OOM
2
0.32
0.84
Minesweeper
0.36
2.79
Table 5: Accuracy with different numbers of shots. The best-performing method is bolded, and the runner-up is underlined.
3-shot
Pre-training Strategies
Graph Prompting
Cora
Minesweeper
Methods
Linear Probe
51.7642.82
63.9346.42
GPPT
49.84
58. +6.211
ALL-in-one
47 47.69
52.40.5.58
GraphCI.
GraphPrompt
52.7614.94
55.35
GraphPrompt+
50.30
50.37 16.99
ProNoG
52.94
59. 59.18+7.93
CraphTOP
56. 56.70+5.70
64.70
10-shot
Pre-training
Graph Prompting
Amazon
Minesweeper
Strategies
Methods
Linear Probe
25.3643.80
61.60
GPPT
22.87
58. 48.90
ALL-in-one
18. 58.36
57 07.64
SimGRACE
GraphPrompt
22.6612.00
58.6515.34
GraphPrompt+
24.06.2.47
61.61
ProNoG
22.88 1.96
62.01 :
GraphTOP
26.78 44..48
63. 63.20 20.
20-shot
Pre-training
Graph Prompting
PubMed
Amazon
Strategies
Methods
Linear Probe
73.3842.28
28. 28.50
GPPT
75.92+3.07
27. 07.5444...8
ALL-in-one
72.2946.42
29.36 49.36
PrrGrppProompt
GraphPrompt
76.40+1.81
25. 25.00+1.34
GraphPrompt+
70.77+2.30
26.41+2.10
ProNoG
75.55.1.69
26.12.1.99
GraphTOP
77.4046.06
32.40+4.60
F.2 Results of memory usage
Apart from time efficiency, we are also interested in GPU memory usage by GraphTOP and GraphTOP nodes Table shows GPU memory usage by GraphTOP and GraphTOP nodes on four datasets. From the table, we notice that GraphTOP all nodes requires more GPU memory resources compared with GraphTOP. The situation is even more pronounced than what we observed in Table 2 Considering this, our design for rewiring edges only between each target node and other nodes within its multi-hop local subgraph is very essential in GraphTOP.
26

---

F.3 Performance with different numbers of shots
We also conduct experiments with different numbers of shots. Table 5 shows the performance of GraphTOP and other baselines.
G
Limitations
The theoretical analysis uses the CSBM [4] model to generate random graphs and analyze the linear separability of linear GCN models. Although it follows previous studies in graph learning, the nonlinear separability is also an important issue to explore.
H
Broader impacts
This study will benefit many real-world applications related to graph prompting, such as anomaly detection and bad actor prediction.
27


Reviews:
[{"review_id": "TsyKaCdiWQ", "reviewer": "Reviewer_dFHj", "summary": "The paper proposes a topology-oriented prompting strategy to adapt a pre-trained GNN to a new task by modifying the input graph topology.", "questions": "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.\n\n\nSouthern et al., Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper is well written and easy to follow. The general idea of leveraging graph topology in prompting is intuitively justified and original.\n\n\nI think the paper has two main weaknesses:\n1. 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. \n2. The evaluation section is weak. The considered datasets are small and outdated. I would recommend to include the ogb datasets (arxiv, proteins, products).\n\n\nZhang et al., 2021. Labeling trick: A theory of using graph neural networks for multi-node representation learning.\n\nBevilacqua et al., 2025. Holographic Node Representations: Pre-training Task-Agnostic Node Embeddings", "was_revised": true, "final_justification": "I maintain my positive score, as I believe a higher score requires a more comprehensive evaluation.", "rebuttal": "We thank the reviewer for providing valuable comments. We hope our point-by-point responses can fully address all your concerns.\n\n---\n- **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.\n\n- **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.\n\n---\n\n- **W2**: The evaluation section is weak. The considered datasets are small and outdated. I would recommend to include the ogb datasets (arxiv, proteins, products).\n- **R2**: Thanks for bringing this up. We conduct experiments on ogbn-arxiv and provide the results under GraphCL and LP-GraphPrompt as follows.\n\n|  Graph Prompting Methods  |      GraphCL     |   LP-GraphPrompt   |\n|---------------------------|----------------------|----------------------|\n|     Linear Probe      |  21.57 $\\pm$ 1.74   |  30.86 $\\pm$ 2.63   |\n|     GPPT           |  18.45 $\\pm$ 1.83   |  27.51 $\\pm$ 1.85   |\n|     ALL-in-one       |  17.85 $\\pm$ 3.22   |  16.43 $\\pm$ 4.02   |\n|      GraphPrompt      |  21.29 $\\pm$ 2.53   |  32.89 $\\pm$ 1.84   |\n|     GraphPrompt+      |  21.86 $\\pm$ 2.91   |  31.56 $\\pm$ 1.24   |\n|      ProNoG         |  20.60 $\\pm$ 3.42   |  32.25 $\\pm$ 2.57   |\n|      GraphTOP        |**23.54 $\\pm$ 2.29**  |**33.86 $\\pm$ 2.81** |\n\n\n---\n\n- **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.\n\n- **A1**: Thanks for bringing this up. We will include related works of subgraph GNNs in the revised version of our paper.\n\n---\n\n[1] Liu, Zemin, et al. GraphPrompt: Unifying Pre-Training and Downstream Tasks for Graph Neural Networks. WWW 2023.  \n[2] Yu, Xingtong, et al. Generalized Graph Prompt: Toward a Unification of Pre-Training and Downstream Tasks on Graphs. TKDE 2024.  \n[3] Sun, Mingchen, et al. GPPT: Graph Pre-training and Prompt Tuning to Generalize Graph Neural Networks. KDD 2022.  \n[4] Yu, Xingtong, et al. Non-Homophilic Graph Pre-Training and Prompt Learning. KDD 2025."}, {"review_id": "KYx3q0n1zw", "reviewer": "Reviewer_pf7m", "summary": "This work focus on the graph prompt tuning topic, it points out existing methods primarily rely on manipulating node features, which often overlook the structural prompting. So the authors propose the GraphTOP prompting framework that optimizes graph topology by learning to rewire edges within local subgraphs using a Gumbel-Softmax relaxation. The method incorporates entropy and sparsity regularization to ensure structural sparsity and interpretability. To support the design, the authors provide theoretical analysis under the Contextual Stochastic Block Model (CSBM), showing that rewiring improves class separability, and conduct experiments across 5 benchmarks demonstrating consistent gains over existing prompt methods on diverse pre-training strategies.", "questions": "1. Is this topology-based prompt compatible with existing feature-based prompt? \nany chance they could be combined to make further improvement?\n\n2. Is there any visualized example to illustrate a subgraph before/after re-wiring?", "limitations": "n/a", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The proposed GraphTOP achieves good performance \n2. The analysis under CSBM provides justification for why graph topology optimization improves downstream task performance.\n3. Code is provided.\n\nWeakness\n\n1. Missing related work - This work (https://arxiv.org/pdf/2503.00750) is graph prompting from edge perspective and should be somewhat related.\n2. 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.", "was_revised": true, "final_justification": "I have read all the author responses, but all the responses are like \"we will do xxx\", I did not really see the updates. Therefore, I keep my previous score.", "rebuttal": "We thank the reviewer for providing valuable comments. We hope our point-by-point responses can fully address all your concerns.\n\n---\n- **W1**: Missing related work - This work (https://arxiv.org/pdf/2503.00750) is graph prompting from edge perspective and should be somewhat related.\n- **R1**: Thanks for bringing our attention to this excellent work. We will include it in the revised version of our paper.\n\n---\n\n- **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.\n- **R2**: Thanks for pointing it out. We will try to add some illustrative figures to make the paper more readable.\n\n---\n\n- **Q1**: Is this topology-based prompt compatible with existing feature-based prompt? any chance they could be combined to make further improvement?\n- **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.\n\n---\n\n- **Q2**: Is there any visualized example to illustrate a subgraph before/after re-wiring?\n- **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."}, {"review_id": "GvDE97r4yX", "reviewer": "Reviewer_JEMG", "summary": "This paper proposes GraphTOP, the first graph topology-oriented prompting framework that adapts pre-trained Graph Neural Networks by learning to modify the graph’s adjacency structure rather than node features. Through edge rewiring formulated as a differentiable probability optimization problem, GraphTOP significantly improves few-shot node classification performance across multiple datasets and pre-training strategies.", "questions": "1. Given that in many graphs (e.g., chemical molecules, transportation networks) the edge structure is determined by strict domain knowledge, how does the method ensure that modifying the adjacency matrix does not introduce unreasonable or invalid pseudo-structures?\n2. How does this work compare in practice and motivation to Graph Structure Learning methods (such as SLAPS, GSL, IDGL), which also learn or adapt the graph structure\n3. In the experiments with varying numbers of shots, why were the pre-training strategies not kept consistent across comparisons?", "limitations": "yes", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Pros:\n1. The design of the method corresponds to the motivation.\n2. The time cost of the method is taken into consideration, and constraints are imposed on the method to increase the practicality of the method.\n3. Extensive experiments supported the method.\n\n\nCons:\n1. 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.\n2. The experimental tasks are single and all focus on node classification.\n3. Some similar methods may be considered as baselines to compare, or for moderate discussion to distinguish them, such as Graph Structure Learning methods.\n4. 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.", "was_revised": true, "final_justification": "After reading the rebuttal and other reviews, I would like to maintain my score.", "rebuttal": "We thank the reviewer for providing constructive comments. We hope our point-by-point responses can fully address all your concerns.\n\n---\n- **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.\n- **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].\n\n---\n- **C2**: The experimental tasks are single and all focus on node classification.\n- **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.\n\n---\n- **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.\n- **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.\n\n---\n- **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.\n- **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.\n\n---\n\n[1] Zhou, Kaiyang, et al. Learning to Prompt for Vision-Language Models. IJCV 2022.  \n[2] Jia, Menglin, et al. Visual Prompt Tuning. ECCV 2022."}, {"review_id": "J1z6LXb02Q", "reviewer": "Reviewer_6YGZ", "summary": "This paper presents a graph topology-oriented prompting framework, GraphTOP, designed to adapt pre-trained graph neural networks (GNNs) to downstream tasks, with a primary focus on node classification. In contrast to conventional feature-based graph prompting approaches, GraphTOP addresses the topological properties of subgraph rewiring by formulating it as a discrete-to-continuous optimization problem. Specifically, the proposed method transforms discrete topological structures into a continuous probability space amenable to gradient-based training through a carefully designed reparameterization technique. To enhance the framework's robustness, the authors introduce two key components: (1) an entropy regularization term to ensure tight relaxation of the probabilistic formulation, and (2) a sparsity constraint to maintain computational efficiency while preserving meaningful graph structure.The experimental evaluation demonstrates GraphTOP's superiority over six baseline methods across five real-world datasets. Comprehensive ablation studies further validate the effectiveness of the proposed topological prompting mechanism and optimization strategies. The results consistently support the claim that explicitly modeling topological adaptations yields significant performance improvements compared to feature-centric prompting approaches.", "questions": "1.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?\n\nScoring impact: Providing experiments on synthetic datasets or large-scale graphs, along with optimization strategies, could potentially improve the rating.\n\n2.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)?\n\nScoring impact: Demonstrating that GraphTOP can still enhance GNN training effectiveness under nonlinear representations may lead to rating improvement.\n\n3.The selection of parameters λ₁ and λ₂ shows significant impact on results. Could more robust optimization strategies be proposed?\n\nScoring impact: The inclusion of more robust optimization approaches may warrant rating consideration.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1.The methodological design of this study is rigorous, with meticulous language descriptions demonstrating high quality. For instance, Section 4.2 provides comprehensive theoretical justification for the effectiveness of topology-oriented prompting.\n\n2.Departing from conventional feature-based graph prompting frameworks, this work pioneers topology-oriented graph prompting learning, filling a critical gap in the research field and exhibiting significant originality.\n\n3.The paper features substantial mathematical derivations complemented by clear algorithmic descriptions in the experimental section. Furthermore, the appendices contain complete mathematical proofs of relevant corollaries, substantially enhancing the clarity and rigor of the work.\n\nWeaknesses\n\n1.The experimental evaluation exclusively employs real-world graph datasets, lacking validation on synthetic (artificially constructed) datasets. This omission raises questions about the model's robustness in specialized or edge-case scenarios.\n\n2.The theoretical analysis primarily relies on the CSBM model and linear GCN architectures. The absence of complementary experiments examining generalization to nonlinear scenarios remains an important open question for discussion.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing valuable comments. We hope our point-by-point responses can fully address all your concerns.\n\n---\n- **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?\n- **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.\n\n|  Graph Prompting Methods  |      SimGRACE     |   LP-GPPT   |\n|---------------------------|----------------------|----------------------|\n|     Linear Probe      |  59.93 $\\pm$ 2.76   |  54.07 $\\pm$ 3.11   |\n|     GPPT           |  61.39 $\\pm$ 4.10   |  53.03 $\\pm$ 2.65   |\n|     ALL-in-one       |  58.20 $\\pm$ 4.09   |  52.42 $\\pm$ 2.46   |\n|      GraphPrompt      |  60.55 $\\pm$ 2.05   |  51.91 $\\pm$ 3.72   |\n|     GraphPrompt+      |  63.85 $\\pm$ 1.64   |  53.05 $\\pm$ 1.85   |\n|      ProNoG         |  61.74 $\\pm$ 2.49   |  54.60 $\\pm$ 2.67   |\n|      GraphTOP        |**65.49 $\\pm$ 3.54**  |**57.43 $\\pm$ 4.16** |\n\nAdditionally, we conduct experiments on ogbn-arxiv with ~170K nodes and provide the results under GraphCL and LP-GraphPrompt as follows.\n\n|  Graph Prompting Methods  |      GraphCL     |   LP-GraphPrompt   |\n|---------------------------|----------------------|----------------------|\n|     Linear Probe      |  21.57 $\\pm$ 1.74   |  30.86 $\\pm$ 2.63   |\n|     GPPT           |  18.45 $\\pm$ 1.83   |  27.51 $\\pm$ 1.85   |\n|     ALL-in-one       |  17.85 $\\pm$ 3.22   |  16.43 $\\pm$ 4.02   |\n|      GraphPrompt      |  21.29 $\\pm$ 2.53   |  32.89 $\\pm$ 1.84   |\n|     GraphPrompt+      |  21.86 $\\pm$ 2.91   |  31.56 $\\pm$ 1.24   |\n|      ProNoG         |  20.60 $\\pm$ 3.42   |  32.25 $\\pm$ 2.57   |\n|      GraphTOP        |**23.54 $\\pm$ 2.29**  |**33.86 $\\pm$ 2.81** |\n\n---\n- **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)?\n- **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.\n\n---\n- **Q3**: The selection of parameters $\\lambda_1$ and $\\lambda_2$ shows significant impact on results. Could more robust optimization strategies be proposed?\n- **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.\n\n---\n\n[1] Ma, Yao, et al. Is Homophily a Necessity for Graph Neural Networks? ICLR 2022.  \n[2] Baranwal, Aseem, Kimon Fountoulakis, and Aukosh Jagannath. Graph Convolution for Semi-Supervised Classification: Improved Linear \nSeparability and Out-of-Distribution Generalization. ICML 2021.  \n[3] Li, Liam, et al. Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization. JMLR 2018."}]

Author rebuttal:

Meta-review: This paper proposes a new graph prompting method that works by changing the graph structure instead of node features. The idea is original and fills an important gap in the area. The authors design a complete framework, GraphTOP, that uses edge rewiring in a way that can be optimized during training. The method is supported by theoretical analysis and tested on several datasets with different pre-training strategies. Most reviewers agree that the paper is technically strong and that the proposed idea is interesting and promising. The experimental results are good and show consistent improvements over many baselines.

One reviewer raised concern about modifying the graph structure in cases where the topology is given by domain knowledge. However, the authors explain clearly that the goal of prompting is not to keep domain constraints but to improve performance by adapting to the pre-trained model. I agree with this explanation and believe the concern comes from a misunderstanding. Other reviewers asked for larger and synthetic datasets, and the authors provided additional experiments that helped support their claims. For these reasons, I recommend to accept this paper.
Decision: Accept (poster)