PSP: Pre-Training and Structure Prompt Tuning for Graph Neural Networks
Graph Neural Networks (GNNs) are powerful in learning semantics of graph
data. Recently, a new paradigm "pre-train and prompt" has shown promising
results in adapting GNNs to various tasks with less supervised data. The
success of such paradigm can be attributed to the more consistent objectives of
pre-training and task-oriented prompt tuning, where the pre-trained knowledge
can be effectively transferred to downstream tasks. Most existing methods are
based on the class prototype vector framework. However, in the few-shot
scenarios, given few labeled data, class prototype vectors are difficult to be
accurately constructed or learned. Meanwhile, the structure information of
graph is usually exploited during pre-training for learning node
representations, while neglected in the prompt tuning stage for learning more
accurate prototype vectors. In addition, they generally ignore the impact of
heterophilous neighborhoods on node representation and are not suitable for
heterophilous graphs. To bridge these gaps, we propose a novel pre-training and
structure prompt tuning framework for GNNs, namely PSP, which consistently
exploits structure information in both pre-training and prompt tuning stages.
In particular, PSP 1) employs a dual-view contrastive learning to align the
latent semantic spaces of node attributes and graph structure, and 2)
incorporates structure information in prompted graph to construct more accurate
prototype vectors and elicit more pre-trained knowledge in prompt tuning. We
conduct extensive experiments on node classification and graph classification
tasks to evaluate the effectiveness of PSP. We show that PSP can lead to
superior performance in few-shot scenarios on both homophilous and
heterophilous graphs. The implemented code is available at
https://github.com/gqq1210/PSP.
Qingqing Ge, Zeyuan Zhao, Yiding Liu, Anfeng Cheng, Xiang Li, Shuaiqiang Wang, Dawei Yin
# Enhancing Graph Neural Networks with Structure-Based Prompt

###### Abstract.

Graph Neural Networks (GNNs) are powerful in learning semantics of graph data. Recently, a new paradigm "pre-train & prompt" has shown promising results in adapting GNNs to various tasks with less supervised data. The success of such paradigm can be attributed to the more consistent objectives of pre-training and task-oriented prompt tuning, where the pre-trained knowledge can be effectively transferred to downstream tasks. However, an overlooked issue of existing studies is that the _structure information_ of graph is usually exploited during pre-training for learning node representations, while neglected in the prompt tuning stage for learning task-specific parameters. To bridge this gap, we propose a novel structure-based prompting method for GNNs, namely SAP, which consistently exploits structure information in both pre-training and prompt tuning stages. In particular, SAP 1) employs a dual-view contrastive learning to align the latent semantic spaces of node attributes and graph structure, and 2) incorporates structure information in prompted graph to elicit more pre-trained knowledge in prompt tuning. We conduct extensive experiments on node classification and graph classification tasks to show the effectiveness of SAP. Moreover, we show that SAP can lead to better performance in more challenging few-shot scenarios on both homophilulous and heterophilious graphs.

Graph neural networks, pre-training, prompt, few-shot learning Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.

_Conference'17, July 2017, Washington, DC, USA_

© 2023 Association for Computing Machinery.

