Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
Authors: Qunzhong Wang
Xiangguo Sun
Hong Cheng
Venue: ICML 2025 poster (2025)
Keywords: graph prompting
graph neural networks
Primary area: deep_learning->graph_neural_networks
TL;DR: we offer theoretical proof of why and how much graph prompting works

Abstract: In recent years, graph prompting has emerged as a promising research direction, enabling the learning of additional tokens or subgraphs appended to original graphs without requiring retraining of pre-trained graph models across various applications. This novel paradigm, shifting from the traditional "pre-training and fine-tuning" to "pre-training and prompting," has shown significant empirical success in simulating graph data operations, with applications ranging from recommendation systems to biological networks and graph transferring. However, despite its potential, the theoretical underpinnings of graph prompting remain underexplored, raising critical questions about its fundamental effectiveness. The lack of rigorous theoretical proof of why and how much it works is more like a "dark cloud" over the graph prompting area for deeper research. To fill this gap, this paper introduces a theoretical framework that rigorously analyzes graph prompting from a data operation perspective. Our contributions are threefold: **First**, we provide a formal guarantee theorem, demonstrating graph prompts’ capacity to approximate graph transformation operators, effectively linking upstream and downstream tasks. **Second**, we derive upper bounds on the error of these data operations for a single graph and extend this discussion to batches of graphs, which are common in graph model training. **Third**, we analyze the distribution of data operation errors, extending our theoretical findings from linear graph models (e.g., GCN) to non-linear graph models (e.g., GAT). Extensive experiments support our theoretical results and confirm the practical implications of these guarantees.

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
Qunzhong Wang"
Xiangguo Sun
22
Hong Cheng?
Abstract
sive experiments support our theoretical results and confirm the practical implications of these guarantees.
In recent years, graph prompting has emerged as promising research direction, enabling the learn- ing of additional tokens or subgraphs appended to the original graphs without requiring retrain- ing of pre-trained graph models across various applications. This novel paradigm, shifting from the traditional "pre-training and innettunig" to "pre-training and prompting" has shown signifi- cant empirical success in simulating graph data operations, with applications ranging from rec- ommendation systems to biological networks and graph transferring. However, despite its potential, the theoretical underpinnings of graph prompt- ing remain underexplored, raising critical ques- tions about its fundamental effectiveness. The lack of rigorous theoretical proof of why and how much it works is more like a "dark cloud" over the graph prompt area to go further. To fill this gap, this paper introduces theoretical framework that rigorously analyzes graph prompting from a data operation perspective. Our contributions are threefold: First, we provide formal guarantee theorem, demonstrating graph prompts' capacity to approximate graph transformation operators, ef- fectively linking upstream and downstream tasks. Second, derive upper bounds the error of these data operations by graph prompts for sin- gle graph and extend this discussion to batches of graphs, which are common in graph model train- ing. Third, we analyze the distribution of data operation errors, extending our theoretical find- ings from linear graph aggregations (e.g., GCN) to non-linear graph aggregations (e.g., GAT). Exten-
1 Introduction
Graph Neural Networks (GNNs) have been widely used in analyzing various graph-structured data. A standard workflow using GNNs is the ppre-training and fine-tuning" paradigm, where a model is first trained on a large-scale, general-purpose dataset and then fine-tuned on a specific downstream task. While this method has been effective in transferring learned representations, it often needs many ad- vanced tricks to retrain the model parameters for each new task, which can be computationally intensive and may not fully capture the unique characteristics of the downstream tasks, potentially limiting the model's generalization.
Inspired by the success of prompting techniques in natu- ral language processing (NLP), there has been a growing interest in adapting similar ideas to graph data through "pre- training and prompting". Graph prompts (Sun et al., 2023b) modify the input graphs by adding learnable tokens or sub- graphs, enabling the pre-trained GNN to better align with the requirements of downstream tasks without tuning the model parameters. Many empirical works (Sun et al., 2022; Liu et al., 2023; Tan et al., 2023; Huang et al., 2023; Ma et al., 2023) have found that graph prompting can reduce computational overhead, preserve the generality of the pre- trained model, and allow for seamless application across multiple tasks achieve better expressive capability than the traditional paradigm.
Recently, some studies (Fang et al., 2024; Sun et al., 2023a) have realized that the reason why graph prompts work may relate to their capability in simulating various data opera- tions like deleting/adding nodes/edges, changing node fea- tures, and even removing subgraphs. This makes graph prompts stand out from their counterpart in the NLP area and inspires many empirical applications like recommenda- tion systems (Yang et al., 2023; 2024), biological networks (Diao et al., 2022), transferring knowledge across differ- ent graph domains (Guo et al., 2023; Zhu et al., 2024b), and more. Unfortunately, despite these promising results,
Equul contribution 'Department of Information Engineer- ing. The Chinese University of Hong Kong. 'Department of Systems Engineering and Engineering Management, and Shun Hing Institute of Advanced Engineering, The Chinese University of Hong Kong. Correspondence to: Xiangguo Sun <xiangguo- sun @ edu.hk....k>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
the theoretical basis of graph prompting remains underex- plored. Existing works primarily rely on empirical valida- tion and lack rigorous theoretical analysis to explain why graph prompts are effective and how they can be systemat- ically designed. This gap is just like a "dark could" over the graph prompt area, raising critical questions about their broader applications and the development of more advanced methods that could leverage their full potential.
& denotes the edge set and the connection of nodes can be further indicated by the adjacent matrix A {0, 1) MM Let Pa denote a parameterized graph prompt function with learnable w. In most cases, graph prompts consist of some token vectors or subgraphs which will be integrated into the original graph G. Pw indicates how to define such graph prompts and how to combine them with the original graph to generate new graph: Gw = (G)). Graph prompt learning aims to optimize the following target:
In light of these limitations, this paper provides a compre- hensive theoretical framework for graph prompting from a data operation perspective. First, we establish rigorous guarantee theorems that demonstrate the underlying rea- son why graph prompts work is their capacity to simulate various graph data operations, and our theorems further an- swer why such capacity can make the pre-trained model meet new task requirements without retraining. Second, we derive upper bounds on the error introduced by graph prompts when simulating these data operations. We analyze this error for individual graphs and extend our discussion to batches of graphs, which is crucial for understanding the scalability and generalization of graph prompts in practi- cal scenarios where models are usually trained on multiple graphs. Third, we explore the distribution of the data oper- ation error and extend our theoretical findings from linear graph aggregations, such as Graph Convolutional Networks (GCNs), to non-linear aggregations like Graph Attention Networks (GATs). This extension demonstrates the robust- ness of our theoretical framework across different GNN architectures and provides insights into how non-linearity affects the effectiveness of graph prompts. We conduct extensive experiments to confirm our theoretical findings. By offering such solid theoretical foundation for graph prompting, our work advances the understanding of how and why graph prompts work, guides for designing more effective prompting techniques, and empowers researchers and practitioners to leverage them with greater confidence in various applications.
w" arg min w
Σ CTio (Fe- (Fo GEG
(I)
Without loss of generality, we assume all these tasks are graph level (e.g., graph classification). That means GG( will output a graph-level embedding for the downstream task. For node-level and edge-level tasks, many studies (Sun et al., 2023a; Liu et al., 2023) have proved that we can always find solutions to translate these tasks to the graph- level task.
GPF and All-in-One. Current graph prompt designs, as described in the review by Sun et al. (2023b), can be pri- marily categorized into two types: prompt as token vectors added to node features, and prompt as additional graph in- serted to the original graph. In the rest of this paper, we focus on two representative frameworks: GPF (Fang et al., 2022) as example of adding extra prompt vectors, and All-in-One (Sun et al., 2023a) as an example of adding prompt subgraphs. Our choice is motivated by our interest in simulating graph operations at a theoretical level. The GPF and All-in-One frameworks provide the most funda- mental approaches among these methods. The rest graph prompt designs can usually be treated as their special cases or natural extensions (Sun al., 2023b).
Specifically, GPF aims to learn token vector E RIIF where F is the same dimension of the node features in the original graph, then the prompt token is directly added to each node's feature vector, making the original fea- ture matrix X- = {"1,--. , ,NN changed to X {ai + w.... ,NN + w) In this way, the original graph G = (), V,E,X,AN A) is changed to (G) = G (V, X X,, A).
2 Background
Graph Prompt. tuning", which first trains a graph model via some easily accessible task on the graph dataset and then tries to adapt the model to a new task (or even a new graph dataset), "pre- training and prompting" aims to keep the pre-trained model unchanged but adjust the input data to make the downstream task compatible with the pre-training task. Mathematically, let Fg- be a graph model where its parameters (0*) have been pre- pre-trained and frozen; Taow be the downstream task, in which the task objective is measured by a loss function Trowm. Let G be a graph dataset and each graph instance G can be denoted as G EV,E, X, A) where V de- notes the node set with node feature matrix X E R
Compared with "pre-training and fine-
All-in- One offers the prompt as a graph format by defin- ing prompt tokens, token structures and inserting patterns. Let Ω E R be the learnable matrix corresponding to K prompt tokens. Let Air E (0. 1}*** indicate token struc- tures where A = 1 means there is an inner link connecting the i-th and the j-th tokens and vice versa. Ain can be calculated by the inner product of these tokens. Similarly, the inserting pattern tells us how to connect each token to the original graph nodes, which is denoted by a cross matrix A E {0, 1| Then the graph prompt changes the original graph G to G. = (Vw, E,, X, Ω A.,) where VL is the collection of the original nodes and the token nodes; &
2

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
includes the original edges, inner links among tokens and the cross links between tokens and the original nodes; A_ is the collection of A.Ain. and Acro.
downstream tasks Tdow-
3.1 Perspective from Model Tuning
Motivations. Initially, Fang et al. (2022) have proved that graph prompt can simulate any graph data operation (e.g-- deleting/adding nodes/edges, changing node features, or removing subgraphs, etc). That means for any graph data operation t(-), we can always Iearn a graph prompt reach- ing Fg. (Gw) Fo- (t(G)). However, this equivalence needs a very strong precondition: the graph model F should not contain any non- non-linear layer, which is apparently very hard to meet in the practical solutions. Later, Sun et al. (2023a) extended this finding with more advanced prompts and empirically observed that the error to such approxima- tion F'. (Gw) + Fe- (f(G)) may relate to the non-linear layers of the graph model and the prompt design. How- ever, these observations are not followed by a critical theory proof. Recently, there has been an increasing number of empirical works on graph prompts achieving success in var- ious applications. Unfortunately, the theoretical basis of graph prompt is still very tumbledown and we still have not figured out why graph prompts work in theory, espe- cially for questions like how powerful the graph promp! is in. manipulating, graph, data? and why, such capability works for downstream tasks?
To fill this gap, "pre-training and fine-tuning" aims to adapt the pre-trained model to a new version and wish it could perform better. Assume there exists optimal function, say C, which can map Gori to the embedding C(Gori) to achieve good performance on Tdow The nature of "pre- training and fine-tuning" is to hope the fine-tuned graph model could approximate to ((Gor)):
Fg (Gors) + C(Gori)
(2)
However, achieving this goal usually requires fine-tuning the graph model, which is not always efficient and needs many empirical tuning tricks. The tuning course may be even harder if the pre-trained model is ill-designed for the downstream task. In addition, we can not guarantee that fine-tuning the pre-trained model (i.e. 0* + (*) can al- ways surpass training the model from scratch because the preserved knowledge may contribute negatively to the down- stream task.
3.2 Perspective from Data Operation
Instead of the above model-level tricks, graph prompts pro- vide a data-level alternative. Some prior works (Fang et al., 2024; Sun et al., 2023a) have initially proved that graph prompts can simulate any graph operations (e.g., delet- ing/adding nodessedgee//uuggrahhs. changing node features, etc). However, how effective of graph prompt is and why this works for the new task are still not yet answered. To answer these questions, we first explain our data operation perspective by a theorem as follows:
In this paper, we go deeper in theory for the graph prompt capability of manipulating data. We conduct a comprehen- sive effectiveness analysis of general graph prompt learn- ing through the concepts of "bridge sets" and "c-extended bridge sets" (see in section 3.3). Based on extensive the- oretical derivations and substantial experimental evidence, we establish theorems related to the error bound of graph prompts in simulating graph data operations. Our goal is to figure out in theory how this error changes from a single graph to a batch of graphs, from a linear model to a non- linear model, and which factors relate to this error. Through this work, we wish to push forward the graph prompt area with a more solid theory basis, help researchers to design more scientific graph prompt techniques, and offer them theory confidence for their further usage.
Theorem 1. Let Fo- be GNN model pre-trained on task Tpre with frozen parameters (0*) ); let Toow be the down- stream task and C is an optimal function to Taow- Given any graph Gori C(Gon) denotes the optimal embedding vector to the downstream task (i.e. can be parsed to yield correct results for Gon in the downstream task), then there always exists a bridge graph Gort such that Fg- (Gors) = C(Gors).
A detailed proof of Theorem can be seen in Appendix 1.3.1, from which we can find that for any given graph Gori, there always exists bridge graph, say Gyré, making the following equation hold:
3 Why Graph Prompt Works? A Data Operation Perspective
Let Fg- be any given GNN model that has been pre-trained on a given task Tpre- Here 8" means the parameters have been determined and frozen. For a given graph instance Gori, we can expect the model to output appropriate graph- level embedding on Tree because this model has already been trained on this task. However, when we try to use this model on new task Taow, the output embedding, Fg. (Gors), can not guarantee acceptable performance be- cause the pre- traiirii task Tpre may be incompatible with
Fo- (Gbri) = C(Gori)
(3)
That means, without needing to tune the model, we can try to find data operation method that translates Gori to Gbri with the pre-trained model unchanged. Graph prompts can be treated as a learnable data operation framework to help us manipulate these graph data. In this way, we can significantly reduce the difficulty of traditional fine-tuning
3

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
work, improve the performance on a new task (or even new dataset); and further enhance the generalization of graph neural networks. With this perspective, our next question is: How difficult to find such a bridge, graph using, graph prompts?
4
The Upper Bound of Data Operation Error via Graph Prompt
4.1 Upper Bound of the Error on A Single Graph
Here we aim to demonstrate that using graph prompts pro- vided by frameworks such as GPF and All-in- denoted as parameterized operators P. with parameter w, can con- sistently project G' into an c-extended Bg, where c has uniform upper bound. This would initially validate the ef- fectiveness of graph prompting methods in leveraging the potential of rre-trained models without compromising their expressive power If G can be seamlessly projected into BG or an e-extended Be (for small e). it would indicate excellent performance and full utilization of the model's capabilities.
3.3 Measuring the Difficulty of Finding Bridge Graphs via Graph Prompts
Graph prompts can be viewed as a type of graph transfor- mation operator. For example, the simplest graph prompt is just adding a specific prompt token vector Pw to each node feature of the graph and then we can transform this graph G' into family of graphs (G)) RF), where Pa represents the output graph obtained by graph prompt on G. Once w is determined, the corresponding data transforma- tion rule and unique output graph data are also defined. This family can be understood as the transformation space" of graph G under prompt P. denoted as Dp (G). If the prompt operator maps the original graph Goe to bridge graph Gur (i.e., o(Gor) Gb then applying the pre-trained model Fo. yields Fg. (P(G.))) the downstream task. In this process, we achieve seamless aligmment of upstream and downstream tasks solely through data transformation operators, without relying on tuning the model's 's parameters.
To this end, we first conduct a quantitative analysis of P. 's graph transformation approximation ability on single graph. With our proposed data operation perspective, we can reformulate the findings in Fang et al. (2022) as follows:
Theorem 2. Given a GPF-like prompt vector pa,, ifa GCN model Fo does not have any non-lineat transformations. then there exists an optimal w for any input graph G such that (G) E BG.
Fe- (Gun), which conforms to
This theorem is proved by Fang et al. (2022) but it's impor- tant to note that all GNN models employ non-linear transfor- mations. According to the function approximation theorem for neural networks (Hornik et al., 1989), the core of im- proving a model's s approximation and simulation ability lies in its non-linear components. Removing these non-linear parts would limit the model to approximating only linear transformations and functions. To demonstrate the effective- ness of graph prompt learning in real downstream tasks, we offer the following theorems further:
Definition (Bridge Set and e-extended Bridge Set). The bridge set of a graph G is defined as:
Bg = BG (G)) =
where Fg. is the frozen graph model from the pre-training task, and C' is the optimal function for the downstream task. The e-extended bridge set of G is a relaxed version of the bridge set, which is defined as:
Theorem 3. Given a GPF-like prompt vector pw, if GCN model Fg has non-linear function layers but the model's ' weight matrix is row full-rank, then there exists an optimal w for any input graph G such that PG BG.
B-Ba = (G, le= |Fo [G,) C(G) se)}.
Achieving a transformation exactly equivalent to C(G) is highly non-parametric and nonlinear. Finding the corre- sponding Gbri or even the bridge set for any Goni involves solving complex, high-order nonlinear equations. This task becomes virtually impossible manually, especially if the pre-training method integrates multiple tasks or intricate mechanisms. Fortunately, graph prompts Pa can be viewed as parameterized fitting for these operators and they usu- ally contain very lightweight parameters, which dramati- cally simplify the search space compared with manually designed strategies. The effectiveness of graph prompting methods hinges on their ability to approximate these opera- tors whether they can uniformly project G in the dataset into the bridge set Bg, or at least map them into the extended bridge set with small upper error bound e*.
Theorem 4. Given the Ml-in-One-lie prompt graph SG (a subgraph containing prompt tokens and token structures), if GCN model Fo does not have any non-linear transfor- mations, or has non-linear layers but the model's 's weight matrix is row full-rank, then there exists an optimal w for any inpul graph such that (G) E Be-
Theorems 3 and 4 are proved in Appendix A.3.2. Although we' 'e only added the row full-rank condition, these two theorems significantly expand the applicability of Theorem 2. According to Pennington & Worah (2017), well-trained models mostly contain full-rank matrices, which can be easily guaranteed by some tricks like orthogonal initializa- tion, He initialization, etc. Raghu et al. (2017) also find that a full-rank parameter matrix in the model usually indi-
4

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
cates stronger expressiveness. Intuitively, a weight matrix in the graph model usually indicates how to project the input graph into some latent embedding for the downstream task. According to the basic knowledge of linear algebra, when the weight matrix is row full-rank, we can always restore the input from the output. That means we can always find an appropriate input format to meet various downstream requirements. Therefore, from a practical empirical per- spective, we assume that in most cases, both GPF-llie and All-in-One-like frameworks can achieve seamless pro- jection of G' into Bg, demonstrating the effectiveness and rationality of graph prompting.
transform each graph G in the downstream dataset into its corresponding Bg or e-Bg (for small c). If such uniform upper bound E" exists, it would theoretically validate the excellent performance of graph prompting in general down- stream tasks, confirming the rational utilization of powerful upstream models.
For a batch of graphs, the complexity and information con- tained in the graph prompt become particularly important. For instance, the increased number of prompt vectors in GPF (a.k.a GPF-Plus) and the selection of a larger size of the prompt graph in All-in-One greatly expand the trans- formation space of graph G under prompt P (see Dp(-) in section 3.3). A larger transformation space corresponds to a smaller e upper bound. In our theoretical analysis, we found that when the prompt takes an overly simple form, the capability of prompt learning is limited. This manifests as a theoretical lower bound of the bridge set extension as suggested in Theorem 6:
For the cases where weight matrices are not full-rank, we have found that the error value (c) of the extended bridge set (e-Bc), into which the prompting framework can map G, is positively correlated with the distance of the graph model parameter matrix from being full-rank. However, a consistent upper bound does exist for the error of the extended bridge set when the matrix rank is determined. This means that even in some extreme cases, graph prompt learning can still guarantee certain level of performance without experiencing extremely unexpectedly poor results:
Theorem 6. For a GCN model Fo. for GPF with a single prompt vector or All-in-One with a single- token graph prompt, given a batch of graphs G = [GI,... "......,n,,, the root mean squared error (RMSE) over (E1,-.., has a lower bound e such that RMSE(G,," ,G,)2
Theorem 5. For a GCN model Fg, assume at least one layer's ' parameter matrix is not full rank, for GPF or All- in- oneOne prompt, there exists an upper bound of e such that for any input graph G, there exists an optimal w where (G) E e-BG, with S {(0) k(G), where {(0) is an implicit function corresponding to the model and kGG) is an implicit function corresponding to graph G, denoting the two parts of the error boundaries.
Theorem 6 is proved in Appendix A.3.4 and we also give the detailed formulation of c in the proof, from which we can find that e" is related to graph data and the prompt to- ken. This indicates that when the downstream task dataset is relatively large, we must correspondingly increase the trans- formation space of the prompt to better utilize the model's capabilities, which also aligns with existing empirical obser- vations (Liu et al., 2021). Then our next question is: With the increase of graphs, how does graph wwtpppttcooppppeepp. complexity increase with e error bound increased?.
We recommend the readers go further to see the details of Theorem 5 as proved in Appendix A.3.3, where the upper bound has two terms: one part (C(0) is only related to the model itself and increases as the model's expressive power decreases, such as increasing with decreasing rank; The other part (s(G)) is related to the complexity of the solution space of downstream task on the given graph. Note that this is the upper bound of the error, not the error itself. In practice, we use the graph prompt to approximate such solution space, which means a better prompt design makes the real error even less than this upper bound. In this way, in theory confirm, the
Intuitively, a good graph prompt should not increase its com- plexity faster than the growth of the dataset because in that case the effectiveness of prompt learning in practical applica- tions would be significantly compromised. Fortunately, we found that for relatively large datasets, the scale of prompts required for prompt learning is highly controllable with the number of needed tokens for the prompt almost constant, far from the increase of graphs. This explains why even with relatively large downstream datasets, as reflected in Sun et al. (2023a), empirical results using medium-scall prompts can still achieve excellent outcomes. Compared to fine-tuning the entire model parameters, Theorem 7 (see the proof in Appendix A.3.4) indicates why graph prompt- ing can achieve comparable or even better results with less parameter adjustment scale:
findings, by Sun et al. ......ee peeeeetie t.... ........ (2023a) mentioned in our motivation section.
.... ......... ww..............................
4.2 Extend the Error Bound Discussion to A Batch of Graphs
In Sections 3 and 4.1, we have proved that graph prompting frameworks can indeed fit graph transformation operators given a single graph, thereby exploiting model capabilities. However, in other cases, we often train the model via a batch of graphs and seek to find better performance over the whole graph dataset. Correspondingly, we should aspire to
Theorem 7. Given a GCN model Fg. an
graph prompt with multiple prompt tokens, and a dataset G with M graphs, there exists an upper bound denoted by
5

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
e, making an optimal Pw such that VG, E PG,, E 4-BG, and Vi G/M S 6" 6 can be further calcu-
lated as follows:
Cumulative Dit Detribation Femetions
Frobability Deasity Functions
M
A//M
Here for the M graphs in G, we first construct an opti- mal solution matrix according to function C. thus have: S = al) Then = S S E RafxM de- notes the correlation matrix of downstream solutions upon such graph dataset. The eigenvalues of V sorted by the de- scending order can be denoted as (A..... Au J. Then the upper bound c* can be treated as the mean square over the smallest M - k eigenvalues. In practice, the eigenvalues of V in datasets often exhibit an exponential decay (Johnstone, 2001). This explains the rapid decrease in error rate as k increases, proving that prompts are not only effective but also efficient. With the increasing number of graphs M in the dataset, the largest & (k < M) eigenvalues can almost explain most of the matrix, which means using small-scaled prompt tokens can achieve reasonably accurate results. This finding is also consistent with many existing empirical re- searches (Liu et al., 2023; Sun et al., 2023a; Wang et al., 2024; Zhu et al., 2024a).
Error
Figure 1. Real e distribution and fitted curves.
wy is the weight of the i-th node for graph pooling (e.g.. summation graph pooling means for any node i in Gbri. we have w; = 1); can be either 0 or -1 and depends on the original graph, graph prompt, and the bridge graph, the details of which can be seen in Appendix A.3.5. Here, we as- sume that B3 should follow an i..d. normal distribution with mean O and variance C. (we carefully discuss the rational- ity of this assumption in Appendix A.3.5): B ~ (O0 cln) where In is the n X n identity matrix and c is a positive constant. Then we theoretically find that c conforms to the Chi distribution (Xw):
Theorem 8. Given a GCN model Fg with the last layer parameter matrix having rank F-r (F is the graph embed- ding dimension, is the rank lost), input graph G. for the optimal w. (G) E e-Ba. If the Graph Embedding Resid- uals follow the i.i.d. normal distribution, then e follows a Chi distribution Xr with r free variables.
-T(F
4.3
Value Distribution of the Data Operation Error with Graph Prompt
In the previous sections, we established a theoretical upper bound of S c", allowing the graph prompt Pa to map given graph G into the e-extended BG range. However, the conditions to reach this upper bound are often difficult to meet, making the theoretical upper bound usually corre- spond to some corner cases which may be not that practical in processing empirical experimental analysis. To offer stronger practical guidance for researchers' general exper- imental purposes, the value distribution of (a.k.a "error range"), comes our next point of interest. The error range analysis indicates quantitative degree of the bridge set tension, which includes estimating the mean, and variance, and finding the approximate distribution pattern.
We give the proof of Theorem 8 in Appendix A.3.5. In the practical settings, the distribution of graph residual terms may slightly diverge from i.i.d. normal distribution, making the real distribution of a little different from standard XA- Besides, there is also a theoretical upper bound e", making the real distribution of more like a truncated X The statistical measures of this distribution can be easily obtained as follows:
Corollary 1 (Statistical Measures and Confidence Val- ues of c). The mean of is ev2 [ the variance is c² (r ( (((+++))22) and confidence values can be obtained through CTP using numerical methods or table lookup. where c is the sealing factor compared to the stan- dard distribution, and is the number of dimensions lost compared to full-rank matrix.
T(r/2)
Definition (Graph Embedding Residual Vector). Con- sider a graph model with Leaky-Rels as their activation function, we denote the graph embedding residual vector as B E RIxP where F is the graph embedding dimensions. Each entry of B is related to the bridge graph embedding, graph prompt, and the original graph, which is mathemati- cally defined as follows:
(T(r/2]]²
To further confirm our theoretical findings, we compare the real-world distribution of e with 4 commonly used distribu- tion patterns (Chi, Chi-square, Exponential, and Gamma). Figure/ 1 presents the fitting results and Table 1 shows the p-value significance, from which we can see that the Chi distribution provides the best approximation within non-
(5)
where a is the parameter of Leaky- Relu; usy is the j-th ele- ment in the i-th node embedding of the bridge graph Gurs;
6

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
Distribution
Notation
p-value
dataset, facilitating our study of the relationship between these features and We further conduct the experiments the real-world dataset in Appendix B, from which we can find similar observations.
Chi
X
0,65
Gamma
I'
0.23
Chi-squared
x2
0.04
Exponential
Exp
0.01
Model Settings: We utilize two GNN frameworks: GCN (representing linear models) and GAT (representing non- linear models). We limit our experiments to these two models as other models follow similar patterns. Unless otherwise specified, use a 3-layer GNN with Leaky- ReLU activation function and feature dimension F == 25. For full-rank matrix studies, we ensure each layer's matrix is full-rank (selected after pre-training). For non-full-rank matrix studies, we set the rank loss to by default. The default ReadOut method is mean pooling. For more de- tailed experimental settings, please check in the Appendix C. We open testing code at ht http//gtttbbb.c// com/ qua saazhoone hongwang dgow
Table 1. p-values w.r.t distributions
extreme range of 6.
4.4
Extend the Discussion from Linear to Non-linear
While our previous analysis focused on GCN or linear ag- gregation models that can be represented in the form of "diffusion matrices", many advanced models utilizing atten- tion mechanisms exhibit distinctly different characteristics. Their aggregation methods involve the computation of at- tention matrices, which in turn depend the node feature vectors of G. This can be considered as non-linear model W.r.t G's feature matrix. In our analysis, we use Graph At- tention Networks (GAT) as an exemplar, as the attention mechanism in GAT is a common component many non- linear models. Fortunately, the guarantees provided by our theorems do not differ significantly for these models. This indicates that even models become more non-linear and complex, graph prompting can still effectively harness the powerful capabilities of pre-trained models:
Loss(epsilon)
0.1
0.01
Froepe mangeettttdtGG
Frotd of 339h
Theorem 9. Let Fe be GAT model. If any layer of the model has full row rank parameter matrix, then for the All-in-One prompting framework, for any imput graph G, there exists an optimal w such that (G) E Bg. When the parameter matrix not full rank, there an upper bound <()) - (() making (G) e-BG, e S (()) x(G).
100u
Tranpe mutkeed All
Parad 21
Proad bao diil
1000
Epochs
We give a detailed proof in Appendix A.3.6. The above theorem demonstrates the robustness of graph prompting methods across different types of GNN architectures, in- cluding those with non-linear attention mechanisms. The consistency of these results with our earlier findings for linear models suggests that the fundamental principles of graph prompting remain effective even as we move towards
Loss(epsilon)
truepeiathbd:c00 GPP
Forad 111 of
Forad 211 Cf
more complex and non-linear model architectures.
Franpe
Forad Eli Bau
Forad Bau dil'
$1500
Experiments
Epochs
5.1 Experimental Settings
Figure 2. Convergence rate analysis. GCN (left) and GAT (right).
Data Preparation: We first confirm our theoretical findings on synthetic datasets because these datasets offer controlled environments, allowing to isolate specific variables and study their impacts. We generate these datasets by defin- ing the dimension of graph feature vector (F), average of graph node numbers (Navg), average of graph edge numbers (Eavg), ) and number of graphs in the dataset (M). These pa- rameters characterize both individual graphs and the entire
5.2 On mapping to BG with single graph
According to Theorems 3, 4, and 9, error-free projection can be achieved in full-rank situations. Here we investigate con- vergence properties with a maximum of 5,000 epochs. Fig- ure presents the results for GPF and All-in-Ome prompts with GCN and GAT, respectively. From the results we can

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
find that for single-graph, full-rank matrix scenarios, both GPF and All-in-one approaches show loss converging zero, which is consistent with our theoretical findings.
theoretical analysis in section 4.1.
5.4 On mapping c-Bg with multiple graphs
Theorem 6 discusses a lower bound on the RMSE over the errors multiple graphs with single prompt token. In this section, conducted experiments the number of graphs in the dataset w.r.t the empirical minimum error. As shown in Figure 4, the minimum error shows an upward trend and then tends to saturate, which is highly consistent with the findings in Theorem 6.
5.3 On mapping to c-Bg with single graph
Theorem 5 states that in non-full-rank situations, there exists an upper bound on the error. Here we extensively examine the relationship between various parameters and the enror upper bounds in the context of non-full-rank matrices given a single graph. Since showing this upper bound in prac- tice is usually intractable, we fix all other parameters and employ five pre-trained models. For each fixed pre-trained model, we conduct experiments and repeat each experiment 30 times. Then take the maximum loss from these repe- titions as the approximation to the upper bound.
Empirical Min Error
Empirical Max Error
Empirical bla t
34
Drcept natkei Proepe
Graph Number
Rank lost
Feature Number
Figure 4. raagee with simple prompt token
(a) Error w.r.t matrices rank.
(h) Feature Number Vs.
Theorem 7 suggests that for the graph prompt with multiple tokens and multiple graphs, small & tokens is sufficient to achieve good performance. In particular, we wish to see how the error (loss) changes as M (number of graphs) increases while remains fixed, and its counterpart case: how does the error change as i increases while M remains fixed? Here we explored the relationship between the number of prompt tokens, the number of graphs in the dataset, and the error. We present experimental results in Figure 5a and Figure 5b, which indicate two surfaces. From these figures we can find that both GPF and All-in-One show similar effects: when the number of prompt tokens exceeds 10, the error becomes relatively small. As the number of prompt tokens increases further, the loss does not significantly decrease. Similarly, when the number of graphs increases and the number of prompt tokens is large, the decrease in error is also not that obvious.
Empiriaal Max Error
Empirical Max
Graph Size
GNN Layer
(c) Graph Size vs.
(d) Layer Number vs.
Figure 3. epsilon range analysis
The parameters interest include weight rank (Figure 3a), node feature dimension (Figure 3b), graph size (Figure 3c), and model layer number (Figure 3d). Here All-in-One-Pla extends All-in-One model by treating the inserting pattern as free parameters. and GPF-plus extends GPF by adding more than one tokens. Intuitively, with the increase data complexity (e.g., larger features and graph size), the upper bound becomes larger in general. As the graph model be- comes more complicated (e.g., layer number increase), the projected space becomes larger making the error bound in- tend to be smaller. When weight rank declines, the model's capacity intends to poor results, making the error bound increase. More advanced graph prompts (e.g., All-in-One) usually have lower error bound than the naive one (c.g., GPF). These observations can be naturally inferred from our
6 Conclusion
This paper addresses the theoretical gap in graph prompt- ing by introducing comprehensive framework from data operation perspective. We introduced the concepts of "bridge sets" and "e-extended bridge sets" to formally demonstrate that graph prompts can approximate graph transformation operators, effectively bridging pre-trained models with downstream tasks without retraining. Our con- tributions are threefold: first, we established guarantee the-
8

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
consequences of our work, none which we feel must be specifically highlighted here.
Mean Value
Acknowledgmentss
This research is supported by project #MMT-p2-22 of the Shun Hing Institute of Advanced Engineering, The Chinese University Hong Kong, and by grants from the Research Grants Council of the Hong Kong Special Administrative Region, China (No. CUHK 14217622).
Nunbber Frongt
Number of Graples
(a) GPF Plus
References
Ben-Tal, A. and Nemirovski, A. Lectures on modern con- vex optimization: analysis, algorithms, and engineering applications. SIAM, 2001.
2014
Mean Value
Boyd, S. and Vandenberghe, L. Convex optimization. Cam- bridge university press, 2004.
Diao, C., Zhou, K., Liu, Z., Huang, X., and Hu, X. Mol- cpt: Molecule continuous prompt tuning general- ize molecular representation learning. arXiv preprint wrXiv:221..06114 2022.
Namber Prompt
Number of Graphi
Fang. M., Zhang, Y., Jiang, K., Zhao, K., Xue, Q., Zheng, B., Qin, G., and Zhang, X. Graph prompt learning: To- wards generalization of graph neural networks for out- of-distribution data. In Proceedings of the 31st ACM International Conference Information & Knowledge Management, pp. 442-452, 2022.
(b) All in one
Figure 5, range based on multiple graphs analysis
orems confirming that graph prompts can simulate various graph data operations, explaining their effectiveness in align- ing upstream and downstream tasks. Second, we derived up- per bounds on the approximation errors introduced by graph prompts for both individual graphs and batches of graphs, highlighting how factors like model rank and prompt com- plexity influence these errors. Third, we analyzed the distri- bution of these errors and extended our theoretical findings from linear models like GCNs to non-liness models such as GATs, showcasing the robustness of graph prompting across different architectures. Our extensive experiments validate these theoretical results and confirm their practical impli- cations, demonstrating that graph prompts can effectively leverage pre-trained models in various settings. By provid- ing solid theoretical foundations, our work not only explains why graph prompts work but also guides the design more effective prompting techniques. This empowers researchers and practitioners utilize graph prompts with greater confi- dence, potentially leading more efficient and generalized graph neural network models across diverse applications.
Fang, T., Zhang, Y., Yang. Y., Wang, C., and Chen, Uni- versal prompt tuning for graph neural networks. Advances in Neural Information Processing Systems. 36, 2024.
Gasteiger, J., Weißenberger, S., and Günnemann, S. Diffu- sion improves graph learning. Advances in neural infor- mation processing systems, 32, 2019.
Guo, Y., Yang. C., Chen, Y., Liu, J., Shi, C., and Du, J. A data-centric framework to endow graph neural networks with -isto--distribution detection ability. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 638-648, 2023.
Hornik, K., Stinchcombe, M., and White, H. Multilayer feedforward networks are universal approximators. Neu- ral networks, 2(5):359-366, 1989.
Hotelling, H. Analysis of complex of statistical variables into principal components. Journal of Educational Psy- chology, 24(6):417-441 1933.
Impact Statement
Huang, Q., Ren, H., Chen, P., Kržmane, G., Zeng, D., Liang, P., and Leskovec, J. PRODIGY: Enabling In-context Learning Over Graphs. In NewrIPS, 2023.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
Johnstone, M. On the distribution of the largest eigenvalue in principal components analysis. The Annals of statistics, 29(2):95-337,, 2001.
Sun, X., Zhang, J., Wu, X., Cheng, H., Xiong, Y., and Li, J. Graph prompt learning: A comprehensive survey and beyond. arXiv preprint arXiv:2311. 2023b.
Jolliffe, I. T. and Cadima, J. Principal component analysis: review and recent developments. Philosophical transac- tions of the royal society A: Mathematical, Physical and Engineering Sciences, 374(2065):2015222) 2016.
Tan, Z., Guo, R., Ding, K., and Liu, H. Virtual Node Tuning for Few-shot Node Classification. In KDD, pp. 2177- 2188, 2023.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. arXiv preprint arXiv: 1XX1:17100.1003 2017.
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint arXiv: 1609.029079 2016.
Wang, Y., Xiong, Y., Wu, X., Sun, X., and Zhang, J. Ddiprompt: Drug-drug interaction event prediction based on graph prompt learning. CIKM, 2024.
Liu, X., Zhang, F., Hou, Z., Mian, L., Wang, Z., Zhang, J., and Tang, J. Pre-training graph neural networks: A comprehensive review, arXiv preprint arXiv:2102.00611, 2021.
Yang, H., Zhao. X., Li, Y., Chen, H., and Xu, G. An Empiri- cal Study Towards Prompt-Tumee for Graph Contrastive Pre-Traine Training in Recommendations. In NeurlPS, 2023.
Liu, Z., Yu, X., Fang, Y., and Zhang, X. Graphprompt: Uni- fying pre-training and downstream tasks for graph neural networks. In Proceedings of the ACM Web Conference 2023, pp. 417-428, 2023.
Yang, Y., Xia, L., Luo. D.,, Lin, K., and Huang, C. Graphpro: Graph pre-training and prompt learning for recommen- dation. In Proceedings of the ACM on Web Conference 2024, pp. 3690-3699 2024.
Ma. Y., Yan, N., Li, J., Mortazavi, M., and Chawla, N. V. HetGPT: Harnessing the Power of Prompt Tuning in Pre- Trained Heterogeneous Graph Neural Networks. arXiv preprint, 2023.
Zhu, D.-.., Dai, X.-Y.. and Chen, J.-J. Pre-train and learn: Preserving global information for graph neural networks. Journal of Computer Science and Technology, 36:1420- 1430, 2021.
Morris, C., Kriege, N. M., Bause, F,, Kersting, K., Mutzel, P., and Neumann, M. Tudataset: A collection of bench- mark datasets for learning with graphs. In ICML. 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL www. www. www.graphhearning.. io.
Zhu, J., Ding, Z., Yu, J., Tan, J., Li, X.,, and Qian, W. Relief: Reinforcement learning empowered graph feature prompt tuning. arXiv preprint arXiv:2408.03/11 2024a.
Zhu, Y., Wang, Y., Shi, H., Zhang, Z., Jiao, D., and Tang, S. Graphcontrol: Adding conditional control univer- sal graph pre-trained models for graph domain transfer learning. In Proceedings of the ACM on Web Conference 2024, pp. 539-550, 2024b.
Pennington, and Worah, P. Nonlinear random matrix the- ory for deep learning. In Advances Neural Information Processing Systems, pp. 2637-2646, 2017.
Raghu, M., Poole, B., Kleinberg, J., Ganguli, S., and Sohl- Dickstein, J. On the expressive power of deep neural networks. In international conference on machine learn- ing, pp. 2847-2854. PMLR, 2017.
Rockafellar, R. T. Convex analysis. Princeton University Press, 1970.
Sun. M. Zhou, K., Hc, X., Wang, Y., and Wang, X. GPPT: Graph Pre- Pre-Training and Prompt Tuning to Generalize Graph Neural Networks. In KDD, pp. 1717-1727, 2022.
Sun, X., Cheng, H., Li, J., Liu, B., and Guan, J. All in one: Multi-task prompting for graph neural networks. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1894-1904, 2023a.
10

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
Appendix
H H =o (AH (AH)W
(6)
The appendix of this paper is organized as follows: Ap- pendix A presents the detailed theoretical content on the main findings in the paper. In order to reduce the bar of reading this content, we first give some preliminaries and definitions in Appendix A.I, followed by fundamental lem- mas (Appendix A. that will be used prove our theorems. In Appendix A.3, carefully prove the theorems in the main body of this paper, followed by further mathematical discussion in Appendix A.4. Beyond theoretical analysis, Appendix B presents additional experimental results on the real-world datasets, which have similar observations to the main experiments in the paper. Appendix C introduces more details on the settings of the experiment.
where À D 1/2ADDD----- matrix, H()) is the node feature matrix at layer W is the learnable weight matrix, and a is nonlinear activation function.
the normalized adjacency
Graph Attention Networks (GAT) (Veličković et al., 2017) enhance GCNs by introducing attention mechanisms to weigh the importance of neighboring nodes during aggre- gation. In the simplest form of self-attention, the attention te.. coefficient between node j and node k is based on the inner product of their feature vectors:
Cyk H
A Theoretical Analysis And Proofs
exp(exk)
ayk = Σ EmENG) exp(emm)
(8)
Reading Guideline: Appendix A "Theoretical Results and Proofs" is divided into four subsections:
H (1+1) o
Σ KEA(()
( (wi))
A.1 Definitions and Preliminaries: Readers are ad- vised to initially skip this subsection. serves as reference for unfamiliar terms encountered later in the text.
where N(j denotes the neighbors of node j. azk is the normalized attention coefficient, and W is the learnable weight matrix at layer i, Hj is the embedding vector of the j-th node. This mechanism allows the model to focus on the most relevant neighbors when updating node representa- tions.
A.2 Fundamental Lemmas: These properties are sential components for proving the main theorems. We will clearly express what each lemma demonstrates. Readers are recommended to refer to this subsection when encountering these lemmas while reading the theorem proofs.
Preliminary 2 (Pre-training and Fine-tuning vs Pre-training and Prompt).
Pre-training and Fine-tuning (Zhu et al., 2021 Iinvolees two stages: first, a model pre-trained on a large dataset to learn general representations, and then it is fine-tuned specific downstream task.
A.3 Detailed Proofs of Main Theorems: This subsec- tion is recommended as the primary focus for readers. It contains the core ideas behind why prompts work, even though some lemmas may be required for com- plete understanding.
Formally, let Fg. be the pre- pre-trained model and C(-) be the optimal mapping function that maps the original graph to the embedding vector of the downstream task (i.e., can be parsed to yield correct results for Gori the downstream task)
A.4 Additional Mathematical Lemmas: This subsec- tion includes purely mathematical lemmas encountered during the proofs in A.2 or A.3, These lemmas are not directly related to GNN models or prompts. Readers are advised to review this subsection after reading the previous content.
Fine-tuning aims adjust the model parameters from 6* to (# so that:
Fgr (Gon) - C(Gon).
(10)
A.1 Preliminaries And Definitions
Pre-training and Prompting keeps the pre-trained model parameters fixed and instead modifies the input data to bridge the pre-training and downstream tasks. Specifically, it seeks transformation from the original graph Gon to prompt-enhanced graph Gbai such that:
A.1.1 PRELIMINARIES
Preliminary (GCN and GAT).
Graph Convolutional Networks (GCN) (Kipf & Welling, 2016) perform convolution operations on graph-structured data by aggregating feature information from a node's 's neigh- bors. The recursive update rule for GCN layer is:
Fg. (Gbn) C(Gon).
(11)

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
This approach leverages the frozen pre-trained model by adapting the input data through graph prompts, eliminating the need to fine-tune the model parameters.
convenience, in the proof section below, we often the equivalent form of All-In-One similar Equation:23.
Preliminary 4 (Diffusion Matrix).
Preliminary 3 (GPF and All-in-One).
Diffusion Matrix (Gasteiger al., 2019) plays a crucial role in representing the diffusion process on graph. Specif- ically, many GNN architectures can be expressed using the following formulation:
Graph Prompt Frameworks introduce learnable modifica- tions to input graphs to enhance the performance of frozen pre-trained GNNs on downstream tasks. Two primary frame- works are prompt token vectors like GPF/GPF-Plus (Fang et al.. 2022) and prompt subgraph like All-in-One (Sun et al., 2023a).
H-S.X.W,
(16)
GPF (Graph Prompt Feature) adds a prompt vector to each node's feature vectors. Let = {p}. p E RFx1 be the learnable prompt vector, then the updated node features are:
Where: S is the diffusion matrix, derived from the graph's adjacency matrix and model structure, which governs how information propagates across the graph. X is the original node feature matrix. W is the learnable weight matrix asso- ciated with the GNN layer. H is the node feature embedding matrix after message transformation and aggregation.
[x = X +p
(12)
The original graph G = A) becomes the prompt- enhanced graph G = (X,, The prompt vector p optimized minimize the loss on the downstream task:
A.1.2 DEFINITIONS
We provide a glossary and default symbols meanings here for the reader's convenience.
p- = arg min P
Eram (Fo-(Pa GE9
(13)
A.2
Fundamental Lemmas
This lemma serves a foundational component for proving the theorem. However, readers may choose to skip the lemma initially and return to it when it is referenced in the theorem's proof.
GPF-Plus adds combination of multiple prompt vectors to each node's features, with different combinations for
different graphs.. Let = P1,-.. . Pk: Q, where p; E Fx1 represents learnable prompt vector, and Q E [R- is matrix in which the i-th row corresponds to the combination coefficients of the k prompt vectors for graph i. Here, M denotes the number of graphs in the dataset Ω. Let P =
Default Case By default, we consider the GNN model as a surjective mapping operator from the graph set {G} to RF, obtained after pre-training tasks. This operator can provide sufficient information express the correct results of the graph in the pre-training task. (For instance, through task- specific head mapping to the likelihood of 0/1 decision.)
The node features are updated in such a way:
X + +
(14) Notations Here and in subsequent related content, we use Fg to represent a GNN model whose aggregation process can be described by a diffusion matrix S. Here, is derived from the model type and the adjacency matrix A. For in- stance, GCN, S = A+ where 5 controls the strength of the self-loop for gathering information from the node itself. The graph aggregation process is described as:
The original graph G; = (X, A) becomes the prompt- enhanced graph G = A).
All-in-One incorporates entire prompt subgraphs into the original graph. Let P E p represent K learnable prompt token vectors, and Ai E 1,x1 denote the internal adjacency among prompt tokens. The connections between prompt tokens and original nodes are defined by a cross adjacency matrix Acmo E (0, 1] A The prompt- enhanced graph is:
H = o ((((S-((())) ((i W)
(17)
Where (0) is exactly the node feature matrix X, and H6) is referred as the i-th order embedding matrix. With- out loss of generality, we analyze the non-linear function using Leaky ReL.U. Other non-linear functions such as sigmoid can be analyzed similarly.
G~ = (AUA X XUD).
(15)
All-in-One optimizes the prompt tokens and their connec- tions to adapt the pre-traines model to downstream tasks without altering the model parameters. For computational
Denote the transformation space of P. and G by Dr(G) = (Pw E Rlw) where w is the parameter
12

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
Term
Explanation
Bridge Set Be
Bg [Gp =
e-extended Bridge Set e-Bg
e-Be {Gp [1
C(G)
Adjacency matrix
A square matrix used to represent finite graph, where Aij = 1 if there is an edge from vertex to vertex j. and otherwise. The matrix equivalent to graph aggregation in GNNs.
Diffusion matrix
Span i-th order embedding matrix
For a set V, we say "p spans V if can take any value V.
The embedding matrix after iterations of message passing and aggregation in GNN.
Cone
C. A set S such that for any æ, y/ E S and [0, 1]. az + (1 aly E S. The smallest convex set containing a given set of points.
A set C such that for any C and 2
Convex set
Convex hull
Graph Embedding Residual Vector
vector representing the additional error in graph fitting due to non-linear components. For details, refer to the related A.3.5.
Table 2. Glossary
Symbol Gori
Description
The original graph without prompting.
Po
Graph prompting method with parameter w.
C(Gori)
The optimal embedding vector for the downstream task. C(-) can be understood as the optimal downstream task model.
Gbrr
The bridge graph that can be used obtain C(Gors) using the original model.
Gp
The graph after prompting.
G
The graph after prompting with parameter
Represents the extent of Bridge set expansion, i.e. the "error."
Generally represents the number of layers in the GNN. Represents the dimension of the graph feature vector.
F
N
Represents the number of nodes in the graph. Represents the number of graphs the dataset f
M
Represents the aperture the convex cone, which can be understood as the maximum opening angle.
Table 3. Symbol Table
of method P, |س] denotes the dimensionality of the param- eter and P represents either GPF All In One prompt method. We denote Pw(()) as Gw. and the corresponding diffusion matrix and node feature matrix S and after prompt as S_, and X., respectively.
Here, Fo(Gw) can be expressed in formula form
Fo(Gw) Red W))
(19)
= ReeadOu((H(()))
(20)
Hence, the graph embedding vector obtained from graph Go prompted by P.,, after passing through the GNN model Fg can be denoted as (G().).
Where, the dots (...) indicate that the parentheses nested times, representing iterations of the message passaging and aggregation. is the number of layers. (m))
Then, we can take each graph G. from the transformation space (G) and pass it through the GNN model F, to obtain the corresponding embedding vector. These embed- ding vectors can collected into set, the transformation embedding vector set:
is the n-th embedding matrix.
ReadOut process is viewed as the linear combination of the embedding matrix H. i.e. ReadOut( (7))) = w (()),, where is determined by the pre-trained model.
Specifically, we denote the process of obtaining the n-th order embedding matrix (i.e. final embedding matrix) as:
(Fo() for all G. E Dr(G))
(18)
Ko(Gw)) (n)) (.S( (X. .) (21)
13

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
A.2.1 ON THE RANGE OF GRAPH EMBEDDING MATRIX AFTER GRAPH PROMPTING, ONE PROMPT NODE CASE
spans R(W). Therefore, R2 + c.p T R(W), and spans R(W). For i & I, c= 0, the i-th row of R + cp' is simply R
Lemma 1 (Transformation of Graph after Prompt).
Hence, R+ cp" can be written in the form of R' + (AR+ ep ). where p spans R(W), R' represents the matrix with the rows whose index & I. and all other rows set to zero. R-
Here we consider GPF and All-in-One methods. Without loss of generality, we assume that the prompt subgraph in All-in-One has only one node.
Noted that every row of AR + cp with index i E I, such row vector spans R(W)., as shown above, regardless of what the specific matrix A is. Hence, the expressive power of graph prompting does not fundamentally differ for different A R. vectors (i.e., if the same embedding vectors can produced through Readout, we don't distinguish the specific form of the matrix), we can simplify AR into cpò where is exactly the same the in the assumption in the lemma, Po E R(W) is vector with the same size as c. More detailed discussion refer to A.4. In this way, the calculation is greatly simplified.
For GPF, the prompt vector is added to each node of graph G. while the topological connections of the graph remain unchanged. Therefore:
We claim that from the perspective of embedding
S, X + INP
(22)
Where N is the number of nodes in the graph, p is the prompt vector, p E Rf, F' represents the dimension of the parameter vector, 1y is a vector E R.V with every compo- nent to be 1.
For All-in-One, the prompt subgraph is connected to graph G in a parameterized way, i.e. there exist parameters that control the connection relationship between any two nodes in the prompt subgraph and the original graph. defined in I.I.I). Therefore:
Now, consider adding a nonlinear function o() Leaky-ReLU(-). We examine ofR' AR + cp ):
Scenario 1: When W has full row rank, i.c., p_. o(p)) spans RF. In this case, for each row, we have:
For i E
Sw Sa= 55=(1 (s S
X 0F
X_
CN+1P
oR + +R++ a(R + t.pp + +.p)))
(23)
=o(a(p T + + T)
Where / E RV is a column vector, 4 2 Vi (1,....,4 N..
ēN+1 is a vector E RN++ with (N+1)-th component to and others to be Of E Rf with every component to be 0. Please note that we can shift the number of nodes(N)) the original number of nodes at this point can be denoted as N 1, to maintain consistency format with GPF case.
since R2 = 0. After the Leaky- transformation,
(c + + T) can still span Rf, Let's denote ap +
Po as p" i.e. (p T + +po ))= =pp"
For I
In summary, the transformation of X can be denoted as:
o(R + tcp + c.pp)) oRRTT)
X X Tp where c,
(24)
we use R', to denote o o
Where e can be referred to as the coefficient vector, X can be either X the natural extension of X:
X
In conclusion, oRR' AR + cp can be written as A' + cp" 'T, where p. p' spans R². Note that the property of and p' is the same and there is a natural bijection between them as pointed out A.4. Without causing confusion in notation, we can use p to represent p' here.
OF
Lemma 2 (Range of Embedding Matrix after Nonlinear Transformation).
Consider a weight matrix W E RFxF, and R(W) denote its row space. Suppose there exists matrix R such that each row of matrix R is taken from the space R(W). Let be a vector with 2 O, and let Z be the set of indices where takes strictly positive values. Let p be vector spans (i.e. could take any value in R(W)).
Scenario 2:
When W is not full rank, p spans R(W) space. In this case, row-wise, similar to Scenario I:
a R' + cp T) R'' + cp
(25)
where the set of all possible values of p' is V.. defined as:
Now, we consider R + TT For E I, the i-th row of R + cp is: R. + c.p. where e > 0. R₁ E R(W), p
V. = (Leaky-
R(W))
(26)
14

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
Lemma 3 (Range of Embedding Matrix after Prompt, Sin- gle Layer Case).
where C2 Si [cy]s 0. Compared with the equation in lemma 3, find only R has been replaced by Ri W2. and components remain unchanged, so this lemma can be used again. Hence, we have:
Consider single-layer GNN model Fg. Kg represents the embedding process for obtaining graph embedding matrix H. Then, have:
Ko(Pu(G)) = o(S
o -(s
= (p]
(31)
XW + Spep W) = =o(ltcpp"))
where p spans RN
Iteratively, complete the entire aggregation processes of the GNN, and obtain:
Where R = SW,W each row of R is a vector in the row space R(W). spans R(W) since p spans IR- (c) of S is non-negative, the sum of each column in S. is strictly greater than 0 and the initial value of is either ēN or 1l. Note that the number of positive terms increases in c.)
c. di 2 0, p JW = p" Here, p' since each element
(o(PL(G)) R, + c,p'
(32)
where p spans the R. (This formula can represent the expressiveness of prompt Pa in the full-rank case)
According to lemma 2, al + c'p'T) can be written as R' + c'p, Here R' represents the element-wise Leaky- ReLu of the rows of R with index i E I and other rows take 0.p, represents p (p spans R*)) if W is of full row rank; P; represents p'T (p' spans Va) if W is non-full-rank,
We can interpret this result as follows: (1) R is related to the embedding matrix the original graph G (2) C.P describes the additional range of the expression of GNN model after adding prompt.
Remark 1.
V. = (Leaky-ReLU(v)) v E R(W)).
A.2.2 ON THE RANGE OF GRAPH EMBEDDING
Hence, conclusion, we have: Ko(Px(G)) A + c'pp"
MATRIX AFTER GRAPH PROMPTING, MULTIPLE PROMPT NODE CASE
Lemma (Range Embedding Matrix after Prompt, Mul- tiple Layer Full Rank Case).
Lemma 5 (Range of Embedding Matrix after multiple prompt, Single Layer Case).
Consider multiple-layer GNN model Fg. Then, we have:
We are considering single layer GNN Fe here.
Ko(Ga)
.W,))
(27)
For the GPF or All one Prompt Method, we can use the following uniform formula: we have independent prompt vectors p. IR (or equivalently & prompt nodes with p: its node feature), which form a k F matrix P, where
According to lemma 3, we have:
(S. = Re' c'p..
(28)
P
Denote by M the number of graphs in the
We considering the full-rank case, i.c. W is full-rank matrix, according to lemma 3, we should take the equation for the full-rank case, which is:
PP
dataset Q. There exists an M & coefficient matrix Q, each vector of this coefficient matrix, denoted Q, R express how to linearly combine these k vectors to add them to ith. graph, i.e.:
a (S.PW = TIP
(29)
where p spans N. [c,]: 2 0.
Giw - (Aw, +c. (AC
For this output, consider:
According to lemma 3, the embedding matrix for the in graph
(S, +cp T)W)) = R Tc
(30)
15

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
H. = k
+c..Q.))Wa)
RR" Q
=Si, + +1Q, P)W)
Where spans R
=(R+ Q
Iterativly applying lemma 5 times, we obtain:
-o(R + c1.PP
Rt' + cr.P'
Ko(Gi,w) H7!)) R((n) + Cn,P! = R(m) + Q2
Where pl spans RP. (Implicit assumption is W is full rank. we are discussing the upper limit of the expressive power of graph prompting, we should use the full-rank model with stronger expressive power)
where P spans R and Q spans RMxK
In summary, for multi-layer GNN with full-rank W matri- ces in each layer, and for a dataset Q with multiple graphs and use multiple prompts P, we have:
As discussed in lemma 2, we are considering from the per- spective of embedding vectors. We claim that we can write P = (Q1) T P' where Q'; denotes the in row of Q', Q' is a linear combination coefficient matrix, which is mapping of Q. p' spans R which mapping of P. More detailed discussion is referred to A.4.
(G = R(n) + c R + QT P
Without causing confusion in notation, we can directly use P. Q to denote P', Q' here.
where P spans REXP, Q spans RMxk for any i E [l....,M,
In summary, for a single-layer GNN with multiple prompts, the embedding matrix takes the form:
A.2.3 ON THE RANGE GRAPH EMBEDDING MATRIX AFTER GRAPH PROMPTING, NoT FULL-RANK CASE
H, = K(Gw,) = ft' C..
Lemma 7 (Range of Embedding after Prompt, Multiple Layer Non-Full Rank Case).
where for any (1...., M). P: = QiP, and R' is de- fined consistently with Lemma 3.
We consider multiple-layer GNN model Fg with poten- tial non-full-rank weight matrix.
Lemma (Range Embedding Matrix after Prompt, Mul- tiple Layer Case).
We have:
We now consider a multiple-layer GNN model. For this model, we have:
= o(5 .W)
(33)
According to lemma 3, we have:
Ko(Gi,w)= !1
(SS. = R2' c'p.
(34)
where, according lemma
Since we are considering the non-full rank case, according to lemma 3, we should consider the non-full rank equation:
a (S = (XS..
TT
a a(S.P.W) R cpp
(35)
with p Q.P, and P is the collection of k prompts, spans R space.
where spans the set V1 defined in lemma 3.
At this point, we can consider iG equal to zero. Since, for GPF, co = 1,, and the monotonicity of e implies that each component of the vector strictly greater than O. For All-in-One, c êx. We have S., [Ny] where
This form is consistent with lemma 5, except is replaced by R'' and cu is replaced by C1 Applying this result again, we get:
16

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
also be in the convex hull of cone surface V We name such convex hull be Cj and further, Co is convex cone. Based on lemmal2, iteratively, we have each row of H should also be in the convex hull C of cone surface V
SNN (NNW = sv. we assume >> 0 component-
SN
Wise(This can be achieved by adjusting parameters in All in one), then c' is component-wise
O.
Recall that R2 only preserves rows where the corresponding component of c = 0. Hence, Ri can be considered to be zero.
We conclude the following: For any graph G, each row vec- tor of the embedding matrix H(m), obtained after applying the GNN model F8 G. lies within specific convex cone, whose surface is exactly Va mentioned in lemma 7
For this output, we consider:
Remark 3. Lemmna 8 characterizes the properties of each vector in the embedding matrix after it hus been pro- cessed by a non-full rank GNN model.
(S + c.p (i)")W)-=---- (SL(ci =o(cpp'') cop"
(36)
(37)
A.3 Proof of Theorem in the Paper
Here, p" = P W.. This demonstrates that: (1). p' spans W. (2). p' E R(W). Hence, the set of the range of p' is only a linear transformation Va i.e. V.W. The set of the range of p" operating Leaky-ReL.U to the set V.W, i.c oVV2W), W), denoted by V2.
A.3.1 BRIDGE GRAPI EXISTENCE THEOREM
Proof of Theorem 1
Proof. For given Gori and downstream task Tdow: the embedding vector corresponding to the downstream task is formally defined the embedding vector produced by the optimal downstream model for Taow which is thus uniquely determined.
Iteratively, We have:
FG = (n)
(38)
Given our previous definition for the default case A.2, the Fe discussed here a surjective mapping from the graph space {G} R.. According to the properties of surjective mappings, for this particular C(Gor) E RF. there must exist special graph Gua such that:
where p (a) spans Vaa Specifically, according to lemma 12, V is a cone surface, i.e., for any v E Va and X E RT, Av Vir
Remark 2. Choosing RG to be zero is to simplify the calcu- lation without affecting the theorem. Based on the principle that the minimum of the whole less than or equal to the minimum of a part, under this assumption, we have obtained that the upper bound of the error for the prompt satisfy our assumption is certainly the upper bound for the optimal prompt.
Fe (G(im = C(Gon)
(40)
Upon examining the definition of Ghri, we find that G.i Gbn Theorem is thereby proved.
A.3.2 ON ERROR-FREE MAPPING TO BRIDGE SET
Lemma 8 (Embedding Matrix Property, Multiple Layer GNN Non-Full Rank Case).
Proof of Theorem 3 and 4
We consider the GNN model Fg be multi-layered and could have not full-rank weight matrix. Then, the embedding matrix of graph G, according to the iterative formula of GNN, is:
Proof. We aim to prove that there exists an optimal parame- ter wp such that the transformed graph obtained through the graph prompting method Pa, (G) Bg. This equivalent to proving that there exists Wo such that Fo (P (Gori)) Fe (Gori) = C(Gor)). where the existence of Gori is guar- anteed by Theorem 1.
(o(G.) = (S(........... OS. X WV....WW W)) (39)
Consider a multi-layer GNN model Fg where each layer has full-rank matrices and non-linear function a-)). According to lemma 4, regardless GPF or All-in-One prompt method,
Let S X be denoted X'. Then X'W an N F embedding matrix where each row is in the row space of W. According to the properties of Leaky-ReLU and the definition of Vi1 (X'W) = Y' where each row vector is in the set V.]
have:
Ko (P. H()) = R(n) + cp
Then SY' = H', where each row of H' is a positive linear combination of rows in Y". Hence, each row of H' should
Where & 2 0, ||||| > 0. p spans RF. Ko(-) denote the
17

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
process of obtaining the embedding matrix, R! matrix IRNXF, which is related to the embedding matrix of the original graph G without prompting, w' denotes the parame- ter of the Prompt method.
Using the same readout method as in A.3.2, we have:
Fe (Ps = Σ we W.H. w cp =
Then, Fo Ps. (Grrr) = Readout H))). Considering the readout function as linearly combines the embedding vectors of nodes to n with certain weights: w [wi...., wn],
where spans surface of the convex cone (ŌC). Based on the properties of the cone surface, Ap is on the cone surface for any 0, so we have Fo (Gort)) spans the cone surface aC.
where w; O, as defined in A.2, we have:
To(Pa(Gori))) =
E w; (
Consider ( of this distance, according to definition 3, is the distance from an element in the convex cone to the cone surface, which is sin(O)[[u|], where 0 represents the angle of o to the surface.
I)ll. The minimum value
Then:
(orP)) wR()) + w/ Tcp Ro + Ap
This proves that [Fu Fo (Grridggl) has upper [Fo(Goridge]]
where RJ X= ((>> 0), since p spans RF,
bound, sin( where 0 is related to both and C.
know that (P. (Gor)) Rg + Ap T is surjective mapping from the range of w to Rf Mcanwhile, (obr)))) is a fixed vector in R
According to definition 4, we know that 0 S 4/2, where O represents the aperture of the cone C.
By the surjective property, there must exist an such that:
In summary:
|Fo -
(41)
Fo (wo (Gr))) = Fe (G(Griddge) = C(G)
[Pl Fo(Gori)l
(42)
S sin( [Goor)l)
(43)
This completes the proof.
= =inn(4/2) ||C(Gori)]l
(44)
A.3.3 ON ERROR UPPER BOUND ANALYSIS MAPPING TO BRIDGE SET AT SINGLE GRAPH LEVEL
The left part of the error upper bound (sin (a/n))) ) is only related to the model, while the right part is only related to the data (Gorz). This indicates that the error upper bound grows linearly with [[C(Gori)] by a coefficient, i.e. sin( (2/2).
Proof of Theorems 5
Since the features magnitude and number of node of the graph data in the dataset have upper bounds, I|C(Gori) ll also has an upper bound C.Hence, for the dataset, there is a uniform upper bound, which demonstrates that the model is effective and can utilize the powerful pre-trained model within certain error range.
Proof. (Prompt Error Upper Bound on Single Graph With GCN model with layers containing non-linear functions and possibly non-full rank matrices)
Consider the optimal wo such that the transformed graph Pan E B-B.. where the "error" c takes the minimum possible value: 60-
We aim to prove Theorems by showing that for any graph G there exists 6 such that:
A.3.4 ERROR BOUND ANALYSIS MAPPING TO BRIDGE SET AT MULTIPLE GRAPH LEVEL
Proof of Theorems 6
I (Gori) Fo(Grr)) [oo
d0
Proof. We prove this theorem by considering the sum of squared of e, where e denotes the degree the bridge set extension. For simplicity, we will refer to it as the "error". Consider dataset with M graphs. We use either a single prompt vector GPF or single node-prompted subgraph All-in-one approach. According to lemma 4, for each graph, we have the following formula:
According to lemma 7 and 8, for both GPF and All-in-One prompts, there exists a convex cone C' such that:
Kg(Gw) = (m) = cp
where p is on the surface of such convex cone, i.e., aC, and (o a vector inside the convex cone C.
Ko(G,, HH(") R(") + ccp
(45)
18

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
where c, have the subseript i to indicate that different graphs produce different c, p spans Rf Note that p does not have subscript i because single Prompt Vector is used for all graphs, despite different graphs having different diffusion matrices S and feature matrices X.
value("RMSE") I(G Gn) satisfies
T(G Gm)
(53)
M
min
XGI pll2/M)
(54)
After performing the ReadOut operation, we get:
i=1
|[C(G.) 1pP--//MMMMMM
(55)
FG( = w (H!" = =w -WTR R + wowwe c. Rdj A.p
(46)
Jmin
(47)
(56)
Where A; w TT., We can assume R is zero matrix without loss of generality as discussed in lemma 7.
Here, IGI,.... GM) is a lower bound that is independent of the value of w, but is related to the distances between C(G.). This proves that the capability of single prompt has an upper limit in this case, which proves Theorem
Now, consider the sum of squared "errors":
M Σ |C((G)) x Σ CI(/A))C(C)
Proof of Theorem 7
pll
Proof. We validate this theorem by minimizing the sum of squared of e, where denotes the degree of the bridge set extension. For simplicity, we will refer to it as the "error". Consider dataset with M graphs. We use k prompt vec- tors for GPF or k node-prompted subgraphs. According to lemma for each graph, we have:
(48)
M Σ CG,)) 2ll
(49)
The optimal Wo corresponds to correspond minimizing the following loss value.
H!!T) Ko(Gi,w) = R(()) P.
(57)
where P spans RAXFF, Q represents the combination coeffi- cients of different Prompts, and spans RR xk As discussed in Proof for Theorem 6, we assume R((") is zero matrix for simplicity.
M J= Σ (G.)
(50)
Which is the weighted sum of squared distances from to M different points in the space, denoted D((Cs, (G. (G.)), (AI)...,A,.)
After the ReadOut operation:
The optimal p is the weighted centroid of these n vectors (Cx, (G. as pointed out at (Boyd & Vandenberghe, 2004), i.e.:
Fo(G:) = w TTH, P
(58)
Since Q: spans R X, = Q4 also spans R (A, > 0). Thus, (G. spans the row space R(P), which (at most) a la-dimensional vector space determined by I independent prompt vectors. Consider:
MM (. ''=
(51)
IM
The closed-form expression for Jmin is:
M
M Σ [C(G)) - -p'1l? (59)
Σ IC Qf
Jmin Σ [C(G.) >,p"11
(52)
where p': spans the row space of P. Equation 59 is the sum of squared distances from n vectors to the vector space P. We want to minimize:
Therefore, the minimum root mean squared of
19

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
M J= Σ [C(G.)
(60)
Ko(Gu) (Gu) (SL(((( + +cp)wW
= co(Scp
(64)
Let S = IC(G)),.... C(G and V = S S. According to lemma 11, the minimum value of J is the sum of the (k + 1) to M-th largest eigenvalues of V:
= =
where p' spans the row space R(W).
M
Juin
X
(61)
1=R+1
Consider Ko(Gbri) H1)) (Gtri)
where v
Where N! denotes the ieh largest eigenvalue of symmetric matrix V. Therefore, there exists optimal wo such that the mean squared epsilon(error) is:
R Then,
EM Dink+t k+1 N
Foo(Gori = Fo(Gw) - C(Gori)
DIGI,
"G ..)
(62)
WT (GW) w TTH (Gors)
M
= ww (G)) - (Gor))
This indicates that in the multiple prompt framework, the op- timal mean squared e has an upper bound [(G), ('Gi,""",aa)) Gar), which proves Theorem 7.
= =HAAH.
(65)
Notably, if 2 n, we can find a suitable P such that (G,). and C(G,) are error-free for any i {1,..., M). This can be seen as an extension of Theorems 3 and 4.
Here, AH, = (cpp/) U1 = (cpp -(( -o-
= Therefore, [AFo(G)) - (wis)) This is a piecewise linear function of f/j. denoted as g(p) = a(p)p 3(p) for simplicity, where and are the coef- ficients of this piecewise linear function when takes the value p.
Remark 4. As Johnstone (2001) pointed out, the eigenval- ues of CT in datasets often exhibit truncated eigen- value distribution. The first ko eigenvalues explain most of the variance. Furthermore, Jolliffe & Cadima (2016) shows that in many datasets, eigenvalues may exhibit exponential decay. Hence, the sum of remaining eigenvalues decreases rapidly as k increases. This could explain why moderate- scale prompts are sufficient to achieve good results on large graph datasets.
When (the graph prompt coefficient) is optimal, due to the independence of p², all [A))(G) should take the min- imum absolute value. That is, p² minimizes (g(p)), for any
(1,..., FF)
this point, |AF(())] = VEn=16051 where s(p3) = EN (pp o -m)()) = a,p} Bg..
ERROR DISTRIBUTION ANALYSIS OF MAPPING A.3.5
TO BRIDGE SET
Proof of Theorem 8
Let p² =
p² and g = 18,,..., BB]
Proof. Consider GNN model F& where the W matrix in the last layer is not full rank. Denote by F- the rank of the W weight matrix in the last layer. Consider GPF prompt single node prompt in an All-in-one framework.
OF
Then p' R(W). hence [ = 1|p' B1. This value represents the distance between ,3 and p Since /' already minimizes ||Ap' - 31| and Av' E R(AW), Yp' E R(W), where denotes diag(a1, .......................... .FF w.w. can estimate I|p" BB using the distance from 3 the space R(AW).
According to lemma 4, we have:
(nn 1) = 1) + cp
(63)
Consider the projection matrix P onto the space R(AW). Then || = [[(1 - B).
where H(n-1) is the (n- - 1) 1)th order embedding matrix, P spans RF. As discussed in lemma 7, for simplicity, we can assume ((n 0. Then:
We make the following assumption: when Py = p}. 3, follows an i.i.d. normal distribution.
20

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
(4). Independence: The components of /3 are assumed be independent due the independence of the input features and the structure of the GNN.
N 8
Σ
(66)
1=1
Therefore, it is reasonable to assume that / follows an F F-dimensional i.i.d. normal distribution with mean O and variance e for some positive constant c.
if (cap') - (mx)) >
Where, k- =
(67)
otherwise
A.3.6 ANALYSIS OF NONLINEAR GRAPH NEURAL NETWORKS
Where a is the is the parameter of the Leaky-ReL.U. Ac- cording to the Central Limit Theorem and the independence of different components in B3 it is reasonable to assume that /3 follows an n-dimensional i.i.d. normal distribution with mean 0 and variance e for some positive constant discussed in A.3.5.
Proof of Theorem 9
Proof. According to Preliminary A.I.1, we choose the sim- plest form of GAT here, with only self-attention mech- anism. We consider the diffusion matrix S as weighted adjacency matrix, where each entry Siş represents the co- efficient of the edge between node i and node j. Such coefficient is a non-negative scalar, which can be under- stood as the weight of the edge connecting node and node j. S E [0, l| N Here, single-node All-in-one connection matrices Ain E [0, 1] and Aero E [0, 1] respectively. Then, we have such an iterative formula:
Since P is an (F - r-- dimeensional projection matrix, ac- cording to lemma we know that [| - P| follows a Chi distribution with r degrees of freedom and scalar c, i.e. CXr-
Remark 5. Here, our (63) implicitly assumes that the first N 1 layers of GNN are of full rank. However, even if the rank of the first N - layers of GNN could be non-full-rant we still have p' E R(W), according to lemma Therefore, we can still use this theorem for approximation.
H == (Xa) X W)
Normal Distribution Assumption
where O denotes the Hadamard product, representing element-wise multiplication of two matrices, (++) repre- sents the inner product of 2 matrices. In this case, have:
We assume that the vector 3, which we call the graph embed- ding residual vector, follows an F F-dimensional i.i.d. normal distribution with mean 0 and variance c:
X P
Xw
B ~ N~0,0,
(68)
X p XT p.p.
Xp
(Xw, N.)
where LF is the F identity matrix.
Intuitively, this graph embedding residual vector /3 repre- sents the additional term that the graph needs to fit due to non-full-rank and non-linear components. Formally, its components are defined as:
Sw (s TT !)
Where denotes the cross adjacency matrix Acro E [0, 1ja We Ain to O, hence, SNn is O. p is the prompted vector node feature. Then, have:
[g, Σ (a))muu
(69)
if o (c.pp - o (c;)))
S O X
(71)
Where, A:
(70)
otherwise
(X,X)
(X (X.p))
X
W
(72)
p
The reasons behind this assumption are follows: (1). Sym- metry (2). The sum of random variables and Central Limit Theorem: Each 33 is a sum of multiple terms, each of which can be considered a random variable. The Central Limit Theorem suggests that its distribution should approach a nor- mal distribution. (3). Continuous and smooth distribution
(O, 1F (X
x-(lp))
X
W
(73)
p
For simplification, we consider only updating the embed- ding of rows of original nodes in the embedding matrix. Then we can obtain:
21

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
Now let us prove that the specific form of R does affect the results based ReadOut. This is equivalent proving the following lemma:
H[1:N,
(74)
-1 S (X,X)
FF (
x (,+)
(p)p)
W][L: NN.]
Lemma 9 (Equivalence of R under ReadOut). Consider- ing a vector spans R", then (1) ReadOuat ( + cp' )) (75) spans R (2) Given P; is independent of each other, then [ReadOut(ortt (R + cp })} is independent of each other.
(X)
(0 x(Op))
W)
(76) Consider the ReadOut of the Output Matrix of + cpo ) i.c. ReadOut(o + T)))). Then the jth compoenet of (77) such IR vector is:
p
H[N 1|
Here, we can choose 4 = 2. Then, we have:
N Σ t=1
la (R )l
Lws (us(Ris)1)) (g()))))))
X
H[1 o[ c)
(pT)
W) (78)
(79) where Raj(p) = f
Rag
when p p2 -Rij/es
Cij like-
=W(SXXW + ccpp WW)
aRis
otherwise
wise
cp
(80) Here, subscript i indicates summing by row. Then, consid-
H[N + +1,1 = p'
(81)
ering each column j, we have F independent functions of
H = R² + cp'
(82)
Pj:
(83)
N p}(Ps) = Σ wi wi(Ris (p;) + (p)())))))
1=1
This translates to the iterative formula we have discussed earlier in 2. By analogy with the proofs of Theorems 3, 4, and 5, we can obtain similar Theorem
where is chosen independent of p. c'
= (p,) + C)(p))p
Where (-) is a piece- wise linear function of Py and C₁ and R2 are corresponding piecewise linear coefficients of py- such a piecewise linear function takes values in (-00, +o0). Considering the independence of F columns, it follows that (1) ReadOut(a R + cp spans RF (2) each component of [ReadOut(( R + cp ))] is independent of each other. Which is what we need for the proofs of Theorems and 4.
A.4 Further Mathematical Discussion
Discussion on p: In lemma 2, we rely on the claim that assumes A cpo won't lose the generality. This as- sumption is mainly for simplification, allowing us to obtain cAR + cp cp'T, p. p' spans RF.
Discussion on and P: As lemma pointed out, we may use the same notations Q and P in the preceding and following layers, but they have different meanings. We write it to simplify the expressions. To verify it is valid under ReadOut perspective, as A.4 pointed out, the following lemma required:
The core purpose of this assumption is that when AR- cp the Tiy below is invariant to i.
[R + cp Tho aalR + cp Ji
when Pj 2 Tij
cppR+cp + c) =
Lemma 10. (Equivalence of P and Q under ReadOut) Consider a matrix R matrix Q E R. P. Q. P then ReadOut(a(cp)) spans R.
when Pj < Tij
Use Ti is independent of i, we immediately estab- lish a one-to-one mapping between p' and p. (i.e., p/J
According to lemma 9, we have:
[C(p:)l, = [ReadOut[[[cp;]] T))1;
when Pj 2 Tj (p, T when Pj < T tablishing an equivalence between changes in p at the input end and the p' at the output end. This is what lemma 2 is doing. Noted that AR = CPT don't 't hold in general.
[2j -
thereby successfully
(.Go([p))s) = (o((i))))
Where p: = Q.P. we is the coefficient of ReadOut pro-
22

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
cess, C(Pi) denotes the embedding vector after ReadOut, À denotes Σ W.C.
For Theorem we are seeking an upper bound for the optimal case. Among all prompt parameters satisfying the claim, we can obtain the result in 7. Then, based on the principle that the global minimum is less than or equal to any partial minimum, the error in the optimal prompt would only be smaller, making such upper bound smaller.
Hence, every component (with subscript j) of the embed- ding vector C(-) is a piece-wise wise linear function of [pilj- Specifically, this function is:
Apj pf 20 0
In conclusion, our assumption is valid.
p'(,))
axp otherwise
Lemma 11 (Minimum Sum of Squared Distances from M Vectors k-dimensional Subspace).
where a is the coefficient of the leaky ReLU. range of such
function is (oo) Since F components of (pi) is independent, ReadOut(((cc)) = C(p;) spans R²..
Suppose we have M vectors in R and k-dimensional sub- space of IR We consider the minimum sum of squared dis- tances from these M vectors to the k-dimensional subspace. This is equivalent to minimizing the following objective:
Specific form of the bijective mapping of P and Q
Then, for each i E (1,... , M). we have a Embedding Vector (p.)). Considering putting such Embedding Vectors C(p1)
J = J= - XWW =Tr((X - XX
into matrix, i.e., Č=
Then:
C(PM)
o((T)
Where W is a k: x F matrix. According to Hotelling (1933), let: x = VAVT where V is the matrix of eigenvectors and A is the diagonal matrix of eigenvalues. The optimal W is then the first & columns of V: W = Vla k]. Substituting this into the objective function:
Ö = diag( (m))
(84)
((P))
a' "'"(p1]1 a
[PI]F
= diag(A), An)
J = Tr(VAVT VAV VV HV K)T
J [MM] ... a Jar [PM] F
- VV[;: :VV::& kj AV
(85)
VV[,:A]V[:: 4) A/"AV"V[: kJV k)²)
(86)
Here, we claim that we can take Ii = I1 by 6, i.e. for any
E ,1,"..,, ,M,,
Teg- = 1z-
Simplifying, we get:
Then we have:
J = -Tr(A - Al: k, - -|: k, Al:
[Pi]
[Di]F]
Tr(A) Tr(A[: k,; k))
δ =
M
[pm)
|PMle
= Σ
A
(87)
i=t+1
P1 diag(a"
Therefore, the minimum sum of squared distances from M vectors a k-dimensional subspace is MM Ai where X the i-th eigenvalue of X
diag(An .,,
PM
(88)
Remark 7. This result is essentially the property of dimen-
diag(A)...,,An) QP- Ai-aiaa(a', di... "aaaaa"""",," ('r)
(89)
sionality reduction of M vectors to k-dimensional.
Q'P"
(90)
Definition (Minimum Projection Distance Cone Sur- face).
Where P' and Q' give out the specific form of the bijective mapping between P and Q in lemma 5.
Given a cone C' C R" with surface oC, and any vector E C, we define L(v, OC) as the minimum distance (projection distance) from v to the surface of C. Formally:
Remark 6. We demonstrate that the claim in Explanation A.4 does not affect the results in Theorems and 7.
L(v,
min ||v - x|| xE80
(91)
Theorem 6 is about the case of a single prompt, making the claim trivially true.
23

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
Definition (The angle to boundary and the aperture of the cone).
the nonlinear transformation a(-) turns the convex cone V.W non-convex, which is unlikely when piece-wise linear function Leaky-ReLU is used as the nonlinear function as discussed in Ben-Tal & Nemirovski (2001).
For any interior point of convex cone C, we define:
(i) The minimum distance from to the boundary of C:
Lemma 13 (Distribution of the Norm of an n-Dimensional i.i.d. Normal Vector After Multiplying Projection Matrix),
d(r, aC) = min yll E ac} = d(æ, (x))
Let P be projection matrix onto linear subspace V. Then I - P is a projection matrix onto the orthogonal complement of V. Assume is an n-dimenniinal random vector follow- ing a normal distribution with mean 0 and covariance matrix cIF, where e a positive constant. i.e., < ~ NV cIp
where proje (x) is the projection of x onto C.
(ii) The cosine of the angle between x and the boundary of C:
(z, (r))
cos 02
> proje
Let ( (T P) s, according the linear property of Gaussian Random vector, we have Ç ~ NN',, 2'), where: /² (1 P). 1
(iii) The relationship between the distance and the angle
d(æ, 0C) = || sin 22.c.
= 0 E' (I- P. PI-P) E
(iv) The aperture & of the cone
=[I-p] =0== ((I-) P)
U, u > |0|| ||||||
sin( ④) max v.uEC'
Denote by r the rank of matrix T- P. Apply decorrelation to Ç, we have U -,, NO E").
Moreover, for any interior point x, we have 0n,c S 4/2. This formulation is based on the Distance-Supee Support Theorem by Rockafellar (1970).
c² Ir
O OP-XX--)) )
where Σ" matrix. Hence,
U is orthogonal
Lemma 12 (Relationship between Range of Prompted and Embedding matrix).
r
II(I - -|s|| ||
As mentioned in lemma 3, V! = Va = {o(v) v R(W)). In lemma 8, under the alternating action of the non-linear function Leaky-ReLU and linear transformation W. we have V oVV
Since Σi= o ~ (r), we have: |||| v x(r)
VE of
First prove V is cone surface. For V.L given À >> 0 and E R(W), we have (Av) = \v(v). Thus, if (v)) E V1. then AA > 0, \v(v) E V.. Furthermore, consider V E Vi-1, AA > 0, ((Av)WW) = Xo(vW). It follows that, VV E V. AA > 0, λv E Vi, hence, Vi is a cone surface. Iteratively, we obtain that V is cone surface for i E nI.
It follows that the norm of an n-dimensional i.i.d. normal vector after multiplying projection matrix: || P)sll
obey Chi-Distribution with degrees of freedom.
Next, consider C₁ as the convex hull of V. Specifically, since V is a cone surface, C² is convex cone. By lin- earity of multiple a matrix, C₁ W remains a convex cone. After applying (.), this convex hull transforms into another convex cone or cone surface, namely, (C) and the corresponding Vi+1 is the surface of C++1, a (CC) is then the convex hull of W).
After n iterations of the aggregation, we can conclude that: V is a cone surface, Cj is convex cone, and V is the surface of C.:
Remark& 8. Here we assume that the process of obtain- ing the convex hull Cr++1 from (CC,) W) keeps the Vi+1 to be the surface of Cs+1_ This always holds true unless
24

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
B Supplementary Experiments
increases in multiple graph mapping scenarios. We observed that in real-world datasets, RMSE also increases rapidly as the number of graphs increases, which aligns with our observation in the main experiment.
We conducted supplementary experiments on real-world datasets validate our results. We performed similar exper- iments as in the main text using entirely different datasets, namely NCI1 and DD (Morris al., 2020). The NCI1 dataset has 37-dimensional node features, 4,1 10 subgraphs, an average of 29.87 nodes per subgraph, and an average of 64.60 edges per subgraph. The DD dataset has 89- dimensional node features, 1,178 subgraphs, an average of 284.32 nodes per subgraph, and an average of 1,431.32 edges per subgraph. Our results are shown in the following figures.
Mandeer of Pringe
Nomber Grogle
Figure 9, Additional multiple graph analysis with All-in-one-plus
Egede
Exp 4 implemented Experiment B in Section 5.4 to supplement the analysis of All-in-one-plus in multi-graph prompts. All-in-one-plus also achieved reduction in over- all error due to the expanded search space, and the resulting surface exhibits a shape similar to that of the other two experiments Section 5.4(b).
(a) NCI1
(b) DD
Figure 6. Convergence analysis.
Expl we examined the loss curves during training for GPF and All-in-one prompting methods with full-rank matrices. Similar to observations from synthetic datasets, the prompt method shows period of steady decline followed by rapid decrease to a small magnitude, then slowly converging to zero. This aligns with our theoretical results.
C EXPERIMENT DETAILS
Data Preparation: We first confirm our theoretical findings on synthetic datasets because these datasets offer controlled environments, allowing us to isolate specific variables and study their impacts. We generate these datascts by defin- ing the dimension of graph feature vector(F) (F), average of graph node numbers (Nang)) average of graph edge numbers (Eavg). and number of graphs in the dataset (M). These pa- rameters characterize both individual graphs and the entire dataset, facilitating our study of the relationship between these features and e. In detail, the distribution of graph node feature vectors is set to a normal distribution ((0, 1); the graph edge density p is set to 0.15, where p represents the probability of an edge existing between any two nodes.
Prepiiical Forar
Rank Lind
Raak Lost
(a) NCII
(b) DD
Figure 7. Empirical Max Error v.s. Rank Lost.
Exp 2 we investigated the relationship between empirical maximum error and rank loss for non-full-rank matrices. The results here are similar to those in the main text, with loss (empirical maximum error) increasing rank loss in- creases. Where rank loss is means the rank of weight matrix W in GNN is n
Model Settings: To evaluate our approach, we conduct experiments using two representative Graph Neural Net- work (GNN) architectures: Graph Convolutional Networks (GCN) as linear propagation models and Graph Attention Networks (GAT) as non-linear propagation models. We focus on these two architectures because other models tend to exhibit similar behavior patterns. Unless stated otherwise. our default configuration employs three-layer GNN with feature dimension of F = 25 and utilizes the Leaky-Rel.U activation function. For experiments involving full-rank matrices, we ensure that each layer's ''r's weight matrix is full rank, selected after an initial pre-training phase. Conversely, for studies with non-full- fullulll-rnk matrices, we set the rank loss
(a) NCI1
(b) DD
Figure& 8. Empirical Min Error v.s. Graph Number.
Exp We examined how the RMSE of GPF or single-node All-in-one Prompt methods change as the number of graphs
25

---

Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis
parameter to default value of 5. We adopt mean pooling as the default readout method throughout our experiments.
G + (G) Here, (u(G) is the prompted graph, where Pie is learnable function parameterized by w.
Task Settings: Our loss function is defined as F (Gp) - C(G) for single-graph tasks, and V EGeg F | - C(G))I/M for multi-graph tasks. Here Gp is the combined graph with G and graph prompt. Kindly note that C(G) means an optimal function to the downstream task, which is not accessible without specific task. Since the ultimate purpose of graph prompting is to approximate graph operation, we here treat C()) as various graph data operations such as adding/deleting nodes, aading/deleting/hhnnin edges, and transforming features of given graph G. The intensity of these graph operations is controlled by a parameter 8 E [o, 1). where O indicates no change and indicates generating a completely random new graph. In our experiments, we fix B at 0.7, which means we have a 0.7 probability of removing a node/edge or masking some features.
4. Computing Prompted Graph Embedding: We pass the prompted graph (G((G) through the same GNN and pooling operations obtaín the embed- ding Fo (P)((G))): (G)(G) - GNN - Pooling + (P)
Error Computation: We compute the error between the embeddings of the prompted graph and the ground truth embedding: Error [P (G) I This error quantifies how well the graph prompt ap- proximates the desired graph data manipulation.
Empirical Maximum Error in Figure/ 1. Figure 1 in our pa- per illustrates the empirical maximum error observed in our experiments, corresponding to the theoretical upper bound discussed in Theorem 5. To approximate this upper bound: We perform multiple trials by repeating the experiment with different random removals of edges or nodes (i.e., generat- ing different G') and different initializations of the graph prompt Pu- For each trial, we compute the error as de- scribed above. We record the maximum error observed across all trials, which serves as an empirical approximation of the theoretical upper bound.
Definition of C(G). In our experiments, C(G) represents the optimal graph-level embedding of a modified graph G' derived from the original graph G. Specifically, G' is obtained by performing graph data manipulation opera- tion on G, such as removing a certain percentage e% of edges or nodes. The function C(G) is defined as:C(G) = Pooling (G)) where GNN is a graph neural network, and Pooling is a graph-level pooling operation that aggre- gates node embeddings into a single vector representing the entire graph G'. This embedding C(G) serves as the ground truth in our experiments.
Training:
In the graph prompting training process, we per- form gradient descent on the parameters of the graph prompt P.. using the Adam optimizer. We use a learning rate of x 10 and weight decay of 5 x 10 We im- plement an early stopping mechanism with a maximum of 2000 epochs by default. When analyzing the upper bound of the error of the prompt method, it is crucial to ensure that the convergence value of P is indeed the global minimum. To prevent the training of prompt parameters from falling into local minima, we approximate the global minimum by independently training times with random initialization for each prompt, and selecting the minimum loss. Typically, k set to 3.
Experimental Procedure. We focus on graph-level task that inherently requires graph data manipulation. The exper- imental procedure is as follows:
1. Graph Manipulation: Starting with an original graph G. we generate modified graph G' by randomly ap- plying graph manipulations, including all the afore- mentioned actions (specifically, adding/deleting nodes, adding/deleting/channii edges, and transforming fea- tures of G, each with chosen hyperparameter ratios). This process simulates a data operation that alters the graph structure.
Note that the error bound in Theorem 5 is the product of two terms: sin (222 and ||C(G)]| For fixed pre-trained model, sin(a/ /2) is consistent, but C(G) varies with different generated datasets. In our experiments, the 30 graphs used to find the empirical maximum value are from the same dataset, while the different empirical maximum values are obtained from different datasets. Considering the average value better represents the change in the Er- ror Bound relative to the independent variables like "Rank Lost".
Testing:
2. Computing Ground Truth Embedding C(G):: We pass G' through a pre-trained and fixed GNN model followed by a pooling operation to obtain the graph- level embedding C(G)) G' - GNN - Pooling - C(G) This embedding represents the desired outcome of the data operation.
Codes: dgpw
https: com htwpttuwwbb..ooogguuungoggaggago qunzhongwang/
3. Graph Prompting on G: Instead of directly manipu- lating G. we apply a graph prompt P., to the original graph G to approximate the effect of the manipulation:
26


Reviews:
[{"review_id": "llLIfsXx4A", "reviewer": "Reviewer_cRh6", "summary": "The paper presents a comprehensive theoretical analysis of graph prompting, a novel technique aimed at adapting pre-trained GNN models to downstream tasks without retraining. It introduces the concepts of \"bridge sets\" and \"ϵ-extended bridge sets\" to explain the capacity of graph prompts to simulate graph transformations and align upstream pre-trained models with downstream tasks. The authors provide theoretical proofs demonstrating the conditions under which graph prompts effectively approximate various graph data operations, establish error bounds on these approximations, and examine error distributions. Empirical results validate these theoretical findings, supporting the practicality and effectiveness of graph prompting.\n\n---\n\n(+) The paper fills a significant theoretical gap in the graph prompting literature, rigorously establishing conditions under which graph prompts can successfully approximate data operations.\n\n(+) It systematically addresses various scenarios including single and batch graphs, linear and non-linear graph aggregation models (GCN and GAT), and extends its theoretical guarantees to practical GNN architectures.\n\n(+) Introducing bridge sets as a theoretical tool is innovative and clarifies how prompting impacts model behavior from a data manipulation perspective.\n\n---\n\n(-) Despite rigorous theoretical insights, practical application and generalization to various real-world graph tasks might still face challenges in prompt design and optimization.\n\n(-) Some theoretical guarantees depend on assumptions like \"full-rank\" model parameters, which, although justified by practical model initialization and training strategies, might limit generalization or require specific model conditions.\n\n(-) While synthetic datasets convincingly demonstrate theoretical validity, broader validation across diverse real-world datasets and complex scenarios would enhance practical relevance.\n\n---\n\n## update after rebuttal\n\nThank you to the authors for the thoughtful and detailed rebuttal. I appreciate the clarifications regarding the full-rank assumption and the inclusion of supporting theorems (e.g., Theorems 5, 8, and 9) for scenarios where the assumption does not hold. The explanation of practical conditions under which full-rank matrices are likely to appear is helpful.\n\nThat said, I still believe the practical implications and generalizability of prompt design remain open challenges, especially in more complex real-world settings. While I acknowledge the experiments in the appendix, I would encourage the authors to highlight these results more explicitly in the main text to improve accessibility and clarity.\n\nOverall, the rebuttal strengthens my confidence in the theoretical contributions, but my initial position remains unchanged. I still lean toward a weak accept, primarily due to the paper’s rigorous theoretical insights and the novelty of the proposed framework.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> C1: Despite rigorous theoretical insights, practical application and generalization to various real-world graph tasks might still face challenges in prompt design and optimization.\n\nThank you for your insightful comment. This paper primarily focuses on providing theoretical insights and rigorous proofs for graph prompting. We believe that exploring practical applications and generalizations should be left to the broader research and industrial communities. To triger this exploration, we added some open discussion to our work in the code project homepage, from which you could see some practical impact of our theory.\n\n\n> C2: Some theoretical guarantees depend on assumptions like \"full-rank\" model parameters, which, although justified by practical model initialization and training strategies, might limit generalization or require specific model conditions.\n\nThank you for your comment. In Theorems 3 and 4, the \"full-rank\" assumption are critical for ensuring the existence of lossless graph prompting methods in general settings.  For cases where the full-rank assumption does not hold, we have dedicated considerable effort in our work to analyze such scenarios (e.g., Theorems 5, 8, and 9). These theorems provide corresponding bounds that demonstrate only controllable errors and ensure the robustness of prompt design. Therefore, the \"full-rank\" assumption is a key condition discovered during our exploration and does not detract from the contributions of this paper.\n\n>  C3: While synthetic datasets convincingly demonstrate theoretical validity, broader validation across diverse real-world datasets and complex scenarios would enhance practical relevance.\n\nIn Appendix B of our paper, we conducted extensive analyses and experiments on various real-world datasets. The results obtained are very similar to those from synthetic datasets in the main text. Therefore, we believe that both synthetic and real-world datasets yield consistent results, fully supporting the validity of our theoretical findings.  \n\nRegarding the experimental setup, we carefully aligned each experiment with the theoretical discoveries, focusing on the core theoretical insights. From a practical experimental perspective, this is sufficient to validate the problem. Broader and more complex settings could be left to the wider research community. Our goal is to emphasize the solid theoretical results.\n\n> C4: typos and references:\n\nWe have noted the minor editing errors and suggestions for updating references. These will be totally included in the final version of the paper.\n\n\n> Q1. Could you clarify under which practical conditions the assumption of a full-rank matrix in Theorems 3 and 4 typically holds?\n\nThank you for your question. As discussed in the section following Theorem 4, when parameter matrices are initialized using methods such as orthogonal initialization, He initialization, or Xavier initialization, they are almost always full-rank throughout the training process.  \n\nHere, \"almost always\" can be understood as follows: the determinant of a matrix is 0 if and only if the matrix is rank-deficient. However, during training, the determinant can take any value along the real number axis and its behavior can be considered as random fluctuations, making it extremely unlikely to be exactly 0. Since He initialization is the standard initialization method in modern practices, the direct answer is that with proper initialization, trained models can be considered full-rank matrices in practice. We added some open discussion to our work in the code project homepage, from which you could see further practical discussion on full-rank condition.\n\n>  Q2. Can you discuss the scalability of your proposed graph prompting methods to extremely large graph datasets, such as those encountered in industrial applications?\n\nOur work primarily analyzes classical prompting methods, such as GPF and All-In-One. In Theorem 7, we provide a detailed discussion on the performance of multi-token GPF and multi-node subgraph All-In-One methods on large-scale graph datasets. Specifically, part (4) of Theorem 7 gives an upper bound on the final error, theoretically demonstrating the scalability of graph prompting methods to extremely large graph datasets.  \n\nSome studies have already achieved promising results on larger datasets, and our work provides theoretical support for these findings. For extremely large graph datasets, following our theorems and subsequent discussions, effective results can be achieved using prompts that are much smaller than the dataset itself. This theoretical work strongly supports the scalability of graph prompting methods to extremely large graph datasets and provides a solid foundation for future industrial applications.\n\nWe will add more scalability discussion in the final version.", "claims_and_evidence": "The claims in the paper are clearly stated and largely supported by convincing theoretical proofs and controlled empirical evidence. However, claims about generalizability to complex real-world scenarios are not thoroughly supported by empirical experiments.", "methods_and_evaluation_criteria": "The methods and evaluation criteria, including synthetic benchmarks and the use of GCN and GAT as representative models, are appropriate and relevant to the theoretical focus of the study. However, additional real-world datasets could provide a more comprehensive evaluation.", "theoretical_claims": "I checked the correctness of key theoretical claims such as Theorems 3, 4, and 5. The proofs appear mathematically sound and logically consistent. Minor concerns may exist around the conditions for full-rank assumptions, but they are clearly justified.", "experimental_designs_or_analyses": "The experimental designs using synthetic datasets effectively validate theoretical claims. The choice of metrics and analysis approaches are sound. However, the extension to real-world graph data could be more comprehensive.", "relation_to_broader_scientific_literature": "The paper clearly positions itself in relation to recent literature, especially in the area of prompting techniques and graph neural networks. It effectively references significant prior work such as Sun et al. (2023a, b), Fang et al. (2022, 2024), and Liu et al. (2023).", "essential_references_not_discussed": "The paper adequately references essential and relevant prior work. No critical omission is evident concerning the core contributions.\nHowever, (not necessarily) I recommend to include more recent papers such as GSPF, SUPT, GSmFP, and HGPROMPT at the final version.\nBecause graph prompting has rapidly emerged as a promising research direction, as mentioned by authors.", "other_strengths_and_weaknesses": "The paper's originality lies significantly in its rigorous theoretical grounding of prompting techniques for GNNs, contributing valuable insights and clarity to an otherwise empirically driven field. The clarity and structure of the presentation further enhance its impact.", "other_comments_or_suggestions": "Minor editing for typographical errors could further enhance readability. Overall, the manuscript is clearly written.\nThe `citeauthor` format is inconsistent. For instance, in page 2, \n\n> (line 071) ... as described in the review by `Sun et al. (2023b)`, can be ...\n\n> (line 107) Initially, `(Fang et al., 2022)` have proved that ...", "questions_for_authors": "1. Could you clarify under which practical conditions the assumption of a full-rank matrix in Theorems 3 and 4 typically holds?\n\n2. Can you discuss the scalability of your proposed graph prompting methods to extremely large graph datasets, such as those encountered in industrial applications?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oi2gsjBSIX", "reviewer": "Reviewer_SySL", "summary": "The paper theoretically analyzes graph prompting. First, it shows that the main reason why graph prompting works is because it can simulate graph operations, and why this is important when encountering new tasks. Second, it presents upper bounds on the error of  graph prompt when simulating graph operations. Third, the results are extended to non linear graph aggregations.\n\n\n## update after rebuttal\n\nThe paper presents an interesting contribution. However, I am keeping my score unchanged, as stronger experimental validation would be needed for a higher score. Specifically:\n\n1. The evaluation focuses on embedding reconstruction rather than performance on the actual downstream task, despite having access to labels of the downstream task.\n\n2. The training task consists on approximating graph data operations such as random corruption, but it would be more insightful to train on real-world graph tasks. **More importantly, to properly assess the potential of graph prompting, it is necessary to change the dataset between training and test.**", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> C1: Why aren't we considering a completely different training task defined on a different dataset than the downstream task? I understand that this setting is significantly more challenging, but otherwise, I believe we are not really testing the generalization ability of graph prompting.\n\n\nThank you for your question. Transferring graph models on different domains (graph datasets) is a very promising potential application of graph prompt because we believe the core challenge on this topic is how to learn effective data manipulation strategy. before graph prompt, we can nearly only focus on hand-crafted design, which is far from promising to achieve this goal. Transfering across graph datasets/domain, or across differnt tasks, are two hard problems in graph learning area. The one across domains/datasets is still a not well solved problem. recently, there are some work trying for this but most of them are far from sufficient to industrial applications. \n\nOur paper found that, learning an effective data manipulation strategy might be helpful for both domain transfering and task transfering in graph learning area. recently, some graph prompt-based work have found the promsing restuls for graph domain transfering for recommendation (Zhang et al. Adaptive Coordinators and Prompts on Heterogeneous Graphs for Cross-Domain Recommendations. arxiv 2410.11719). The potential behind this lies in the powerful graph data manipulation capability of graph prompt. However, diving into so many various applications is far out of the scope of our motivation. This paper wishes to provide the background theory support for our community to explore further. To this end, we focus on the core problem: how well does graph prompt manipulate graph data? According to this, our experiments are close to justify the correctiness of our theory analysis. We will explore more task settings in the futre to expand the imapct of this paper.\n\n\n> C2: I think the authors should include intuitive explanations throughout the paper. The experimental settings are unclear, as I discussed above. Appendix C partially helped me understand the loss and the training procedure ..., and should be partially moved to the main paper...\"  \n\nThank you for the suggestion.We will carefully consider better formatting and move some key explanations from Appendix C to the main paper in the final version to improve clarity.\n\n> C3: typos\n\nThanks for pointing our this, we will carefully update in our final version.\n\n> C3: Why does the loss in Equation 1 only take the graph-level embedding? Why aren't we taking the output of the downstream classifier (which is applied to the graph-level embedding) and the ground truth labels?\n\nThis concern might come from our expression issue. We are sorry for the caused misunderstanding. Take the graph classification as an example, the classifier (like MLP) can be usually treated as some addion layers for the graph model so the output of the classifier can be treated as a special graph embedding. We take this expression just for conciseness without loss of generality. In a standard graph prompt workflow, the task head is usually fixed and pre-defined so the task head is just a constant mapping and it is usually won't affect the graph prompt design. We thank you for this suggestion and we will try our best to refine this section in our final version.", "claims_and_evidence": "The theoretical claims are supported by clear and convincing evidence", "methods_and_evaluation_criteria": "I am not sure I understand the evaluation criteria. I was expecting to have defined a training task, a the training dataset, a downstream task and a downstream dataset. However, from Appendix C, it seems that the training task is to approximate graph data operations such as random corruption, and that the downstream task is the one of interest (and the dataset does not change).\n\nWhy aren't we considering a completely different training task defined on a different dataset than the downstream task? I understand that this setting is significantly more challenging, but otherwise I believe we are not really testing the generalization ability of graph prompting.", "theoretical_claims": "The proofs seem correct to me.", "experimental_designs_or_analyses": "Unfortunately I do not think I fully understand the settings of the experimental design. If the goal of graph prompting is to adjust the downstream data to make the downstream task compatible with the pretraining task, why don't we directly test the performance on the downstream task (since we have the labels), instead of reporting the error in reconstructing the embeddings?", "relation_to_broader_scientific_literature": "The key contributions of the paper relate to the broader scientific literature by extending the concept of graph prompting, which has been explored in empirical studies but lacks theoretical understanding. The paper demonstrates that graph prompts can simulate graph data operations and provides theoretical guarantees for their effectiveness.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "The topic is interesting but the paper is hard to hard. This is partially due to the presence of many theoretical results, but I think the authors should include intuitive explanations throughout the paper.\n\nThe experimental settings are unclear, as I discussed above. Appendix C partially helped me understanding the loss and the training procedure (which aims at obtaining the same graph embeddings under manipulations of the graph), and should be partially moved to the main paper, otherwise it is unclear what are the training task and dataset.", "other_comments_or_suggestions": "$\\rightarrow$ in Equation 2 should be $\\approx$\n\n$A_{in}$ should be $\\mathbf{A}_{in}$ in line 97 right\n\nplease use \\citet in Section 2 motivation.", "questions_for_authors": "Why does the loss in Equation 1 only takes the graph-level embedding? Why aren't we taking the output of downstream classifier (which is applied to the graph-level embedding) and the ground truth labels?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EdvMfc3gv9", "reviewer": "Reviewer_K4mS", "summary": "This study aims to provide solid theoretical analysis of graph prompts. The theoretical findings include the capabilities of graph prompts on GCN models with and without non-linear layers, the error bound of the data operations by graph prompts for both a single graph and batch of graphs, and the error distributions of the data operations by graph prompts. This work also provides empirical studies to confirm these theoretical findings.\n\n## update after rebuttal\nThis study analyzes the capacity of graph prompting methods for pre-trained GNN models. The analysis primarily focuses on GPF(-Plus) and All-in-One(-Plus) as the graph prompting methods and GCNs and GATs as the GNN models. I think **the correct formulations of the studied graph prompting methods and GNN models are the most basic requirement of a theoretical paper**. However, when checking their corresponding descriptions in the paper, we can find out that **most of them are questionable, confusing, and even incorrect**, e.g., GPF-Plus (line 630 to 638), GAT (Equation 7 to 9), GCN (line 642), All-in-One-Plus (no descriptions found).\n\nConsidering this, I have to keep my evaluation as negative. I hope the authors can check their paper from beginning to end rigorously to avoid such obvious mistakes.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> W1\n\n- The motivation of this distance we used is that: we assume once we are given an anchor/target graph embedding, our theory proves that we can use graph prompt to approximate such embedding. The given embedding is not necessarily the only optimal graph embedding. It can be any one. The purpose of this paper is to present the powerful data operation approximation from graph prompt. Of course, in a more realistic view, we usually hope such anchor graph embeding should be some optimal one for specific task because it can link graph prompt to various downstream tasks, but please note that this is not necessary for the theory basic of this paper, we say it just for indicating our reader that we can use such technique to find potential optimal solution for downstream task, and let our readers understand that graph prompt and traditional fine-tune are two routines to achive such target. \n- Although the distance between **Fθ∗(Gp)** and **C(G)** may overestimate the actual performance deviation, this further supports the fact that the distance serves as an **upper bound** for the deviation. Our theoretical results demonstrate that this **upper bound** of the error is either zero or tightly controlled, ensuring that the performance deviation is also controlled. This, in turn, guarantees the effectiveness of the prompt. Thus, the strategy of using this distance as the error remains valid.\n- Concerning different task predictors (decoders), while optimal embeddings  vary across decoders, in practice, each downstream task has a fixed decoder from the pretrained model. Our analysis focuses solely on scenarios with fixed downstream tasks, ensuring consistent optimal embeddings .\n- Additionally, our analysis does not require uniqueness of the optimal embeddings —only their existence. If  exists and the distance to  remains small, performance quality is assured, maintaining the validity of our approach regardless of embedding uniqueness.\n- We appreciate your insightful comments and agree that exploring additional measurement approaches is promising, though somewhat beyond this paper's current scope. We intend to include such discussions in the camera-ready version upon acceptance.\n\n> W2\n\nThank you for your question. Please note that we clearly discuss **non-linear graph aggregations** in Section 4.4. The definitions of **linear** and **non-linear graph aggregations** are clearly stated in the paper. Specifically:  \n\n- **Linear graph aggregations:** The aggregation coefficients do not depend on the node feature vectors. For example, in GCN, the coefficients for combining neighboring nodes' embeddings are constant.  (e.g. $H=AXW$ with A a constant matirx and W the parameter, just like what we call $y=ax+b$ in linear algebra)\n- **Non-linear graph aggregations:** The aggregation coefficients depend on the node feature vectors. For example, in GAT, the coefficients are determined by attention scores, which are computed based on the feature vectors of neighboring nodes.  \n\nYou are correct that GAT and GCN both use non-linear activation functions for processing aggregated information. However, we emphasize the distinction in the **aggregation process**, not the subsequent **information processing**. Almost all GNN models use non-linear layers (e.g., MLPs) to capture complex patterns during **information processing**, but this is not the focus of our discussion.  \n\n> W3\n\nSorry for this typos. We will modify Equation (7) by replacing **Xj, Xk** with **Hj, Hk** (hidden embeddings), which is consistent with the reference of GAT. Please note that this typos will not affect our downstream theory analysis. \n\n> W4\n\nIn the mentioned section, we state that **GPF-plus adds a combination of multiple prompt vectors to each node’s features.** Specifically, **Q ∈ R^M × k** is a matrix, where the i-th row **Qi** represents the combination coefficients of the k prompt vectors, which are then added to the node features. We stated the update rule is mathematically expressed as:  \n**[Xω]i = Xi + QiP.**  **\"M represents the number of graphs in the dataset Ω.\"**  This indicates the number of graphs being processed, each with distinct combinations of prompt coefficients **Qi**.  We will add the explanation in the final version.\n\n> W5\n\nWe apologize for this inconsistency, which may cause confusion.  We will replace this notation in Equation (17) with a different symbol and update the notation table accordingly in the final version. \n\n> W6\n\n**All-in-one-Plus**: we set the inserting patter of all-in-one as independent parameters (all-in-one, however, relies on prompt tokens). We will clarify this in the final version.\n\n> W7\n\nOur implementation of the **modified graph** includes all the operations you mentioned:  **\"Adding/deleting nodes, adding/deleting/changing edges, and transforming features of a given graph G.\"**  This is explicitly stated in the task settings described in Appendix C. We will revise this section further in the final version.", "claims_and_evidence": "Not fully supported. For example, using the distance between $F_{\\theta^*}(G_p)$ and $C(G)$ as the error is questionable. In addition, the formulation of GAT is weird. More details are provided in the weakness list.", "methods_and_evaluation_criteria": "Not fully make sense. The theoretical analysis in this paper has some issues in terms of the assumptions, formulations, and proof. More details are provided in the weakness list.", "theoretical_claims": "I checked the proofs for theoretical claims, including most parts from page 11 to 17. The issues can be found in the weakness list.", "experimental_designs_or_analyses": "I checked the experiments in the main paper and the supplementary material. The issues can be found in the weakness list.", "relation_to_broader_scientific_literature": "The key contribution of this paper is the theoretical analysis of the existing graph prompt learning methods, such as GPF and All-in-one. So it is very related to the literature.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "- **Weakness1**: Using the distance between $F_{\\theta^*}(G_p)$ and $C(G)$ as the error is questionable. In many cases, there are multiple optimal graph embeddings given different task predictors. There may exist graph embeddings that are far from the optimal graph embeddings but can achieve almost-optimal performance. Hence, using the distance as the error may be improper to determine whether a prompted graph is close to the optimal ones.  \n- **Weakness2**: The definition of linear and non-linear graph aggregations is vague. The meaning of so-called “non-linear graph aggregations” like GAT is vague in this paper. Basically, GAT and GCN both aggregate the embeddings from neighboring nodes of a node linearly and pass the aggregated embedding to a non-linear activation function to obtain the updated embedding. Using linear and non-linear graph aggregations to distinguish them is quite confusing.  \n- **Weakness3**: The formulation of GAT is weird. In Equation (7)~(9), the authors use “the simplest form” of the attention mechanism in GAT. In “the simplest form”, the attention coefficient $\\alpha_{jk}$ is determined by node features and irrelevant to hidden embeddings. As a result, $\\alpha_{jk}$ will be constant across different GAT layers, not affected by GAT parameters at all. Therefore, it is quite strange to formulate GAT in this way.  \n- **Weakness4**: The formulation of GPF-plus is unclear. The authors should specify what $Q$ represents in Equation (14) and the meaning of $M$.  \n- **Weakness5**: The meaning of $\\epsilon$ when formulating Equation (17) should be specified. According to Table 3, $\\epsilon$ represents an error. But it seems that $\\epsilon$ before Equation (17) does not represent an error.  \n- **Weakness6**: The authors should introduce the method All-in-one-Plus in the experiments. It is not introduced anywhere but only appears in some experimental results.  \n- **Weakness7**: The design for obtaining $C(G)$ in the experiments is questionable. $C(G)$ is obtained based on a modified graph by randomly removing nodes edges. These modifications do not include other graph manipulations, such as changing node features and adding extra nodes.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please mainly address the weaknesses above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l7d9zFrhnQ", "reviewer": "Reviewer_jpAA", "summary": "The paper addresses the challenge that the theoretical underpinnings of graph prompting remain underexplored, particularly highlighting the lack of rigorous theoretical proof regarding why and to what extent it works. This has often been seen as a \"dark cloud\" over the field, hindering further progress. In response, the paper introduces a theoretical framework that rigorously analyzes graph prompting from a data operation perspective.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> W1. The paper does not offer theoretical guidance for designing new graph prompting methods. While it rigorously analyzes existing methods, it does not extend the theoretical framework to propose novel techniques.\n\nThank you for pointing this out. In fact, our theoretical framework can provide fundamental theoretical guarantees for designing **novel graph prompting methods**. By considering Theorems 6 and 7, one can derive guidance for selecting the structure and number of prompts. These results can serve as useful directions for designing new graph prompting methods in future research. In our code project homepage, we also added some discussion to inspire the community for desining better graph prompt according to our theory analysis. please see the open discussion of our work in the code link.\n\n> W2. The paper lacks experiments on real-world cross-domain datasets, which are crucial for assessing how well graph prompting adapts to different downstream tasks.\n\nRegarding experiments on real-world data, please refer to **Appendix C**, where we provide detailed experiments on real-world datasets. These results are consistent with those obtained on synthetic datasets in the main text, further supporting the validity of our theoretical findings.\n\nRegarding the cross-domain datasets, we have the same response to Reviewer SySL  C1. \n\n> Other Comments or Suggestions\n\nWe thank the reviewer for these insightful suggestion. We will open a new discussion online to keep updating our latest research findings on more real-world applications and more graph prompt design. We currently have already finished such explorations and that is the reason why we wish to find a pure theory support, just like the motivation of this  paper. For anonymity policy, we will open these explorations once accepted.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for the problem at hand.  However, the paper lacks results on cross-domain datasets from real-world scenarios.", "theoretical_claims": "I have roughly checked the proof process for all the theorems presented in the paper.", "experimental_designs_or_analyses": "I have checked the datasets, experimental setup, and results presented in the paper.", "relation_to_broader_scientific_literature": "The paper provides a comprehensive analysis and proof of the existing literature on graph prompting. It offers valuable insights by approaching the topic from a macro-level theoretical perspective.", "essential_references_not_discussed": "NAN", "other_strengths_and_weaknesses": "Strengths:\n\n1. The motivation of the paper is clear, effectively addressing the gap in existing heuristic graph prompting methods that lack theoretical grounding.\n\n2. The topic of the paper is valuable, with a well-organized structure and clear writing, presenting the ideas in a step-by-step manner.\n\n3. The paper provides thorough theoretical proofs for the claims and approaches introduced, offering solid justification for the proposed framework.\n\nWeaknesses:\n\n1. The paper does not offer theoretical guidance for designing new graph prompting methods. While it rigorously analyzes existing methods, it does not extend the theoretical framework to propose novel techniques.\n\n2. The paper lacks experiments on real-world cross-domain datasets, which are crucial for assessing how well graph prompting adapts to different downstream tasks.", "other_comments_or_suggestions": "1. Testing on  real-world cross-domain datasets would provide insights into the bridge graph method's generalizability and effectiveness across diverse applications.\n\n2. It would be best to extend the theoretical framework to propose novel graph prompting methods, as this would add more practical value.", "questions_for_authors": "Please refer to the Weaknesses and  Suggestions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a theoretical analysis of graph prompting (inserting new subgraphs or features to the target graph and applying a pretrained GNN to adapt to downstream tasks), addressing a critical gap in the literature by providing formal guarantees on its approximation capabilities, error bounds, and applicability to both linear and non-linear graph models. The work is well-received by most reviewers for its rigorous theoretical contributions. Though some concerns remain regarding practical applicability, experimental validation, and clarity of certain assumptions, the rebuttals adequately address most critiques.
Decision: Accept (poster)