StructSeek: Learning to Acquire Structural Evidence for Zero-Shot Graph Learning

Large language models (LLMs) have demonstrated strong semantic generalization, creating new opportunities for zero-shot graph learning. However, link prediction remains challenging because it depends critically on structural relations between node pairs. Existing Graph LLMs either require the LLM to recover such relations from serialized graph context or encode them implicitly in learned representations, while recent graph agents mainly retrieve graph observations rather than directly access task-relevant structural information. We propose StructSeek, an interactive graph agent that introduces a structure-as-tool paradigm for zero-shot graph learning. StructSeek actively seeks the semantic and structural evidence needed for each prediction through dedicated graph operators. The agent learns which operators to invoke, when to invoke them, and how to use the returned evidence for prediction. We train StructSeek with supervised fine-tuning on teacher trajectories followed by reinforcement learning. Experiments across multiple unseen graph domains show overall improvements on both node classification and link prediction. The gains are particularly pronounced for link prediction, where StructSeek-3B outperforms the strongest baseline by 12.9–25.8 percentage points across four unseen graphs. These results demonstrate the benefit of directly accessible structural evidence for zero-shot graph learning.