ACM ISBN 978-1-4503-XXC-X/18/06. $15.00 [https://doi.org/10.1145/mnmnmn.nmmn](https://doi.org/10.1145/mnmnmn.nmmn)

3

## 1. Introduction

Graph Neural Networks (GNNs) have been widely applied in a variety of fields, such as social network analysis [(9)], drug discovery [(18)], financial risk control [(35)], and recommender systems [(38)], where both structural and attribute information are learned via message passing on the graphs [(15)]. Recently, extensive efforts [(10; 19; 41)] have been made to design graph pre-training methods, which are further fine-tuned for various downstream tasks. Nevertheless, inconsistent objectives of pre-training and fine-tuning often leads to catastrophic forgetting during downstream adaptation [(42)], especially when the downstream supervised data is too scarce to be easily over-fitted.

To bridge this gap, many prompt tuning methods for GNNs [(8; 21; 30; 31; 42)] have also been proposed to achieve remarkable performance in few-shot learning tasks on graphs. In particular, the key insight of these methods is to freeze the pre-trained model (i.e., GNN) and introduce extra task-specific parameters, which learns to exploit the pre-trained knowledge for downstream tasks. For example, GPPT [(30)] and GraphPrompt [(21)] pre-train a GNN model based on the link prediction task, then they take the class prototype vectors and the readout function as parameters respectively to reformulate the downstream node/graph classification task into the same format as link prediction.

Despite the initial success, a clear limitation in these existing models is that _graph structure_, as the key ingredient in pre-training, is under-explored in prompt tuning, which limits their effectiveness in unleashing pre-trained knowledge. In particular, their task-specific parameters (e.g., class prototype vectors or readout functions) are usually learned only with few labeled data. They fail to consider the relationships between the task and the massive unlabeled data, which could also provide rich pre-trained knowledge that is very useful for the task at hand. This is even more important when the labeled data is scarce, e.g., few-shot node classification.
As shown in Figure 1 (b), existing methods that directly use the average embeddings of labeled nodes/graphs as the class prototype representations can easily be undermined by noisy/outlier data when the number of labeled nodes is scarce. In contrast, facilitating class representation learning with structural connections between class prototype vectors and unlabeled nodes could help solve this issue (as shown in Figure 1 (d)).

In this paper, we propose a novel **S**tructure-**b**A**sed **P**rompting (SAP) method for GNNs, which unifies the objectives of pre-training and prompt tuning for GNNs and integrates structural information in both pre-training and prompt tuning stages. For pre-training, we employ dual-view contrastive learning to align the latent semantic spaces of node attributes and graph structure. Specifically, one view is implemented with MLP, which only uses node attributes in the graph. The other view adopts GNN to leverage both node attributes and structural information of the graph. For downstream prompt-tuning, we fix the learned parameters of MLP and GNN in the pre-training stage, add class prototype vectors as new nodes to the raw graph and introduce structural connections between prototype vectors and original nodes as prompts to learn more accurate prototype vectors (see Figure 1 (c)). Note that weights associated with these connections are parameters to be learned. In the training phase, we use representations of labeled nodes/graphs calculated by MLP as anchors, and representations of prototype vectors obtained through GNN as positive/negative samples. Specifically, the prototype vector in the same class as the anchor is considered as positive sample, while prototype vectors in other classes serve as negative samples. Then, contrastive learning between nodes/graphs (MLP-based view) and prototype vectors (GNN-based view) is performed to learn prompt parameters. As a result, we unify the objectives of pre-training and prompt tuning. After prompt tuning, the nodes and their corresponding class prototypes are learned to have higher weights on the edges, as shown in Figure 1(d). We also experimentally show the results in Figure 6 of Section 5.5. Based on the learned weights, for each prototype vector, GNN formulates its embedding by weighted-aggregating information from its neighboring nodes, i.e., all the nodes in the raw graph. Finally, in the testing stage, node/graph classification can be conducted via comparing the similarity of representations between node/graph and the prototype vectors.

Compared with conventional graph prompt tuning methods, our method is more desirable in learning better prototype vectors, as we leverage both labeled nodes and massive unlabeled nodes in the graph, which is particularly useful in few-shot scenarios. We further highlight that our prompt tuning method is applicable to both homophilious and heterophilious graphs. First, node/graph representations computed from MLP-based view are not affected by structural heterophily. Second, prototype vectors calculated from GNN-based view are based on the learned weights in structure prompt tuning, which takes all nodes in the raw graph as neighbors and learns to assign large (small) weights to those in the same (different) class. As such, the computation of prototype vectors is not affected by the heterophily of the graph. To summarize, our main contributions in this paper are:

* We propose an effective structure-based prompting method SAP for GNNs, which unifies the objectives of pre-training and prompt tuning.
* We present a novel prompt tuning strategy, which introduces a learnable structure prompt to enhance model performance in few-shot learning tasks on both homophilious and heterophilious graphs.
* We extensively demonstrate the effectiveness of SAP with different benchmark datasets on both node classification and graph classification. In particular, we vary the number of labeled training data and show that SAP can lead to better performance in challenging few-shot scenarios.

## 2. Related Work

### Graph Neural Networks

GNNs have presented powerful expressiveness in many graph-based applications (Gan et al., 2016; Gan et al., 2016; Gan et al., 2016; Li et al., 2017). Modern GNNs typically follow a message-passing scheme, which combines the attribute information and structural information of the graph to derive low-dimensional embedding of a target node by aggregating messages from its context nodes. There are many effective neural network structures proposed such as graph attention network (GAT) (Shen et al., 2016), graph convolution network (GCN) (Gan et al., 2016), GraphSAGE (Gan et al., 2016).

### Graph Pre-training

Inspired by the remarkable achievements of pre-trained models in Natural Language Processing (NLP) (Gan et al., 2016; Li et al., 2017; Li et al., 2017) and Computer Vision (CV) (Gan et al., 2016; Li et al., 2017; Li et al., 2017), graph pre-training (Kang et al., 2016) emerges as a powerful paradigm that leverages self-supervision on label-free graphs to learn intrinsic graph properties. Some effective and commonly-used pre-training strategies include node-level comparison (Shen et al., 2016), edge-level pretext (Shen et al., 2016), and graph-level contrastive learning (Shen et al., 2016; Li et al., 2017). Recently,

Figure 1. The construction of class prototype vectors. The colored areas contain the labeled nodes for training. The circles represent nodes, and the triangles represent class prototype vectors for node classification task. The solid black lines and gray dashed lines denote the original edges in the graph and the new weighted edges, respectively. For each node, the dashed line in red or green denotes the edges with the largest weight to the class prototype vector.
there are also some newly proposed pre-training methods. For example, GCC (Zhou et al., 2017) leverages contrastive learning to capture the universal network topological properties across multiple networks and transfers the learned prior knowledge to downstream tasks. GPT-GNN (Yang et al., 2018) introduces a self-supervised attributed graph generation task to pre-train GNN models that can capture the structural and semantic properties of the graph. L2P-GNN (Yang et al., 2019) utilizes meta-learning to learn the fine-tune strategy during the pre-training process. In summary, there exists a diverse range of pre-training strategies for GNN models, each characterized by unique pre-training objectives. However, these approaches do not consider the gap between pre-training and downstream objectives, which limits their generalization ability to handle different tasks.

### Prompt-based Learning

The training strategy "pre-train & fine-tune" is widely used to adapt pre-trained models onto specific downstream tasks. However, this strategy ignores the inherent gap between the objectives of pre-training and diverse downstream tasks, where the knowledge learned via pre-training could be forgot or infectively leveraged for downstream tasks, leading to poor performance.

To bridge this gap, natural language processing proposes a new paradigm (Zhou et al., 2017), namely "pre-train & prompt". These methods freeze the parameters of the pre-trained models and introduce additional learnable components in the input space, thereby enhancing the compatibility between inputs and pre-trained models. On graph data, there are a handful of studies that adopt prompt tuning to learn more generalizable GNNs. GPPT (Zhou et al., 2017) relies on edge prediction as the pre-training task and reformulates the downstream task as edge prediction by introducing task tokens for node classification. GraphPrompt (Yang et al., 2018) proposes a unified framework based on subgraph similarity and link prediction, hinging on a learnable prompt to actively guide downstream tasks using task-specific aggregation in readout function. SGL-PT (Yang et al., 2019) unifies the merits of generative and contrastive learning through the asymmetric design as pre-training, and computes class prototype vectors via supervised prototypical contrastive learning (SPCL) (Shen et al., 2017; Wang et al., 2018). GPF (Chen et al., 2018) extends the node embeddings with additional task-specific prompt parameters, and can be applied to the pre-trained GNN models that employ any pre-training strategy. ProG (Yang et al., 2019) reformulates node-level and edge-level tasks to graph-level tasks, and introduces the meta-learning technique to the graph prompt tuning study.

Despite their success, we observe that most of them utilize the _structure information_ in pre-training, while ignoring it in downstream prompt tuning stage. This restricts their effectiveness to fully utilize pre-trained knowledge stored in the entire graph. Moreover, their task-specific parameters are usually learned only with few labeled data, leading to poor performance in more challenging few-shot scenarios. In this paper, our proposed method SAP integrates structure information in both pre-training and prompt tuning stage, and achieve superior performance under few-shot setting on both node classification and graph classification tasks.

## 3. Preliminary

**Graph.** We denote a graph as \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), where \(\mathcal{V}=\{v_{i}\}_{i=1}^{N}\) is a set of \(N\) nodes and \(\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}\) is a set of edges. We also define \(\mathbf{A}\in\mathbb{R}^{N\times N}\) as the adjacency matrix of \(\mathcal{G}\), where \(A_{ij}=1\) if \(v_{i}\) and \(v_{j}\) are connected in \(\mathcal{G}\), and \(A_{ij}=0\) otherwise. Each node in the graph is associated with an \(F\)-dimensional feature vector \(\mathbf{z}_{i}\in\mathbb{R}^{1\times F}\), and the feature matrix of all nodes is defined as \(\mathbf{X}\in\mathbb{R}^{N\times F}\).

