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

W1. The paper does not offer theoretical guidance for designing new graph prompting methods. While it rigorously analyzes existing methods, it does not extend the theoretical framework to propose novel techniques.

Thank you for pointing this out. In fact, our theoretical framework can provide fundamental theoretical guarantees for designing novel graph prompting methods. By considering Theorems 6 and 7, one can derive guidance for selecting the structure and number of prompts. These results can serve as useful directions for designing new graph prompting methods in future research. In our code project homepage, we also added some discussion to inspire the community for desining better graph prompt according to our theory analysis. please see the open discussion of our work in the code link.

W2. The paper lacks experiments on real-world cross-domain datasets, which are crucial for assessing how well graph prompting adapts to different downstream tasks.

Regarding experiments on real-world data, please refer to Appendix C, where we provide detailed experiments on real-world datasets. These results are consistent with those obtained on synthetic datasets in the main text, further supporting the validity of our theoretical findings.

Regarding the cross-domain datasets, we have the same response to Reviewer SySL C1.

Other Comments or Suggestions

We thank the reviewer for these insightful suggestion. We will open a new discussion online to keep updating our latest research findings on more real-world applications and more graph prompt design. We currently have already finished such explorations and that is the reason why we wish to find a pure theory support, just like the motivation of this paper. For anonymity policy, we will open these explorations once accepted.

W1

• The motivation of this distance we used is that: we assume once we are given an anchor/target graph embedding, our theory proves that we can use graph prompt to approximate such embedding. The given embedding is not necessarily the only optimal graph embedding. It can be any one. The purpose of this paper is to present the powerful data operation approximation from graph prompt. Of course, in a more realistic view, we usually hope such anchor graph embeding should be some optimal one for specific task because it can link graph prompt to various downstream tasks, but please note that this is not necessary for the theory basic of this paper, we say it just for indicating our reader that we can use such technique to find potential optimal solution for downstream task, and let our readers understand that graph prompt and traditional fine-tune are two routines to achive such target.
• Although the distance between Fθ∗(Gp) and C(G) may overestimate the actual performance deviation, this further supports the fact that the distance serves as an upper bound for the deviation. Our theoretical results demonstrate that this upper bound of the error is either zero or tightly controlled, ensuring that the performance deviation is also controlled. This, in turn, guarantees the effectiveness of the prompt. Thus, the strategy of using this distance as the error remains valid.
• Concerning different task predictors (decoders), while optimal embeddings vary across decoders, in practice, each downstream task has a fixed decoder from the pretrained model. Our analysis focuses solely on scenarios with fixed downstream tasks, ensuring consistent optimal embeddings .
• Additionally, our analysis does not require uniqueness of the optimal embeddings —only their existence. If exists and the distance to remains small, performance quality is assured, maintaining the validity of our approach regardless of embedding uniqueness.
• We appreciate your insightful comments and agree that exploring additional measurement approaches is promising, though somewhat beyond this paper's current scope. We intend to include such discussions in the camera-ready version upon acceptance.

W2

Thank you for your question. Please note that we clearly discuss non-linear graph aggregations in Section 4.4. The definitions of linear and non-linear graph aggregations are clearly stated in the paper. Specifically:

• Linear graph aggregations: The aggregation coefficients do not depend on the node feature vectors. For example, in GCN, the coefficients for combining neighboring nodes' embeddings are constant. (e.g. $H=AXW$ with A a constant matirx and W the parameter, just like what we call $y=ax+b$ in linear algebra)
• Non-linear graph aggregations: The aggregation coefficients depend on the node feature vectors. For example, in GAT, the coefficients are determined by attention scores, which are computed based on the feature vectors of neighboring nodes.

You are correct that GAT and GCN both use non-linear activation functions for processing aggregated information. However, we emphasize the distinction in the aggregation process, not the subsequent information processing. Almost all GNN models use non-linear layers (e.g., MLPs) to capture complex patterns during information processing, but this is not the focus of our discussion.

W3

Sorry for this typos. We will modify Equation (7) by replacing Xj, Xk with Hj, Hk (hidden embeddings), which is consistent with the reference of GAT. Please note that this typos will not affect our downstream theory analysis.

W4

In the mentioned section, we state that GPF-plus adds a combination of multiple prompt vectors to each node’s features. Specifically, Q ∈ R^M × k is a matrix, where the i-th row Qi represents the combination coefficients of the k prompt vectors, which are then added to the node features. We stated the update rule is mathematically expressed as:
[Xω]i = Xi + QiP. "M represents the number of graphs in the dataset Ω." This indicates the number of graphs being processed, each with distinct combinations of prompt coefficients Qi. We will add the explanation in the final version.

W5

We apologize for this inconsistency, which may cause confusion. We will replace this notation in Equation (17) with a different symbol and update the notation table accordingly in the final version.

W6

All-in-one-Plus: we set the inserting patter of all-in-one as independent parameters (all-in-one, however, relies on prompt tokens). We will clarify this in the final version.

W7

Our implementation of the modified graph includes all the operations you mentioned: "Adding/deleting nodes, adding/deleting/changing edges, and transforming features of a given graph G." This is explicitly stated in the task settings described in Appendix C. We will revise this section further in the final version.

C1: Despite rigorous theoretical insights, practical application and generalization to various real-world graph tasks might still face challenges in prompt design and optimization.

Thank you for your insightful comment. This paper primarily focuses on providing theoretical insights and rigorous proofs for graph prompting. We believe that exploring practical applications and generalizations should be left to the broader research and industrial communities. To triger this exploration, we added some open discussion to our work in the code project homepage, from which you could see some practical impact of our theory.

