S-GAP: Stealthy Graph Attack Primitives for Graph Large Language Models

A new arXiv paper (2610.23465v1) introduces S-GAP, a multi-agent framework that attacks Graph Large Language Models by unifying textual and structural perturbations under a single "Graph Attack Primitive" intent, improving attack success rate over the strongest baselines by 7.02% on average. Experiments across four datasets, three GraphLLMs and two attack settings found S-GAP produced more relationally plausible perturbations, which the authors say exposes critical vulnerabilities in current GraphLLMs and motivates more robust defenses.

arXiv:2610.23465v1 Announce Type: new Abstract: Graph Large Language Models GraphLLMs enable powerful semantic understanding and reasoning over Text-Attributed Graphs TAGs , while their semantic reasoning may exhibit vulnerabilities to perturbations in node text and graph structure under adversarial attack evaluation. Existing attacks typically construct textual and structural perturbations in separate stages guided by distinct realization intents. However, this separation results in attack-intent fragmentation, causing semantic incoherence between the two perturbation types, thereby undermining attack stealth and making them easier for GraphLLMs to identify and disregard, ultimately weakening attack effectiveness. To avoid attack-intent fragmentation, we propose the Graph Attack Primitive GAP , an atomic semantic representation that unifies textual and structural perturbations under a coherent attack intent. By carefully calibrating the semantic composition of a GAP, we can achieve strong attack effectiveness while maintaining sufficient attack stealth. Furthermore, we introduce S-GAP Stealthy GAP , a multi-agent framework that iteratively refines the semantic content of the GAP. The framework unifies GAP planning and realization and continuously refines this process through surrogate evaluation and textual feedback. Extensive experiments across four datasets, three GraphLLMs, and two attack settings show that S-GAP improves ASR over the strongest baselines by 7.02% on average while producing more relationally plausible perturbations, exposing critical vulnerabilities in current GraphLLMs and motivating more robust defenses.