**Research problem.** In this paper, we investigate the problem of graph pre-training and prompt tuning, which learns representations of graph data via pre-training, and transfer the pre-trained knowledge to solve downstream tasks, i.e., node classification and graph classification. Moreover, we further consider the scenarios where downstream tasks are given limited supervision, i.e., \(k\)-shot classification. For each class, only \(k\) labeled samples (i.e., nodes or graphs) are provided as training data.

**Prompt tuning of pre-trained models.** Given a pre-trained model, a set of learnable prompt parameters \(\theta\) and a labeled task dataset \(\mathcal{D}\), we fix the parameters of the pre-trained model and only optimize \(\theta\) with \(\mathcal{D}\) for the downstream graph tasks.

## 4. Proposed Method

In this paper, we propose a novel structure-based prompting method for GNNs, namely SAP, which unifies the objectives of pre-training and prompt tuning for GNNs and integrates structure information in both pre-training and prompt tuning stage to achieve better performance in more challenging few-shot scenarios. The overall framework of SAP is shown in Figure 2.

### Graph Pre-training

For graph data, both attribute and structural information are critical for revealing the underlying semantics of graph during the pre-training phase. As such, we design a dual-view contrastive learning to align the latent semantic spaces of node attributes and graph structures. The top part of Figure 2 shows the dual-view pre-training paradigm. In particular, one view is implemented with MLP, which only uses node attributes in the graph, while the other adopts GNN to leverage both node attributes and structural information of the graph. More formally, we define the node representations computed by the two views respectively as

\[\mathbf{Z}^{(1)}=\mathrm{MLP}(\mathbf{X})\quad\text{ and }\quad\mathbf{Z}^{(2)}= \mathrm{GNN}(\mathbf{X},\mathbf{A}), \tag{1}\]

where \(\mathbf{Z}^{(1)}\in\mathbb{R}^{N\times D}\) and \(\mathbf{Z}^{(2)}\in\mathbb{R}^{N\times D}\) have the same latent dimensionality \(D\).

To optimize the MLP and GNN, we leverage a contrastive loss function \(\mathcal{L}_{pre}\) to maximize the similarity between the two representations of the same node, denoted as \(\mathbf{z}_{i}^{(1)}\) and \(\mathbf{z}_{i}^{(2)}\) for node \(v_{i}\). For an anchor \(\mathbf{z}_{i}^{(1)}\), other node representations \(\mathbf{z}_{j}^{(2)}\) are considered as negative samples. More specifically, we formulate the loss as the normalized temperature-scaled cross entropy loss (Dai et al., 2018) as

\[\mathcal{L}_{pre}=-\frac{1}{N}\sum_{i}^{N}\log\frac{\exp(\mathrm{sim}( \mathbf{z}_{i}^{(1)},\mathbf{z}_{i}^{(2)})/\tau)}{\sum_{j=0,j\neq i}^{N}( \exp(\mathrm{sim}(\mathbf{z}_{i}^{(1)},\mathbf{z}_{j}^{(2)})/\tau))}, \tag{2}\]

where \(N\) is the number of nodes, \(\tau\) is a temperature parameter, and \(\mathrm{sim}(\cdot)\) is implemented with cosine similarity.

In general, the dual-view contrastive pre-training can exploit both attribute and structure information of graph to encode learning generalizable knowledge in the output node embeddings. In the
next subsection, we introduce graph structure prompt tuning that leverage such knowledge in downstream classification tasks.

### Graph Structure Prompt Tuning

Next, we demonstrate how we freeze the pre-trained model and adapt it to different downstream tasks on graph. In particular, we propose a novel method, namely structure prompt tuning, which considers the structure relationships between the graph data and the task at hand. Compared to existing graph prompt tuning methods, the structure relationships in our method allow the task to more effectively leverage the pre-trained knowledge embedded in the graph data. In the following, we elaborate the structure prompt tuning method on two representative tasks, i.e., node classification and graph classification.

#### 4.2.1. Node Classification

The overall framework of our method is similar to previous prototype-based methods (Zhou et al., 2017; Zhou et al., 2017), which learns a prototype embedding vector \(\mathbf{p}_{c}\) for each node class \(c\in\{1,2,...,C\}\). In particular, our method comprises three steps: 1) structure prompting, 2) prototype initialization, and 3) prompt tuning.

**Step 1: Structure prompting.** For all the class prototypes, the main idea of our method is to consider them as virtual nodes, and connect them to all the original nodes \(\mathcal{V}\) in the graph \(\mathcal{G}\), as shown in Figure 1(c). More specifically, we add totally \(C\) nodes (denoted as \(\mathcal{P}=\{p_{c}\}_{c=1}^{C}\)) and \(N\times C\) weighted edges (denoted as \(\mathcal{W}\)) to construct a prompted graph \(\mathcal{G}^{\prime}\) as

\[\mathcal{G}^{\prime}=(\mathcal{G}\cup\mathcal{P},\mathcal{E}\cup\mathcal{W}). \tag{3}\]

**Step 2: Prototype initialization.** Next, we define the attributes and edge weights for the prototype nodes. In particular, we simply define the attributes for each prototype \(p_{c}\) as the averaged attribute vector of its corresponding labeled nodes, i.e.,

\[\mathbf{x}_{c}=\frac{1}{|\mathcal{D}_{c}|}\sum_{(u_{i},c)\in\mathcal{D}_{c}} \mathbf{x}_{i}. \tag{4}\]

For the edges that connect \(\mathcal{P}\) and \(\mathcal{V}\), we initialize their weights \(\mathbf{W}\in\mathbb{R}^{N\times C}\) as

