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

arXiv: https://arxiv.org/abs/2410.01635 · HTML: https://mlsanity.com/paper/2410.01635/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 35 references that are in the map.
- First posted on arXiv 2 Oct 2024.

## Builds on (most cited first, 23 of 23)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [GraphPrompt: Unifying Pre-Training and Downstream Tasks for Graph Neural Networks](https://mlsanity.com/paper/2302.08043/) (2023)
- [All in One: Multi-task Prompting for Graph Neural Networks](https://mlsanity.com/paper/2307.01504/) (2023)
- [Universal Prompt Tuning for Graph Neural Networks](https://mlsanity.com/paper/2209.15240/) (2022)
- [PRODIGY: Enabling In-context Learning Over Graphs](https://mlsanity.com/paper/2305.12600/) (2023)
- [All in One and One for All: A Simple yet Effective Method towards Cross-domain Graph Pretraining](https://mlsanity.com/paper/2402.09834/) (2024)
- [Graph Prompt Learning: A Comprehensive Survey and Beyond](https://mlsanity.com/paper/2311.16534/) (2023)
- [Virtual Node Tuning for Few-shot Node Classification](https://mlsanity.com/paper/2306.06063/) (2023)
- [GraphControl: Adding Conditional Control to Universal Graph Pre-trained Models for Graph Domain Transfer Learning](https://mlsanity.com/paper/2310.07365/) (2023)
- [HetGPT: Harnessing the Power of Prompt Tuning in Pre-Trained Heterogeneous Graph Neural Networks](https://mlsanity.com/paper/2310.15318/) (2023)
- [ProG: A Graph Prompt Learning Benchmark](https://mlsanity.com/paper/2406.05346/) (2024)
- [GraphPro: Graph Pre-training and Prompt Learning for Recommendation](https://mlsanity.com/paper/2311.16716/) (2023)
- [Prompt Learning on Temporal Interaction Graphs](https://mlsanity.com/paper/2402.06326/) (2024)
- [MolCPT: Molecule Continuous Prompt Tuning to Generalize Molecular Representation Learning](https://mlsanity.com/paper/2212.10614/) (2022)
- [RELIEF: Reinforcement Learning Empowered Graph Feature Prompt Tuning](https://mlsanity.com/paper/2408.03195/) (2024)
- [Pre-train and Learn: Preserve Global Information for Graph Neural Networks](https://mlsanity.com/paper/1910.12241/) (2019)
- [Urban Region Pre-training and Prompting: A Graph-based Approach](https://mlsanity.com/paper/2408.05920/) (2024)
- [DDIPrompt: Drug-Drug Interaction Event Prediction based on Graph Prompt Learning](https://mlsanity.com/paper/2402.11472/) (2024)

## Built on by (most cited first, 10 of 10)

- [GCAL: Adapting Graph Models to Evolving Domain Shifts](https://mlsanity.com/paper/2505.16860/) (2025)
- [Reliable and Compact Graph Fine-tuning via GraphSparse Prompting](https://mlsanity.com/paper/2410.21749/) (2024)
- [Graph Prompting for Graph Learning Models: Recent Advances and Future Directions](https://mlsanity.com/paper/2506.08326/) (2025)
- [Learning and Editing Universal Graph Prompt Tuning via Reinforcement Learning](https://mlsanity.com/paper/2512.08763/) (2025)
- [Boundary Prompting: Elastic Urban Region Representation via Graph-based Spatial Tokenization](https://mlsanity.com/paper/2503.07991/) (2025)
- [Rethinking Link Prediction for Directed Graphs](https://mlsanity.com/paper/2502.05724/) (2025)
- [PLACE: Prompt Learning for Attributed Community Search in Large Graphs](https://mlsanity.com/paper/2507.05311/) (2025)
- [Cross-Paradigm Graph Backdoor Attacks with Promptable Subgraph Triggers](https://mlsanity.com/paper/2510.22555/) (2025)
- [LoRAP: Low-Rank Aggregation Prompting for Quantized Graph Neural Networks Training](https://mlsanity.com/paper/2601.15079/) (2026)
- [Message Tuning Outshines Graph Prompt Tuning: A Prismatic Space Perspective](https://mlsanity.com/paper/2606.03290/) (2026)

## Abstract (arXiv)

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 pretraining and finetuning to pretraining 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.