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

S-GAP: Stealthy Graph Attack Primitives for Graph Large Language Models Wenda Li1 , Tongya Zheng2 , Shunyu Liu3 , Hanyang Yuan1 , Kaixuan Chen1 Yu Wang1 , Yuchen Ying1 , Haoze Jiang1 , Huan Li1 , Gang Chen1 , Zujie Ren4,† 1

arXiv:2610.23465v1 [cs.AI] 16 Oct 2026

3

Zhejiang University 2 Hangzhou City University Nanyang Technological University 4 Zhejiang Lab lwdup@zju.edu.cn, renzju@zju.edu.cn † Corresponding author: Zujie Ren

Abstract Graph Large Language Models (GraphLLMs) enable powerful semantic understanding and reasoning over TextAttributed 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.

Introduction Text-Attributed Graphs (TAGs), which integrate graph structure with textual content, are widely used to represent citation networks (Tang et al. 2024), product networks (Fan et al. 2022), and other knowledge-rich networks (Zhong et al. 2023; Ying et al. 2026). Recently, Graph Large Language Models (GraphLLMs) (Chen et al. 2024; Wang et al. 2024; Zhang et al. 2026) have incorporated the powerful semantic understanding and reasoning capabilities of large language models into graph learning, enabling joint reasoning over node text and graph structure. Compared with conventional graph models, this integration allows GraphLLMs to contextualize node semantics using relational information, supporting richer and more context-sensitive graph reasoning. However, this joint reliance also creates a coupled vulnerability: malicious text can distort node seman-

Low Plausibility

Medium Plausibility

High Plausibility

(a) Graph Injection Attack (GIA) Clean Nettack Mettack PRBCD WTGIA ATAG-LLM BadGraph S-GAP

7

32

67

24

69

(b) Graph Modification Attack (GMA) Clean Nettack Mettack PRBCD WTGIA ATAG-LLM BadGraph S-GAP

32

8

0

67

47

45

50 Proportion (%)

100

Figure 1: Relational-plausibility distributions on Cora. An LLM assesses each relation as having low, medium, or high plausibility, while Clean denotes original graph relations.

tics, while manipulated relations can alter how those semantics are contextualized. Understanding how this coupled vulnerability can be exploited by adversarial attacks is therefore critical to the safe and reliable deployment of GraphLLMs in knowledge-intensive and decision-sensitive applications (Gao et al. 2025; Dai et al. 2024). Graph adversarial attacks systematically expose the vulnerabilities of GraphLLMs through budget-constrained perturbations to graph data and commonly operate in two settings: Graph Injection Attack (GIA), which introduces adversarial nodes together with their incident edges, and Graph Modification Attack (GMA), which alters existing graph elements. Across these settings, conventional methods manipulate graph structure, vectorized node attributes, or both (Zügner, Akbarnejad, and Günnemann 2018; Zügner and Günnemann 2019; Ju et al. 2023; Ma, Trivedi, and Koutra 2026). Attacks on TAGs impose an additional constraint: attribute perturbations must be realized as valid naturallanguage text while being coordinated with structural manipulations (Lyu et al. 2025; Chen et al. 2026; Lei et al. 2024).

These methods typically construct textual and structural perturbations in separate stages, with each stage guided by a separately defined realization intent derived from the shared attack objective. For example, the structural stage (Lyu et al. 2025) is driven by relational criteria, whereas the textual stage (Lei et al. 2024) follows separately defined semantic constraints. Although both stages pursue the same ultimate attack objective, their stage-specific attack intents are defined by different realization criteria rather than explicitly unified. We refer to this separation as attack-intent fragmentation. Attack-intent fragmentation can lead to semantic incoherence between textual and structural perturbations, with the generated text failing to justify the manipulated relations and the structural perturbations failing to support the adversarial semantics introduced by the text. Such incoherent perturbations lack sufficient attack stealth, making them more likely to be judged semantically implausible or weakly relevant and subsequently disregarded by the LLM components of GraphLLMs, ultimately weakening attack effectiveness. We further validate this observation by prompting an LLM to assess the plausibility of the relations produced by each attack and categorize them as low, medium, or high plausibility. As shown in Figure 1, existing attacks produce substantially larger proportions of low-plausibility relations than the clean graph under both attack settings, suggesting that their textual and structural perturbations frequently form semantically implausible relations. In contrast, our method S-GAP yields plausibility distributions much closer to the clean reference, indicating that its perturbations better preserve the relational plausibility profile of the original graph and thus achieve stronger attack stealth. To avoid attack-intent fragmentation, we propose the Graph Attack Primitive (GAP), an atomic semantic representation that provides a coherent attack intent shared by textual and structural perturbations. By explicitly specifying the target semantics to preserve and the adversarial semantics to introduce, a GAP can avoid semantically implausible perturbations while retaining adversarial strength. However, balancing these competing semantic compositions is inherently target-dependent and difficult to achieve in a single generation step. We therefore introduce S-GAP (Stealthy GAP), a multi-agent framework that iteratively refines GAPs through surrogate evaluation and textual feedback. The Planner Agent proposes a GAP for the target, which the Attack Agent instantiates as a concrete text–structure perturbation and evaluates using a surrogate GNN. The Main Agent controls the overall process and uses the target context and execution outcome to construct a textual feedback that guides the Planner Agent’s refinement in the next round. Our contributions are summarized as follows: • We identify attack-intent fragmentation in adversarial attacks, where textual and structural perturbations guided by independent attack intents undermine stealth, and propose GAP, which provides a unified attack intent for both perturbation types and is expressively complete over the defined attack search space. • We introduce S-GAP, a multi-agent framework for unified target-specific GAP planning and realization with