\[\mathbf{W}=\mathbf{Z}^{(2)}\mathbf{p}^{\prime T}. \tag{5}\]

Here, we introduce a surrogate prototype embedding matrix \(\mathbf{p}^{\prime}\), where each row vector \(\mathbf{p}_{c}^{\prime}\) of \(\mathbf{p}^{\prime}\) is aggregated from its labeled nodes, i.e.,

\[\mathbf{p}_{c}^{\prime}=\frac{1}{|\mathcal{D}_{c}|}\sum_{(u_{i},c)\in\mathcal{ D}_{c}}\mathbf{z}_{i}^{(2)}. \tag{6}\]

During the subsequent prompt tuning step, the weight matrix \(\mathbf{W}\) is considered as task-specific parameters to be learned.

**Step 3: Prompt tuning.** We conduct prompt tuning on the prompted graph \(\mathcal{G}^{\prime}\) using the same form of loss function as in Equation 2, while keeping the node representations fixed and only optimize the

Figure 2. Overall framework of SAP. Top: pre-training. Middle: prompt tuning for node classification. Bottom: prompt tuning for graph classification.
prototypes embeddings. Formally, the prompt tuning loss is defined as the following contrastive loss as

\[\mathcal{L}_{pro}=-\frac{1}{|\mathcal{D}|}\sum_{(\eta_{c}|c)\in\mathcal{D}}\log \frac{\exp(\text{sim}(\mathbf{z}_{i}^{(1)},\mathbf{p}_{c})/\tau)}{\sum_{c^{ \prime}\in C_{c},e^{\prime}\neq c}\exp(\text{sim}(\mathbf{z}_{i}^{(1)},\mathbf{ p}_{c^{\prime}})/\tau)}, \tag{7}\]

where \(\mathbf{p}_{c}\) is parameterized by \(\mathbf{W}\) as

\[\mathbf{P}=\text{GNN}([\mathbf{X},\mathbf{X}_{P}],[\mathbf{A},\mathbf{W}]). \tag{8}\]

Here, \(\mathbf{X}\) represents the original node features in graph \(\mathcal{G}\), \(\mathbf{X}_{P}\in\mathbb{R}^{C\times F}\) represents the prototype features, and \([\mathbf{A},\mathbf{W}]\in\mathbb{R}^{N\times(N+C)}\) represents the adjacency matrix of \(\mathcal{G}^{\prime}\). Notably, unlike conventional methods that directly consider \(\mathbf{P}\) as learnable parameters, we parameterize \(\mathbf{P}\) with their structure connections with the graph data, i.e., the added edges \(\mathbf{W}\). In other words, only \(\mathbf{W}\) would be optimized as parameters when minimizing \(\mathcal{L}_{pro}\), which learns to aggregate pre-trained knowledge from all the nodes in the graph to formulate prototype embeddings.

#### 4.2.2. Graph Classification

Our method can also be adopted for graph classification, with some changes to be made in each step. In **structure prompting**, for each graph instance \(\mathcal{G}_{i}\) and a prototype node \(p_{c}\), the added edge between any \(v_{i}\in\mathcal{V}_{i}\) and \(p_{c}\) share the same weight. As such, the prompt tuning of graph classification also has \(N\times C\) parameters, while \(N\) denotes the number of graphs here. **In prototype initialization**, we further introduce a mean-based readout function on node level representations \(\mathbf{Z}^{(1)}\) and \(\mathbf{Z}^{(2)}\) to compute the graph-level representation \(\mathbf{S}^{(1)}\) and \(\mathbf{S}^{(2)}\), respectively, as shown in Figure 2. Then, we can use Equations 5 and 6 to initialize \(\mathbf{W}\) with \(\mathbf{Z}^{(2)}\) replaced by \(\mathbf{S}^{(2)}\). In **prompt tuning**, we can also replace \(\mathbf{Z}^{(1)}\) replaced by \(\mathbf{S}^{(1)}\) in Equation 7 for optimizing graph-level classification tasks.

#### 4.2.3. Remarks

In our proposed SAP method, it worth noting that the weights of pre-trained model are frozen for downstream tasks, and the prompt tuning is parameterized by the learnable adjacency matrix \(\mathbf{W}\in\mathbb{R}^{N\times C}\). Compared with most existing studies where the prototype vectors are directly optimized on few labeled data, this allows the prototype vectors to aggregate pre-trained knowledge from massive unlabeled nodes for more effective task adaptation.

### Inference

In the inference stage, classification is performed by comparing the similarity of representations between node/graph (from MLP-based view) and prototype vectors (from GNN-based view) from different classes. The class corresponding to the prototype vector with the largest similarity is taken as the final prediction of the node/graph. We use node classification as an example to explain in detail. By comparing the node representation with each class prototype vector \(\mathbf{p}_{c}\), we can get the predicted class probability

\[p(c|\eta_{i})=\frac{\exp(\text{sim}(\mathbf{z}_{i}^{(1)},\mathbf{p}_{c})/\tau) }{\sum_{c=0}^{C}\exp(\text{sim}(\mathbf{z}_{i}^{(1)},\mathbf{p}_{c})/\tau)}, \tag{9}\]

where the highest-scored class is chosen as the prediction.

## 5. Experiments

In this section, we conduct extensive experiments on node classification and graph classification tasks with 10 benchmark datasets to evaluate our proposed SAP.

### Experimental Setup

**Datasets.** We evaluate the performance of SAP using various benchmark datasets with diverse properties, including homophilous graphs: citation networks (Krizhevsky et al., 2017) (i.e, Cora, CiteSeer, PubMed), ogbn-arxiv (Zhu et al., 2017), and heterophilous graphs: Chameleon (Zhu et al., 2017), Actor (Zhu et al., 2017), ENZYMES (Zhu et al., 2017), PROTEINS (Zhu et al., 2017), COX2 (Zhu et al., 2017), BZR (Zhu et al., 2017). We summarize these datasets in Table 1. Note that the "Task" column indicates the type of downstream task on each dataset, where "N" represents node classification and "G" represents graph classification.

**Baselines.** To evaluate the proposed SAP, we compare it with 3 categories of state-of-the-art approaches as follows.

