Graph Large Language Models (GraphLLMs) provide powerful semantic understanding and reasoning over text-attributed graphs (TAGs), yet their reasoning can be compromised by adversarial perturbations to node text and graph structure. Existing attacks usually construct textual and structural perturbations in separate stages, each guided by its own intent, which fragments the overall attack intent and creates semantic inconsistency between the two perturbation types. This reduces stealth and makes the attacks easier for GraphLLMs to detect, weakening their effectiveness. To eliminate intent fragmentation we introduce the Graph Attack Primitive (GAP), an atomic semantic representation that unifies textual and structural perturbations under a single coherent intent. Careful calibration of GAP’s semantic composition enables strong attack performance while preserving stealth. Building on GAP, we propose S‑GAP (Stealthy GAP), a multi‑agent framework that iteratively refines the semantic content of a GAP. The framework merges GAP planning and realization, continuously improving them through surrogate evaluation and textual feedback. Extensive experiments on four datasets, three GraphLLMs, and two attack settings show that S‑GAP improves attack success rate (ASR) by an average of 7.02% over the strongest baselines and produces more relationally plausible perturbations, exposing critical vulnerabilities in current GraphLLMs and motivating more robust defenses.
Review