iterative feedback-guided refinement through surrogate evaluation and textual feedback. • We conduct comprehensive experiments on four datasets with three victim GraphLLMs under two attack settings. The results demonstrate superior attack effectiveness and stealth over existing methods, exposing fundamental vulnerabilities in the joint textual and structural reasoning of current GraphLLMs.

Related Work Graph Adversarial Attacks. Graph adversarial attacks traditionally manipulate graph topology or vectorized node attributes. In the graph injection setting, attackers (Chen et al. 2022) introduce adversarial nodes together with their incident edges. TDGIA (Zou et al. 2021) jointly optimizes injected features and connectivity to increase their influence on target predictions, while reinforcement-learning-based approaches (Sun et al. 2020; Ju et al. 2023; Zhao and Zhang 2025) formulate node injection as a sequential decision process under different levels of model access. In the graph modification setting, attacks (Li et al. 2021; Xu et al. 2022) alter existing graph elements: Nettack (Zügner, Akbarnejad, and Günnemann 2018) constructs targeted local perturbations by modifying edges and node attributes, Metattack (Zügner and Günnemann 2019) formulates graph poisoning as a metalearning problem, and PRBCD (Geisler et al. 2021) improves the scalability of structural attacks through randomized block coordinate descent. Despite their different threat models and optimization strategies, these methods operate primarily on graph topology and discrete or continuous feature representations, rather than directly constructing or editing the underlying natural-language text. Attacks on Text-Attributed Graphs. Recent studies extend graph attacks from vectorized attributes to textual and semantic perturbations on TAGs. WTGIA (Lei et al. 2024) pioneers text-level graph injection by converting adversarial feature patterns into interpretable textual nodes. ATAGLLM (Lyu et al. 2025) further employs LLMs to generate candidate injection texts and uses graph explanations to determine their injection positions in a black-box setting. Beyond raw-text generation alone, GraphTextack (Ma, Trivedi, and Koutra 2026) jointly searches the connectivity and semantic feature assignments of injected nodes through evolutionary optimization. For graph modification, IMDGA (Fan et al. 2026) combines graph-aware textual substitutions with edge pruning to improve attack effectiveness and stealthiness, while BadGraph (Chen et al. 2026) leverages graph priors and LLM reasoning to jointly perturb textual semantics and topology. These studies establish textual semantics and graph structure as coupled attack surfaces. However, their semantic coordination is embedded in particular generation procedures and perturbation mechanisms, such as node injection, textual substitution, or topology modification. In contrast, S-GAP introduces the Graph Attack Primitive as an explicit semantic interface between attack intent and concrete text–structure realization, enabling the same representation to guide both GIA and GMA.

GIA Mode Attack

Multi Agent System

Target Context Node Text

Main Agent

Neighbor Nodes

S-GAP

Proxy Output Contrastive Nodes

Surrogate GNN

Select

𝑣

Origin Graph

Attack Graph

The first primitive only…, which is insufficient. Explore a stronger theoretical direction …

1

Inject Nodes

2

Inject Edges 𝑧

𝑡

𝑢 𝑤

𝑣

Nodes Retrieval

Target Context

GMA Mode Attack

Generated Text

Textual Feedback

1

Modify Text

Generate a primitive that preserves the topic while exploring away from ...

2

Add/Delete Edges

Generate a plausible paper node that connects the target and retrieved bridge while …

𝑣

Given the current context, decide whether to plan a graph attack primitive, attack, or …

Attack Agent

𝑡𝑣′

Planner Agent

𝑢

𝑣

𝑤

Figure 2: Overview of the proposed S-GAP framework.

