# RELIEF: Reinforcement Learning Empowered Graph Feature Prompt Tuning

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in RL training of language and agent models, one of 15 directions in Deep reinforcement learning methods.
- Builds on 40 of its 52 references that are in the map.
- First posted on arXiv 6 Aug 2024.

## Placed in

- Deep reinforcement learning methods / [RL training of language and agent models](https://mlsanity.com/deeprl/rl-training-of-language-and-agent-models/)

## Builds on (most cited first, 30 of 40)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Segment Anything](https://mlsanity.com/paper/2304.02643/) (2023)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [The Power of Scale for Parameter-Efficient Prompt Tuning](https://mlsanity.com/paper/2104.08691/) (2021)
- [Pre-train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processing](https://mlsanity.com/paper/2107.13586/) (2021)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Safe RLHF: Safe Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2310.12773/) (2023)
- [Visual-Language Prompt Tuning with Knowledge-guided Context Optimization](https://mlsanity.com/paper/2303.13283/) (2023)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Prioritized Level Replay](https://mlsanity.com/paper/2010.03934/) (2020)
- [Self-Supervised Learning of Graph Neural Networks: A Unified Review](https://mlsanity.com/paper/2102.10757/) (2021)
- [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)
- [Self-supervised Learning on Graphs: Contrastive, Generative,or Predictive](https://mlsanity.com/paper/2105.07342/) (2021)
- [From Local Structures to Size Generalization in Graph Neural Networks](https://mlsanity.com/paper/2010.08853/) (2020)
- [Why Generalization in RL is Difficult: Epistemic POMDPs and Implicit Partial Observability](https://mlsanity.com/paper/2107.06277/) (2021)
- [Overcoming Catastrophic Forgetting in Graph Neural Networks](https://mlsanity.com/paper/2012.06002/) (2020)
- [Decoupling Value and Policy for Generalization in Reinforcement Learning](https://mlsanity.com/paper/2102.10330/) (2021)
- [Improving Generalization in Reinforcement Learning with Mixture Regularization](https://mlsanity.com/paper/2010.10814/) (2020)
- [SUGAR: Subgraph Neural Network with Reinforcement Pooling and Self-Supervised Mutual Information Mechanism](https://mlsanity.com/paper/2101.08170/) (2021)
- [Reinforcement Learning with Parameterized Actions](https://mlsanity.com/paper/1509.01644/) (2015)
- [Graph Prompt Learning: A Comprehensive Survey and Beyond](https://mlsanity.com/paper/2311.16534/) (2023)
- [Parametrized Deep Q-Networks Learning: Reinforcement Learning with Discrete-Continuous Hybrid Action Space](https://mlsanity.com/paper/1810.06394/) (2018)
- [Hybrid Actor-Critic Reinforcement Learning in Parameterized Action Space](https://mlsanity.com/paper/1903.01344/) (2019)

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

- [One Prompt Fits All: Universal Graph Adaptation for Pretrained Models](https://mlsanity.com/paper/2509.22416/) (2025)
- [Does Graph Prompt Work? A Data Operation Perspective with Theoretical Analysis](https://mlsanity.com/paper/2410.01635/) (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)
- [A Survey of Cross-domain Graph Learning: Progress and Future Directions](https://mlsanity.com/paper/2503.11086/) (2025)
- [GILT: An LLM-Free, Tuning-Free Graph Foundational Model for In-Context Learning](https://mlsanity.com/paper/2510.04567/) (2025)
- [Relation-Aware Graph Foundation Model](https://mlsanity.com/paper/2505.12027/) (2025)
- [When Prompting Meets Spiking: Graph Sparse Prompting via Spiking Graph Prompt Learning](https://mlsanity.com/paper/2601.02662/) (2026)
- [Unified Graph Prompt Learning via Low-Rank Graph Message Prompting](https://mlsanity.com/paper/2604.11257/) (2026)

## Abstract (arXiv)

The advent of the "pre-train, prompt" paradigm has recently extended its generalization ability and data efficiency to graph representation learning, following its achievements in Natural Language Processing (NLP). Initial graph prompt tuning approaches tailored specialized prompting functions for Graph Neural Network (GNN) models pre-trained with specific strategies, such as edge prediction, thus limiting their applicability. In contrast, another pioneering line of research has explored universal prompting via adding prompts to the input graph's feature space, thereby removing the reliance on specific pre-training strategies. However, the necessity to add feature prompts to all nodes remains an open question. Motivated by findings from prompt tuning research in the NLP domain, which suggest that highly capable pre-trained models need less conditioning signal to achieve desired behaviors, we advocate for strategically incorporating necessary and lightweight feature prompts to certain graph nodes to enhance downstream task performance. This introduces a combinatorial optimization problem, requiring a policy to decide 1) which nodes to prompt and 2) what specific feature prompts to attach. We then address the problem by framing the prompt incorporation process as a sequential decision-making problem and propose our method, RELIEF, which employs Reinforcement Learning (RL) to optimize it. At each step, the RL agent selects a node (discrete action) and determines the prompt content (continuous action), aiming to maximize cumulative performance gain. Extensive experiments on graph and node-level tasks with various pre-training strategies in few-shot scenarios demonstrate that our RELIEF outperforms fine-tuning and other prompt-based approaches in classification performance and data efficiency. The code is available at https://github.com/JasonZhujp/RELIEF.