* **Supervised models**: GraphSAGE (Chen et al., 2017), GCN (Krizhevsky et al., 2017) and GAT (Zhu et al., 2017). They use the labeled data to learn GNNs, which are then directly applied for the classification tasks.
* **Graph pre-training models**: EdgeMask (Zhu et al., 2017) and GraphCL (Zhu et al., 2017). Following the transfer learning strategy of "pre-train & fine-tune", the pre-trained models are fine-tuned on the downstream tasks.
* **Graph prompt models**: GPPT (Zhu et al., 2017), GraphPrompt (Zhu et al., 2017), GPF (Zhu et al., 2017) and ProG (Zhu et al., 2017). They adopt the "pre-train & prompt" paradigm, where the pre-trained models are frozen, and task-specific learnable prompts are introduced and trained in the downstream tasks. Note that GPF works for all pre-training tasks, in our experiments GraphCL is used for pre-training.

**Implementation details.** To train SAP, we adopt the Adam optimizer (Kingmae and Ba, 2014), where the learning rate and weight decay in the pre-training stage is fixed as 1e-4. We set the number of both graph neural layers and multilayer perceptron layers as 2. We set the hidden dimension for node classification as 128, and for graph classification as 32. Other hyper-parameters are tuned on the results on the validation set by a grid search. Details of the hyper-parameter setting is listed in Appendix C. Furthermore, for those non-prompt-based competitors, some of their results are directly reported as in (Zhu et al., 2017) and (Zhu et al., 2017) (i.e., node classification with 0%, 30% and 50% masking

\begin{table}
\begin{tabular}{c|c c c c c c} \hline \hline Datasets & Graphs & Graph classes & Avg. nodes & Avg. edges & Node features classes (N/G) \\ \hline Cora & 1 & - & 2,708 & 5,429 & 1433 & 7 & N \\ CiteSeer & 1 & - & 3,327 & 4,732 & 3703 & 6 & N \\ PubMed & 1 & - & 19,717 & 44,338 & 500 & 3 & N \\ ogbn-arxiv & 1 & - & 169,343 & 1,166,243 & 128 & 40 & N \\ Chameleon & 1 & - & 2,277 & 31,421 & 2325 & 5 & N \\ Actor & 1 & - & 7,600 & 26,752 & 931 & 5 & N \\ ENZYMES & 600 & 6 & 32.63 & 62.14 & 18 & 3 & N, G \\ PROTEINS & 1,113 & 2 & 39.06 & 72.82 & 1 & 3 & G \\ COX2 & 467 & 2 & 41.22 & 43.45 & 3 & - & G \\ BZR & 405 & 2 & 35.75 & 38.36 & 3 & - & G \\ \hline \hline \end{tabular}
\end{table}
Table 1. Statistics of the datasets.
ratio and graph classification). For other cases and prompt-based models, we fine-tune hyper-parameters with the codes released by their original authors. For fair comparison, we report the average results with standard deviations of 5 runs for node classification experiments, while the setting of graph classification experiments follow (Krizhevsky et al., 2017). We run all the experiments on a server with 32G memory and a single Tesla V100 GPU.

### Node classification

**Experimental setting**. We conduct node classification on 6 datasets, i.e., Cora, CiteSeer, PubMed, ogb-arxiv, Chameleon and Actor. For homophilous graph datasets, we use the official splitting of training/validation/testing (Krizhevsky et al., 2017). For heterophilous graph datasets, we randomly sample 20 nodes per class as training set and validation set, respectively. The remaining nodes which are not sampled will be used for evaluation. Following the setting of (Zhu et al., 2017), we randomly mask 0%, 30% and 50% of the training labels. Note that for datasets except ogbn-arxiv, the masking ratio of 0%, 30% and 50% correspond to 20-shot, 14-shot and 10-shot.

**Results.** Table 2 summarizes the performance results, from which we make the following major observations.

(1) Most supervised methods are very hard to achieve better performance compared with pre-training methods and prompt methods. This is because the annotations required by supervised frameworks are not enough. In contrast, pre-training approaches are usually facilitated with more prior knowledge, alleviating the need for labeled data. However, these pre-training methods still face an inherent gap between the training objectives of pre-training and downstream tasks. Pre-trained models may suffer from catastrophic forgetting during downstream adaptation. Therefore, we can find that compared with pre-training approaches, prompt-based methods usually achieve better performance.

(2) In all cases except for 0% mask on Cora, our proposed SAP outperforms all the baselines on node classification. This is because SAP bridges the gap between the pre-training stage and the downstream prompt tuning stage, and leverages graph structure prompt to provide more information from the massive unlabeled nodes. Specifically, we add class prototype vectors as new nodes to the raw graph and introduce weighted edges between prototype vectors and original nodes as prompts.

### Few-shot node classification

**Experimental setting**. To explore more challenging few-shot node classification settings, we only assign a very smaller number of labeled data as the training data for each class. Specifically, for ENZYMES, we follow existing study (Krizhevsky et al., 2017) to only choose graphs that consist of more than 50 nodes, which ensures there are sufficient labeled nodes for testing. On each graph, we randomly sample 1 node per class for training and validation, respectively. The remaining nodes which are not sampled will be used for testing. For Cora, CiteSeer and PubMed, we randomly sample 3 nodes per class for training, while the validation and test sets follow the official