Background Text-Attributed Graphs. A Text-Attributed Graph (TAG) is denoted by G = (V, E, T ), where V is the node set, E ⊆ V × V is the edge set, and T = {ti | vi ∈ V} is the collection of node texts, with ti denoting the text associated with node vi . The graph structure is represented by an adjacency matrix A ∈ {0, 1}|V|×|V| , where Aij = 1 if (vi , vj ) ∈ E and Aij = 0 otherwise. In node classification, each node vi has a label yi ∈ Y, where Y denotes the label space (Lei et al. 2024; Chen et al. 2026). Threat Model. We consider untargeted evasion attacks under a strict black-box setting. The attacker observes only the clean graph and training labels, but has no internal knowledge of or query access to the fixed victim model. The goal is to change the target node’s prediction to any other class. We consider two common graph perturbation settings (Zou et al. 2021; Ma, Trivedi, and Koutra 2026; Chen et al. 2026). (1) Graph Injection Attack (GIA). The attacker injects a set of nodes Vvinj for a target node v, together with their associated texts Tvinj and incident edges Evinj . The perturbed TAG is
G ′ = V ∪ Vvinj , E ∪ Evinj , T ∪ Tvinj . (1) Each edge in Evinj has at least one injected node as an endpoint, while the existing nodes, edges, and texts remain unchanged (Zou et al. 2021; Lei et al. 2024; Ma, Trivedi, and Koutra 2026). (2) Graph Modification Attack (GMA). The attacker modifies the text of an existing node v and its local connectivity, yielding a modified text t′v , a set of added edges Ev+ , and a set of removed edges Ev− . The perturbed TAG is
G ′ = V, (E \ Ev− ) ∪ Ev+ , (T \ {tv }) ∪ {t′v } . (2)

Each edge in Ev+ ∪ Ev− has the target node v as an endpoint, while the node set, all other node texts, and non-v-incident edges remain unchanged (Zhang et al. 2025; Chen et al. 2026).

Methodology Overview As illustrated in Figure 2, S-GAP is a multi-agent framework that iteratively refines GAPs using surrogate evaluation and textual feedback. The Main Agent coordinates the process by maintaining the attack state and deciding whether refinement should continue or terminate. At each iteration, the Planner Agent composes or refines a GAP. The Attack Agent then generates setting-specific text–structure perturbations from the GAP and evaluates them using a surrogate GNN. The Main Agent then updates the attack state with the execution outcome and produces textual feedback to guide the Planner Agent’s next refinement.

Graph Attack Primitive Target context. Let fsur be a surrogate GNN trained on the clean training split. To reduce the combinatorial cost of endpoint selection over all |V| graph nodes, S-GAP restricts free attack-edge endpoints to a contrastive candidate pool Dv comprising the M nodes in V with the lowest cosine similarity to v under normalized text embeddings. We construct the target context:
Cv = tv , ntext , psur (3) v v , dv , where tv is the target text, ntext is a bounded set of randomly v sampled one-hop neighbors of v, psur = fsur (G, v) is the v clean surrogate prediction, and dv denotes a few nodes drawn from Dv and provided to the LLM as contrastive context, whose number is much smaller than |Dv |.

Definition 1 (Graph Attack Primitive) A Graph Attack Primitive (GAP) is an atomic semantic representation of a coherent attack intent that serves as a general interface between the intent and its concrete text–structure realization. Let P denote the primitive space, with Pv ∈ P representing a GAP associated with target node v. For an attack setting m ∈ {GIA, GMA}, the realization map Im (v, Pv )

(4)

