G²PRO: Gradient-guided Graph Prompt Optimization for LLM-based POI Recommendation

Large Language Models (LLMs) have shown strong potential for sequential reasoning, creating new opportunities for next Point-of-Interest (POI) recommendation. However, applying LLMs to POI prediction remains challenging due to the modality gap between textual semantics and continuous spatio-temporal signals. Existing rule-based prompting methods often introduce redundant context when bridging this gap. To address this issue, we propose G2PRO, a collaborative framework that combines the structural perception of Graph Neural Networks (GNNs) with the reasoning capability of LLMs. Specifically, we construct a User-Behavior Spatio-Temporal Knowledge Graph (UST-KG) to capture POI relations and transition dynamics, and train a lightweight GNN-based Prompt Selector (GPS) to select informative POI nodes for prompt construction. We further introduce a gradient-guided positive prompt labeling strategy that estimates each POI's contribution to the target prediction through gradients over prompt embeddings, turning prompt selection into an optimizable learning objective rather than a hand-crafted heuristic. Experiments on four real-world datasets show that G2PRO consistently outperforms state-of-the-art traditional and LLM-based baselines. Ablation and breakdown studies further validate the effectiveness of each component and demonstrate the benefits of structure-aware, attribution-guided prompting for LLM-based POI recommendation.