Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis

## Abstract

Abstract In recent years, graph prompting has emerged as a promising research direction, enabling the learning of additional tokens or subgraphs appended to the 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 prompt area to go further. 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 by graph prompts 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.

## 1 Introduction

Graph Neural Networks (GNNs) have been widely used in analyzing various graph-structured data. A standard workflow using GNNs is the “pre-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 advanced 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 natural 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., ) modify the input graphs by adding learnable tokens or subgraphs, 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., ; Liu et al., ; Tan et al., ; Huang et al., ; Ma et al., ; Chen et al., ) 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 to achieve better expressive capability than the traditional paradigm.

Recently, some studies (Fang et al., ; Sun et al., ) have realized that the reason why graph prompts work may relate to their capability in simulating various data operations like deleting/adding nodes/edges, changing node features, and even removing subgraphs.
This makes graph prompts stand out from their counterpart in the NLP area and inspires many empirical applications like recommendation systems (Yang et al., ; ; Wang et al., ), biological networks (Diao et al., ; Gao et al., ), transferring knowledge across different graph domains (Guo et al., ; Zhu et al., ; Zhao et al., ), and more (Jin et al., ). Unfortunately, despite these promising results, the theoretical basis of graph prompting remains underexplored. Existing works primarily rely on empirical validation and lack rigorous theoretical analysis to explain why graph prompts are effective and how they can be systematically 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.

In light of these limitations, this paper provides a comprehensive theoretical framework for graph prompting from a data operation perspective. First, we establish rigorous guarantee theorems that demonstrate the underlying reason why graph prompts work is their capacity to simulate various graph data operations, and our theorems further answer 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 practical scenarios where models are usually trained on multiple graphs. Third, we explore the distribution of the data operation error and extend our theoretical findings from linear graph models, such as Graph Convolutional Networks (GCNs), to non-linear models like Graph Attention Networks (GATs). This extension demonstrates the robustness 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 a 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.

## 2 Background

Graph Prompt.
Compared with “pre-training and fine-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 $F_{\theta^{*}}$ be a graph model where its parameters ($\theta^{*}$) have been pre-trained and frozen; $T_{dow}$ be the downstream task, in which the task objective is measured by a loss function $\mathcal{L}_{T_{dow}}$. Let $\mathcal{G}$ be a graph dataset and each graph instance $G\in\mathcal{G}$ can be denoted as $G=(\mathcal{V},\mathcal{E},\mathbf{X},\mathbf{A})$ where $\mathcal{V}$ denotes the node set with a node feature matrix $\mathbf{X}\in\mathbb{R}^{|\mathcal{V}|\times F}$; $\mathcal{E}$ denotes the edge set and the connection of nodes can be further indicated by the adjacent matrix $\mathbf{A}\in\{0,1\}^{|\mathcal{V}|\times|\mathcal{V}|}$. Let $P_{\omega}$ denote a parameterized graph prompt function with learnable $\omega$. In most cases, graph prompts consist of some token vectors or subgraphs which will be integrated into the original graph $G$. $P_{\omega}$ indicates how to define such graph prompts and how to combine them with the original graph to generate a new graph: $G_{\omega}=P_{\omega}(G)$. Graph prompt learning aims to optimize the following target:

$$ $\omega^{*}=\arg\min_{\omega}\sum_{G\in\mathcal{G}}\mathcal{L}_{T_{dow}}(F_{ \theta^{*}}(P_{\omega}(G))$ (1) $$

Without loss of generality, we assume all these tasks are graph level (e.g., graph classification). That means $F_{\theta}(G)$ will output a graph-level embedding for the downstream task. For node-level and edge-level tasks, many studies (Sun et al., ; Liu et al., ) 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. (), can be primarily categorized into two types: prompt as token vectors added to node features, and prompt as additional graph inserted to the original graph. In the rest of this paper, we focus on two representative frameworks: GPF (Fang et al., ) as an example of adding extra prompt vectors, and All-in-One (Sun et al., ) 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 fundamental approaches among these methods. The rest graph prompt designs can usually be treated as their special cases or natural extensions.

Specifically, GPF aims to learn a token vector $\omega\in\mathbb{R}^{1\times F}$ 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 feature matrix $\mathbf{X}=\{x_{1},\cdots,x_{N}\}$ changed to $\mathbf{X}_{\omega}=\{x_{1}+\omega,\cdots,x_{N}+\omega\}$.
In this way, the original graph $G=(\mathcal{V},\mathcal{E},\mathbf{X},\mathbf{A})$ is changed to $P_{\omega}(G)=G_{\omega}=(\mathcal{V},\mathcal{E},\mathbf{X}_{\omega},\mathbf{
A})$.

All-in-One offers the prompt as a graph format by defining prompt tokens, token structures and inserting patterns. Let $\Omega\in\mathbb{R}^{k\times F}$ be the learnable matrix corresponding to $K$ prompt tokens. Let $\mathbf{A}_{in}\in\{0,1\}^{k\times k}$ indicate token structures where $A_{ij}=1$ means there is an inner link connecting the $i$-th and the $j$-th tokens and vice versa. $A_{in}$ 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 $\mathbf{A}_{cro}\in\{0,1\}^{k\times N}$. Then the graph prompt changes the original graph $G$ to $G_{\omega}=(\mathcal{V}_{\omega},\mathcal{E}_{\omega},\mathbf{X},\mathbf{
\Omega},\mathbf{A}_{\omega})$ where $\mathcal{V}_{\omega}$ is the collection of the original nodes and the token nodes; $\mathcal{E}_{\omega}$ includes the original edges, inner links among tokens and the cross links between tokens and the original nodes; $\mathbf{A}_{\omega}$ is the collection of $\mathbf{A}$,$\mathbf{A}_{in}$, and $\mathbf{A}_{cro}$.

Motivations.
Initially, Fang et al. () 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(\cdot)$, we can always learn a graph prompt reaching $F_{\theta^{*}}(G_{\omega})=F_{\theta^{*}}(t(G))$. However, this equivalence needs a very strong precondition: the graph model $F$ should not contain any non-linear layer, which is apparently very hard to meet in the practical solutions. Later, Sun et al. () extended this finding with more advanced prompts and empirically observed that the error to such approximation $F_{\theta^{*}}(G_{\omega})\rightarrow F_{\theta^{*}}(t(G))$ may relate to the non-linear layers of the graph model and the prompt design. However, 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 various 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, especially for questions like how powerful the graph prompt is in manipulating graph data? and why such capability works for downstream tasks?

In this paper, we go deeper in theory for the graph prompt capability of manipulating data. We conduct a comprehensive effectiveness analysis of general graph prompt learning through the concepts of “bridge sets” and “$\epsilon$-extended bridge sets” (see in section 3.3).
Based on extensive theoretical 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.

## 3 Why Graph Prompt Works? A Data Operation Perspective

Let $F_{\theta^{*}}$ be any given GNN model that has been pre-trained on a given task $T_{pre}$. Here $\theta^{*}$ means the parameters have been determined and frozen. For a given graph instance $G_{ori}$, we can expect the model to output appropriate graph-level embedding on $T_{pre}$ because this model has already been trained on this task. However, when we try to use this model on a new task $T_{dow}$, the output embedding, $F_{\theta^{*}}(G_{ori})$, can not guarantee acceptable performance because the pre-training task $T_{pre}$ may be incompatible with downstream tasks $T_{dow}$.

### 3.1 Perspective from Model Tuning

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 an optimal function, say $C$, which can map $G_{ori}$ to the embedding $C(G_{ori})$ to achieve good performance on $T_{dow}$. The nature of “pre-training and fine-tuning” is to hope the fine-tuned graph model could approximate to $C(G_{ori})$:

$$ $F_{\theta^{*}\rightarrow\theta^{\#}}(G_{ori})\rightarrow C(G_{ori})$ (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. $\theta^{*}\rightarrow\theta^{\#}$) can always surpass training the model from scratch because the preserved knowledge may contribute negatively to the downstream task.

### 3.2 Perspective from Data Operation

Instead of the above model-level tricks, graph prompts provide a data-level alternative. Some prior works (Fang et al., ; Sun et al., ) have initially proved that graph prompts can simulate any graph operations (e.g., deleting/adding nodes/edges/subgraphs, 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:

###### Theorem 1 .

Let $F_{\theta^{*}}$ be a GNN model pre-trained on task $T_{pre}$ with frozen parameters ($\theta^{*}$); let $T_{dow}$ be the downstream task and $C$ is an optimal function to $T_{dow}$. Given any graph $G_{ori}$, $C(G_{\text{ori}})$ denotes the optimal embedding vector to the downstream task (i.e. can be parsed to yield correct results for $G_{\text{ori}}$ in the downstream task), then there always exists a bridge graph $G_{bri}$ such that $F_{\theta^{*}}(G_{bri})=C(G_{ori})$.

A detailed proof of Theorem 1 can be seen in Appendix A.3.1, from which we can find that for any given graph $G_{ori}$, there always exists a bridge graph, say $G_{bri}$, making the following equation hold:

$$ $F_{\theta^{*}}(G_{bri})=C(G_{ori})$ (3) $$

That means, without needing to tune the model, we can try to find a data operation method that translates $G_{ori}$ to $G_{bri}$ 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 work, improve the performance on a new task (or even a 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?

###### Theorem 1 .

### 3.3 Measuring the Difficulty of Finding Bridge Graphs via Graph Prompts

Graph prompts can be viewed as a type of graph transformation operator. For example, the simplest graph prompt is just adding a specific prompt token vector $p_{\omega}$ to each node feature of the graph and then we can transform this graph $G$ into a family of graphs $\{P_{\omega}(G)|\omega\in\mathbb{R}^{F}\}$, where $P_{\omega}(G)$ represents the output graph obtained by graph prompt on $G$. Once $\omega$ is determined, the corresponding data transformation 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 $D_{P}(G)$. If the prompt operator maps the original graph $G_{\text{ori}}$ to a bridge graph $G_{\text{bri}}$ (i.e., $P(G_{\text{ori}})=G_{\text{bri}}$), then applying the pre-trained model $F_{\theta^{*}}$ yields $F_{\theta^{*}}(P(G_{\text{ori}}))=F_{\theta^{*}}(G_{\text{bri}})$, which conforms to the downstream task. In this process, we achieve seamless alignment of upstream and downstream tasks solely through data transformation operators, without relying on tuning the model’s parameters.

###### Definition 1 ( Bridge Set and $\epsilon$ -extended Bridge Set ) .

The bridge set of a graph $G$ is defined as:

$$ $B_{G}=\{G_{p}\mid F_{\theta^{*}}(G_{p})=C(G)\}$ $$

where $F_{\theta^{*}}$ is the frozen graph model from the pre-training task, and $C$ is the optimal function for the downstream task. The $\epsilon$-extended bridge set of $G$ is a relaxed version of the bridge set, which is defined as:

$$ $\epsilon\text{-}B_{G}=\{G_{p}\mid\epsilon=\|F_{\theta^{*}}(G_{p})-C(G)\|\leq \epsilon^{*}\}.$ $$

Achieving a transformation exactly equivalent to $C(G)$ is highly non-parametric and nonlinear. Finding the corresponding $G_{\text{bri}}$ or even the bridge set for any $G_{\text{ori}}$ 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 $P_{\omega}$ can be viewed as parameterized fitting for these operators and they usually contain very lightweight parameters, which dramatically simplify the search space compared with manually designed strategies. The effectiveness of graph prompting methods hinges on their ability to approximate these operators closely—whether they can uniformly project $G$ in the dataset into the bridge set $B_{G}$, or at least map them into the extended bridge set with a small upper error bound $\epsilon^{*}$.

###### Definition 1 ( Bridge Set and ϵ italic-ϵ \epsilon italic_ϵ -extended Bridge Set ) .

## 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 provided by frameworks such as GPF and All-in-One, denoted as parameterized operators $P_{\omega}$ with parameter $\omega$, can consistently project $G$ into an $\epsilon$-extended $B_{G}$, where $\epsilon$ has a uniform upper bound. This would initially validate the effectiveness of graph prompting methods in leveraging the potential of pre-trained models without compromising their expressive power. If $G$ can be seamlessly projected into $B_{G}$ or an $\epsilon$-extended $B_{G}$ (for small $\epsilon$), it would indicate excellent performance and full utilization of the model’s capabilities.

To this end, we first conduct a quantitative analysis of $P_{\omega}$’s graph transformation approximation ability on a single graph. With our proposed data operation perspective, we can reformulate the findings in Fang et al. () as follows:

###### Theorem 2 .

Given a GPF-like prompt vector $p_{\omega}$, if a GCN model $F_{\theta}$ does not have any non-linear transformations, then there exists an optimal $\omega$ for any input graph $G$ such that $P_{\omega}(G)\in B_{G}$.

This theorem is proved by Fang et al. () but it’s important to note that all GNN models employ non-linear transformations. According to the function approximation theorem for neural networks (Hornik et al., ), the core of improving a model’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 effectiveness of graph prompt learning in real downstream tasks, we offer the following theorems further:

###### Theorem 3 .

Given a GPF-like prompt vector $p_{\omega}$, if a GCN model $F_{\theta}$ has non-linear function layers but the model’s weight matrix is row full-rank, then there exists an optimal $\omega$ for any input graph $G$ such that $P_{\omega}(G)\in B_{G}$.

###### Theorem 4 .

Given the All-in-One-like prompt graph $SG_{\omega}$, if a GCN model $F_{\theta}$ does not have any non-linear transformations, or has non-linear layers but the model’s weight matrix is row full-rank, then there exists an optimal $\omega$ for any input graph $G$ such that $P_{\omega}(G)\in B_{G}$.

Theorems 3 and 4 are proved in Appendix A.3.2. Although we’ve only added the row full-rank condition, these two theorems significantly expand the applicability of Theorem 2.
According to Pennington & Worah (), well-trained models mostly contain full-rank matrices, which can be easily guaranteed by some tricks like orthogonal initialization, He initialization, etc. Raghu et al. () also find that a full-rank parameter matrix in the model usually indicates 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 perspective, we can assume that in most cases, both GPF-like and All-in-One-like frameworks can achieve seamless projection of $G$ into $B_{G}$, demonstrating the effectiveness and rationality of graph prompting.

For the cases where weight matrices are not full-rank, we have found that the error value ($\epsilon$) of the extended bridge set ($\epsilon-B_{G}$), 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 $\epsilon$ 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 a certain level of performance without experiencing extremely unexpectedly poor results:

###### Theorem 5 .

For a GCN model $F_{\theta}$, assume at least one layer’s parameter matrix is not full rank, for GPF or All-in-One prompt, there exists an upper bound of $\epsilon$ such that for any input graph $G$, there exists an optimal $\omega$ where $P_{\omega}(G)\in\epsilon\text{-}B_{G}$, with $\epsilon\leq\mu(\theta^{*})\cdot\lambda(G)$, where $\mu(\theta^{*})$ and $\lambda(G)$ correspond to the model and graph $G$, respectively.

Theorem 5 is proved in Appendix A.3.3, where the upper bound of the error $\epsilon$ can be further expressed as follows:

$$ $\mu(\theta^{*})\lambda(G)=\sin(\Phi/2)\|C(G)\|$ (4) $$

The upper bound has two terms, one part is related to the model because $\sin(\Phi/2)$ can be treated as a measurement of the model’s expressiveness, the details of which can be seen in Appendix A.3.3. The other part is related to $\|C(G)\|$.
Since the graph prompt aims to approximate $G$ with $P_{\omega}(G_{ori})$, that means the error is also related to the prompt design. In this way, we in theory confirm the intuitional findings by Sun et al. () as mentioned in our motivation section.

Figure: Figure 1: Error w.r.t matrices rank.
Refer to caption: extracted/5895852/graphs/4_1.png

The upper bound of $\epsilon$ given in Theorem 5 reveals the potential distortion of $B_{G}$’s shape when the matrix is not full-rank and the model’s expressive power is insufficient. This can lead to an increased distance between $B_{G}$ and the transformation domain $D_{P}(G)$ (see this term in section 3.3) of GPF or All-in-One prompts.
To confirm this judgment, we conducted a quantitative analysis using numerical methods for the case of non-full rank matrices. We make the graph model weight matrix be not full-rank (with rank $n-r$ where $n$ is the full rank number and $r=0,\cdots n$) and use the distance between the embedding vectors of $P_{\omega}(G)$ and $C(G)$ as the loss function. We applied stochastic gradient descent with a learning rate of 0.0001 to optimize $\omega$ until convergence. To avoid local optima, we repeated the process multiple times with different initializations for each graph. The results are shown in Figure 1, where the vertical axis is the empirical max $\epsilon$ of the extended $B_{G}$ and the horizontal axis is $r$ where $r=0,1,2,\cdots,9,10$, making the matrix rank become $n-r$. From Figure 1 we can find that with the increase of $r$, the rank of the model matrix becomes lower, making the model expressiveness worse and then leading to a larger error bound. Besides, more advanced graph prompts (e.g., GPF-Plus, All-in-One, and All-in-One-Plus) generally have a lower bound than the naive one (e.g., GPF).

###### Theorem 2 .

###### Theorem 3 .

###### Theorem 4 .

###### Theorem 5 .

### 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 transform each graph $G$ in the downstream dataset into its corresponding $B_{G}$ or $\epsilon\text{-}B_{G}$ (for small $\epsilon$). If such a uniform upper bound $\epsilon^{*}$ exists, it would theoretically validate the excellent performance of graph prompting in general downstream tasks, confirming the rational utilization of powerful upstream models.

For a batch of graphs, the complexity and information contained 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 transformation space of graph $G$ under prompt $P$ (see $D_{P}(\cdot)$ in section 3.3). A larger transformation space corresponds to a smaller $\epsilon$ 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:

###### Theorem 6 .

For a GCN model $F_{\theta}$, for GPF with a single prompt vector or All-in-One with a single-token graph prompt, given a batch of graphs $\mathcal{G}=\{G_{1},\cdots,G_{i},\cdots,G_{n}\}$, the root mean squared error (RMSE) over $\{\epsilon_{1},\cdots,\epsilon_{n}\}$ has a lower bound $\epsilon^{o}$ such that $RMSE(\epsilon_{1},\cdots,\epsilon_{n})\geq\epsilon^{o}$.

Theorem 6 is proved in Appendix A.3.4 and we also give the detailed formulation of $\epsilon^{o}$ in the proof, from which we can find that $\epsilon^{o}$ is related to graph data and the prompt token. This indicates that when the downstream task dataset is relatively large, we must correspondingly increase the transformation space of the prompt to better utilize the model’s capabilities, which also aligns with existing empirical observations (Liu et al., ). Then our next question is: With the increase of graphs, how does graph prompt complexity increase with their error bound increased?

Intuitively, a good graph prompt should not increase its complexity faster than the growth of the dataset because in that case the effectiveness of prompt learning in practical applications 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. (), empirical results using medium-scale 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 prompting can achieve comparable or even better results with less parameter adjustment scale:

###### Theorem 7 .

Given a GCN model $F_{\theta}$, an All-in-One-like graph prompt with multiple prompt tokens,
and a dataset $\mathcal{G}$ with $M$ graphs, there exists an upper bound denoted by $\epsilon^{*}$,
making an optimal $P_{\omega}$ such that $\forall G_{i}\in\mathcal{G},P_{\omega}(G_{i})\in\epsilon_{i}\text{-}B_{G_{i}}$, and $\sqrt{\sum^{M}_{i=1}\epsilon_{i}^{2}/M}\leq\epsilon^{*}$. $\epsilon^{*}$ can be further calculated as follows:

$$ $\epsilon^{*}=\sqrt{\sum_{i=k+1}^{M}\lambda_{i}/M}$ (5) $$

Here for the $M$ graphs in $\mathcal{G}$, we first
construct an optimal solution matrix according to function $C$, thus have: $S=[C(G_{1}),\ldots,C(G_{M})]$. Then $V=S^{\top}S\in\mathbb{R}^{M\times M}$ denotes the correlation matrix of downstream solutions upon such graph dataset. The eigenvalues of $V$ sorted by the descending order can be denoted as $\{\lambda_{1},\cdots,\lambda_{M}\}$. Then the upper bound $\epsilon^{*}$ 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, ). 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$ ($k\ll 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 researches (Liu et al., ; Sun et al., ; Wang et al., ; Zhu et al., ; Zi et al., ).

###### Theorem 6 .

###### Theorem 7 .

### 4.3 Value Distribution of the Data Operation Error with Graph Prompt

In the previous sections, we established a theoretical upper bound of $\epsilon\leq\epsilon^{*}$, allowing the graph prompt $P_{\omega}$ to map a given graph $G$ into the $\epsilon$-extended $B_{G}$ range. However, the conditions to reach this upper bound are often difficult to meet, making the theoretical upper bound usually correspond to some corner cases which may be not that practical in processing empirical experimental analysis. To offer stronger practical guidance for researchers’ general experimental purposes, the value distribution of $\epsilon$ (a.k.a “error range”), comes to our next point of interest. The error range analysis indicates a quantitative degree of the bridge set extension, which includes estimating the mean, and variance, and finding the approximate distribution pattern.

###### Definition 2 ( Graph Embedding Residual Vector ) .

Consider a graph model with Leaky-Relu as their activation function, we denote the graph embedding residual vector as $\bm{\beta}\in\mathbb{R}^{1\times F}$ where $F$ is the graph embedding dimensions. Each entry of $\bm{\beta}$ is related to the bridge graph embedding, graph prompt, and the original graph, which is mathematically defined as follows:

$$ $[\bm{\beta}]_{j}=\sum_{i}-\alpha^{k}w_{i}v_{ij}$ (6) $$

Figure: Figure 2: real $\epsilon$ distribution and fitted curves
Refer to caption: extracted/5895852/graphs/5_1.png

where $\alpha$ is the parameter of Leaky-Relu; $v_{ij}$ is the $j$-th element in the $i$-th node embedding of the bridge graph $G_{bri}$; $w_{i}$ is the weight of the $i$-th node for graph pooling (e.g., summation graph pooling means for any node $i$ in $G_{bri}$, we have $w_{i}=1$); $k$ can be either 0 0 or $-1$ and depends on the original graph, graph prompt, and the bridge graph, the details of which can be seen in Appendix 5. Here, we assume that $\bm{\beta}$ should follow an i.i.d. normal distribution with mean 0 and variance $c$ (we carefully discuss the rationality of this assumption in Appendix 5):
$\bm{\beta}\sim\mathcal{N}(0,cI_{n})$ where $I_{n}$ is the $n\times n$ identity matrix and $c$ is a positive constant. Then we theoretically find that $\epsilon$ conforms to the Chi distribution ($\chi_{k}$):

###### Theorem 8 .

Given a GCN model $F_{\theta}$ with the last layer parameter matrix having rank $F-r$ ($F$ is the graph embedding dimension, $r$ is the rank lost), an input graph $G$, for the optimal $\omega$, $P_{\omega}(G)\in\epsilon\text{-}B_{G}$. If the Graph Embedding Residuals follow the i.i.d. normal distribution, then $\epsilon$ follows a Chi distribution $\chi_{r}$ with $r$ free variables.

**Table 1: p-values w.r.t distributions**
| Distribution | Notation | p-value |
| --- | --- | --- |
| Chi | $\chi$ | 0.65 |
| Gamma | $\Gamma$ | 0.23 |
| Chi-squared | $\chi^{2}$ | 0.04 |
| Exponential | Exp | 0.01 |

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 $\epsilon$ a little different from standard $\chi_{k}$. Besides, there is also a theoretical upper bound $\epsilon^{*}$, making
the real distribution of $\epsilon$ more like a truncated $\chi_{k}$. The statistical measures of this distribution can be easily obtained as follows:

###### Corollary 1 (Statistical Measures and Confidence Values of $\epsilon$ ) .

The mean of $\epsilon$ is $c\sqrt{2}\frac{\Gamma((r+1)/2)}{\Gamma(r/2)}$, the variance is $c^{2}\left(r-2\frac{[\Gamma((r+1)/2)]^{2}}{[\Gamma(r/2)]^{2}}\right)$, and confidence values can be obtained through $C_{\chi}^{r,p}$ using numerical methods or table lookup, where
c is the scaling factor compared to the standard distribution, and r is the number of dimensions lost compared to a full-rank matrix.

To further confirm our theoretical findings, we compare the real-world distribution of $\epsilon$ with 4 commonly used distribution patterns (Chi, Chi-square, Exponential, and Gamma). Figure 2 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 a non-extreme range of $\epsilon$.

###### Definition 2 ( Graph Embedding Residual Vector ) .

###### Theorem 8 .

###### Corollary 1 (Statistical Measures and Confidence Values of ϵ italic-ϵ \epsilon italic_ϵ ) .

### 4.4 Extend the Discussion from Linear Models to Non-linear Models

While our previous analysis focused on GCN or linear aggregation models that can be represented in the form of “diffusion matrices”, many advanced models utilizing attention mechanisms exhibit distinctly different characteristics. Their aggregation methods involve the computation of attention matrices, which in turn depend on the node feature vectors of $G$. This can be considered as a non-linear model w.r.t $G$’s feature matrix. In our analysis, we use Graph Attention Networks (GAT) as an exemplar, as the attention mechanism in GAT is a common component in many non-linear models. Fortunately, the guarantees provided by our theorems do not differ significantly for these models. This indicates that even as models become more non-linear and complex, graph prompting can still effectively harness the powerful capabilities of pre-trained models:

###### Theorem 9 .

Let $F_{\theta}$ be a GAT model. If any layer of the model has a full row rank parameter matrix, then for the All-in-One prompting framework, for any input graph G, there exists an optimal $\omega$ such that $P_{\omega}(G)\in B_{G}$. When the parameter matrix is not full rank, there is an upper bound $\mu(\theta)\cdot\lambda(G)$ making $P_{\omega}(G)\in\epsilon\text{-}B_{G}$, $\epsilon\leq\mu(\theta)\cdot\lambda(G)$.

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, including 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 more complex and non-linear model architectures.

###### Theorem 9 .

## 5 Experiments

### 5.1 Experimental Settings

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 datasets by defining the dimension of graph feature vector ($F$), average of graph node numbers ($N_{avg}$), average of graph edge numbers ($E_{avg}$), and number of graphs in the dataset ($M$). These parameters characterize both individual graphs and the entire dataset, facilitating our study of the relationship between these features and $\epsilon$. We further conduct the experiments on the real-world dataset in Appendix B, from which we can find similar observations.

Figure: (a) GCN
Refer to caption: x1.png

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, we 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 5 by default. The default ReadOut method is mean pooling.

Training: In the graph prompting training process, we perform gradient descent on the parameters $\omega$ of the graph prompt $P_{\omega}$ using the Adam optimizer. We use a learning rate of $1\times 10^{-4}$ and weight decay of $5\times 10^{-5}$. We implement an early stopping mechanism with a maximum of 2,000 epochs by default. Our loss function is defined as $\|F_{\theta^{*}}(G_{p})-C(G)\|$ for single-graph tasks, and $\sqrt{\sum_{G\in\mathcal{G}}\|F_{\theta^{*}}(G_{p})-C(G)\|^{2}/M}$ for multi-graph tasks where $G_{p}$ is the combined graph with $G$ and graph prompt, and $C(G)$ means an optimal function to the downstream task, which is not accessible without a specific task. Since the ultimate purpose of graph prompting is to approximate graph operation, we here treat $C(\cdot)$ as various graph data permutations such as adding/deleting nodes, adding/deleting/changing edges, and transforming features of a given graph $G$. Then we wish to see how well the graph prompt reaches $C(G)$ by manipulating graph data with a graph prompt. For more detailed experimental settings, please check in the Appendix C.

### 5.2 On mapping to B G subscript 𝐵 𝐺 B_{G} italic_B start_POSTSUBSCRIPT italic_G end_POSTSUBSCRIPT with single graph

According to Theorems 3, 4, and 9, error-free projection can be achieved in full-rank situations. Here we investigate convergence properties with a maximum of 5,000 epochs. Figure 3 presents the results for GPF and All-in-One prompts with GCN and GAT, respectively. From the results we can find that for single-graph, full-rank matrix scenarios, both GPF and All-in-one approaches show loss converging to zero, which is consistent with our theoretical findings.

### 5.3 On mapping to ϵ ⁢ - ⁢ B G italic-ϵ - subscript 𝐵 𝐺 \epsilon\text{-}B_{G} italic_ϵ - italic_B start_POSTSUBSCRIPT italic_G end_POSTSUBSCRIPT 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 error upper bounds in the context of non-full-rank matrices given a single graph. Since showing this upper bound in practice 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 we take the maximum loss from these repetitions as the approximation to the upper bound.

Figure: (a) Feature Number vs. epsilon
Refer to caption: x3.png

Subsequently, we calculate the mean and standard deviation of these upper bounds to generate plots. The parameters of interest include rank loss (as shown in Figure 1 in section 4.1), node feature dimension (Figure 4a), graph size (Figure 4b), and model layer number (Figure 4c). Intuitively, with the increase of data complexity (e.g., larger features and graph size), the upper bound becomes larger in general. As the graph model becomes more complicated (e.g., layer number increase), the projected space becomes larger making the error bound intend 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 a lower error bound than the naive one (e.g., GPF). These observations can be naturally inferred from our theoretical analysis in section 4.1.

### 5.4 On mapping to ϵ ⁢ - ⁢ B G italic-ϵ - subscript 𝐵 𝐺 \epsilon\text{-}B_{G} italic_ϵ - italic_B start_POSTSUBSCRIPT italic_G end_POSTSUBSCRIPT with multiple graphs

Theorem 6 discusses a lower bound on the RMSE over the errors on multiple graphs with a single prompt token. In this section, we conducted experiments on the number of graphs in the dataset w.r.t the empirical minimum error. As shown in Figure 5a, the minimum error shows an upward trend and then tends to saturate, which is highly consistent with the findings in Theorem 6.

Figure: (a) Simple Prompt
Refer to caption: x6.png

Theorem 7 suggests that for the graph prompt with multiple tokens and multiple graphs, a small $k$ 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 $k$ remains fixed, and its counterpart case: how does the error change as $k$ 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 5b and Figure 5c, 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.

## 6 Conclusion

This paper addresses the theoretical gap in graph prompting by introducing a comprehensive framework from a data operation perspective. We introduced the concepts of “bridge sets” and “$\epsilon$-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 contributions are threefold: first, we established guarantee theorems confirming that graph prompts can simulate various graph data operations, explaining their effectiveness in aligning upstream and downstream tasks. Second, we derived upper 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 complexity influence these errors. Third, we analyzed the distribution of these errors and extended our theoretical findings from linear models like GCNs to non-linear models such as GATs, showcasing the robustness of graph prompting across different architectures. Our extensive experiments validate these theoretical results and confirm their practical implications, demonstrating that graph prompts can effectively leverage pre-trained models in various settings. By providing solid theoretical foundations, our work not only explains why graph prompts work but also guides the design of more effective prompting techniques. This empowers researchers and practitioners to utilize graph prompts with greater confidence, potentially leading to more efficient and generalized graph neural network models across diverse applications.

## Appendix

The appendix of this paper is organized as follows: Appendix 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.1, followed by fundamental lemmas (Appendix A.2) that will be used to prove our theorems. In Appendix A.3, we carefully prove the theorems in the main body of this paper, followed by a 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.

## Appendix A Theoretical Analysis And Proofs

Reading Guideline: Appendix A “Theoretical Results and Proofs” is divided into four subsections:

- •
A.1 Definitions and Preliminaries: Readers are advised to initially skip this subsection. It serves as a reference for unfamiliar terms encountered later in the text.
- •
A.2 Fundamental Lemmas: These properties are essential 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.
- •
A.3 Detailed Proofs of Main Theorems: This subsection 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 complete understanding.
- •
A.4 Additional Mathematical Lemmas: This subsection 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.

### A.1 Preliminaries And Definitions

#### A.1.1 Preliminaries

###### Preliminary 1 (GCN and GAT) .

Graph Convolutional Networks (GCN) Kipf & Welling () perform convolution operations on graph-structured data by aggregating feature information from a node’s neighbors. The recursive update rule for a GCN layer is:

$$ $\mathbf{H}^{(l+1)}=\sigma\left(\tilde{\mathbf{A}}\mathbf{H}^{(l)}\mathbf{W}^{( l)}\right),$ (7) $$

where $\tilde{\mathbf{A}}=\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$ is the normalized adjacency matrix, $\mathbf{H}^{(l)}$ is the node feature matrix at layer $l$, $\mathbf{W}^{(l)}$ is the learnable weight matrix, and $\sigma$ is a nonlinear activation function.

Graph Attention Networks (GAT) Veličković et al. () enhance GCNs by introducing attention mechanisms to weigh the importance of neighboring nodes during aggregation. In the simplest form of self-attention, the attention coefficient between node $i$ and node $j$ is based on the inner product of their feature vectors:

$$ $\displaystyle e_{ij}$ $\displaystyle=\mathbf{X}_{i}^{\top}\mathbf{X}_{j},$ (8) $\displaystyle\alpha_{ij}$ $\displaystyle=\frac{\exp(e_{ij})}{\sum_{k\in\mathcal{N}(i)}\exp(e_{ik})},$ (9) $\displaystyle\mathbf{H}_{i}^{(l+1)}$ $\displaystyle=\sigma\left(\sum_{j\in\mathcal{N}(i)}\alpha_{ij}\mathbf{H}_{j}^{ (l)}\mathbf{W}^{(l)}\right),$ (10) $$

where $\mathcal{N}(i)$ denotes the neighbors of node $i$, $\alpha_{ij}$ is the normalized attention coefficient, and $\mathbf{W}^{(l)}$ is the learnable weight matrix at layer $l$. This mechanism allows the model to focus on the most relevant neighbors when updating node representations.

###### Preliminary 2 (Pre-training and Fine-tuning vs Pre-training and Prompt) .

Pre-training and Fine-tuning Zhu et al. ()involves two stages: first, a model is pre-trained on a large dataset to learn general representations, and then it is fine-tuned on a specific downstream task.

Formally, let $F_{\theta^{*}}$ be the pre-trained model and $C(\cdot)$ 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 $G_{o}ri$ in the downstream task)

Fine-tuning aims to adjust the model parameters from $\theta^{*}$ to $\theta^{\#}$ so that:

$$ $F_{\theta^{*}\rightarrow\theta^{\#}}(G_{\text{ori}})\approx C(G_{\text{ori}}).$ (11) $$

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 a transformation from the original graph $G_{\text{ori}}$ to a prompt-enhanced graph $G_{\text{bri}}$ such that:

$$ $F_{\theta^{*}}(G_{\text{bri}})=C(G_{\text{ori}}).$ (12) $$

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.

###### Preliminary 3 (GPF and All-in-One) .

Graph Prompt Frameworks introduce learnable modifications to input graphs to enhance the performance of frozen pre-trained GNNs on downstream tasks. Two primary frameworks are prompt token vectors like GPF/GPF-Plus Fang et al. () and prompt subgraph like All-in-One Sun et al. ().

GPF (Graph Prompt Feature) adds a prompt vector to each node’s feature vectors. Let $\bm{\omega}=\{p\}$, $p\in\mathbb{R}^{F\times 1}$ be the learnable prompt vector, then the updated node features are:

$$ $[\mathbf{X}_{\omega}]_{i}=\mathbf{X}_{i}+p$ (13) $$

The original graph $G=(\mathbf{X},\mathbf{A})$ becomes the prompt-enhanced graph $G_{\omega}=(\mathbf{X}_{\omega},\mathbf{A})$. The prompt vector $p$ is optimized to minimize the loss on the downstream task:

$$ $p^{*}=\arg\min_{p}\sum_{G\in\mathcal{G}}\mathcal{L}_{T_{\text{dow}}}\left(F_{ \theta^{*}}(P_{\bm{\omega}}(G))\right)$ (14) $$

GPF-Plus adds a combination of multiple prompt vectors to each node’s features. Let $\bm{\omega}=\{p_{1},\cdots,p_{k},Q\}$, $p_{i}\in\mathbb{R}^{F\times 1}$ be the learnable prompt vector, $Q\in\mathbb{R}^{M\times k}$. Let $P=\begin{pmatrix}p_{1}^{\top}\\
\vdots\\
p_{k}^{\top}\end{pmatrix}$. The node features are updated in such a way:

$$ $[\mathbf{X}_{\omega}]_{i}=\mathbf{X}_{i}+Q_{i}P$ (15) $$

The original graph $G_{i}=(\mathbf{X},\mathbf{A})$ becomes the prompt-enhanced graph $G_{i,\omega}=(\mathbf{X}_{\omega},\mathbf{A})$.

All-in-One incorporates entire prompt subgraphs into the original graph. Let $P\in\mathbb{R}^{k\times F}$ represent $K$ learnable prompt token vectors, and $\mathbf{A}_{\text{in}}\in\{0,1\}^{k\times k}$ denote the internal adjacency among prompt tokens. The connections between prompt tokens and original nodes are defined by a cross adjacency matrix $\mathbf{A}_{\text{cro}}\in\{0,1\}^{k\times N}$. The prompt-enhanced graph is:

$$ $G_{\omega}=\left(\mathbf{A}\cup\mathbf{A}_{\text{in}}\cup\mathbf{A}_{\text{cro }},\mathbf{X}\cup\Omega\right).$ (16) $$

All-in-One optimizes the prompt tokens and their connections to adapt the pre-trained model to downstream tasks without altering the model parameters.

###### Preliminary 4 (Diffusion Matrix) .

Diffusion Matrix Gasteiger et al. () plays a crucial role in representing the diffusion process on a graph. Specifically, many GNN architectures can be expressed using the following formulation:

$$ $\mathbf{H}=\mathbf{S}\cdot\mathbf{X}\cdot\mathbf{W},$ (17) $$

Where: $\mathbf{S}$ is the diffusion matrix, derived from the graph’s adjacency matrix and model structure, which governs how information propagates across the graph. $\mathbf{X}$ is the original node feature matrix. $\mathbf{W}$ is the learnable weight matrix associated with the GNN layer. $\mathbf{H}$ is the node feature embedding matrix after message transformation and aggregation.

###### Preliminary 1 (GCN and GAT) .

###### Preliminary 2 (Pre-training and Fine-tuning vs Pre-training and Prompt) .

###### Preliminary 3 (GPF and All-in-One) .

###### Preliminary 4 (Diffusion Matrix) .

#### A.1.2 Definitions

We provide a glossary and default symbols meanings here for the reader’s convenience.

**Table 2: Glossary**
| Term | Explanation |
| --- | --- |
| Bridge Set $B_{G}$ | $B_{G}=\{G_{p}\mid F_{\theta^{*}}(G_{p})=C(G)\}$ |
| $\epsilon$-extended Bridge Set $\epsilon\text{-}B_{G}$ | $\epsilon\text{-}B_{G}=\{G_{p}\mid\|F_{\theta^{*}}(G_{p})-C(G)\|\leq\epsilon\}$ |
| Adjacency matrix | A square matrix used to represent a finite graph, where $A_{ij}=1$ if there is an edge from vertex $i$ to vertex $j$, and 0 otherwise |
| Diffusion matrix | The matrix equivalent to graph aggregation in GNNs |
| Span | For a set $V$, we say “p spans V” if p can take any value in V |
| $i$-th order embedding matrix | The embedding matrix after $i$ iterations of message passing and aggregation in a GNN |
| Cone | A set $C$ such that for any $x\in C$ and $\alpha\geq 0$, $\alpha x\in C$ |
| Convex set | A set $S$ such that for any $x,y\in S$ and $\alpha\in[0,1]$, $\alpha x+(1-\alpha)y\in S$ |
| Convex hull | The smallest convex set containing a given set of points |
| Graph Embedding Residual Vector | A vector representing the additional error in graph fitting due to non-linear components. For details, refer to the related 5 |

**Table 3: Symbol Table**
| Symbol | Description |
| --- | --- |
| $G_{ori}$ | The original graph without prompting |
| $P_{\omega}$ | Graph prompting method with parameter $\omega$ |
| $C(G_{ori})$ | The optimal embedding vector for the downstream task. $C(\cdot)$ can be understood as the optimal downstream task model |
| $G_{bri}$ | The bridge graph that can be used to obtain $C(G_{ori})$ using the original model |
| $G_{p}$ | The graph after prompting |
| $G_{\omega}$ | The graph after prompting with parameter $\omega$ |
| $\epsilon$ | Represents the extent of Bridge set expansion, i.e. the “error” |
| $n$ | Generally represents the number of layers in the GNN |
| $F$ | Represents the dimension of the graph feature vector |
| $N$ | Represents the number of nodes in the graph |
| $M$ | Represents the number of graphs in the dataset $\Omega$ |
| $\Phi$ | Represents the aperture of the convex cone can be understood as the maximum opening angle |

### A.2 Fundamental Lemmas

This lemma serves as 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.

##### Default Case

By default, we consider the GNN model as a surjective mapping operator from the graph set $\{G\}$ to $\mathbb{R}^{F}$, obtained after pre-training tasks. This operator can provide sufficient information to express the correct results of the graph in the pre-training task. (For instance, through a task-specific head mapping to the likelihood of a 0/1 decision.)

##### Notations

Here and in subsequent related content, we use $F_{\theta}$ to represent a GNN model whose aggregation process can be described by a diffusion matrix $S$. Here, $S$ is derived from the model type and the adjacency matrix $A$. For instance, in GCN, $S=A+\epsilon I$. The graph aggregation process is described as:

$$ $H^{(i)}=\sigma(S\cdot H^{(i-1)}\cdot W)$ (18) $$

Where $H^{(0)}$ is exactly the node feature matrix $X$, and $H^{(i)}$ is referred to as the i-th order embedding matrix. Without loss of generality, we analyze the non-linear function $\sigma$ using Leaky ReLU. Other non-linear functions such as sigmoid can be analyzed similarly.

Denote the transformation space of $P_{\omega}$ and $G$ by $D_{P}(G)=\{P_{\omega}(G)|\omega\in\mathbb{R}^{|\omega|}\}$, where $\omega$ is the parameter of method $P$, $|\omega|$ denotes the dimensionality of the parameter $\omega$, and $P$ represents either GPF or All In One prompt method. We denote $P_{\omega}(G)$ as $G_{\omega}$, and the corresponding diffusion matrix and node feature matrix $S$ and $X$ after prompt as $S_{\omega}$ and $X_{\omega}$ respectively.

Hence, the graph embedding vector obtained from graph $G_{\omega}$ prompted by $P_{\omega}$ after passing through the GNN model $F_{\theta}$ can be denoted as $F_{\theta}(G_{\omega})$.

Then, we can take each graph $G_{\omega}$ from the transformation space $D_{P}(G)$ and pass it through the GNN model $F_{\theta}$ to obtain the corresponding embedding vector. These embedding vectors can be collected into a set, the transformation embedding vector set:

$$ $\{F_{\theta}(G_{\omega})|\text{ for all }G_{\omega}\in D_{P}(G)\}$ (19) $$

Here, $F_{\theta}(G_{\omega})$ can be expressed in formula form as:

$$ $F_{\theta}(G_{\omega})=\text{ReadOut}(\sigma(S_{\omega}(\cdots\sigma(S_{\omega }X_{\omega}W)\cdots)W))=\text{ReadOut}(H^{(n)})$ (20) $$

Where, the dots $(\cdots)$ indicate that the parentheses are nested $n$ times, representing $n$ iterations of the message passaging and aggregation. $n$ is the number of layers. $H^{(n)}$ is the n-th embedding matrix.

ReadOut process is viewed as the linear combination of the embedding matrix $H$, i.e. $\text{ReadOut}(H^{(n)})=\mathbf{w}H^{(n)}$, where $\mathbf{w}$ 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:

$$ $K_{\theta}(G_{\omega})=H^{(n)}=\sigma(S_{\omega}(\cdots\sigma(S_{\omega}X_{ \omega}W)\cdots)W)$ (21) $$

#### A.2.1 On the Range of Graph Embedding Matrix After Graph Prompting, one prompt node case

###### Lemma 1 (Transformation of Graph after Prompt) .

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.

For GPF, the prompt vector is added to each node of graph $G$, while the topological connections of the graph remain unchanged. Therefore:

$$ $S_{\omega}=S,\quad X_{\omega}=X+\mathbf{1}_{N}\mathbf{p}^{\top}$ (22) $$

Where $N$ is the number of nodes in the graph, $p$ is the prompt vector, $p\in\mathbb{R}^{F}$, $F$ represents the dimension of the parameter vector, $\mathbf{1}_{N}$ is a vector $\in\mathbb{R}^{N}$ with every component 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.(as defined in A.1.1). Therefore:

$$ $S_{\omega}=\begin{pmatrix}S&l\\ l^{\top}&S_{NN}\end{pmatrix},\quad X_{\omega}=X+\mathbf{e}_{N}\mathbf{p}^{\top}$ (23) $$

Where $l\in\mathbb{R}^{N-1}$ is a column vector, $l_{i}\geq 0$, $\forall i\in\{1,\cdots,N-1\}$. In summary, the transformation of $X_{\omega}$ can be denoted as:

$$ $X_{\omega}=X+\mathbf{c}\mathbf{p}^{\top},\quad\text{where }\mathbf{c}_{i}\geq 0$ (24) $$

Where $\mathbb{c}$ can be referred to as the coefficient vector.

###### Lemma 2 (Range of Embedding Matrix after Nonlinear Transformation) .

Consider a weight matrix $W\in\mathbb{R}^{F\times F}$, and let $R(W)$ denote its row space. Suppose there exists a matrix $R$ such that each row of matrix $R$ is taken from the space $R(W)$. Let $\mathbf{c}$ be a vector with $c_{i}\geq 0$, and let $\mathcal{I}$ be the set of indices where $\mathbf{c}$ takes strictly positive values. Let $\mathbf{p}$ be vector spans $R(W)$(i.e. could take any value in $R(W)$).

Now, we consider $R+\mathbf{c}\mathbf{p}^{\top}$. For $i\in\mathcal{I}$, the $i$-th row of $R+\mathbf{c}\mathbf{p}^{\top}$ is: $R_{i}^{\top}+c_{i}\mathbf{p}^{\top}$ where $c_{i}>0$, $R_{i}\in R(W)$, $\mathbf{p}$ spans $R(W)$. Therefore, $R_{i}^{\top}+c_{i}\mathbf{p}^{\top}\in R(W)$, and spans $R(W)$. For $i\notin\mathcal{I}$, $c=0$, the $i$-th row of $R+\mathbf{c}\mathbf{p}^{\top}$ is simply $R_{i}^{\top}$.

Hence, $R+\mathbf{c}\mathbf{p}^{\top}$ can be written in the form of $R^{\prime}+(\Delta R+\mathbf{c}\mathbf{p}^{\top})$, where $\mathbf{p}$ spans $R(W)$, $R^{\prime}$ represents the matrix with the rows whose index $i\notin\mathcal{I}$, and all other rows set to zero. $\Delta R=R-R^{\prime}$.

Noted that every row of $\Delta R+\mathbf{c}\mathbf{p}^{\top}$ with index $i\in\mathcal{I}$, such row vector spans $R(W)$, as shown above, regardless of what the specific matrix $\Delta R$ is. Hence, the expressive power of graph prompting does not fundamentally differ for different $\Delta R$. We claim that from the perspective of embedding vectors (i.e., if the same embedding vectors can be produced through Readout, we don’t distinguish the specific form of the matrix), we can simplify $\Delta R$ into $\mathbf{cp_{0}^{\top}}$, where $\mathbf{c}$ is exactly the same $\mathbf{c}$ as the $\mathbf{c}$ in the assumption in the lemma, $\mathbf{p}_{0}\in R(W)$ is a vector with the same size as $\mathbf{c}$. More detailed discussion refer to A.4. In this way, the calculation is greatly simplified.

Now, consider adding a nonlinear function $\sigma(\cdot)=\text{Leaky-ReLU}(\cdot)$. We examine $\sigma(R^{\prime}+\Delta R+\mathbf{c}\mathbf{p}^{\top})$:

Scenario 1:
When $W$ has full row rank, i.e., $\mathbf{p}^{\top}$, $\sigma(\mathbf{p}^{\top})$ spans $\mathbb{R}^{F}$. In this case, for each row, we have:

For $i\in\mathcal{I}$

$$ $\displaystyle\sigma(R_{i}^{\prime\top}+\Delta R+c_{i}\mathbf{p}^{\top})=\sigma (R_{i}^{\prime\top}+c_{i}\mathbf{p}^{\top}+c_{i}\mathbf{p}_{0}^{\top})$ $\displaystyle=\sigma(c_{i}(\mathbf{p}^{\top}+\mathbf{p_{0}}^{\top}))$ $$

since $R^{\prime}_{i}=0$. After the Leaky-ReLU transformation, $\sigma(c_{i}(\mathbf{p}^{\top}+\mathbf{p_{0}}^{\top}))$ can still span $\mathbb{R}^{F}$. Let’s denote $\sigma(\mathbf{p}^{\top}+\mathbf{p_{0}}^{\top})$ as $\mathbf{p}^{\prime\top}$, i.e. $\sigma(\mathbf{p}^{\top}+\mathbf{p_{0}}^{\top})=\mathbf{p}^{\prime\top}$

For $i\notin\mathcal{I}$,

$$ $\displaystyle\sigma(R_{i}^{\prime\top}+c_{i}\mathbf{p}^{\top}+c_{i}\mathbf{p}_ {0}^{\top})$ $\displaystyle=\sigma(R_{i}^{\prime\top})$ $$

we use $\hat{R^{\prime}}_{i}^{\top}$ to denote $\sigma(R_{i}^{\prime\top})$ .

In conclusion, $\sigma(R^{\prime}+\Delta R+\mathbf{c}\mathbf{p}^{\top})$ can be written as $\hat{R}^{\prime}+\mathbf{c}\mathbf{p}^{\prime\top}$, where $\mathbf{p}$, $\mathbf{p}^{\prime}$ spans $\mathbb{R}^{F}$. Note that the property of $\mathbf{p}$ and $\mathbf{p}^{\prime}$ is the same and there is a natural bijection between them as pointed out A.4. Without causing confusion in notation, we can use $\mathbf{p}$ to represent $\mathbf{p}^{\prime}$ here.

Scenario 2: When $W$ is not full rank, $\mathbf{p}$ spans $R(W)$ space. In this case, row-wise, similar to Scenario 1:

$$ $\sigma(R^{\prime}+\mathbf{c}\mathbf{p}^{\top})=\hat{R}^{\prime}+\mathbf{c} \mathbf{p}^{\prime\top}$ (25) $$

where the set of all possible values of $\mathbf{p}^{\prime}$ is $V_{\alpha}$, defined as:

$$ $V_{\alpha}=\{\text{Leaky-ReLU}(\mathbf{v})\mid\mathbf{v}\in R(W)\}$ (26) $$

###### Lemma 3 (Range of Embedding Matrix after Prompt, Single Layer Case) .

Consider a single-layer GNN model $F_{\theta}$. $K_{\theta}$ represents the embedding process for obtaining graph embedding matrix $H$. Then, we have:

$$ $\displaystyle K_{\theta}(P_{\omega}(G))$ $\displaystyle=\sigma(S_{\omega}X_{\omega}W)$ $\displaystyle=\sigma(S_{\omega}(X+\mathbf{c}\mathbf{p}^{\top})W)$ $\displaystyle=\sigma(S_{\omega}XW+S_{\omega}\mathbf{c}\mathbf{p}^{\top}W)$ $\displaystyle=\sigma(R+\mathbf{c}^{\prime}\mathbf{p}^{\prime\top})$ $$

Where $R=S_{\omega}XW$, each row of $R$ is a vector in the row space $R(W)$. $\mathbf{c}^{\prime}=S_{\omega}\mathbf{c}$, $c^{\prime}_{i}\geq 0$, $\mathbf{p}^{\top}W=\mathbf{p}^{\prime\top}$. Here, $\mathbf{p}^{\prime}$ spans $R(W)$ since $\mathbf{p}$ spans $\mathbb{R}^{N}$. ($c^{\prime}_{i}\geq 0$ since each element of $S_{\omega}$ is non-negative, the sum of each column in $S_{\omega}$ is strictly greater than 0 and the initial value of $\mathbf{c}$ is either $\mathbf{e}_{N}$ or $\mathbf{1}_{N}$. Note that the number of positive terms increases in $\mathbf{c}$.)

According to lemma 2,
$\sigma(R+\mathbf{c}^{\prime}\mathbf{p}^{\prime\top})$ can be written as $\hat{R^{\prime}}+\mathbf{c}^{\prime}\mathbf{p}_{\dagger}^{\top}$. Here $\hat{R^{\prime}}$ represents the element-wise Leaky-ReLu of the rows of $R$ with index $i\in\mathcal{I}$ and other rows take $\mathbf{0}$.$\mathbf{p}_{\dagger}^{\top}$ represents $\mathbf{p}^{\top}$ ($\mathbf{p}$ spans $\mathbb{R}^{N}$) if W is of full row rank; $\mathbf{p}_{\dagger}^{\top}$ represents $\mathbf{p}^{\prime\top}$ ($\mathbf{p}^{\prime}$ spans $V_{\alpha}$) if W is non-full-rank, $V_{\alpha}=\{\text{Leaky-ReLU}(\mathbf{v})\mid\mathbf{v}\in R(W)\}$.

Hence, in conclusion, we have:
$K_{\theta}(P_{\omega}(G))=\hat{R^{\prime}}+\mathbf{c}^{\prime}\mathbf{p}_{
\dagger}^{\top}$

###### Lemma 4 (Range of Embedding Matrix after Prompt, Multiple Layer Full Rank Case) .

Consider a multiple-layer GNN model $F_{\theta}$. Then, we have:

$$ $K_{\theta}(G_{\omega})=\sigma(S_{\omega}(\cdots\sigma(S_{\omega}X_{\omega}W_{1 })\cdots)W_{n})$ (27) $$

According to lemma 3, we have:

$$ $\sigma(S_{\omega}X_{\omega}W_{1})=\hat{R^{\prime}}+\mathbf{c}^{\prime}\mathbf{ p}_{\dagger}^{\top}$ (28) $$

We are considering the full-rank case, i.e. $W$ is a full-rank matrix, according to lemma 3, we should take the equation for the full-rank case, which is:

$$ $\sigma(S_{\omega}P_{\omega}W_{1})=\hat{R}^{\prime}_{1}+\mathbf{c}_{1}\mathbf{p }^{\top}$ (29) $$

where $\mathbf{p}$ spans $\mathbb{R}^{N}$, $[\mathbf{c}_{1}]_{i}\geq 0$.

For this output, consider:

$$ $\sigma(S_{\omega}(\hat{R}^{\prime}_{1}+\mathbf{c}_{1}\mathbf{p}^{\top})W_{2})= \sigma(S_{\omega}\hat{R}^{\prime}_{1}W_{2}+\mathbf{c}_{2}\mathbf{p}^{\top})$ (30) $$

where $\mathbf{c}_{2}=S_{\omega}\mathbf{c}_{1}$, $[\mathbf{c}_{2}]_{i}>0$. Compared with the equation in lemma 3, we find only $R$ has been replaced by $S_{\omega}\hat{R}^{\prime}_{1}W_{2}$, and components remain unchanged, so this lemma can be used again. Hence, we have:

$$ $\sigma(S_{\omega}(\hat{R}^{\prime}_{1}+\mathbf{c}_{1}\mathbf{p}^{\top})W_{2})= \sigma(S_{\omega}\hat{R}^{\prime}_{1}W_{2}+\mathbf{c}_{2}\mathbf{p}^{\top})= \hat{R}^{\prime}_{2}+\mathbf{c}_{2}\mathbf{p}^{\top}$ (31) $$

where $\mathbf{p}$ spans $\mathbb{R}^{N}$.

Iteratively, we complete the entire $n$ aggregation processes of the GNN, and obtain:

$$ $K_{\theta}(P_{\omega}(G))=\hat{R}^{\prime}_{n}+\mathbf{c}_{n}\mathbf{p}^{\top}$ (32) $$

where $\mathbf{p}$ spans the $\mathbb{R}^{N}$. (This formula can represent the expressiveness of prompt $P_{\omega}$ in the full-rank case)

###### Remark 1 .

We can interpret this result as follows: (1) $\hat{R}^{\prime}_{n}$ is related to the embedding matrix of the original graph $G$ (2) $\mathbf{c}_{n}\mathbf{p}^{\top}$ describes the additional range of the expression of GNN model after adding prompt.

###### Lemma 1 (Transformation of Graph after Prompt) .

###### Lemma 2 (Range of Embedding Matrix after Nonlinear Transformation) .

###### Lemma 3 (Range of Embedding Matrix after Prompt, Single Layer Case) .

###### Lemma 4 (Range of Embedding Matrix after Prompt, Multiple Layer Full Rank Case) .

###### Remark 1 .

#### A.2.2 On the Range of Graph Embedding Matrix After Graph Prompting, multiple prompt node case

###### Lemma 5 (Range of Embedding Matrix after multiple prompt, Single Layer Case) .

We are considering single layer GNN $F_{\theta}$ here.

For the GPF or All in one Prompt Method, we can use the following uniform formula: we have $k$ independent prompt vectors $\mathbf{p}_{i}\in\mathbb{R}^{F}$ (or equivalently $k$ prompt nodes with $\mathbf{p}_{i}$ as its node feature), which form a $k\times F$ matrix $P$, where $P=\begin{pmatrix}\mathbf{p}_{1}^{\top}\\
\vdots\\
\mathbf{p}_{k}^{\top}\end{pmatrix}$. Denote by $M$ the number of graphs in the dataset $\Omega$. There exists an $M\times k$ coefficient matrix $Q$, each row vector of this coefficient matrix, denoted as $Q_{i}\in\mathbb{R}^{k}$, express how to linearly combine these $k$ vectors to add them to $i_{th}$ graph, i.e.:

$$ $G_{i,\omega}=(A_{\omega},X+\mathbf{c}\cdot Q_{i}^{\top}P)$ $$

According to lemma 3, the embedding matrix for the $i_{th}$ graph is:

$$ $\displaystyle H_{i}$ $\displaystyle=K_{\theta}(G_{i,\omega})$ $\displaystyle=\sigma(S_{i,\omega}X_{i,\omega}W)$ $\displaystyle=\sigma(S_{i,\omega}(X_{i,\omega}+\mathbf{1}_{N}Q_{i}^{\top}P)W)$ $\displaystyle=\sigma(R+\mathbf{c}_{1,i}Q_{i}^{\top}P)$ $\displaystyle=\sigma(R+\mathbf{c}_{1,i}\mathbf{p}_{i}^{\top})$ $\displaystyle=\hat{R}^{\prime}+\mathbf{c}_{1,i}\mathbf{p^{\prime}}_{i}^{\top}$ $$

Where $\mathbf{p}^{\prime}_{i}$ spans $\mathbb{R}^{F}$. (Implicit assumption is $W$ is full rank. we are discussing the upper limit of the expressive power of graph prompting, so we should use the full-rank model with stronger expressive power)

As discussed in lemma 2, we are considering from the perspective of embedding vectors. We claim that we can write $\mathbf{p}^{\prime}_{i}=(Q^{\prime}_{i})^{\top}P^{\prime}$, where ${Q^{\prime}}^{\top}_{i}$ denotes the $i_{th}$ row of $Q^{\prime}$, $Q^{\prime}$ is a linear combination coefficient matrix, which is a mapping of $Q$. $P^{\prime}$ spans $\mathbb{R}^{k\times F}$, which is a mapping of $P$. More detailed discussion is referred to A.4.

Without causing confusion in notation, we can directly use $P$, $Q$ to denote $P^{\prime}$, $Q^{\prime}$ here.

In summary, for a single-layer GNN with multiple prompts, the embedding matrix takes the form:

$$ $H_{i}=K(G_{i,\omega})=\hat{R}^{\prime}+\mathbf{c}_{1,i}\mathbf{p}_{i}^{\top}$ $$

where for any $i\in\{1,\ldots,M\}$, $\mathbf{p}_{i}=Q_{i}P$, and $\hat{R}^{\prime}$ is defined consistently with Lemma 3.

###### Lemma 6 (Range of Embedding Matrix after Prompt, Multiple Layer Case) .

We now consider a multiple-layer GNN model. For this model, we have:

$$ $K_{\theta}(G_{i,\omega})=H_{i}^{(n)}=\sigma(S_{i,\omega}(\cdots\sigma(S_{i, \omega}X_{i,\omega}W)\cdots)W)$ $$

where, according to lemma 5,

$$ $\sigma(S_{i,\omega}X_{i,\omega}W)=\sigma(S_{i,\omega}(X_{i}+\mathbf{1}_{N}Q_{i }P)W)=\hat{R}^{\prime}+\mathbf{c}_{1,i}p^{\top}$ $$

with $\mathbf{p}^{\top}=Q_{i}P$, and $P$ is the collection of $k$ prompts, spans $\mathbb{R}^{k\times F}$ space.

This form is consistent with lemma 5, except $R$ is replaced by $\hat{R}^{\prime}$ and $\mathbf{c}_{0}$ is replaced by $\mathbf{c}_{1,i}$. Applying this result again, we get:

$$ $\displaystyle\sigma(S_{i,\omega}\sigma(S_{i,\omega}X_{i,\omega}W_{1})W_{2})$ $\displaystyle=\sigma(S_{i,\omega}(\hat{R}^{\prime}+\mathbf{c}_{1,i}Q_{i}P)W_{2})$ $\displaystyle=\hat{R}^{\prime\prime}+\mathbf{c}_{2,i}Q_{i}P$ $$

Where $P$ spans $\mathbb{R}^{k\times F}$.

Iterativly applying lemma 5 $n$ times, we obtain:

$$ $K_{\theta}(G_{i,\omega})=H_{i}^{(n)}=\hat{R}^{(n)}+\mathbf{c}_{n,i}p_{i}^{\top }=\hat{R}^{(n)}+\mathbf{c}_{n,i}Q_{i}^{\top}P$ $$

where $P$ spans $\mathbb{R}^{k\times F}$, and $Q$ spans $\mathbb{R}^{M\times k}$.

In summary, for a multi-layer GNN with full-rank $W$ matrices in each layer, and for a dataset $\Omega$ with multiple graphs and use multiple prompts $P$, we have:

$$ $K_{\theta}(G_{i,\omega})=\hat{R}^{(n)}+\mathbf{c}_{n,i}p_{i}^{\top}=\hat{R}^{( n)}+\mathbf{c}_{n,i}Q_{i}^{\top}P$ $$

where $P$ spans $\mathbb{R}^{k\times F}$, $Q$ spans $\mathbb{R}^{M\times k}$, for any $i\in\{1,\ldots,M\}$.

###### Lemma 5 (Range of Embedding Matrix after multiple prompt, Single Layer Case) .

###### Lemma 6 (Range of Embedding Matrix after Prompt, Multiple Layer Case) .

#### A.2.3 On the Range of Graph Embedding Matrix After Graph Prompting, Not Full-Rank Case

###### Lemma 7 (Range of Embedding after Prompt, Multiple Layer Non-Full Rank Case) .

We consider a multiple-layer GNN model $F_{\theta}$ with a potential non-full-rank weight matrix.
We have:

$$ $K_{\theta}(G_{\omega})=\sigma(S_{\omega}(\cdots\sigma(S_{\omega}X_{\omega}W) \cdots)W)$ (33) $$

According to lemma 3, we have:

$$ $\sigma(S_{\omega}X_{\omega}W)=\hat{R^{\prime}}+\mathbf{c}^{\prime}\mathbf{p}_{ \dagger}^{\top}$ (34) $$

Since we are considering the non-full rank case, according to lemma 3, we should consider the non-full rank equation:

$$ $\sigma(S_{\omega}P_{\omega}W)=\hat{R}^{\prime}_{1}+\mathbf{c}_{1}\mathbf{p}^{\top}$ (35) $$

where $\mathbf{p}$ spans the set $V^{1}_{\alpha}$ as defined in lemma 3.

At this point, we can consider $\hat{R}^{\prime}_{1}$ equal to zero. Since, for GPF, $\mathbf{c}_{0}=\mathbf{1}_{N}$, and the monotonicity of $\mathbf{c}$ implies that each component of the vector $\mathbf{c}$ is strictly greater than 0. For All-in-One, $\mathbf{c}=\mathbf{e}_{N}$. We have $S_{\omega}=[s_{1},\ldots,s_{N}]$, where $s_{N}=\begin{pmatrix}l\\
S_{NN}\end{pmatrix}$, $\mathbf{c}^{\prime}=s_{N}$. we assume $l>0$ component-wise(This can be achieved by adjusting parameters in All in one), then $\mathbf{c}^{\prime}$ is component-wise $>0$.

Recall that $R^{\prime}_{1}$ only preserves rows where the corresponding component of $\mathbf{c}=0$. Hence, $\hat{R}^{\prime}_{1}$ can be considered to be zero.

For this output, we consider:

$$ $\sigma(S_{\omega}(\hat{R}^{\prime}_{1}+\mathbf{c}_{1}\mathbf{p}^{\top})W)= \sigma(S_{\omega}(\mathbf{c}_{1}\mathbf{p}^{\top})W)=\sigma(\mathbf{c}_{2} \mathbf{p^{\prime}}^{\top})=\mathbf{c}_{2}\mathbf{p^{\prime\prime}}^{\top}$ (36) $$

Here, $\mathbf{p^{\prime}}^{\top}=\mathbf{p}^{\top}W$. This demonstrates that: (1). $\mathbf{p}^{\prime}$ spans $V^{1}_{\alpha}W$ (2). $\mathbf{p}^{\prime}\in R(W)\vspace{0.15cm}$. Hence, the set of the range of $\mathbf{p^{\prime}}$ is only a linear transformation to $V^{1}_{\alpha}$, i.e. $V^{1}_{\alpha}W$. The set of the range of $\mathbf{p^{\prime\prime}}$ is operating Leaky-ReLU to the set $V^{1}_{\alpha}W$, i.e. $\sigma(V^{1}_{\alpha}W)$, denoted by $V^{2}_{\alpha}$.

Iteratively, We have:

$$ $F_{\theta}(G_{\omega})=\mathbf{c}_{n}\mathbf{p}^{(n)\top}$ (37) $$

where $\mathbf{p}^{(n)}$ spans $V^{n}_{\alpha}$. Specifically, according to lemma 12, $V^{n}_{\alpha}$ is a cone surface, i.e., for any $\mathbf{v}\in V^{n}_{\alpha}$ and $\lambda\in\mathbb{R}^{+}$, $\lambda\mathbf{v}\in V^{n}_{\alpha}$.

###### Remark 2 .

Choosing $\hat{R}^{\prime}_{1}$ to be zero is to simplify the calculation without affecting the theorem. Based on the principle that the minimum of the whole is 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.

###### Lemma 8 (Embedding Matrix Property, Multiple Layer GNN Non-Full Rank Case) .

We consider the GNN model $F_{\theta}$ be multi-layered and could have not a full-rank weight matrix.
Then, the embedding matrix of graph $G$, according to the iterative formula of GNN, is:

$$ $K_{\theta}(G_{\omega})=\sigma(S(\cdots\sigma(S\cdot X\cdot W)\cdots)W)$ (38) $$

Let $S\cdot X$ be denoted as $X^{\prime}$. Then $X^{\prime}W$ is an $N\times F$ embedding matrix where each row is in the row space of $W$. According to the properties of Leaky-ReLU and the definition of $V^{1}_{\alpha}$, $\sigma(X^{\prime}W)=Y^{\prime}$ where each row vector is in the set $V^{1}_{\alpha}$.

Then $SY^{\prime}=H^{\prime}$, where each row of $H^{\prime}$ is a positive linear combination of rows in $Y^{\prime}$. Hence, each row of $H^{\prime}$ should also be in the convex hull of cone surface $V^{1}_{\alpha}$. We name such a convex hull to be $C^{1}_{\alpha}$ , and further, $C^{1}_{\alpha}$ is a convex cone. Based on lemma12, iteratively, we have each row of $H^{(i)}$ should also be in the convex hull $C^{i}_{\alpha}$ of cone surface $V^{i}_{\alpha}$.

We conclude the following: For any graph $G$, each row vector of the embedding matrix $H^{(n)}$, obtained after applying the GNN model $F_{\theta}$ to $G$, lies within a specific convex cone, whose surface is exactly $V^{n}_{\alpha}$ mentioned in lemma 7

###### Remark 3 .

Lemma 8 characterizes the properties of each row vector in the embedding matrix after it has been processed by a non-full rank GNN model.

###### Lemma 7 (Range of Embedding after Prompt, Multiple Layer Non-Full Rank Case) .

###### Remark 2 .

###### Lemma 8 (Embedding Matrix Property, Multiple Layer GNN Non-Full Rank Case) .

###### Remark 3 .

### A.3 Proof of Theorem in the Paper

#### A.3.1 Bridge Graph Existence Theorem

Proof of Theorem 1

###### Proof.

For a given $G_{ori}$ and a downstream task $T_{dow}$, the embedding vector corresponding to the downstream task is formally defined as the embedding vector produced by the optimal downstream model for $T_{dow}$, which is thus uniquely determined.

Given our previous definition for the default case A.2, the $F_{\theta}$ discussed here is a surjective mapping from the graph space $\{G\}$ to $\mathbb{R}^{F}$. According to the properties of surjective mappings, for this particular $C(G_{\text{ori}})\in\mathbb{R}^{F}$, there must exist a special graph $\hat{G}_{\text{bri}}$ such that:

$$ $F_{\theta}(\hat{G}_{\text{bri}})=C(G_{\text{ori}})$ (39) $$

Upon examining the definition of $G_{\text{bri}}$, we find that $\hat{G}_{\text{bri}}=G_{\text{bri}}$. Theorem 1 is thereby proved.
∎

###### Proof.

#### A.3.2 On Error-free Mapping to Bridge Set

Proof of Theorem 3 and 4

###### Proof.

We aim to prove that there exists an optimal parameter $\omega_{0}$ such that the transformed graph obtained through the graph prompting method $P_{\omega_{0}}(G)\in B_{G}$. This is equivalent to proving that there exists $\omega_{0}$ such that $F_{\theta}(P_{\omega_{0}}(G_{ori}))=F_{\theta}(G_{bri})=C(G_{ori})$, where the existence of $G_{bri}$ is guaranteed by Theorem 1.

Consider a multi-layer GNN model $F_{\theta}$ where each layer has full-rank matrices and non-linear function $\sigma(\cdot)$. According to lemma 4, regardless GPF or All-in-One prompt method, we have:

$$ $K_{\theta}(P_{\omega}(G_{ori}))=H^{(n)}=R^{(n)}+\mathbf{c}\mathbf{p}^{\top}$ $$

Where $c_{i}\geq 0$, $\|\mathbf{c}\|>0$, $\mathbf{p}$ spans $\mathbb{R}^{F}$, $K_{\theta}(\cdot)$ denote the process of obtaining the embedding matrix, $R^{(n)}$ a matrix $\in\mathbb{R}^{N\times F}$, which is related to the embedding matrix of the original graph $G$ without prompting, $\omega$ denotes the parameter of the Prompt method.

Then, $F_{\theta}(P_{\omega}(G_{ori}))=\text{Readout}(H^{(n)})$. Considering the readout function as linearly combines the embedding vectors of nodes $1$ to $n$ with certain weights: $\mathbf{w}=[w_{1},\ldots,w_{n}]$, where $w_{i}>0$, as defined in A.2, we have:

$$ $F_{\theta}(P_{\omega}(G_{ori}))=\sum_{i}w_{i}H^{(n)}_{i}$ $$

Then:

$$ $F_{\theta}(P_{\omega}(G_{ori}))=\mathbf{w}R^{(n)}+\mathbf{w}^{\top}\mathbf{c} \mathbf{p}^{\top}=R_{0}^{\top}+\lambda\mathbf{p}^{\top}$ $$

where $R_{0}^{\top}=\mathbf{w}R^{(n)}$, $\lambda=\mathbf{w}^{\top}\mathbf{c}$ ($\lambda>0$), since $\mathbf{p}$ spans $\mathbb{R}^{F}$, we know that $F_{\theta}(P_{\omega}(G_{ori}))=R_{0}^{\top}+\lambda\mathbf{p}^{\top}$ is a surjective mapping from the range of $\omega$ to $\mathbb{R}^{F}$. Meanwhile, $F_{\theta}(G_{bri})$ is a fixed vector in $\mathbb{R}^{F}$.

By the surjective property, there must exist an $\omega_{0}$ such that:

$$ $F_{\theta}(P_{\omega_{0}}(G_{ori}))=F_{\theta}(G_{bridge})=C(G)$ $$

This completes the proof.
∎

###### Proof.

#### A.3.3 On Error Upper Bound Analysis of Mapping to Bridge Set at Single Graph Level

Proof of Theorems 5

###### 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 $\omega_{0}$ such that the transformed graph $P_{\omega_{0}}(G)\in\epsilon$-$B_{G}$, where the “error” $\epsilon$ takes the minimum possible value: $\epsilon_{0}$.
We aim to prove Theorems 5 by showing that for any graph $G$ there exists an $\delta_{0}$ such that:

$$ $\frac{\|F_{\theta}(P_{\omega_{0}}(G_{ori}))-F_{\theta}(G_{bri})\|}{\|F_{\theta }(G_{bri})\|}<\delta_{0}$ $$

According to lemma 7 and 8, for both GPF and All-in-One prompts, there exists a convex cone $C$ such that:

$$ $K_{\theta}(G_{\omega})=H^{(n)}=\mathbf{c}\mathbf{p}^{\top}$ $$

where $\mathbf{p}$ is on the surface of such convex cone, i.e., $\partial C$, and $F_{\theta}(G_{bri})$ is a vector inside the convex cone $C$.

Using the same readout method as in A.3.2, we have:

$$ $F_{\theta}(P_{\omega}(G_{ori}))=\sum_{i}w_{i}H^{(n)}_{i}=\mathbf{w}^{\top} \mathbf{c}\mathbf{p}^{\top}=\lambda\mathbf{p}^{\top}$ $$

where $\mathbf{p}$ spans surface of the convex cone ($\partial C$). Based on the properties of the cone surface,
$\lambda\mathbf{p}$ is on the cone surface for any $\lambda>0$, so we have
$F_{\theta}(P_{\omega}(G_{ori}))$ spans the cone surface $\partial C$.

Consider $\|F_{\theta}(G_{bri})-F_{\theta}(P_{\omega}(G_{ori}))\|$. The minimum value of this distance, according to definition 3, is the distance from an element in the convex cone to the cone surface, which is $\sin(\theta)\|v\|$, where $\theta$ represents the angle of $v$ to the surface.

This proves that $\frac{\|F_{\theta}(P_{\omega}(G_{ori}))-F_{\theta}(G_{bridge})\|}{\|F_{\theta}
(G_{bridge})\|}$ has a upper bound, $\sin(\theta)$, where $\theta$ is related to both $v$ and $C$.

According to definition 4, we know that $\theta\leq\Phi/2$, where $\Phi$ represents the aperture of the cone $C$.

In summary:

$$ $\displaystyle\|F_{\theta}(P_{\omega}(G_{ori}))-C(G_{ori})\|$ $\displaystyle=\|F_{\theta}(P_{\omega}(G_{ori}))-F_{\theta}(G_{bri})\|$ (40) $\displaystyle\leq\sin(\Phi/2)\cdot\|F_{\theta}(G_{bri})\|$ (41) $\displaystyle=\sin(\Phi/2)\cdot\|C(G_{ori})\|$ (42) $$

The left part of the error upper bound ($\sin(\Phi/2)$) is only related to the model, while the right part is only related to the data ($G_{ori}$). This indicates that the error upper bound grows linearly with $\|C(G_{ori})\|$ by a coefficient, i.e. $\sin(\Phi/2)$.

Since the features magnitude and number of node of the graph data in the dataset have upper bounds, $\|C(G_{ori})\|$ 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 a certain error range.
∎

###### Proof.

#### A.3.4 Error Bound Analysis of Mapping to Bridge Set at Multiple Graph Level

Proof of Theorems 6

###### Proof.

We prove this theorem by considering the sum of squared of $\epsilon$, where $\epsilon$ denotes the degree of the bridge set extension. For simplicity, we will refer to it as the “error”.
Consider a dataset with M graphs. We use either a single prompt vector GPF or a single node-prompted subgraph All-in-one approach. According to lemma 4, for each graph, we have the following formula:

$$ $K_{\theta}(G_{i},\omega)=H_{i}^{(n)}=R_{i}^{(n)}+\mathbf{c}_{i}\mathbf{p}^{\top}$ (43) $$

where $\mathbf{c}_{i}$ have the subscript $i$ to indicate that different graphs produce different $\mathbf{c}$, $\mathbf{p}$ spans $\mathbb{R}^{F}$. Note that $\mathbf{p}$ does not have a subscript $i$ because single Prompt Vector is used for all graphs, despite different graphs having different diffusion matrices $S$ and feature matrices $X$.

After performing the ReadOut operation, we get:

$$ $F_{\theta}(G_{i})=\mathbf{w}^{\top}H_{i}^{(n)}=\mathbf{w}^{\top}R_{i}^{(n)}+ \mathbf{w}^{\top}\mathbf{c}_{i}\mathbf{p}^{\top}=R_{0}^{\top}+\lambda_{i} \mathbf{p}^{\top}$ (44) $$

Where $\lambda_{i}=\mathbf{w}^{\top}\mathbf{c}_{i}$. We can assume $R_{0}^{\top}$ is a zero matrix without loss of generality as discussed in lemma 7.

Now, consider the sum of squared “errors”:

$$ $\displaystyle\sum_{i=1}^{M}\|C(G_{i})-\lambda_{i}\mathbf{p}\|^{2}$ $\displaystyle=\sum_{i=1}^{M}\lambda_{i}^{2}\|(1/\lambda_{i})C(G_{i})-\mathbf{p }\|^{2}$ (45) $\displaystyle=\sum_{i=1}^{M}\lambda_{i}^{2}\|C_{\lambda_{i}}(G_{i})-\mathbf{p} \|^{2}$ (46) $$

The optimal $\omega_{0}$ corresponds to correspond to minimizing the following loss value.

$$ $J=\sum_{i=1}^{M}\lambda_{i}^{2}\|C_{\lambda_{i}}(G_{i})-\mathbf{p}\|^{2}$ (47) $$

Which is the weighted sum of squared distances from $\mathbf{p}$ to $M$ different points in the space, denoted as: $D((C_{\lambda_{1}}(G_{1}),\ldots,C_{\lambda_{n}}(G_{n})),(\lambda_{1},\ldots,
\lambda_{n}))$

The optimal $p$ is the weighted centroid of these $n$ vectors $(C_{\lambda_{i}}(G_{i}))_{i=1}^{M}$, as pointed out at Boyd & Vandenberghe (), i.e.:

$$ $\mathbf{p}^{*}=\frac{\sum_{i=1}^{M}\lambda_{i}C(G_{i})}{\sum_{i=1}^{M}\lambda_ {i}^{2}}$ (48) $$

The closed-form expression for $J_{min}$ is:

$$ $J_{min}=\sum_{i=1}^{M}\|C(G_{i})-\lambda_{i}\mathbf{p}^{*}\|^{2}$ (49) $$

Therefore, the minimum root mean squared of $\epsilon$ value(“RMSE”) $I(G_{1},\ldots,G_{n})$ satisfies

$$ $\displaystyle I(G_{1},\ldots,G_{M})$ $\displaystyle=\min_{\omega}(\sqrt{\sum_{i=1}^{M}\lambda_{i}^{2}\|C_{\lambda_{i }}(G_{i})-\mathbf{p}\|^{2}/M})=\sqrt{\sum_{i=1}^{M}\|C(G_{i})-\lambda_{i} \mathbf{p}^{*}\|^{2}/M}$ (50) $\displaystyle=\sqrt{\frac{J_{min}}{M}}$ (51) $$

Here, $I(G_{1},\ldots,G_{M})$ is a lower bound that is independent of the value of $\omega$, but is related to the distances between $C(G_{i})$. This proves that the capability of a single prompt has an upper limit in this case, which proves Theorem 6.
∎

Proof of Theorem 7

###### Proof.

We validate this theorem by minimizing the sum of squared of $\epsilon$, where $\epsilon$ denotes the degree of the bridge set extension. For simplicity, we will refer to it as the “error”.
Consider a dataset with M graphs. We use k prompt vectors for GPF or k node-prompted subgraphs. According to lemma 6, for each graph, we have:

$$ $H_{i}^{(n)}=K_{\theta}(G_{i},\omega)=R_{i}^{(n)}+\mathbf{c}_{i}Q^{\top}_{i}P$ (52) $$

where $P$ spans $\mathbb{R}^{k\times F}$, $Q$ represents the combination coefficients of different Prompts, and spans $\mathbb{R}^{M\times k}$. As discussed in Proof for Theorem 6, we can assume ${R}_{i}^{(n)}$ is a zero matrix for simplicity.

After the ReadOut operation:

$$ $F_{\theta}(G_{i})=\mathbf{w}^{\top}H_{i}^{(n)}=\mathbf{w}^{\top}\mathbf{c}_{i} Q^{\top}_{i}P=\lambda_{i}Q^{\top}_{i}P$ (53) $$

Since $Q_{i}$ spans $\mathbb{R}^{k}$, $\lambda_{i}Q_{i}=Q^{\prime}_{i}$ also spans $\mathbb{R}^{k}$ ($\lambda_{i}>0$). Thus, $F_{\theta}(G_{i})$ spans the row space $R(P)$, which is (at most) a $k$-dimensional vector space determined by $k$ independent prompt vectors.
Consider:

$$ $\sum_{i=1}^{M}\|C^{\top}(G_{i})-{Q^{\prime}}^{\top}_{i}P\|^{2}=\sum_{i=1}^{M} \|C(G_{i})-\mathbf{p^{\prime}}_{i}\|^{2}$ (54) $$

where $\mathbf{p^{\prime}}_{i}$ spans the row space of $P$. Equation 54 is the sum of squared distances from n vectors to the vector space $P$. We want to minimize:

$$ $J=\sum_{i=1}^{M}\|C(G_{i})-\mathbf{p^{\prime}}_{i}\|^{2}$ (55) $$

Let $S=[C(G_{1}),\ldots,C(G_{M}]$ and $V=S^{\top}S$. According to lemma 11, the minimum value of $J$ is the sum of the $(k+1)$-th to $M$-th largest eigenvalues of $V$:

$$ $J_{min}=\sum_{i=k+1}^{M}\lambda^{V}_{i}$ (56) $$

Where $\lambda^{V}_{i}$ denotes the $i_{th}$ largest eigenvalue of symmetric matrix $V$. Therefore, there exists an optimal $\omega_{0}$ such that the mean squared epsilon(error) is:

$$ $\mathcal{L}(G_{1},\cdots,G_{M})=\sqrt{\frac{\sum_{i=k+1}^{M}\lambda_{i}^{V}}{M}}$ (57) $$

This indicates that in the multiple prompt framework, the optimal mean squared $\epsilon$ has an upper bound $\mathcal{L}(G_{1},\cdots,G_{M})$, which proves Theorem 7.

Notably, if $k\geq n$, we can find a suitable $P$ such that $F_{\theta}(G_{i})$ and $C(G_{i})$ are error-free for any $i\in\{1,\cdots,M\}$. This can be seen as an extension of Theorems 3 and 4.
∎

###### Remark 4 .

As Johnstone () pointed out, the eigenvalues of $V=C^{\top}C$ in datasets often exhibit a truncated eigenvalue distribution. The first $k_{0}$ eigenvalues explain most of the variance. Furthermore, Jolliffe & Cadima () 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.

###### Proof.

###### Proof.

###### Remark 4 .

#### A.3.5 Error Distribution Analysis of Mapping to Bridge Set

Proof of Theorem 8

###### Proof.

Consider a GNN model $F_{\theta}$ where the $W$ matrix in the last layer is not full rank. Denote by $F-r$ the rank of the $W$ weight matrix in the last layer. Consider a GPF prompt or a single node prompt in an All-in-one framework.

According to lemma 4, we have:

$$ $H^{(n-1)}=R^{(n-1)}+\mathbf{c}\mathbf{p}^{\top}$ (58) $$

where $H^{(n-1)}$ is the $(n-1)_{th}$ order embedding matrix, $\mathbf{p}$ spans $\mathbb{R}^{F}$.
As discussed in lemma 7, for simplicity, we can assume $R^{(n-1)}=0$. Then:

$$ $\displaystyle K_{\theta}(G_{\omega})=H^{n}(G_{\omega})$ $\displaystyle=\sigma(S_{\omega}(R^{(n-1)}+\mathbf{c}\mathbf{p}^{\top})W)$ (59) $\displaystyle=\sigma(S_{\omega}\mathbf{c}\mathbf{p}^{\top}W)$ $\displaystyle=\sigma(\mathbf{c^{\prime}}\mathbf{p^{\prime}}^{\top})$ $$

where $\mathbf{p}^{\prime}$ spans the row space $R(W)$.

Consider $K_{\theta}(G_{bri})=H^{(n)}(G_{bri})=\begin{pmatrix}\mathbf{v}^{\top}_{1}\\
\vdots\\
\mathbf{v}^{\top}_{n}\end{pmatrix}$, where $\mathbf{v}_{i}\in\mathbb{R}^{F}$.

Then, $\Delta F_{\theta}(G_{ori})=F_{\theta}(G_{\omega})-C(G_{ori})=\mathbf{w}^{\top}
H^{(n)}(G_{\omega})-\mathbf{w}^{\top}H^{(n)}(G_{bri})=\mathbf{w}^{\top}(H^{(n)
}(G_{\omega})-H^{(n)}(G_{bri}))=\mathbf{w}^{\top}\Delta H$.

Here, $\Delta H_{ij}=\sigma(c_{i}p^{\prime}_{j})-v_{ij}=\sigma(c_{i}p^{\prime}_{j}-
\sigma^{-1}(v_{ij}))$.

Therefore, $[\Delta F_{\theta}(G)]_{j}=\sum_{i}w_{i}\sigma(c_{i}p^{\prime}_{j}-\sigma^{-1}
(v_{ij}))$. This is a piecewise linear function of $p^{\prime}_{j}$, denoted as $g(p)=\alpha(p)p-\beta(p)$ for simplicity, where $\alpha$ and $\beta$ are the coefficients of this piecewise linear function when $x$ takes the value $p$.

When $\omega$ (the graph prompt coefficient) is optimal, due to the independence of $p^{j}$, all $[\Delta F_{\theta}(G)]^{j}$ should take the minimum absolute value. That is, $p^{*}$ minimizes $|g(p^{*}_{j})|$, for any $j\in\{1,\cdots,F\}$.

At this point, $\|\Delta F_{\theta}(G)\|=\sqrt{\sum_{j=1}^{F}g(p^{*}_{j})^{2}}$, where $g(p^{*}_{j})=\sum^{N}_{i=1}w_{i}\sigma(c_{i}p^{*}_{j}-\sigma^{-1}(v_{ij}))=
\alpha_{j}p^{*}_{j}-\beta_{j}$.

Let $p^{\prime*}=\begin{pmatrix}\alpha_{1}&\cdots&0\\
\vdots&\ddots&\vdots\\
0&\cdots&\alpha_{F}\end{pmatrix}p^{*}$ and $\bm{\beta}=[\beta_{1},\ldots,\beta_{F}]^{\top}$.

Then $p^{\prime*}\in R(W)$, so $\|\Delta F_{\theta}(G)\|=\|p^{\prime*}-\bm{\beta}\|$. This value represents the distance between $\bm{\beta}$ and $p^{\prime*}$. Since $p^{\prime*}$ already minimizes $\|\bm{A}p^{\prime}-\bm{\beta}\|$ and $\bm{A}p^{\prime}\in R(\bm{A}W)$, $\forall p^{\prime}\in R(W)$, where $\bm{A}$ denotes $diag(\alpha_{1},\cdots,\alpha_{F})$,we can estimate $\|p^{*^{\prime}}-\bm{\beta}\|$ using the distance from $\bm{\beta}$ to the space $R(\bm{A}W)$.

Consider the projection matrix $P$ onto the space $R(\bm{A}W)$. Then $\|\Delta F_{\theta}(G)\|=\|(I-P)\bm{\beta}\|$.

We make the following assumption: when $p_{j}=p^{*}_{j}$, $\beta_{j}$ follows an i.i.d. normal distribution.

$$ $\beta_{j}=\sum^{N}_{i=1}-(\alpha)^{k}w_{i}v_{ij},\quad\text{where }k=\begin{ cases}0&\text{if }\sigma(c_{i}p^{\prime}_{j}-\sigma^{-1}(v_{ij}))>0\\ -1&\text{otherwise}\end{cases}$ (60) $$

Where $\alpha$ is the is the parameter of the Leaky-ReLU. According to the Central Limit Theorem and the independence of different components in $\bm{\beta}$, it is reasonable to assume that $\bm{\beta}$ follows an $n$-dimensional i.i.d. normal distribution with mean 0 and variance $c$ for some positive constant $c$ as discussed in 5.

Since $P$ is an $(F-r)$-dimensional projection matrix, according to lemma 13,we know that $\|(I-P)\bm{\beta}\|$ follows a Chi distribution with $r$ degrees of freedom and scalar $c$, i.e. c$\chi_{r}$.
∎

###### Remark 5 .

Here, our equation 58 implicitly assumes that the first $N-1$ layers of GNN are of full rank. However, even if the rank of the first $N-1$ layers of GNN could be non-full-rank, we still have $\mathbf{p^{\prime}}\in R(W)$, according to lemma 3. Therefore, we can still use this theorem for approximation.

Normal Distribution Assumption

We assume that the vector $\bm{\beta}$, which we call the graph embedding residual vector, follows an $F$-dimensional i.i.d. normal distribution with mean $\mathbf{0}$ and variance $c$:

$$ $\bm{\beta}\sim\mathcal{N}(0,cI_{F})$ (61) $$

where $I_{F}$ is the $F\times F$ identity matrix.

Intuitively, this graph embedding residual vector $\bm{\beta}$ represents the additional term that the graph needs to fit due to non-full-rank and non-linear components. Formally, its components are defined as:

$$ $[\bm{\beta}]_{j}=\sum^{N}_{i=1}-(\alpha)^{k}w_{i}v_{ij},\quad\text{where }k= \begin{cases}0&\text{if }\sigma(c_{i}p^{\prime}_{j}-\sigma^{-1}(v_{ij}))>0\\ -1&\text{otherwise}\end{cases}$ (62) $$

The reasons behind this assumption are as follows: (1). Symmetry (2). The sum of random variables and Central Limit Theorem: Each $\beta_{j}$ 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 normal distribution. (3). Continuous and smooth distribution (4). Independence: The components of $\bm{\beta}$ are assumed to be independent due to the independence of the input features and the structure of the GNN.

Therefore, it is reasonable to assume that $\bm{\beta}$ follows an $F$-dimensional i.i.d. normal distribution with mean 0 and variance $c$ for some positive constant $c$.

###### Proof.

###### Remark 5 .

#### A.3.6 Analysis of Nonlinear Graph Neural Networks

Proof of Theorem 9

###### Proof.

According to Preliminary 1, we choose the simplest form of GAT here, with only a self-attention mechanism. We consider the diffusion matrix $S$ as a weighted adjacency matrix, where each entry $S_{ij}$ represents the coefficient of the edge between node $i$ and node $j$. Such coefficient is a non-negative scalar, which can be understood as the weight of the edge connecting node $i$ and node $j$, $S\in[0,1]^{N\times N}$ . Here, single-node All-in-one connection matrices $A_{in}\in[0,1]^{1\times 1}$ and $A_{cro}\in[0,1]^{N\times 1}$ respectively. Then, we have such an iterative formula:

$$ $H^{(m)}=\sigma((S_{\omega}\odot\langle X_{\omega},X_{\omega}\rangle)\cdot X_{ \omega}\cdot W)$ $$

where $\odot$ denotes the Hadamard product, representing element-wise multiplication of two matrices, $\langle\cdot,\cdot\rangle$ represents the inner product of 2 matrices. In this case, we have:

$$ $X_{\omega}=\begin{pmatrix}X\\ \mathbf{p}^{\top}\end{pmatrix}$ $$

$$ $\langle X_{\omega},X_{\omega}\rangle=\begin{pmatrix}X^{\top}X&X\mathbf{p}\\ \mathbf{p}^{\top}X^{\top}&\mathbf{p}^{\top}\mathbf{p}\end{pmatrix}$ $$

$$ $S_{\omega}=\begin{pmatrix}S&l\\ l^{\top}&0\end{pmatrix}$ $$

Where $l$ denotes the cross adjacency matrix $A_{cro}\in[0,1]^{N}$. We set $A_{in}$ to 0 0, hence, $S_{NN}$ is 0 0. $\mathbf{p}$ is the prompted vector or node feature. Then, we have:

$$ $\displaystyle S_{\omega}\odot\langle X_{\omega},X_{\omega}\rangle W$ $\displaystyle=\begin{pmatrix}S\odot\langle X,X\rangle&l\odot(X\cdot\mathbf{p}) \\ l^{T}\odot(X\cdot\mathbf{p})^{T}&0\end{pmatrix}\cdot\begin{pmatrix}X\\ \mathbf{p}^{\top}\end{pmatrix}\cdot W$ (63) $\displaystyle=\begin{pmatrix}S\odot\langle X,X\rangle&X\cdot(l\odot\mathbf{p}) \\ l^{T}\odot(X\cdot\mathbf{p})^{T}&0\end{pmatrix}\cdot\begin{pmatrix}X\\ \mathbf{p}^{\top}\end{pmatrix}\cdot W$ (64) $$

For simplification, we consider only updating the embedding of rows of original nodes in the embedding matrix. Then we can obtain:

$$ $\displaystyle H[1:N,]$ $\displaystyle=[\begin{pmatrix}S\odot\langle X,X\rangle&X\cdot(l\odot\mathbf{p} )\\ l^{T}\odot(X\cdot\mathbf{p})^{T}&(\mathbf{p}^{\top}\mathbf{p})\end{pmatrix} \cdot\begin{pmatrix}X\\ \mathbf{p}^{\top}\end{pmatrix}\cdot W][1:N,]$ (65) $\displaystyle=\sigma(\begin{pmatrix}S\odot\langle X,X\rangle&X(l\odot\mathbf{p })\end{pmatrix}\cdot\begin{pmatrix}X\\ \mathbf{p}^{\top}\end{pmatrix}\cdot W)$ (66) $\displaystyle H[N+1]$ $\displaystyle=\mathbf{p}^{\top}$ (67) $$

Here, we can choose $l_{i}=\frac{c_{i}}{p_{i}}$. Then, we have:

$$ $\displaystyle H[1:N,]$ $\displaystyle=\sigma(\begin{pmatrix}S\odot\langle X,X\rangle&\mathbf{c}\end{ pmatrix}\cdot\begin{pmatrix}X\\ \mathbf{p}^{\top}\end{pmatrix}\cdot W)$ (68) $\displaystyle=\sigma(S^{\prime}XW+\mathbf{c}^{\prime}\mathbf{p}^{\top}W)$ (69) $\displaystyle=R+\mathbf{c}\mathbf{p}^{\top}$ (70) $\displaystyle H[N+1,]$ $\displaystyle=\mathbf{p}^{\top}$ (71) $\displaystyle H$ $\displaystyle=R^{\prime}+\mathbf{c}\mathbf{p}^{\top}$ (72) $$

where $\mathbf{c}$ is chosen independent of $\mathbf{p}$, $\mathbf{c^{\prime}}=\begin{pmatrix}\mathbf{c}\\
1\end{pmatrix}$.
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 9.
∎

###### Proof.

### A.4 Further Mathematical Discussion

##### Discussion on 𝐩 𝐩 \mathbf{p} bold_p :

In lemma 2, we rely on the claim that assumes $\Delta R=\mathbf{c}\mathbf{p}_{0}^{\top}$ won’t lose the generality. This assumption is mainly for simplification, allowing us to obtain $\sigma(\Delta R+\mathbf{cp}^{\top})=\mathbf{cp}^{\prime\top}$, $\mathbf{p},\mathbf{p^{\prime}}$ spans $R^{F}$.

The core purpose of this assumption is that when $\Delta R=\mathbf{c}\mathbf{p}^{\top}$, the $\tau_{ij}$ below is invariant to $i$.

$$ $[\sigma(R+cp^{\top})]_{ij}=\begin{cases}[R+\mathbf{cp}^{\top}]_{ij}&\text{when }p_{j}\geq\tau_{ij}\\ \alpha[R+\mathbf{cp}^{\top}]_{ij}&\text{when }p_{j}<\tau_{ij}\end{cases}$ $$

Use $\tau_{ij}$ is independent of $i$, we can immediately establish a one-to-one mapping between $\mathbf{p^{\prime}}$ and $\mathbf{p}$, (i.e., $p^{\prime}_{j}=\begin{cases}p_{j}-\tau_{j}&\text{when }p_{j}\geq\tau_{j}\\
(p_{j}-\tau_{j})/\alpha&\text{when }p_{j}<\tau_{j}\end{cases}$ ), thereby successfully establishing an equivalence between changes in $\mathbf{p}$ at the input end and the $\mathbf{p}^{\prime}$ at the output end. This is what lemma 2 is doing. Noted that $\Delta R=\mathbf{cp_{0}^{\top}}$ don’t hold in general.

Now let us prove that the specific form of $R$ does not affect the results based on ReadOut. This is equivalent to proving the following lemma:

###### Lemma 9 (Equivalence of R under ReadOut) .

Considering a vector $\mathbf{p}$ spans $R^{F}$, then (1) ReadOut($\sigma(R+\mathbf{c}\mathbf{p}^{\top})$) spans $R^{F}$. (2) Given $\mathbf{p}_{i}$ is independent of each other, then $[\text{ReadOut}(\sigma(R+\mathbf{c}\mathbf{p}^{\top}))]_{i}$ is independent of each other.

Consider the ReadOut of the Output Matrix $\sigma(R+\mathbf{cp_{0}^{\top}})$, i.e. ReadOut($\sigma(R+\mathbf{c}\mathbf{p}^{\top})$). Then the $j_{th}$ compoenet of such a $\mathbb{R}^{F}$ vector is:

$$ $\sum^{N}_{i=1}w_{i}[\sigma(R+\mathbf{cp}^{\top})]_{ij}=\sum^{N}_{i=1}[w_{i}(R_ {ij}(p_{j})+c_{ij}(p_{j})p_{j})]$ $$

where $R_{ij}(p)=\begin{cases}R_{ij}&\text{when }p\geq-R_{ij}/c_{i}\\
\alpha R_{ij}&\text{otherwise }\end{cases}$, $c_{ij}$ likewise.

Here, subscript $i$ indicates summing by row. Then, considering each column $j$, we have $F$ independent functions of $p_{j}$:

$$ $p_{j}^{\prime}(p_{j})=\sum^{N}_{i=1}w_{i}(R_{ij}(p_{j})+c_{ij}(p_{j})p_{j})=R^ {\prime}_{j}(p_{j})+C^{\prime}_{j}(p_{j})p_{j}$ $$

Where $p^{\prime}_{j}(\cdot)$ is a piece-wise linear function of $p_{j}$ and $C^{\prime}_{i}$ and $R^{\prime}_{i}$ are corresponding piecewise linear coefficients of $p_{j}$. such a piecewise linear function takes values in $(-\infty,+\infty)$. Considering the independence of $F$ columns, it follows that (1) ReadOut($\sigma(R+\mathbf{c}\mathbf{p}^{\top})$) spans $\mathbb{R}^{F}$ (2) each component of $[\text{ReadOut}(\sigma(R+\mathbf{c}\mathbf{p}^{\top}))]$ is independent of each other. Which is what we need for the proofs of Theorems 3 and 4.

###### Lemma 9 (Equivalence of R under ReadOut) .

##### Discussion on Q 𝑄 Q italic_Q and P 𝑃 P italic_P :

As lemma 7 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 is required:

###### Lemma 10 .

(Equivalence of $P$ and $Q$ under ReadOut)
Consider a matrix $P\in\mathbb{R}^{k\times F}$, a matrix $Q\in\mathbb{R}^{M\times k}$, $\mathbf{p^{\top}_{i}}=Q_{i}^{\top}P$ then ReadOut$(\sigma(\mathbf{c}\mathbf{p_{i}^{\top}}))$ spans $\mathbb{R}^{F}$.

According to lemma 9, we have:

$$ $[C(\mathbf{p_{i}})]_{j}=[\text{ReadOut}(\sigma(\mathbf{cp_{i}}^{\top}))]_{j}= \sum^{N}_{i=1}w_{i}c_{i}\sigma([\mathbf{p_{i}}]_{j})=\lambda\sigma([\mathbf{p_ {i}}]_{j})$ $$

Where $\mathbf{p_{i}}=Q_{i}P$,
$w_{i}$ is the coefficient of ReadOut process, $C(\mathbf{p_{i}})$ denotes the embedding vector after ReadOut, $\lambda$ denotes $\sum^{N}_{i=1}w_{i}c_{i}$.

Hence, every component (with subscript $j$) of the embedding vector $C(\cdot)$ is a piece-wise linear function of $[\mathbf{p_{i}}]_{j}$. Specifically, this function is:

$$ $p^{\prime}(p_{j})=\begin{cases}\lambda p_{j}&\text{if }p_{j}\geq 0\\ \alpha\lambda p_{j}&\text{otherwise}\end{cases}$ $$

where $\alpha$ is the coefficient of the leaky ReLU.
range of such a function is $(-\infty,+\infty)$. Since $F$ components of $C(\mathbf{p_{i}})$ is independent, ReadOut$(\sigma(\mathbf{c}\mathbf{p_{i}^{\top}}))$ = $C(\mathbf{p_{i}})$ spans $\mathbb{R}^{F}$.

Specific form of the bijective mapping of $P$ and $Q$

Then, for each $i\in\{1,\cdots,M\}$, we have a Embedding Vector $C(\mathbf{p}_{i})$. Considering putting such Embedding Vectors into a matrix, i.e., $\tilde{C}$ = $\begin{pmatrix}C(p_{1})\\
\vdots\\
C(p_{M})\end{pmatrix}$. Then:

$$ $\displaystyle\tilde{C}$ $\displaystyle=\text{diag}(\lambda_{1},\ldots,\lambda_{n})\begin{pmatrix}\sigma (\mathbf{p^{\top}_{1}})\\ \vdots\\ \sigma(\mathbf{p^{\top}_{M}})\end{pmatrix}$ (74) $\displaystyle=\text{diag}(\lambda_{1},\ldots,\lambda_{n})\begin{pmatrix}\alpha ^{I_{11}}[\mathbf{p_{1}}]_{1}\cdots\alpha^{I_{1F}}[\mathbf{p_{1}}]_{F}\\ \vdots\\ \alpha^{I_{M1}}[\mathbf{p_{M}}]_{1}\cdots\alpha^{I_{MF}}[\mathbf{p_{M}}]_{F}\\ \end{pmatrix}$ (75) $$

Here, we claim that we can take $I_{ij}=I_{j}$ by 6, i.e. for any $i\in\{1,\cdots,M\}$, $I_{ij}=I_{j}$.

Then we have:

$$ $\displaystyle\tilde{C}$ $\displaystyle=\text{diag}(\lambda_{1},\ldots,\lambda_{n})\begin{pmatrix}[ \mathbf{p_{1}}]_{1}\cdots[\mathbf{p_{1}}]_{F}\\ \vdots\\ [\mathbf{p_{M}}]_{1}\cdots[\mathbf{p_{M}}]_{F}\\ \end{pmatrix}\text{diag}(\alpha^{I_{1}},\cdots,\alpha^{I_{F}})$ (77) $\displaystyle=\text{diag}(\lambda_{1},\ldots,\lambda_{n})\cdot\begin{pmatrix} \mathbf{p_{1}}^{\top}\\ \vdots\\ \mathbf{p_{M}}^{\top}\end{pmatrix}\cdot\text{diag}(\alpha^{I_{1}},\cdots, \alpha^{I_{F}})$ (78) $\displaystyle=\text{diag}(\lambda_{1},\ldots,\lambda_{n})\cdot QP\cdot\text{ diag}(\alpha^{I_{1}},\cdots,\alpha^{I_{F}})$ (79) $\displaystyle=Q^{\prime}P^{\prime}$ (80) $$

Where $P^{\prime}$ and $Q^{\prime}$ give out the specific form of the bijective mapping between $P$ and $Q$ in lemma 5.

###### Remark 6 .

We demonstrate that the claim in Explanation A.4 does not affect the results in Theorems 6 and 7.

Theorem 6 is about the case of a single prompt, making the claim trivially true.

For Theorem 7, we are seeking an upper bound for the optimal case. Among all prompt parameters satisfying the claim, if 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.

In conclusion, our assumption is valid.

###### Lemma 11 (Minimum Sum of Squared Distances from M Vectors to a k-dimensional Subspace) .

Suppose we have M vectors in $\mathbb{R}^{F}$ and a k-dimensional subspace of $\mathbb{R}^{F}$. We consider the minimum sum of squared distances from these M vectors to the k-dimensional subspace. This is equivalent to minimizing the following objective:

$$ $J=\|X-XWW^{T}\|^{2}_{F}=\text{Tr}((X-XWW^{T})^{T}(X-XWW^{T}))$ $$

Where $W$ is a $k\times F$ matrix. According to Hotelling (), let: $X^{T}X=V\Lambda V^{T}$ where $V$ is the matrix of eigenvectors and $\Lambda$ is the diagonal matrix of eigenvalues. The optimal $W$ is then the first $k$ columns of $V$: $W=V[:,:k]$. Substituting this into the objective function:

$$ $\displaystyle J$ $\displaystyle=\text{Tr}(V\Lambda V^{T}-V\Lambda V^{T}VV[:,:k]V[:,:k]^{T}$ $\displaystyle\quad-VV[:,:k]V[:,:k]^{T}\Lambda V^{T}+VV[:,:k]V[:,:k]^{T}\Lambda V ^{T}V[:,:k]V[:,:k]^{T})$ $$

Simplifying, we get:

$$ $\displaystyle J$ $\displaystyle=\text{Tr}(\Lambda-\Lambda[:k,:k]-\Lambda[:k,:k]+\Lambda[:k,:k])$ $\displaystyle=\text{Tr}(\Lambda)-\text{Tr}(\Lambda[:k,:k])$ $\displaystyle=\sum_{i=k+1}^{M}\lambda_{i}$ $$

Therefore, the minimum sum of squared distances from M vectors to a k-dimensional subspace is $\sum_{i=k+1}^{M}\lambda_{i}$, where $\lambda_{i}$ is the $i$-th eigenvalue of $X^{T}X$.

###### Remark 7 .

This result is essentially the property of dimensionality reduction of M vectors to k-dimensional.

###### Definition 3 (Minimum Projection Distance to Cone Surface) .

Given a cone $C\subseteq\mathbb{R}^{n}$ with surface $\partial C$, and any vector $\mathbf{v}\in C$, we define $L(\mathbf{v},\partial C)$ as the minimum distance (projection distance) from $\mathbf{v}$ to the surface of $C$. Formally:

$$ $L(\mathbf{v},\partial C)=\min_{\mathbf{x}\in\partial C}\|\mathbf{v}-\mathbf{x}\|$ (81) $$

###### Definition 4 (The angle to boundary and the aperture of the cone) .

For any interior point $x$ of a convex cone $C$, we define:

(i) The minimum distance from $x$ to the boundary of $C$:

$$ $d(x,\partial C)=\min\{\|x-y\|\mid y\in\partial C\}=d(x,\text{proj}_{C}(x)),$ $$

where $\text{proj}_{C}(x)$ is the projection of $x$ onto $C$.

(ii) The cosine of the angle $\theta$ between $x$ and the boundary of $C$:

$$ $\cos\theta_{x,C}=\frac{\langle x,\text{proj}_{C}(x)\rangle}{\|x\|\|\text{proj} _{C}(x)\|}.$ $$

(iii) The relationship between the distance and the angle $\theta$:

$$ $d(x,\partial C)=\|x\|\sin\theta_{x,C}.$ $$

(iv) The aperture $\Phi$ of the cone

$$ $\sin(\Phi)=\max_{v,u\in C}(|\frac{<v,u>}{\|v\|\cdot\|u\|}|)$ $$

Moreover, for any interior point $x$, we have $\theta_{x,C}\leq\Phi/2$. This formulation is based on the Distance-Support Theorem by Rockafellar ().

###### Lemma 12 (Relationship between Range of Prompted and Embedding matrix) .

As mentioned in lemma 3, $V^{1}_{\alpha}=V_{\alpha}=\{\sigma(\mathbf{v})\mid\mathbf{v}\in R(W)\}$. In lemma 8, under the alternating action of the non-linear function Leaky-ReLU and linear transformation $W$, we have $V^{i}_{\alpha}=\sigma(V^{i-1}_{\alpha}W)$.

First prove $V^{i}_{\alpha}$ is a cone surface. For $V^{1}_{\alpha}$, given $\lambda>0$ and $\mathbf{v}\in R(W)$, we have $\sigma(\lambda\mathbf{v})=\lambda\sigma(\mathbf{v})$. Thus, if $\sigma(\mathbf{v})\in V^{1}_{\alpha}$, then $\forall\lambda>0$, $\lambda\sigma(\mathbf{v})\in V^{1}_{\alpha}$. Furthermore, consider $\mathbf{v}\in V^{i-1}_{\alpha}$, $\forall\lambda>0$, $\sigma((\lambda\mathbf{v})W)=\lambda\sigma(\mathbf{v}W)$. It follows that, $\forall\mathbf{v}\in V^{i}_{\alpha},\forall\lambda>0$, $\lambda\mathbf{v}\in V^{i}_{\alpha}$, hence, $V^{i}_{\alpha}$ is a cone surface. Iteratively, we obtain that $V^{i}_{\alpha}$ is a cone surface for $i\in\{1,\ldots,n\}$.

Next, consider $C^{i}_{\alpha}$ as the convex hull of $V^{i}_{\alpha}$. Specifically, since $V^{i}_{\alpha}$ is a cone surface, $C^{i}_{\alpha}$ is a convex cone. By linearity of multiple a matrix, $C^{i}_{\alpha}W$ remains a convex cone. After applying $\sigma(\cdot)$, this convex hull transforms into another convex cone or cone surface, namely, $\sigma(C^{i}_{\alpha}W)$, and the corresponding $V^{i+1}_{\alpha}$ is the surface of $C^{i+1}_{\alpha}$. $\sigma(C^{i}_{\alpha})$ is then the convex hull of $\sigma(C^{i}_{\alpha}W)$.

After $n$ iterations of the aggregation, we can conclude that: $V^{i}_{\alpha}$ is a cone surface, $C^{i}_{\alpha}$ is a convex cone, and $V^{i}_{\alpha}$ is the surface of $C^{i}_{\alpha}$.

###### Remark 8 .

Here we assume that the process of obtaining the convex hull $C^{i+1}_{\alpha}$ from $\sigma(C^{i}_{\alpha}W)$ keeps the $V^{i+1}_{\alpha}$ to be the surface of $C^{i+1}_{\alpha}$. This always holds true unless the nonlinear transformation $\sigma(\cdot)$ turns the convex cone $V_{\alpha}^{i}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 ().

###### Lemma 13 (Distribution of the Norm of an n-Dimensional i.i.d. Normal Vector After Multiplying Projection Matrix) .

Let $P$ be a projection matrix onto a linear subspace $V$. Then $I-P$ is a projection matrix onto the orthogonal complement of $V$. Assume $\varsigma$ is an $n$-dimensional random vector following a normal distribution with mean $\mathbf{0}$ and covariance matrix $cI_{F}$, where $c$ is a positive constant. i.e.,
$\varsigma\sim\mathcal{N}(\mathbf{0},cI_{F}$

Let $\zeta=(I-P)\cdot\varsigma$, according to the linear property of Gaussian Random vector, we have $\zeta\sim N(\mu^{\prime},\Sigma^{\prime})$, where:

$$ $\displaystyle\mu^{\prime}$ $\displaystyle=(I-P)\cdot\mu$ $\displaystyle=\mathbf{0}$ $\displaystyle\Sigma^{\prime}$ $\displaystyle=(I-P)^{T}\cdot\Sigma\cdot(I-P)$ $\displaystyle=c(I-P)^{2}=c(I-P)$ $$

Denote by $r$ the rank of matrix $I-P$.
Apply decorrelation to $\zeta$, we have $\iota=U^{T}\cdot\zeta$, $\iota\sim N(\vec{0},\Sigma^{\prime\prime})$, where $\Sigma^{\prime\prime}=$
$\begin{pmatrix}c^{2}\cdot I_{r}&O\\
O&O_{F-r\times F-r}\end{pmatrix}$, $U$ is a orthogonal matrix. Hence,

$$ $\|(I-P)\varsigma\|=\|\iota\|=\sqrt{\sum^{r}_{i=1}\iota^{2}_{i}}$ $$

Since $\sum^{r}_{i=1}\iota^{2}_{i}\sim\chi^{2}(r)$, we have: $\|\zeta\|=\sqrt{\sum^{r}_{i=1}\iota^{2}_{i}}\sim\chi(r)$

It follows that the norm of an n-dimensional i.i.d. normal vector after multiplying projection matrix: $\|(I-P)\varsigma\|$ obey Chi-Distribution with r degrees of freedom.

###### Lemma 10 .

###### Remark 6 .

###### Lemma 11 (Minimum Sum of Squared Distances from M Vectors to a k-dimensional Subspace) .

###### Remark 7 .

###### Definition 3 (Minimum Projection Distance to Cone Surface) .

###### Definition 4 (The angle to boundary and the aperture of the cone) .

###### Lemma 12 (Relationship between Range of Prompted and Embedding matrix) .

###### Remark 8 .

###### Lemma 13 (Distribution of the Norm of an n-Dimensional i.i.d. Normal Vector After Multiplying Projection Matrix) .

## Appendix B Supplementary Experiments

We conducted supplementary experiments on real-world datasets to validate our results. We performed similar experiments as in the main text using entirely different datasets, namely NCI1 and DD Morris et al. (). The NCI1 dataset has 37-dimensional node features, 4,110 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.

Figure: (a) NCI1
Refer to caption: x9.png

Exp1 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 a period of steady decline followed by a rapid decrease to a small magnitude, then slowly converging to zero. This aligns with our theoretical results.

Figure: (a) NCI1
Refer to caption: x11.png

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 as rank loss increases. Where rank loss is $r$ means the rank of weight matrix $W$ in GNN is $n-r$.

Figure: (a) NCI1
Refer to caption: x13.png

Exp 3 We examined how the RMSE of GPF or single-node All-in-one Prompt methods change as the number of graphs 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.

## Appendix 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 datasets by defining the dimension of graph feature vector($F$), average of graph node numbers ($N_{avg}$), average of graph edge numbers ($E_{avg}$), and number of graphs in the dataset ($M$). These parameters characterize both individual graphs and the entire dataset, facilitating our study of the relationship between these features and $\epsilon$. In detail, the distribution of graph node feature vectors is set to a normal distribution $\mathcal{N}(0,1)$; the graph edge density $\rho$ is set to $0.15$, where $\rho$ represents the probability of an edge existing between any two nodes.

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, we 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 $5$ by default. The default ReadOut method is mean pooling.

Task Settings: Our loss function is defined as $\|F_{\theta^{*}}(G_{p})-C(G)\|$ for single-graph tasks, and $\sqrt{\sum_{G\in\mathcal{G}}\|F_{\theta^{*}}(G_{p})-C(G)\|^{2}/M}$ for multi-graph tasks. Here $G_{p}$ 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 a specific task. Since the ultimate purpose of graph prompting is to approximate graph operation, we here treat $C(\cdot)$ as various graph data operations such as adding/deleting nodes, adding/deleting/changing edges, and transforming features of a given graph $G$. The intensity of these graph operations is controlled by a parameter $\beta\in[0,1]$, where 0 indicates no change and 1 indicates generating a completely random new graph. In our experiments, we fix $\beta$ at $0.7$, which means we have a $0.7$ probability of removing a node/edge or masking some features.

Training: In the graph prompting training process, we perform gradient descent on the parameters $\omega$ of the graph prompt $P_{\omega}$ using the Adam optimizer. We use a learning rate of $1\times 10^{-4}$ and weight decay of $5\times 10^{-5}$. We implement 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 $k$ times with random initialization for each prompt, and selecting the minimum loss. Typically, $k$ is set to 3.

Testing: Note that the error bound in Theorem 5 is the product of two terms: $\sin(\Phi/2)$ and $\|C(G)\|$. For a fixed pre-trained model, $\sin(\Phi/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 Error Bound relative to the independent variables like “Rank Lost”.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: In the experimental section, the authors utilize GCN and GAT as the primary models. Given that graph transformers have emerged as SOTA models especially in the context of prompting, could you elaborate on your decision to focus on GCN and GAT? How do you believe your findings might differ if applied to graph transformers?

Based on the theoretical study in the paper, what are the next steps you envision for further research in graph prompting? How can practical application benefit from the theoretical framework? It would be good to have the paper linked to real-world applications
soundness: 3
strengths: The paper introduces a comprehensive theoretical framework for graph prompting, significantly advancing the understanding of how and why graph prompts work. Specifically,
- There are some key concepts such as "bridge sets" and "ϵ-extended bridge sets," which are pivotal for understanding how graph prompts function. By establishing the existence of a bridge graph for any given input graph, the authors provide a strong theoretical foundation that justifies the use of graph prompts.
- The paper provides a thorough and systematic analysis of the errors introduced by graph prompts, establishing upper bounds that offer valuable insights into their performance. By deriving specific error bounds, the authors contribute significantly to the theoretical understanding of graph prompting. 

The paper is well-structured, featuring clearly defined notations and formulas that significantly contribute to its readability and comprehension
summary: The paper presents a theoretical framework for understanding graph prompting, a method of incorporating additional tokens or subgraphs without requiring retraining of pre-trained graph models over various downstream tasks. The authors introduce a comprehensive theoretical framework that establishes formal guarantees on the effectiveness of graph prompts in approximating various graph transformation operations. They derive upper bounds on the errors introduced by these prompts for individual graph, and further extend the findings across different GNN architectures, including both linear and non-linear models. The empirical study supports the theoretical findings and showcases the practical benefits.
weaknesses: The paper offers rigorous theoretical analysis related to data operation perspective, upper bound study, etc. In the meantime, it may lack sufficient contextualization regarding how these error bounds apply in real-world scenarios. A more practical interpretation of the results could help bridge the gap between theory and application. 

In Section 4, the theorems are based on the assumption of full-rank weight matrices. It would be helpful to investigate how well the assumption holds in practical applications

The experimental section of the paper lacks a comprehensive integration of real-world dataset evaluations within the main text, which limits the visibility and perceived relevance of the findings. By omitting a detailed discussion of these real-world results in the primary analysis, the paper misses an opportunity to contextualize its findings and demonstrate the effectiveness of graph prompting in practical applications. Including these insights in the main text would strengthen the paper’s overall impact

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 2
questions: 1. Why is the error related to the prompt design in Theorem 5? Intuitively, the term $||C(G)||$ appears to be related to the graph itself and the downstream task, suggesting it may not depend with the prompt design.
2. Does the number of non-linear layers affect the error bound in Theorem 5?
3. How is $C(G)$ computed in Figure 1?
soundness: 3
strengths: The theoretical analysis in this study addresses the gap in establishing a theoretical basis for the capabilities of graph prompts with non-linear pretrained models and training on batches of graphs. The theoretical findings demonstrate the capabilities of graph prompts across several typical GNN models, providing detailed error bounds and error distributions. Notably, the authors show that the scale of prompts does not increase linearly with the size of the graph dataset, a positive result that supports the scalability of graph prompts.
summary: This study provides a solid theoretical analysis of graph prompts. The theoretical findings include the capabilities of graph prompts on GCN models with 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.
weaknesses: The writing could be further improved to assist readers who may not have sufficient background knowledge about graph prompts. It also lacks some explanations, which might lead to misunderstandings among readers. For instance:

1. The description of the function $C$ is vague and could be clarified using a specific task, such as binary classification. Additionally, $C$ should be denoted as a function of a certain downstream task.
2. The terms  $\Phi ,  \mu , and  \lambda$  in Equation (4) are not explained and should be clarified.
3. The precondition in Corollary 1 is not specified and should be stated explicitly.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. The authors take GCNs as linear graph models and GATs as nonlinear graph models based on different aggregation mechanisms. Could the authors provide some previous studies that use such categories? According to my knowledge, nonlinear graph models are typically GNNs with nonlinear activation functions between GNN layers.
2. What is meaning of $SG_\omega$ in Theorem 4?
3. What does $\mu$ mean in Theorem 5?
4. Could the authors provide more details about All-in-One-Plus?
5. Why do the authors not include the results of GPF-plus and All-in-one-plus in Section 5?
soundness: 2
strengths: 1. The studied problem of theoretical analyses on graph prompts is a significant topic.
2. The authors provide experiments on both synthetic and real-world datasets.
summary: Graph prompting is a popular method to adapt pre-trained graph models for downstream tasks. While many graph prompting methods work well on real-world graph datasets, theoretical analyses on graph prompting methods are still not well explored. This study provides comprehensive analysis of popular graph prompting methods. The authors conduct extensive experiments on both synthetic and real-world datasets to validate the theoretical findings in this study.
weaknesses: 1. Some arguments lack supporting evidence. The authors claim that “The rest graph prompt designs can usually be treated as their special cases or natural extensions.” in line 105. However, drawing this conclusion is not straightforward. For example, GPPT [1] designs graph prompts as structure tokens and task tokens, and GraphPrompt [2] designs graph prompts as prompt-based Readout operations. The authors may discuss how to treat these graph prompt methods as special cases or natural extensions of GPF or All-in-one.
2. Incorrect formulation of All-in-One. According to Section 2, All-in-One obtains the prompt graph by connecting $k$ learnable prompt tokens with $N$ original graph nodes. However, All-in-one in Lemma 1 adds prompt tokens to node features, which conflicts with Section 2. Since most theoretical analysis in this study is related to All-in-one, the authors should at least provide correct formulation of All-in-One as the basis of this paper.
3. The description of All-in-One-Plus in Section 4.1 is missing. The authors should provide the citation of this method and introduce it in the paper.
4. Notations are inconsistent in the paper, which confuses readers a lot. For example, the authors use two different notations $l$ and $i$ to represent the layer index of GNNs in the paper, while $l$ is also used to denote a column vector. The authors should use consistent notations to avoid ambiguity.
5. Duplicated sentences should be avoided. For example, the paragraph *Model Settings* appears twice in Section 5.1 and Appendix C.

[1] Sun, Mingchen, et al. "Gppt: Graph pre-training and prompt tuning to generalize graph neural networks." Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022.  
[2] Liu, Zemin, et al. "Graphprompt: Unifying pre-training and downstream tasks for graph neural networks." Proceedings of the ACM Web Conference. 2023.