returns the set of valid text–structure perturbations that realize the attack intent represented by Pv under setting m. Beyond providing a unified attack intent for text–structure perturbations, another key advantage of GAP is its compatibility with both GMA and GIA. Existing methods are typically tailored to the perturbation mechanism of a single setting and therefore support either graph modification or graph injection. By separating attack intent from setting-specific realization, GAP accommodates both settings within a unified framework through their respective realization functions. Proposition 1 (Candidate Search-Space Completeness) For any candidate endpoint search space Dv ⊆ V and graph cand (Dv , B) denote all valid perturbations budget B, let Fv,m under setting m whose free structural endpoints lie in Dv and whose graph cost is at most B. Assume that the LLM is text-complete and that retrieval is tie-free. Then [ cand Fv,m (Dv , B) ⊆ Im (v, Pv ). (5) Pv ∈P

The proof is provided in Appendix. Proposition 1 establishes candidate-space completeness under the text-completeness assumption. Accordingly, exhaustive optimization over all primitive realizations preserves the optimum within the candidate-restricted attack space. Stealth-oriented primitive representation. To improve attack stealthiness, S-GAP represents each primitive using two semantic components: Pv = (αv , βv ),

(6)

where αv is the target anchor that identifies the target semantics to preserve, and βv denotes the adversarial semantics to introduce. The target anchor keeps the generated entity aligned with the target topic, while the adversarial semantics provide contrastive evidence against the current prediction. The GAP provides a compact and reusable semantic specification that establishes a unified attack direction for text–structure perturbations, while its concrete realization as nodes and edges is determined by the system during instantiation. Since Pv remains a target-specific decision variable, identifying an effective Pv motivates the iterative multi-agent optimization framework presented next.

Primitive planning. At round r, the Planner Agent generates a primitive from the target context and textual feedback produced by the Main Agent: (r−1) Pv(r) = PlannerAgent(Cv , gv,m ).

(7)

(r−1)

Here, gv,m denotes the textual feedback generated by the (−1) Main Agent described below, and gv,m = ∅. (r)

Attack realization and evaluation. Given Pv , the Attack Agent realizes it as K setting-specific executable text– (r) structure perturbations {∆v,i,m }K i=1 . To compare their attack efficacy, the Attack Agent evaluates each perturbation on the surrogate GNN using a confidence-drop score, defined as the reduction in confidence assigned to the class predicted on the clean graph:   (r) (r) Jv,i,m = fsur (G, v)cv − fsur G ⊕m ∆v,i,m , v , (8) cv

where cv = arg maxc fsur (G, v)c , and ⊕m denotes the setting-specific graph transformation defined in Eqs. (1) (r) and (2). A larger Jv,i,m indicates a greater reduction in the surrogate confidence of the clean prediction. The Attack Agent returns the resulting perturbations and their confidence-drop scores as its round output: (r) Ov,m = AttackAgentm (Cv , Pv(r) ) n oK (r) (r) = ∆v,i,m , Jv,i,m .

(9)

i=1

Textual feedback and iterative refinement. The Main Agent controls the refining optimization process by main(r) taining a context history Hv,m and selecting each subsequent operation. This history records the planning and execution results from previous rounds, prior operation instructions, the current best perturbation and edit plan, and the remaining budget. Let Out(r) v,m denote the output returned by the agent invoked in round r: ( (r) Pv , if the Planner Agent is invoked, (r) Outv,m = (r) Ov,m , if the Attack Agent is invoked. (10) Given the current output and the preceding context history, the Main Agent selects the next operation:   (r) (r−1) ηv,m = MainAgent Out(r) , v,m , Hv,m (11) (r) ηv,m ∈ {Plan, Attack, Stop} .

Framework of Stealthy Graph Attack Primitive

The current output and selected operation are then incor(r) (r) porated into Hv,m . When ηv,m = Plan, the Planner Agent (r) receives a planner-facing GAP context Cev,m and the Main (r) Agent’s textual assessment ev,m of the current result as textual feedback:   (r) (r) gv,m = Cev,m , e(r) (12) v,m .

For target v under attack setting m, the Planner, Attack, and Main Agents jointly optimize Pv through a recurrent cycle of primitive planning, attack realization followed by evaluation, and feedback synthesis.

The textual feedback gv,m provides a natural-language update direction for the primitive components, guiding the revi(r) (r+1) (r) sion from Pv to Pv . When ηv,m = Attack, the Attack

(r)

Agent executes an existing primitive and returns its outcome. (r) When ηv,m = Stop, optimization for the current target terminates. This Main-Agent-controlled adaptive decision process allocates fewer primitive rounds to easier targets and more rounds to harder ones, subject to the maximum round budget.

GAP-guided Perturbation Construction GIA and GMA share the same GAP optimization process but use setting-specific perturbation construction. For each i ∈ {1, . . . , K}, the Attack Agent constructs the i-th executable text–structure perturbation from a fixed primitive Pv by retrieving a setting-specific endpoint plan and generating its corresponding textual realization: Ωv,i,m = Retrievem (Cv , Dv , Pv ) , Tv,i,m = Generatem (Cv , Pv , Ωv,i,m ) .

(13) (14)

Here, Ωv,i,m specifies the retrieved endpoints, while Tv,i,m denotes the generated textual realization. Guided by the same GAP, the two perturbations convey consistent semantics and maintain relational plausibility, resulting in improved attack stealthiness. Their setting-specific composition into ∆v,i,m is defined below. Graph Injection Attack Realization. Under GIA, Ωv,i,GIA specifies the existing endpoints retrieved from Dv , while inj Tv,i,GIA = Tv,i contains the texts generated for the injected nodes. Together, they define the perturbation   inj inj inj ∆v,i,GIA = Vv,i , Tv,i , Ev,i , (15) inj inj where Vv,i contains the instantiated nodes, Tv,i denotes the inj corresponding generated node texts, and Ev,i connects these nodes to the endpoints specified by Ωv,i,GIA . The attack is applied as G ′ = G ⊕GIA ∆v,i,GIA , following the graph

transformation in Eq. (1). Graph Modification Attack Realization. Under GMA, Ωv,i,GMA specifies addition endpoints selected from Dv and removal endpoints selected from the existing neighbors of v, while Tv,i,GMA is the generated rewrite of the target text. Together, they define the perturbation
+ − ∆v,i,GMA = Tv,i,GMA , Ev,i , Ev,i , (16) + where Ev,i connects v to the addition endpoints specified by − Ωv,i,GMA , and Ev,i removes its edges to the specified existing neighbors. The attack is applied as G ′ = G ⊕GMA ∆v,i,GMA , following the graph transformation in Eq. (2).

Experiments Experimental Setup Datasets. We conduct experiments on four text-attributed graphs: Cora (McCallum et al. 2000), PubMed (Sen et al. 2008), OGBN-Arxiv (Hu et al. 2020), and a subset of OGBNProducts (Hu et al. 2020). More details and statistics of the datasets are provided in Appendix.

Victim Models and Baselines. We evaluate transfer attacks against three GraphLLMs: LLaGA (Chen et al. 2024), RGLM (Zhang et al. 2026), and TEA-GLM (Wang et al. 2024). We group the baselines according to their original attack settings. The native GIA baselines are G2A2C (Ju et al. 2023), WTGIA (Lei et al. 2024), and ATAG-LLM (Lyu et al. 2025), whereas the native GMA baselines are Nettack (Zügner, Akbarnejad, and Günnemann 2018), Mettack (Zügner and Günnemann 2019), PRBCD (Geisler et al. 2021), and BadGraph (Chen et al. 2026). See the appendix for model and baseline details. Attack Settings. For GIA (Zou et al. 2021; Lei et al. 2024; Ma, Trivedi, and Koutra 2026), the attacker injects one textual node for each target and adds at most two incident edges. For GMA (Zhang et al. 2025; Chen et al. 2026), the attacker may make similarity-constrained revisions to the target text and add or remove at most two target-incident edges. Evaluation metrics. We measure attack effectiveness by Attack Success Rate (ASR) over targets correctly classified on the clean graph (Zhang et al. 2025; Lyu et al. 2025), where higher ASR indicates stronger attacks. Attack stealthiness is measured by the relational plausibility of induced edges, scored from 1 to 6 by a post-hoc LLM using endpoint texts. Scores of 5–6 denote High plausibility, whose proportion increases with stealthiness; original graph relations serve as a reference. Full results for all plausibility levels are reported in the appendix.

Overall Attack Evaluation Attack effectiveness. Table 1 shows that S-GAP achieves the highest ASR in all 24 cases, outperforming the strongest baseline by 12.78 and 1.25 percentage points on average under GMA and GIA, respectively. GMA is generally more effective because it directly modifies target nodes, whereas GIA is more practical but influences predictions indirectly through injected nodes. Baselines perform better in their native settings, suggesting limited adaptability across attack settings. In contrast, the unified GAP representation enables S-GAP to naturally adapt to both GIA and GMA, achieving consistently strong performance in both settings. Nettack, Mettack, PRBCD, and G2A2C mainly optimize structures or numerical features using GNN-oriented objectives, without explicitly modeling raw-text semantics. WTGIA, ATAGLLM, and BadGraph incorporate textual information but depend on predefined features, similarity proxies, or fixed attack strategies, limiting the coordination between text and structure. In contrast, S-GAP directly models semantic attack intentions and uses execution feedback to jointly refine textual and structural perturbations, thereby avoiding reliance on numerical objectives or fixed proxies. Attack stealthiness. Table 1 shows that S-GAP achieves the highest relational plausibility across all datasets and settings. Structure-oriented attacks such as Nettack, Mettack, and PRBCD generally exhibit low plausibility because their edge perturbations lack semantic constraints; for example, Nettack achieves strong GMA ASR on Cora but only 4.89% High-Plaus. Text-aware methods such as WTGIA, ATAG-

Setting Dataset

Metric/Model Clean Nettack Mettack PRBCD G2A2C WTGIA ATAG-LLM BadGraph S-GAP

Cora

LLaGA RGLM TEA-GLM High Plaus.

– – – 66.88

3.01 1.26 2.93 2.40

3.01 1.68 3.66 0.20

3.01 0.84 1.95 2.41

1.72 1.26 4.15 –

2.37 0.63 4.39 4.25

1.94 0.84 2.20 2.86

3.23 1.05 5.12 0.18

6.02 3.15 7.07 69.43

PubMed

LLaGA RGLM TEA-GLM High Plaus.

– – – 87.12

1.78 0.47 0.19 2.10

1.89 0.44 0.08 2.92

2.09 0.69 0.25 4.03

1.83 0.64 0.33 –

2.00 0.75 0.22 6.80

1.94 0.66 0.44 2.40

2.00 0.64 0.14 1.30

2.79 1.47 0.58 61.19

OGBN-Arxiv

LLaGA RGLM TEA-GLM High Plaus.

– – – 63.90

4.48 1.26 9.88 0.00

4.40 1.88 9.58 3.20

4.89 1.64 10.99 0.25

4.26 1.75 11.37 –

4.95 1.67 10.30 0.70

5.11 1.78 10.99 1.30

4.20 1.34 8.42 0.00

6.92 3.25 12.69 67.57

LLaGA RGLM OGBN-Products TEA-GLM High Plaus.

– – – 52.43

2.17 0.29 3.59 0.00

2.09 0.18 2.94 2.24

2.14 0.29 3.74 0.15

2.62 0.34 4.09 –

3.10 0.84 3.78 0.25

3.72 1.05 3.19 0.30

2.19 0.18 3.47 1.88

4.07 2.04 5.53 26.78

Cora

LLaGA RGLM TEA-GLM High Plaus.

– – – 66.88

38.28 28.36 10.24 4.89

23.23 10.71 9.76 0.09

26.67 22.48 9.51 2.77

3.01 1.89 1.71 –

2.37 0.63 4.39 0.81

17.63 9.45 6.59 0.30

19.14 21.22 21.95 41.61

44.95 49.16 50.73 44.92

PubMed

LLaGA RGLM TEA-GLM High Plaus.

– – – 87.12

27.34 8.06 0.92 6.35

1.80 0.42 0.08 2.67

13.28 5.01 0.92 4.44

3.33 0.94 0.14 –

4.23 1.75 0.44 12.66

7.98 2.02 0.56 9.70

26.30 29.42 42.50 46.53

49.01 47.76 56.89 46.90

OGBN-Arxiv

LLaGA RGLM TEA-GLM High Plaus.

– – – 63.90

9.73 3.23 11.34 29.00

4.62 1.72 9.49 1.71

13.32 5.51 13.49 0.50

5.30 1.75 9.94 –

9.53 2.96 12.93 0.30

6.68 2.82 11.07 0.03

20.25 21.54 15.63 24.47

25.19 23.45 30.33 42.05

OGBN-Products

LLaGA RGLM TEA-GLM High Plaus.

– – – 52.43

8.78 3.98 4.05 4.48

2.25 0.16 3.19 1.48

11.67 6.10 3.50 0.15

7.57 1.57 3.87 –

7.92 3.59 3.74 0.42

10.89 5.40 3.93 0.00

34.17 28.50 27.48 22.56

49.08 32.17 30.11 35.30

GIA

GMA

Table 1: Overall attack effectiveness and relational plausibility under GIA and GMA. We report ASR (%) for attack effectiveness and High-Plaus. (%) for relational plausibility. Clean denotes original graph relations; bold indicates the best attack result.

Robustness to Relational Plausibility Filtering To determine whether attack success arises from plausible adversarial evidence or anomalous relational shortcuts, we apply a relational-plausibility filter that reverts edge perturbations assigned scores of 1–2 while retaining the textual perturbations. Several baselines degrade substantially on Cora, indicating reliance on semantically unjustified relations. In contrast, changes on PubMed are minor because lowplausibility relations are rare. S-GAP retains at least 85.0% of its ASR and remains the strongest attack after filtering, showing that its effectiveness primarily arises from plausible text– structure interactions. Its slight improvement under PubMed GMA further suggests that some implausible relations may

even interfere with the attack. Complete plausibility-score distributions and victim-specific post-filtering results are provided in the appendix.

Mean Successful Attacks (%)

LLM, and BadGraph achieve better plausibility by generating natural-language perturbations. However, their separately optimized text and structure or fixed influencer strategies limit semantic alignment. As low-plausibility relations may be ignored by GraphLLMs, we further examine their impact on attack effectiveness in the next subsection.

(a) GIA 20

(b) GMA 100 Cora PubMed

80

15

60 10 40 5 0 <0.1

20 0 0.1–0.2

0.2–0.5 ≥0.5

<0.1

0.1–0.2

0.2–0.5

≥0.5

Confidence-Drop Score

Figure 4: Victim-averaged proportions of successful attacks across confidence-drop score bins.

(a) GIA / Cora 6

(b) GIA / PubMed 2

5

(c) GMA / Cora

(d) GMA / PubMed

60

70

50

60

4

Before filtering After filtering

50

40

40 3

1

30 30 20

20

0.5

0 Ne tta ck ett ac k PR BC D W TG AT IA AG -L LM Ba dG rap h SGA P

10

0 Ne tta ck ett ac k PR BC D W TG AT IA AG -L LM Ba dG rap h SGA P

0

Ne tta ck M ett ac k PR BC D W TG AT IA AG -L LM Ba dG rap h SGA P

0

10

M

1

M

2

Ne tta ck M ett ac k PR BC D W TG AT IA AG -L LM Ba dG rap h SGA P

Mean ASR (%)

1.5

Figure 3: Victim-averaged ASR (%) before and after reverting edge perturbations assigned relational-plausibility scores of 1–2. Setting Dataset

LLaGA RGLM TEA-GLM

Dataset

Variant

LLaGA RGLM TEA-GLM

Cora

Text Structure S-GAP

15.48 27.10 44.95

16.81 15.34 49.16

41.71 8.29 50.73

Text PubMed Structure S-GAP

16.54 13.59 49.01

21.44 4.96 47.76

38.62 0.67 56.89

w/o score w/o GAP w/o feedback S-GAP

2.58 3.44 3.66 6.02

1.05 1.47 1.26 3.15

3.66 4.15 6.83 7.07

w/o score w/o GAP PubMed w/o feedback S-GAP

2.09 2.17 2.68 2.79

0.80 1.02 1.05 1.47

0.22 0.28 0.33 0.58

w/o score w/o GAP w/o feedback S-GAP

30.32 23.23 27.31 44.95

25.00 22.06 28.15 49.16

33.66 26.59 31.71 50.73

Table 3: Comparison of S-GAP with variants using only textual or structural perturbations under GMA.

w/o score w/o GAP PubMed w/o feedback S-GAP

25.96 22.44 22.52 49.01

17.92 19.89 18.53 47.76

25.71 27.65 25.96 56.89

remains the best-performing configuration, although with smaller margins, demonstrating the benefit of the complete design under matched execution budgets.

Cora GIA

Cora GMA

Variant

Table 2: Ablation of surrogate scoring, GAP, and textual feedback. Results are reported as ASR (%).

Quantitative Confidence-Drop Analysis To examine whether the confidence-drop score identifies perturbations likely to succeed on target GraphLLMs, we group attacks by their final scores and measure the victim-averaged proportion of successful attacks in each bin. Figure 4 shows that higher scores generally correspond to larger success proportions. The relatively low proportions reflect the prediction gap between the surrogate model and target GraphLLMs, while the overall trend confirms that the score remains informative of attack success.

Ablation Studies Effects of confidence-drop scoring, GAP, and feedback. We compare S-GAP with three variants: w/o score removes confidence-drop scoring from the Attack Agent, w/o GAP removes the GAP entirely and directly generates candidate attack entities from the target context, and w/o feedback removes textual feedback, with no refinement of GAPs. Table 2 shows that removing any component consistently reduces ASR. Under GMA, the victim-averaged ASR decreases by 18.62–28.88 percentage points. Under GIA, S-GAP also

Text–structure complementarity. Table 3 compares SGAP with variants using only textual or structural perturbations under GMA. S-GAP achieves a victim-averaged ASR of 49.75%, compared with 25.10% and 11.66% for the two variants, respectively. These results demonstrate that the two perturbation modalities provide complementary attack signals and are more effective when used jointly.

Conclusion We investigate vulnerabilities in GraphLLMs’ joint reasoning over textual attributes and graph structure in TAGs. Existing attacks may underexpose these vulnerabilities because attack-intent fragmentation misaligns textual and structural perturbations, weakening stealth and effectiveness. We therefore propose GAP to unify attack intent and develop S-GAP to iteratively refine and realize GAPs through multi-agent planning, surrogate evaluation, and textual feedback. Across all 24 combinations of four datasets, three GraphLLMs, and two attack settings, S-GAP performs best in every case, outperforming the strongest baselines by 7.02% on average while producing more relationally plausible perturbations. Social Impact. This work reveals underexplored security risks in GraphLLMs arising from their joint reliance on text and graph structure. Our findings can support practical security evaluation and defense development for safer deployment in high-impact applications.

References Chen, R.; Zhao, T.; Jaiswal, A.; Shah, N.; and Wang, Z. 2024. Llaga: Large language and graph assistant. arXiv preprint arXiv:2402.08170. Chen, Y.; Yang, H.; Zhang, Y.; Ma, K.; Liu, T.; Han, B.; and Cheng, J. 2022. Understanding and improving graph injection attack by promoting unnoticeability. arXiv preprint arXiv:2202.08057. Chen, Z.; Wang, Y.; Jiao, P.; Wu, K.; Wang, X.; Ao, X.; and Zhang, D. 2026. Can LLMs Fool Graph Learning? Exploring Universal Adversarial Attacks on Text-Attributed Graphs. In Proceedings of the ACM Web Conference 2026. Dai, E.; Zhao, T.; Zhu, H.; Xu, J.; Guo, Z.; Liu, H.; Tang, J.; and Wang, S. 2024. A comprehensive survey on trustworthy graph neural networks: Privacy, robustness, fairness, and explainability. Machine Intelligence Research, 21(6): 1011–1061. Fan, B.; Guo, Z.; Li, X.; Zhou, Y.; Zhou, B.; Li, Z.; Li, R.-H.; and Wang, G. 2026. Unveiling the Vulnerability of Graph-LLMs: An Interpretable Multi-Dimensional Adversarial Attack on TAGs. In Proceedings of the ACM Web Conference 2026. Fan, L.; Li, Q.; Liu, B.; Wu, X.-M.; Zhang, X.; Lv, F.; Lin, G.; Li, S.; Jin, T.; and Yang, K. 2022. Modeling user behavior with graph convolution for personalized product search. In Proceedings of the ACM Web Conference 2022. Gao, Y.; Li, R.; Croxford, E.; Caskey, J.; Patterson, B. W.; Churpek, M.; Miller, T.; Dligach, D.; and Afshar, M. 2025. Leveraging medical knowledge graphs into large language models for diagnosis prediction: Design and application study. Jmir Ai, 4: e58670. Geisler, S.; Schmidt, T.; Şirin, H.; Zügner, D.; Bojchevski, A.; and Günnemann, S. 2021. Robustness of graph neural networks at scale. Advances in Neural Information Processing Systems, 34: 7637–7649. Hu, W.; Fey, M.; Zitnik, M.; Dong, Y.; Ren, H.; Liu, B.; Catasta, M.; and Leskovec, J. 2020. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33: 22118–22133. Ju, M.; Fan, Y.; Zhang, C.; and Ye, Y. 2023. Let graph be the go board: gradient-free node injection attack for graph neural networks via reinforcement learning. In Proceedings of the AAAI conference on artificial intelligence. Lei, R.; Hu, Y.; Ren, Y.; and Wei, Z. 2024. Intruding with words: Towards understanding graph injection attacks at the text level. Advances in Neural Information Processing Systems, 37: 49214–49251. Li, J.; Xie, T.; Chen, L.; Xie, F.; He, X.; and Zheng, Z. 2021. Adversarial attack on large scale graph. IEEE Transactions on Knowledge and Data Engineering, 35(1): 82–95. Lyu, Y.; Li, C.; Zhang, X.; and Zhang, T. 2025. Navigating the Black Box: Leveraging LLMs for Effective Text-Level Graph Injection Attacks. arXiv preprint arXiv:2506.13276. Ma, J.; Trivedi, P.; and Koutra, D. 2026. GRAPHTEXTACK: A Realistic Black-Box Node Injection Attack on LLM-Enhanced GNNs. In Proceedings of the AAAI Conference on Artificial Intelligence.

McCallum, A. K.; Nigam, K.; Rennie, J.; and Seymore, K. 2000. Automating the construction of internet portals with machine learning. Information Retrieval, 3(2): 127–163. Sen, P.; Namata, G.; Bilgic, M.; Getoor, L.; Gallagher, B.; and Eliassi-Rad, T. 2008. Collective classification in network data. AI magazine, 29(3): 93–106. Sun, Y.; Wang, S.; Tang, X.; Hsieh, T.-Y.; and Honavar, V. 2020. Adversarial attacks on graph neural networks via node injections: A hierarchical reinforcement learning approach. In Proceedings of the web conference 2020. Tang, J.; Yang, Y.; Wei, W.; Shi, L.; Su, L.; Cheng, S.; Yin, D.; and Huang, C. 2024. Graphgpt: Graph instruction tuning for large language models. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval. Wang, D.; Zuo, Y.; Li, F.; and Wu, J. 2024. Llms as zero-shot graph learners: Alignment of gnn representations with llm token embeddings. Advances in neural information processing systems, 37: 5950–5973. Xu, J.; Sun, Y.; Jiang, X.; Wang, Y.; Wang, C.; Lu, J.; and Yang, Y. 2022. Blindfolded attackers still threatening: Strict black-box adversarial attacks on graphs. In Proceedings of the AAAI Conference on Artificial Intelligence. Ying, Y.; Jiang, W.; Zheng, T.; Wang, Y.; Liu, S.; Chen, K.; and Song, M. 2026. GraphScout: Empowering Large Language Models with Intrinsic Exploration Ability for Agentic Graph Reasoning. arXiv preprint arXiv:2603.01410. Zhang, Q.; Sheng, X.; Sun, Y.; and Tan, Q. 2025. Trustglm: Evaluating the robustness of graphllms against prompt, text, and structure attacks. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2. Zhang, Z.; Wang, X.; Zhang, M.; Tan, J.; and Shi, C. 2026. Toward graph-tokenizing large language models with reconstructive graph instruction tuning. In Proceedings of the ACM Web Conference 2026. Zhao, M.; and Zhang, J. 2025. Highly imperceptible blackbox graph injection attacks with reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence. Zhong, L.; Wu, J.; Li, Q.; Peng, H.; and Wu, X. 2023. A comprehensive survey on automatic knowledge graph construction. ACM Computing Surveys, 56(4): 1–62. Zou, X.; Zheng, Q.; Dong, Y.; Guan, X.; Kharlamov, E.; Lu, J.; and Tang, J. 2021. Tdgia: Effective injection attacks on graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. Zügner, D.; Akbarnejad, A.; and Günnemann, S. 2018. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining. Zügner, D.; and Günnemann, S. 2019. Adversarial Attacks on Graph Neural Networks via Meta Learning. In International Conference on Learning Representations (ICLR).

Related documents

• CVE-2026-107376 — HIGH 8.2#1267612
• Breaking and Defending LLM-Powered Social Media Bot Detection Systems#617022
• Breaking and Defending LLM-Powered Social Media Bot Detection Systems#616522
• Artificial Intelligence-Powered Cyber Attacks: Adversarial Machine Learning#178253
• HASTE: Evolving Agent Harnesses Against Emerging Attacks Using Sparse Evidence#1187598