C2: Some theoretical guarantees depend on assumptions like "full-rank" model parameters, which, although justified by practical model initialization and training strategies, might limit generalization or require specific model conditions.

Thank you for your comment. In Theorems 3 and 4, the "full-rank" assumption are critical for ensuring the existence of lossless graph prompting methods in general settings. For cases where the full-rank assumption does not hold, we have dedicated considerable effort in our work to analyze such scenarios (e.g., Theorems 5, 8, and 9). These theorems provide corresponding bounds that demonstrate only controllable errors and ensure the robustness of prompt design. Therefore, the "full-rank" assumption is a key condition discovered during our exploration and does not detract from the contributions of this paper.

C3: While synthetic datasets convincingly demonstrate theoretical validity, broader validation across diverse real-world datasets and complex scenarios would enhance practical relevance.

In Appendix B of our paper, we conducted extensive analyses and experiments on various real-world datasets. The results obtained are very similar to those from synthetic datasets in the main text. Therefore, we believe that both synthetic and real-world datasets yield consistent results, fully supporting the validity of our theoretical findings.

Regarding the experimental setup, we carefully aligned each experiment with the theoretical discoveries, focusing on the core theoretical insights. From a practical experimental perspective, this is sufficient to validate the problem. Broader and more complex settings could be left to the wider research community. Our goal is to emphasize the solid theoretical results.

C4: typos and references:

We have noted the minor editing errors and suggestions for updating references. These will be totally included in the final version of the paper.

Q1. Could you clarify under which practical conditions the assumption of a full-rank matrix in Theorems 3 and 4 typically holds?

Thank you for your question. As discussed in the section following Theorem 4, when parameter matrices are initialized using methods such as orthogonal initialization, He initialization, or Xavier initialization, they are almost always full-rank throughout the training process.

Here, "almost always" can be understood as follows: the determinant of a matrix is 0 if and only if the matrix is rank-deficient. However, during training, the determinant can take any value along the real number axis and its behavior can be considered as random fluctuations, making it extremely unlikely to be exactly 0. Since He initialization is the standard initialization method in modern practices, the direct answer is that with proper initialization, trained models can be considered full-rank matrices in practice. We added some open discussion to our work in the code project homepage, from which you could see further practical discussion on full-rank condition.

Q2. Can you discuss the scalability of your proposed graph prompting methods to extremely large graph datasets, such as those encountered in industrial applications?

Our work primarily analyzes classical prompting methods, such as GPF and All-In-One. In Theorem 7, we provide a detailed discussion on the performance of multi-token GPF and multi-node subgraph All-In-One methods on large-scale graph datasets. Specifically, part (4) of Theorem 7 gives an upper bound on the final error, theoretically demonstrating the scalability of graph prompting methods to extremely large graph datasets.

Some studies have already achieved promising results on larger datasets, and our work provides theoretical support for these findings. For extremely large graph datasets, following our theorems and subsequent discussions, effective results can be achieved using prompts that are much smaller than the dataset itself. This theoretical work strongly supports the scalability of graph prompting methods to extremely large graph datasets and provides a solid foundation for future industrial applications.

We will add more scalability discussion in the final version.

C1: Why aren't we considering a completely different training task defined on a different dataset than the downstream task? I understand that this setting is significantly more challenging, but otherwise, I believe we are not really testing the generalization ability of graph prompting.

Thank you for your question. Transferring graph models on different domains (graph datasets) is a very promising potential application of graph prompt because we believe the core challenge on this topic is how to learn effective data manipulation strategy. before graph prompt, we can nearly only focus on hand-crafted design, which is far from promising to achieve this goal. Transfering across graph datasets/domain, or across differnt tasks, are two hard problems in graph learning area. The one across domains/datasets is still a not well solved problem. recently, there are some work trying for this but most of them are far from sufficient to industrial applications.

Our paper found that, learning an effective data manipulation strategy might be helpful for both domain transfering and task transfering in graph learning area. recently, some graph prompt-based work have found the promsing restuls for graph domain transfering for recommendation (Zhang et al. Adaptive Coordinators and Prompts on Heterogeneous Graphs for Cross-Domain Recommendations. arxiv 2410.11719). The potential behind this lies in the powerful graph data manipulation capability of graph prompt. However, diving into so many various applications is far out of the scope of our motivation. This paper wishes to provide the background theory support for our community to explore further. To this end, we focus on the core problem: how well does graph prompt manipulate graph data? According to this, our experiments are close to justify the correctiness of our theory analysis. We will explore more task settings in the futre to expand the imapct of this paper.

C2: I think the authors should include intuitive explanations throughout the paper. The experimental settings are unclear, as I discussed above. Appendix C partially helped me understand the loss and the training procedure ..., and should be partially moved to the main paper..."

Thank you for the suggestion.We will carefully consider better formatting and move some key explanations from Appendix C to the main paper in the final version to improve clarity.

C3: typos

Thanks for pointing our this, we will carefully update in our final version.

C3: Why does the loss in Equation 1 only take the graph-level embedding? Why aren't we taking the output of the downstream classifier (which is applied to the graph-level embedding) and the ground truth labels?

This concern might come from our expression issue. We are sorry for the caused misunderstanding. Take the graph classification as an example, the classifier (like MLP) can be usually treated as some addion layers for the graph model so the output of the classifier can be treated as a special graph embedding. We take this expression just for conciseness without loss of generality. In a standard graph prompt workflow, the task head is usually fixed and pre-defined so the task head is just a constant mapping and it is usually won't affect the graph prompt design. We thank you for this suggestion and we will try our best to refine this section in our final version.