\begin{table}
\begin{tabular}{c|c c c|c c c c c c|c} \hline \multirow{2}{*}{Methods} & \multicolumn{3}{c|}{Supervised} & \multicolumn{3}{c|}{Pre-train} & \multicolumn{3}{c|}{Prompt} & \multirow{2}{*}{Ours} \\  & GraphSAGE & GCN & GAT & EdgeMask & GraphCL & & & & & \\ \hline \multicolumn{11}{c}{Masking ratio = 0\%} \\ \hline Cora & 81.07(0.30) & 76.32(0.95) & 78.47(1.68) & 81.00(0.93) & 81.05(0.59) & **81.40(0.48)** & 72.15(0.51) & 69.44(0.41) & 78.29(0.47) & 80.32(0.35) \\ CiteSeer & 67.95(0.34) & 65.40(0.13) & 65.61(0.57) & 67.39(0.98) & 68.03(0.71) & 69.21(0.48) & 67.62(0.50) & 64.12(0.39) & 70.05(0.54) & **72.23(0.42)** \\ PubMed & 77.24(0.62) & 75.33(0.27) & 75.91(0.14) & 78.51(0.14) & 79.10(0.52) & 79.73(0.38) & 77.90(0.34) & 77.08(0.41) & 76.82(0.31) & **82.04(0.28)** \\ ogbn-arxiv & 65.07(0.67) & 64.26(0.15) & 64.31(0.10) & 65.59(0.18) & 67.34(0.92) & 65.94(0.24) & 59.25(0.31) & 57.02(0.34) & 70.49(0.21) & **72.63(0.67)** \\ \hline Chameleon & 32.85(1.21) & 36.60(0.61) & 34.69(0.72) & 31.62(0.38) & 29.30(0.16) & 34.25(0.81) & 35.11(0.23) & 32.47(1.92) & 36.68(1.25) & **37.94(0.68)** \\ Actor & 22.57(0.83) & 20.98(1.00) & 21.98(0.24) & 22.83(0.90) & 23.17(1.07) & 25.17(0.82) & 22.62(0.96) & 23.70(0.71) & 24.79(1.01) & **28.80(0.48)** \\ \hline \multicolumn{11}{c}{Masking ratio = 30\%} \\ \hline Cora & 75.51(0.73) & 74.04(0.30) & 76.00(0.51) & 76.32(0.32) & 76.72(0.36) & 76.83(0.26) & 67.34(0.37) & 61.72(0.28) & 73.27(0.53) & **77.05(0.40)** \\ CiteSeer & 64.46(0.56) & 56.05(0.56) & 61.23(0.60) & 63.71(0.46) & 63.98(0.54) & 64.74(0.17) & 63.96(0.31) & 62.99(0.48) & 65.02(0.47) & **68.78(0.23)** \\ PubMed & 77.79(0.34) & 78.12(0.64) & 77.40(0.63) & 79.30(0.48) & 79.91(0.61) & 80.15(0.34) & 78.13(0.47) & 71.49(0.25) & 74.23(0.36) & **80.21(0.31)** \\ ogbn-arxiv & 65.69(0.23) & 63.18(0.38) & 64.32(0.25) & 65.99(0.69) & 65.72(0.37) & 66.18(0.33) & 60.25(0.42) & 56.68(0.39) & 69.84(0.49) & **71.96(0.97)** \\ \hline Chameleon & 32.82(0.73) & 35.01(0.42) & 33.69(0.36) & 31.02(0.57) & 31.58(0.10) & 34.31(0.95) & 33.61(0.14) & 30.62(1.67) & 35.28(0.94) & **39.20(0.29)** \\ Actor & 21.28(0.79) & 20.71(0.47) & 21.03(0.51) & 22.94(0.85) & 23.28(0.07) & 24.76(0.49) & 21.90(0.22) & 23.25(0.29) & 24.10(0.93) & **26.64(1.03)** \\ \hline \multicolumn{11}{c}{Masking ratio = 50\%} \\ \hline Cora & 68.40(0.96) & 71.78(0.50) & 74.94(1.26) & 76.38(0.89) & 76.73(0.91) & 77.16(1.35) & 68.43(0.58) & 62.20(0.93) & 72.49(1.04) & **77.62(1.29)** \\ CiteSeer & 57.98(0.98) & 52.15(0.27) & 59.50(0.61) & 65.49(0.90) & 65.94(1.20) & 65.81(0.97) & 61.11(1.24) & 60.78(1.17) & 65.33(0.93) & **67.52(0.95)** \\ PubMed & 68.23(0.46) & 65.05(0.15) & 69.30(0.97) & 71.29(0.66) & 72.03(1.54) & 72.23(1.22) & 72.63(1.72) & 68.81(0.95) & 73.70(1.49) & **75.94(1.06)** \\ ogbn-arxiv & 64.56(0.75) & 64.19(0.59) & 63.97(0.69) & 64.86(0.67) & 65.87(0.82) & 66.13(0.44) & 59.13(0.59) & 56.04(0.97) & 67.80(1.65) & **69.20(0.73)** \\ \hline Chameleon & 27.93(1.72) & 30.38(1.21) & 29.14(0.79) & 30.89(1.15) & 27.37(1.40) & 31.28(0.65) & 31.67(1.19) & 29.31(1.68) & 31.75(1.25) & **34.08(1.26)** \\ Actor & 19.13(0.85) & 18.67(1.94) & 20.85(1.37) & 21.76(0.95) & 22.18(1.24) & 22.07(0.81) & 21.11(1.35) & 20.56(1.09) & 22.82(
splitting (Kumar et al., 2017). For Chameleon and Actor, we randomly sample 3 nodes per class for training and validation respectively, while the remaining nodes which are not sampled are used for testing.

**Results.** Table 3 illustrates the results. From it, we see that

(1) Compared with the results of 10-shot in Table 2, SAP under this few-shot setting improves more than the baselines. Taking Cora as an example, the accuracy of SAP is 0.46% higher than the runner-up under 10-shot, while under 3-shot, the accuracy of SAP is 2.97% higher than the runner-up. This is because SAP uses graph structure information to optimize the prototype vectors, so when the training set is extremely small, the prototype vectors can also be accurate by capturing the underlying information of other unlabeled nodes. In contrast, other methods fail to consider the relationship between the task and the massive unlabeled data.

(2) Our proposed SAP achieves larger improvements in heterophilous graphs. SAP achieves a largest improvement of 2.97% in homogeneous graphs while 5.82% in heterophilous graphs. This is because in the downstream prompt tuning stage of SAP, node representations computed from MLP-based view are not affected by the structural heterophily. Also, the graph structure prompt reduces the heterophily of the graph. Therefore, the prototype vector representations calculated from GNN-based view are more accurate. In contrast, other methods are susceptible to structure heterophily and can only achieve sub-optimal results.

### Few-shot graph classification

We conduct few-shot graph classification on 4 datasets, i.e., ENZYMES, PROTEINS, COX2 and BZR. Following the setting of (Zhu et al., 2017), we conduct 5-shot tasks. The results are listed in Table 4, from which we observe that our proposed SAP significantly outperforms the baselines on these datasets. This again demonstrates the effectiveness of our proposed method. Notably, as both node and graph classification tasks share the same pre-trained model on ENZYMES, the superior performance of SAP on both types of tasks further demonstrates that the gap between different tasks is better addressed by our unified framework.

### Model Analysis

We further analyse several aspects of our model. The following experiments are conducted on the 3-shot node classification and 5-shot graph classification.

**Ablation study on training paradigm.** We conduct an ablation study that compares variants of SAP with different pre-training and prompt tuning strategies: (1) We directly fine-tune the pre-trained models (i.e., MLP and GNN) on the tasks, instead of prompt tuning. We call this variant **SAP-ft** (with **fine-tune**). (2) For downstream tasks, we remove the prompt tuning process and only use the mean embedding vectors of the labeled data as the prototype vectors to perform classification. We call this variant **SAP-np** (**no** prompt). (3) We replace our proposed dual-view contrastive learning in pre-training with GraphCL, i.e., the pre-trained encoder is GNN, while the downstream tasks still use our proposed graph structure prompt. We call this variant **SAP-CL** (with GraphCL as the pre-training model). Figure 3 shows the results of this study, where we have the following observations:

\begin{table}
\begin{tabular}{c|c c c c} \hline \hline Methods & ENZYMES & PROTEINS & COX2 & BZR \\ \hline GraphSAGE & 18.31\(\pm\)6.22 & 52.99\(\pm\)10.57 & 52.87\(\pm\)11.46 & 57.23\(\pm\)10.95 \\ GCN & 20.37\(\pm\)5.24 & 54.87\(\pm\)11.20 & 51.37\(\pm\)11.06 & 56.16\(\pm\)11.07 \\ GAT & 15.90\(\pm\)4.13 & 48.78\(\pm\)18.46 & 51.20\(\pm\)27.93 & 53.19\(\pm\)20.61 \\ \hline InfoGraph & 20.90\(\pm\)3.32 & 54.12\(\pm\)8.20 & 54.04\(\pm\)9.45 & 57.57\(\pm\)9.93 \\ GraphCL & 28.11\(\pm\)4.00 & 56.38\(\pm\)7.24 & 55.40\(\pm\)12.04 & 59.22\(\pm\)7.42 \\ \hline GPPT & - & - & - & - \\ GraphPrompt & 31.45\(\pm\)4.32 & 64.42\(\pm\)4.37 & 59.21\(\pm\)6.82 & 61.63\(\pm\)7.68 \\ GPF & 32.65\(\pm\)5.73 & 57.16\(\pm\)5.96 & 61.62\(\pm\)7.47 & 59.17\(\pm\)6.18 \\ ProG & 29.18\(\pm\)3.09 & 60.98\(\pm\)7.49 & 61.96\(\pm\)6.35 & 63.71\(\pm\)5.25 \\ \hline SAP & **33.57\(\pm\)4.72** & **64.95\(\pm\)5.86** & **65.71\(\pm\)5.34** & **68.58\(\pm\)7.57** \\ \hline \hline \end{tabular}
\end{table}
Table 4. Accuracy (%) on graph classification.

Figure 3. The ablation study on training paradigm.

\begin{table}
\begin{tabular}{c|c c c|c c|c c c|c} \hline \hline \multirow{2}{*}{Methods} & \multicolumn{3}{c|}{Supervised} & \multicolumn{3}{c|}{Pre-train} & \multicolumn{3}{c|}{Prompt} & \multirow{2}{*}{Ours} \\  & GraphSAGE & GCN & GAT & EdgeMask & GraphCL & GPPT & GraphPrompt & GPF & ProG & SAP \\ \hline Cora & 56.28(3.17) & 57.83(5.90) & 60.34(1.5) & 64.10(2.79) & 65.89(3.45) & 64.55(3.72) & 63.91(2.43) & 63.52(5.39) & 65.68(4.29) & **68.65(2.17)** \\ CiteSeer & 52.71(3.28) & 49.69(4.39) & 52.85(3.69) & 55.23(3.17) & 58.37(4.74) & 55.63(2.55) & 53.42(4.98) & 54.31(5.21) & 59.07(2.73) & **61.70(4.21)** \\ PubMed & 63.83(4.21) & 63.16(4.56) & 64.26(3.17) & 65.89(4.26) & 69.06(3.24) & 70.07(6.07) & 68.93(3.93) & 63.98(3.54) & 64.57(3.81) & **72.23(4.20)** \\ ENZYMES & 60.02(3.72) & 61.49(12.87) & 59.94(2.86) & 56.17(14.39) & 58.73(16.47) & 53.79(17.46) & 67.04(11.48) & 60.13(15.37) & 57.22(17.41) & **72.86(14.58)** \\ \hline Chameleon & 25.69(4.82) & 27.88(5.77) & 26.97(4.85) & 23.76(3.74) & 22.25(3.14) & 28.91(3.23) & 26.35(3.50) & 27.38(3.62) & 29.18(4.53) & **33.23(3.80)** \\ Actor & 21.17(3.15) & 20.69(2.96) & 20.93(2.67) & 18.03(2.48) & 19.56(1.15) & 20.88(1.69) & 20.50(2.45) & 19.32(2.52) & 21.43(3.27) & **24.74(2.79)** \\ \hline \hline \end{tabular}
\end{table}
Table 3. Accuracy (%) on few-shot node classification.
(1) SAP-np always performs the worst among all the variants, showing the effectiveness of our proposed graph structure prompt. SAP-ft achieves better performance than SAP-np, which is because SAP-ft is parameterized.

(2) SAP achieves comparable results to SAP-CL in homogeneous graph datasets and clearly outperforms SAP-CL in heterophilous graph datasets. This is because our pre-training method uses MLP and GNN for contrastive learning, where MLP is not affected by the heterophily of the graph. In contrast, SAP-CL is susceptible to structure heterophily and can only achieve sub-optimal result in heterophilous graph datasets.

**Varying the number of the shots.** We next vary the number of shots on two datasets for node classification (Cora, CiteSeer) and graph classification (PROTEINS and COX2), respectively. For node classification, we vary the number of shots between 1 and 10. For graph classification, we vary the number of shots between 1 and 30. We compare SAP with several competitive baselines in Figure 4 and 5. In general, SAP consistently outperforms the baselines, especially when the number of shots is few. We further notice that when the number of shots is relatively large, SAP can be surpassed by graphCL on graph classification, especially on COX2. This could be contributed to more available training data on COX2, where 30 shots per class implies that 12.85% of the 467 graphs are used for training. This is not our target few-shot scenario.

**Varying the ratio of added edges.** Our prompt tuning method is parameterized by the added edges between original nodes and prototype vectors, where the weights of added edges are learnable. We hereby the impact of the ratio of added edges (i.e., parameters) \(r\). To vary the number of edges, we first randomly select \(Nr\) nodes outside the training set. During prompt tuning, we next merge the \(Nr\) nodes with \(N_{t}\) training nodes as the set of nodes to build edges with all the \(C\) prototypes. Following this setting, we conduct 3-shot node classification on 4 datasets. The results are shown in Table 5. Surprisingly, we observe that for Cora, CiteSeer and Chameleon, SAP only needs 1%, 5% and 0.1% parameters, respectively to surpass the runner-up. For PubMed, SAP can outperform runner-up only using the training set. This proves that our prompt tuning model can achieve comparable performance with only a small number of parameters (\(N_{t}+Nr\))\(C\), As such, SAP is promising in scaling to large graphs.

**Visualization of learned edge weights.** We visualize the weight matrix \(\mathbf{W}\) of the added edges after prompt tuning. As shown in Figure 6, for each node, its edge connected to its corresponding class prototype is more likely to have a larger weight. Hence, the

Figure 4. Varying the number of shots for node classification.

Figure 5. Varying the number of shots for graph classification.

Figure 6. The weights of added edges between nodes and class prototype vectors before and after prompt tuning.

\begin{table}
\begin{tabular}{c|c|c c c|c c c|c c c} \hline \hline  & runner-up & 0\% & 0.1\% & 1\% & 5\% & 10\% & 30\% & 50\% & 100\% \\ \hline Cora & 65.89\(\pm\)3.45 & 65.06\(\pm\)3.77 \(\downarrow\) & 65.72\(\pm\)3.14 \(\downarrow\) & 67.50\(\pm\)2.38 \(\uparrow\) & 67.46\(\pm\)2.45 \(\uparrow\) & 67.88\(\pm\)2.83 \(\uparrow\) & 67.56\(\pm\)3.19 \(\uparrow\) & 68.62\(\pm\)2.67 \(\uparrow\) & 68.68\(\pm\)2.17 \(\uparrow\) \\ CiteSeer & 59.07\(\pm\)2.73 & 56.70\(\pm\)4.16 \(\downarrow\) & 57.03\(\pm\)5.25 \(\downarrow\) & 57.52\(\pm\)5.03 \(\downarrow\) & 59.36\(\pm\)5.90 \(\uparrow\) & 60.98\(\pm\)4.98 \(\uparrow\) & 61.44\(\pm\)3.96 \(\uparrow\) & 62.62\(\pm\)4.26 \(\uparrow\) & 62.76\(\pm\)4.21 \(\uparrow\) \\ PubMed & 70.07\(\pm\)6.07 & 70.84\(\pm\)5.31 \(\uparrow\) & 70.32\(\pm\)3.95 \(\uparrow\) & 71.62\(\pm\)4.34 \(\uparrow\) & 70.94\(\pm\)4.40 \(\uparrow\) & 71.42\(\pm\)4.70 \(\uparrow\) & 72.20\(\pm\)4.62 \(\uparrow\) & 72.24\(\pm\)4.33 \(\uparrow\) & 73.23\(\pm\)4.20 \(\uparrow\) \\ Chameleon & 29.18\(\pm\)4.53 & 25.22\(\pm\)3.09 \(\downarrow\) & 30.92\(\pm\)3.07 \(\uparrow\) & 33.41\(\pm\)3.38 \(\uparrow\) & 33.30\(\pm\)2.36 \(\uparrow\) & 33.07\(\pm\)3.79 \(\uparrow\) & 31.89\(\pm\)3.83 \(\uparrow\) & 32.09\(\pm\)2.20 \(\uparrow\) & 33.97\(\pm\)3.22 \(\uparrow\) \\ \hline \hline \end{tabular}
\end{table}
Table 5. Varying the ratio of added edges on few-shot node classification. The \(\downarrow\)/\(\uparrow\) arrow means the decreasing/improvement compared with the accuracy of runner-up.
prototype vectors are very accurate by aggregating massive unlabeled data which contain rich pre-trained knowledge to reflect the semantics of the task labels.

**Time complexity analysis**. The major time complexity in our proposed SAP comes from MLP, GNN and the contrastive loss. We take node classification as an example. Suppose we use one-layer MLP and GCN as the backbone, since the adjacency matrix is generally sparse, let \(d_{A}\) be the average number of non-zero entries in each row of the adjacency matrix \(\mathbf{A}\). Let \(N\) be the number of nodes, \(F\) be the dimensionality of raw features, \(D\) be the dimensionality of output layer and \(C\) be the number of class labels. Then, the time complexities for MLP and GCN are \(O(NFD)\) and \(O(Nd_{A}F+NFD)\), respectively. We next analyze the time complexity of the contrastive loss. In the pre-training stage, let \(M\) be the number of selected negative samples. The time complexity is \(O(NMD)\), which is linear to the number of nodes \(N\). Then we conduct \(C\)-way \(K\)-shot learning for downstream tasks. For each node, we need to calculate its similarity with all prototype vectors, so the time complexity is \(O(CD)\). In the prompt tuning stage, we have a total of \(KC\) labeled nodes for training, so the time complexity is \(O(KC^{2}D)\). In the inference stage, the time complexity is \(O(CD)\).

## 6. Conclusion

In this paper, we proposed SAP, a novel structure-based prompting method for GNNs, which unifies the objectives of pre-training and prompt tuning for GNNs and integrates structural information in both pre-training and prompt tuning stages. For pre-training, we proposed a dual-view contrastive learning to align the latent semantic spaces of node attributes and graph structure. For downstream prompt tuning, we proposed to learn the structural connection between the prototype vectors and the graph, and then leveraged the learned structural information to perform better in few-shot tasks. Finally, we conducted extensive experiments on 10 public datasets, and showed that SAP significantly outperforms various state-of-the-art baselines on both homophilous and heterophilous graphs, especially on few-shot scenarios.
