Paper deep dive

Can LLMs Fool Graph Learning? Exploring Universal Adversarial Attacks on Text-Attributed Graphs

Zihui Chen, Yuling Wang, Pengfei Jiao, Kai Wu, Xiao Wang, Xiang Ao, Dalin Zhang

Year: 2026Venue: arXiv preprintArea: cs.AIType: PreprintEmbeddings: 72

Intelligence

Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 97%

Last extracted: 3/26/2026, 2:24:13 AM

Summary

The paper introduces BadGraph, a novel universal adversarial attack framework for Text-Attributed Graphs (TAGs). BadGraph leverages Large Language Models (LLMs) to perform black-box, cross-modal perturbations on both node topology and textual semantics. By using a target influencer retrieval module to identify semantically distant nodes, the framework constructs adversarial shortcuts that generalize across both GNN-based and LLM-based reasoners, achieving significant performance drops while maintaining stealth.

Entities (5)

BadGraph · adversarial-attack-framework · 100%Graph Neural Networks · model-architecture · 100%Large Language Models · technology · 100%Text-Attributed Graphs · data-structure · 100%Target Influencer Retrieval · module · 95%

Relation Signals (3)

BadGraph → targets → Text-Attributed Graphs

confidence 100% · we propose BadGraph, a novel universal adversarial attack on TAG models

BadGraph → utilizes → Large Language Models

confidence 100% · BadGraph, a novel LLM-powered TAG attacker that efficiently leverages the adversarial capabilities of LLMs

Target Influencer Retrieval → optimizes → BadGraph

confidence 90% · By concentrating LLM reasoning on a small, high-quality subset, our retrieval-first design drastically reduces query cost

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Text-attributed graphs (TAGs) enhance graph learning by integrating rich textual semantics and topological context for each node. While boosting expressiveness, they also expose new vulnerabilities in graph learning through text-based adversarial surfaces. Recent advances leverage diverse backbones, such as graph neural networks (GNNs) and pre-trained language models (PLMs), to capture both structural and textual information in TAGs. This diversity raises a key question: How can we design universal adversarial attacks that generalize across architectures to assess the security of TAG models? The challenge arises from the stark contrast in how different backbones-GNNs and PLMs-perceive and encode graph patterns, coupled with the fact that many PLMs are only accessible via APIs, limiting attacks to black-box settings. To address this, we propose BadGraph, a novel attack framework that deeply elicits large language models (LLMs) understanding of general graph knowledge to jointly perturb both node topology and textual semantics. Specifically, we design a target influencer retrieval module that leverages graph priors to construct cross-modally aligned attack shortcuts, thereby enabling efficient LLM-based perturbation reasoning. Experiments show that BadGraph achieves universal and effective attacks across GNN- and LLM-based reasoners, with up to a 76.3% performance drop, while theoretical and empirical analyses confirm its stealthy yet interpretable nature.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

71,295 characters extracted from source content.

Expand or collapse full text

by Can LLMs Fool Graph Learning? Exploring Universal Adversarial Attacks on Text-Attributed Graphs Zihui Chen 231270002@hdu.edu.cn , Yuling Wang wangyl0612@hdu.edu.cn School of Cyberspace, Hangzhou Dianzi UniversityHangzhouChina , Pengfei Jiao School of Cyberspace, Hangzhou Dianzi University HangzhouChina pjiao@hdu.edu.cn , Kai Wu Hangzhou Dianzi University HangzhouChina wukai@hdu.edu.cn , Xiao Wang Beihang UniversityBeijingChina xiao_wang@buaa.edu.cn , Xiang Ao Institute of Computing Technology, Chinese Academy of SciencesBeijingChina aoxiang@ict.ac.cn and Dalin Zhang Hangzhou Dianzi UniversityHangzhouChina dalinz@cs.aau.dk (2026) Abstract. Text-attributed graphs (TAGs) enhance graph learning by integrating rich textual semantics and topological context for each node. While boosting expressiveness, they also expose new vulnerabilities in graph learning through text-based adversarial surfaces. Recent advances leverage diverse backbones, such as graph neural networks (GNNs) and pre-trained language models (PLMs), to capture both structural and textual information in TAGs. This diversity raises a key question: How can we design universal adversarial attacks that generalize across architectures to assess the security of TAG models? The challenge arises from the stark contrast in how different backbones—GNNs and PLMs—perceive and encode graph patterns, coupled with the fact that many PLMs are only accessible via APIs, limiting attacks to black-box settings. To address this, we propose BadGraph, a novel attack framework that deeply elicits large language models’ (LLMs) understanding of general graph knowledge to jointly perturb both node topology and textual semantics. Specifically, we design a target influencer retrieval module that leverages graph priors to construct cross-modally aligned attack shortcuts, thereby enabling efficient LLM-based perturbation reasoning. Experiments show that BadGraph achieves universal and effective attacks across GNN- and LLM-based reasoners, with up to a 76.3% performance drop, while theoretical and empirical analyses confirm its stealthy yet interpretable nature. Graph Machine Learning, Text-Attributed Graph Attacks †journalyear: 2026†copyright: c†conference: Proceedings of the ACM Web Conference 2026; April 13–17, 2026; Dubai, United Arab Emirates†booktitle: Proceedings of the ACM Web Conference 2026 (W ’26), April 13–17, 2026, Dubai, United Arab Emirates†doi: 10.1145/X.X†isbn: 979-8-4007-2307-0/2026/04†ccs: Computing methodologies Machine learning approaches 1. Introduction Graph representation learning has emerged as a powerful paradigm for modeling intricate relationships among entities in complex real-world systems, such as knowledge graphs (Sanmartin, 2024) and biological networks (Ma et al., 2023). Building on this, text-attributed graphs (TAGs) enhance each node with descriptive textual information, seamlessly integrating structural and semantic features (Yan et al., 2023). This fusion significantly boosts the expressive power of graph representations, enabling more detailed understanding and analysis. Consequently, research on TAGs has gained strong momentum across diverse fields, including graph neural networks (GNNs) (Zhu et al., 2025), natural language processing (Guo et al., 2025; Zhang et al., 2021a), and recommender systems (Li et al., 2025; Zhang et al., 2021b; Wang et al., 2024c). Bridging topological and textual knowledge through effective alignment and fusion is essential for learning on TAGs (Liu et al., 2025a). Broadly, existing efforts fall into two main paradigms: (1) GNN as a reasoner. In this paradigm, node-associated texts are first encoded into feature using language models, and then propagated through the graph topology via GNN message-passing. The quality of text encoding is crucial. As a result, research has shifted from shallow methods like TF-IDF (Kipf and Welling, 2016) to powerful large language models (LLMs) such as OFA (Liu et al., 2023) and TAPE (He et al., 2024). (2) LLM as a reasoner. This paradigm reformats graph data into a format that LLMs can understand, then either prompts frozen LLMs (Chen et al., 2024b) or retrains graph-specific tokenizers (Chen et al., 2024a). The key lies in how to describe TAGs to effectively elicit LLMs’ general knowledge and reasoning abilities for graph-related tasks. Despite their success, TAGs introduce new vulnerabilities through the textual modality, exposing novel adversarial attack surfaces. Given the diverse backbones used for TAGs, there is an urgent need for universal, well-crafted adversarial attacks to expose vulnerabilities and mitigate potential misuse. Existing graph attackers typically perturb edges or node features under constrained budgets (Wang et al., 2024b; Shang et al., 2023), but struggle to adapt to TAG models due to their inability to interpret and manipulate textual information. This aligns with recent findings that graph attackers are less effective in LLM-driven graph learning (Guo et al., 2024; Zhang et al., 2024). Furthermore, embedding-based attacks are often impractical and hard to interpret. While recent efforts explore node injection attacks at the textual level (Lei et al., 2024), their effectiveness still falls short compared to traditional embedding-space attacks. To address this gap, we ask: How can we design universal adversarial attacks that generalize across architectures to effectively evaluate the security of TAG models? Despite its potential, achieving this goal remains challenging. First, uncovering universal vulnerability patterns across both topological and textual modalities is difficult. The complex interactions between these modalities, along with the diverse ways various backbone architectures encode TAG patterns, make it challenging to identify common weaknesses. Second, the unknown architecture and parameters of target models often force attackers to operate in the more restrictive black-box setting. This is especially true for commercial LLMs deployed via APIs without internal access, where gradient-based optimization is not feasible. As a result, these constraints hinder the identification of intrinsic vulnerabilities. Recent advances show that LLMs can act as effective adversarial agents in various domains, including fake news generation (Sun et al., 2024) and recommender system (Ning et al., 2024), thanks to their ability to generate contextually relevant yet misleading content. These successes motivate us to explore LLMs as powerful attackers in graph learning. In this paper, we propose BadGraph, a novel universal adversarial attack on TAG models that harnesses the deep graph reasoning capabilities of LLMs to disrupt the core semantics of TAG. Specifically, we design a target influencer retrieval module to identify semantically dissimilar candidates, enabling the creation of a shortcut between the target node and the intended misleading label—even in black-box settings without access to internal gradients. Subsequently, to enable a universal TAG attack, we elicit the LLM’s deep understanding of graph patterns to jointly guide topological and textual perturbations. Notably, our retrieval module facilitates LLM-based edge perturbation in a highly resource-efficient manner. The attacked TAG can be applied to any target graph learning backbone, including both GNN-based and LLM-based reasoners. Our key contributions can be summarized as follows: • To the best of our knowledge, this is the first universal TAG adversarial attack that generalizes across diverse graph learning models. Our findings reveal that the growing use of TAGs brings new security risks, highlighting the need for a comprehensive evaluation of model robustness. • We propose BadGraph, a novel LLM-powered TAG attacker that efficiently leverages the adversarial capabilities of LLMs across both topological and textual modalities. • Extensive experiments across diverse TAG backbones demonstrate that BadGraph is both effective and generalizable. Moreover, the proposed Cross-Modal Shortcut Theory offers theoretical insight into its stealthiness and efficacy. 2. Related Work 2.1. Graph Adversarial Attacks Identifying potential vulnerabilities and enhancing the security of GNNs are essential for developing trustworthy graph learning systems (Zhang et al., 2022). Existing GNN attacks can be broadly classified into two categories: test-time evasion attacks and training-time poisoning attacks. Evasion attacks manipulate the graph structure or node features at inference time to mislead model predictions (Zügner et al., 2018; Ma et al., 2020; Wang et al., 2022, 2023, 2024a). For example, Nettack proposes a greedy-based edge perturbation strategy (Zügner et al., 2018), while (Li et al., 2024) extends black-box evasion attacks to the explainability setting. In contrast, poisoning attacks perturb the graph during training to embed backdoors or degrade model robustness (Wang and Gong, 2019; Zhang et al., 2021c; Wang et al., 2023; Dai et al., 2024; Liu et al., 2025b; Alom et al., 2025). SBAC injects semantic trigger nodes to generate poisoned samples (Dai et al., 2024), whereas EPD quantifies perturbation importance and distinguishes benign augmentation from adversarial manipulation (Liu et al., 2025b). GOttack reveals the weaknesses of existing defenses by efficiently compromising GNNs through orbit-based structural manipulations (Alom et al., 2025). However, existing works overlook the emerging text-based attack interfaces in the LLM era, which are crucial for preventing misuse of TAGs in realistic settings. 2.2. LLM-Generated Attacks The utilization of LLMs (Ao et al., 2025; Wang et al., 2024c), with their human-like understanding and ability to generate contextually relevant yet misleading content, introduces new capabilities in adversarial attack generation (Sun et al., 2024; Ning et al., 2024). Understanding these new attacks is key to finding AI vulnerabilities and improving their security (Qi et al., ). For example, PromptAttack shows that carefully crafted adversarial prompts can induce a target LLM to produce harmful outputs that deceive itself (Xu et al., 2023). Similarly, PAIR leverages an attacker LLM to iteratively generate jailbreak prompts for a separate target LLM without human intervention (Chao et al., 2023). Attack-in-the-Chain uses chain-of-thought prompting to craft attacks against neural ranking models (Liu et al., 2025c). CheatAgent leverages an LLM agent to generate targeted adversarial perturbations for attacking recommender systems (Ning et al., 2024). Recently, WTGIA explores text-level injection attacks in the graph domain and finds that their effectiveness decreases as text interpretability increases, making them less effective than embedding-based attacks (Lei et al., 2024). This highlights the need for further research on the potential LLM-based attacks in graph learning. 3. Background and Preliminaries Text-attributed Graphs. A TAG is defined as =(V,E,S)G=(V,E,S), where V is the set of nodes, E is the set of edges, and S denotes node-level textual information. The adjacency matrix of the graph G is denoted as A∈ℝ|V|×|V|A ^|V|×|V|, where Aij=1A_ij=1 if nodes viv_i and vjv_j are connected, otherwise Aij=0A_ij=0. In this work, we focus on the node classification task on TAGs. Specifically, each node viv_i corresponds to a label yiy_i that indicates which category the node viv_i belongs to. When attacking GNNs serving as reasoners, we encode the text S into the node feature matrix X=x1,…,x|V|X=\x_1,…,x_|V|\ using various encoding techniques to train the target GNNs, where xi∈ℝdx_i ^d. Attacker’s Knowledge and Capability. We study a black-box evasion setting, i.e., the attacker has no access to model architectures, parameters, training procedures, or text encoders, and is limited to test-time, architecture-agnostic universal attacks on TAGs. Attacker’s Goal. The attacker’s objective is to generate a perturbed graph ′=(A′,S′)G =(A ,S ) by modifying the adjacency A and node text S under a limited budget (e.g., ‖′−‖≤Δ\|G -G\|≤ ), so that the target model outputs a predefined incorrect label Y′Y . We focus on the challenging setting of universal, black-box attacks, where the adversarial graph ′G is required to transfer across heterogeneous backbones with substantial differences in architecture and inference, including (1) a GNN reasoner fθ(k)GNN(A,S)f^GNN_θ^(k)(A,S) and (2) an LLM reasoner fθ(k)LLM(t(A,S))f^LLM_θ^(k)\! (T_t(A,S) ), with θ(k)θ^(k) denoting the k-th model instance and tT_t a task-specific prompt. Formally, given ′=(A′,S′)G =(A ,S ), the attacker enforces: (1) fθ(k)m(A′,S′)→Y′,m∈GNN,LLM, f^m_θ^(k)(A ,S )\;→\;Y , m∈\GNN,LLM\, s.t. ‖A′−A‖0≤bA,‖S′−S‖0≤bS, .t. \|A -A\|_0≤ b_A,\;\;\|S -S\|_0≤ b_S, where bAb_A and bSb_S bound the maximum number of structural and textual edits, respectively. Figure 1. An overview of the proposed BadGraph framework. 4. Proposed Framework In this paper, we propose BadGraph, a novel LLM-driven adversarial attack tailored for TAGs. BadGraph progressively guides an LLM to discover transferable perturbations over topology and text. The retrieval-then-reasoning pipeline is illustrated in Figure 1. 4.1. Graph-Aware Target Influencer Retrieval To leverage LLM-based graph reasoning for constructing a perturbed graph ′=(A′,S′)G =(A ,S ), such that the target graph learning model fθ(k)m(A′,S′)f^m_θ^(k)(A ,S ) is misled to produce a predefined incorrect label Y′Y . The main challenges are twofold: (1) efficiency under black-box constraints—without gradient access, topology-based attacks (e.g., fake edge additions) necessitate querying all node pairs via the LLM, leading to an (V2)O(V^2) query cost; and (2) the absence of graph priors, which hinders the LLM from deriving reliable attack cues and accurately localizing effective perturbation regions. To overcome these challenges, we introduce a Target Influencer Retrieval module that narrows the search space to a compact set of influencer nodes, thereby avoiding exhaustive pairwise prompting. The retrieved nodes act as graph-aware priors, supplying explicit shortcut paths to the incorrect label. Formally, we denote the influencer of a target node viv_i as viinfluencerv_i^influencer, whose label yviinfluencery_v_i^influencer can misdirect the target model’s prediction on viv_i. We then encode the input graph G into node embeddings Z∈ℝ||×dZ ^|V|× d : (2) Z=GraphEncoder⁡(A,X),Z=GraphEncoder(A,X), where Z serves as a model-agnostic influencer database for retrieval. The graph encoder can be instantiated with any lightweight or expressive GNN (e.g., GCN, GAT); empirically, more expressive encoders lead to stronger and more transferable perturbations. For each target node viv_i with embedding ziz_i, we retrieve a compact candidate influencer set ℐviI_v_i that are semantically distant from viv_i. Let dcos(zi,zv)d_ (z_i,z_v) denote cosine-based dissimilarity; the retriever selects the top-K nodes with the largest dissimilarity to viv_i: (3) ℐvi=Retriever⁡(dcos(zi,zv)v∈∖vi,K),I_v_i\;=\;Retriever (\d_ (z_i,z_v)\_v \v_i\,\,K ), where ℐviI_v_i forms the candidate pool for subsequent LLM-driven adversarial perturbations. By concentrating LLM reasoning on a small, high-quality subset, our retrieval-first design drastically reduces query cost and injects graph-aware attack priors. 4.2. LLM-Driven Cross-Modal TAG Perturbation LLMs have recently exhibited a surprising degree of graph reasoning intelligence. Building on this insight, we investigate how such emergent reasoning can be harnessed to mount adversarial attacks on TAGs. A central challenge remains: the dual nature of TAGs requires that topological and textual edits be tightly aligned; directional misalignment substantially undermines attack effectiveness. To ensure cross-modal coherence, for each target node viv_i with retrieved influencers ℐviI_v_i, we jointly generate anchor-based topological and textual perturbations, forming aligned shortcuts that steer the model toward the target misleading label. 4.2.1. Universal Topology-Aware Perturbations Topology manipulation is central to constructing adversarial shortcuts on TAGs. Here, the LLM is prompted to produce budget-constrained structural perturbations—edge removals and additions—guided by the retrieved influencers. These topology-aware edits jointly reshape the local connectivity of the target node. Eliciting Graph Knowledge. We first prompt the LLM to extract graph-relevant cues from limited prior information, thereby eliciting the LLM’s implicit knowledge of graph patterns. Specifically, for each target node viv_i, we construct a structured prompt that directs the LLM to reason over its local adjacency viN_v_i and node text Si(1)S_i^(1): (4) ℛi=graph(vi,vi,Si(1)),R_i=T_graph\! (v_i,\,N_v_i,\,S_i^(1) ), where graph(⋅)T_graph(·) instructs the LLM to infer relational cues between viv_i and its neighbors, yielding a reasoning summary ℛiR_i that serves as the foundation for subsequent perturbation generation. Step 1: Analyze the target node and its neighboring set. Summarize why the nodes in the neighboring set are adjacent to the target node. Be sure to highlight the most prominent factors that guide their strong correlation. Edge Deletion Guidance. Building upon the structural understanding elicited in the Step 1, we guide the LLM to identify and attack a critical edge of a target node viv_i via stepwise reasoning. Formally, given the 1-hop neighborhood viN_v_i, the LLM performs a stepwise reasoning process to select the most semantically relevant neighbor as the deletion target: (5) videl=arg⁡maxv∈vi⁡LLMrel(vi,v).v_i^del= _v _v_iLLM_rel(v_i,v). The removal of edge (vi,videl)(v_i,v_i^del) reduces the local structural reinforcement for viv_i and weakens the evidence supporting its original label. Step 2: From the neighboring set, choose the node that is most relevant to the target node. Let’s break it down step by step to ensure we accurately evaluate the correlation. Edge Insertion Guidance. To further distort the neighborhood structure, we leverage the retrieved influencer candidates ℐviI_v_i as potential targets for edge addition; this retrieval set provides principled attack evidence—its semantic gap to viv_i. The LLM analyzes the semantic relationships within ℐviI_v_i and selects the least semantically related node as the addition target: (6) viadd=arg⁡minv∈ℐvi⁡LLMrel(vi,v).v_i^add= _v _v_iLLM_rel(v_i,v). Adding the edge (vi,viadd)(v_i,v_i^add) introduces a misleading connection to a semantically distant node, constructing an adversarial shortcut that biases the model toward the influencer’s label. This process reduces the edge prediction complexity from (N2)O(N^2) to (N)O(N), as the LLM focuses reasoning on a compact influencer set. Step 3: Based on the inferred prominent factors from Step 1, exclude the node from the following Candidate List that is least related to the target node and analyze why. Unified Formulation. The resulting topology perturbation for node viv_i can thus be represented as: (7) ΔAi=(vi,viadd)∪(vi,videl),‖ΔAi‖0≤bAi, A_i= \(v_i,v_i^add) \∪ \(v_i,v_i^del) \, \| A_i\|_0≤ b_A_i, where bAib_A_i is the topology perturbation budget. This unified formulation allows the LLM to perform topology attacks within a consistent reasoning framework, yielding universal and transferable topology-aware perturbations. Empirically, we set bAi=2b_A_i=2, corresponding to one edge addition and one edge deletion per target node. 4.2.2. Universal Text-Aware Perturbations LLMs have proven effective at crafting adversarial text in NLP. Inspired by this, we harness LLMs’ human-like understanding of semantics and graph context to generate targeted textual perturbations for TAGs, providing a principled, text-centric adversarial interface. The main challenge is to induce model misclassification with minimal, stealthy edits: textual changes must be small yet directionally consistent with topology edits so as to form coherent cross-modal shortcuts. Influencer Analysis Guidance. To maintain cross-modal consistency, we follow the same influencer viaddv_i^add selected in the structural attack (Eq. (6)) as the textual perturbation source, steering each target node viv_i toward the class of its influencer yviaddy_v_i^add. Formally, the LLM is prompted to extract a representative keyword from the influencer node viaddv_i^add: (8) kvi=LLMkey(viadd,Sviadd),k_v_i=LLM_key\! (v_i^add,\,S_v_i^add ), where kvik_v_i denotes the category-indicative keyword extracted from the influencer’s text SviaddS_v_i^add, which serves as a semantic anchor for subsequent textual perturbations on viv_i. Step 1: Given the target node titled viaddv^add_i, identify one keyword that reflects its category. Text Modification Guidance. Building on the extracted influencer keyword kvik_v_i, we prompt the LLM to subtly revise the target node’s text so that it aligns with the influencer’s category yviaddy_v_i^add. To ensure both stealth and cross-modal coherence, two constraints are imposed: (1) retain partial lexical content to preserve linguistic fluency and adversarial stealth; and (2) integrate the influencer keyword kvik_v_i form Eq. (9), ensuring directional semantic drift toward yviaddy_v_i^add. Formally, the adversarially modified text is generated as: (9) Si′=LLMtext(Si,kvi),s.t. ‖Si′−Si‖0≤bSi,S_i =LLM_text\! (S_i,\,k_v_i ), .t. \|S_i -S_i\|_0≤ b_S_i, where SiS_i denotes the textual perturbation budget. This formulation allows the LLM to synthesize minimal yet semantically effective text edits, achieving coherent alignment between structural and textual perturbations under strict black-box constraints. Step 2: Given the paper P1 titled SiS_i, your task is to generate a new paper by modifying P1 title so that it meets the following requirements: 1. It must retain some of the original words from the P1 title. 2. It should include the keyword identified in Step 1 and be aligned with the target node category determined in Step 1. Departing from gradient-driven or retraining-based attacks, BadGraph unifies structural and textual attacks within a LLM reasoning pipeline. It achieves directionally aligned and transferable attacks at low cost, requiring only two LLM queries per target node. 5. Theoretical Foundations of BadGraph. A key question arises regarding the stealthiness of BadGraph: how can it remain effective while inducing only minimal disruption? To resolve this paradox, we establish a unified theoretical framework with two complementary components: (1) a homophily-preserving bound, explaining why BadGraph maintains stealthiness under sparse perturbations; and (2) a cross-modal shortcut theory, revealing how such subtle perturbations achieve strong attack efficacy. 5.1. Homophily-Preserving Bound The adversary jointly perturbs topology and text to maximize the probability of misclassification: (10) max‖A′−A‖0≤bA,‖S′−S‖0≤bS⁡ℙ(Y′∣A′,S′;fθ(k)m). _\|A -A\|_0≤ b_A,\;\|S -S\|_0≤ b_SP\! (Y A ,S ;f^m_θ^(k) ). Let xi=Φ(Si)x_i= (S_i) denote the textual embedding, where we assume that the encoder Φ is LΦL_ -Lipschitz continuous. A bounded textual perturbation ‖S′−S‖0≤bSi\|S -S\|_0≤ b_S_i thus induces a semantic deviation ‖xi′−xi‖2≤LΦτ(bSi)\|x_i -x_i\|_2≤ L_ τ(b_S_i), where τ(bSi)τ(b_S_i) quantifies the embedding drift. Similarly, the relative edge perturbation ratio is ΔE=‖A′−A‖0/|E|≪1 _E=\|A -A\|_0/|E| 1 . Then, following the node-centric definition of homophily (Chen et al., 2022), the change in global homophily satisfies: (11) |H(G′)−H(G)|≤C1ΔE+C2LΦτ(bS),|H(G )-H(G)|≤ C_1 _E+C_2L_ τ(b_S), where C1,C2>0C_1,C_2>0 depend on graph smoothness and the continuity of the similarity metric. Because both ΔE _E and τ(bS)τ(b_S) remain small under BadGraph’s budget-constrained and semantically aligned perturbations, the resulting global homophily variation is provably bounded—offering a formal guarantee of stealthiness. In section 6.3.1(Observation 2) further corroborate this homophily stability. 5.2. Cross-Modal Shortcut Theory Although the joint optimization (Ai′⁣∗,Si′⁣∗)(A_i *,S_i *) is intractable under black-box constraints, a capable LLM can implicitly approximate this reasoning objective: (12) (Ai′⁣∗,Si′⁣∗)≈LLM⁡(vi,vi,Si(1),ℐvi),(A_i *,S_i *) \! (v_i,\,N_v_i,\,S_i^(1),\,I_v_i ), yielding two coordinated perturbations: • a structural shortcut δA _A that connects the target node viv_i to its influencer viaddv_i^add, and • a textual shortcut δS _S that semantically aligns SiS_i toward SviaddS_v_i^add, both coherently anchored on the same influencer node viaddv_i^add. This alignment induces a directional shift in the latent space: z(vi′)≈z(viadd)⇒f(z(vi′))→yviadd,z(v_i )≈ z(v_i^add) f\! (z(v_i ) )→ y_v_i^add, where z(⋅)z(·) is the TAG encoder. By anchoring both modalities to the same influencer and label yviaddy_v_i^add, LLM-guided reasoning enforces cross-modal coherence, allowing the structural and textual shortcuts to reinforce each other and form a unified adversarial pathway. Consequently, the joint perturbation exhibits a synergistic effect: (13) Δjoint≈ΔδA,δS>ΔδA+ΔδS, _joint≈ _ _A, _S> _ _A+ _ _S, This indicates that aligned cross-modal perturbations substantially outperform isolated attacks. As shown in Table 4 (Anchor Mis), disrupting this alignment sharply lowers success rates, underscoring the importance of cross-modal coherence for effective transfer. 6. Experiments 6.1. Experimental Settings 6.1.1. Datasets. We conduct extensive experiments on three TAG datasets: Cora (McCallum et al., 2000), OGBN-Products, and OGBN-Arxiv (Hu et al., 2020). More details and statistics of the dataset can be found in Appendix A.1. 6.1.2. Target Backbones. We evaluate BadGraph across two backbone paradigms. (1) GNN Reasoners. Node texts are first encoded, then processed by GNNs (Kipf and Welling, 2016; Xu et al., 2018; Hamilton et al., 2017; Du et al., 2017), and the robust R-GCN (Zhu et al., 2019). (2) LLM Reasoners. Following (Chen et al., 2024b), LLMs are used for zero-shot node classification (Jiang et al., 2024; Lu et al., 2024), with details in Appendix A.2. 6.1.3. Baselines. We compare BadGraph against seven representative graph attack baselines: RND, FLIP (Bojchevski and Günnemann, 2019), STACK (Xu et al., 2012), PGD (Madry et al., 2018), NETTACK (Zügner et al., 2018), SGAttack (Li et al., 2023), and WTGIA (Lei et al., 2024). For comparison, we assume that the attacker has no knowledge of embedding technology. Additional details are provided in Appendix A.3. 6.1.4. Evaluation Metrics. Following (Zheng et al., 2021), we report Accuracy as the primary metric, along with 3-Max Accuracy—the average performance against the three most robust defenses—and Weighted Accuracy, which weights results by defense robustness. All results are averaged over five random seeds. Table 1. GNN-as-Reasoner Scenarios. Attack performance on three datasets across various target GNNs. Lower scores indicate stronger attacks. "Clean" denotes unperturbed graphs; Our-text and Our-struct correspond to text-only and structure-only variants. Best results are in bold. Dataset Emb. Models Clean STACK PGD RND FLIP SGAttack WTGIA Our-text Our-struct BadGraph Cora TF-IDF R-GCN 86.67 82.37 78.07 73.93 73.11 85.41 86.22 84.44 79.11 70.89 GIN 85.93 72.37 78.30 72.59 72.89 81.04 85.70 84.44 76.96 63.04 GraphSAGE 84.96 72.30 77.41 74.81 74.74 73.70 83.19 73.93 76.37 54.67 TAGCN 87.33 75.33 80.22 75.04 75.85 87.33 87.56 85.48 83.41 73.93 GCN 85.48 73.78 77.70 74.89 74.44 83.63 83.85 84.15 78.67 71.33 SBERT R-GCN 87.33 76.37 80.30 76.00 75.93 86.30 85.93 80.30 79.11 56.67 GIN 85.70 73.85 80.15 75.33 75.93 81.04 84.96 77.70 76.00 47.04 GraphSAGE 86.00 75.93 79.48 76.00 77.56 72.44 83.33 64.30 70.15 39.93 TAGCN 88.22 78.00 80.81 76.74 75.85 88.74 87.93 79.04 83.26 51.19 GCN 87.11 77.63 80.59 79.04 77.33 86.37 86.30 80.15 78.07 56.00 TAPE R-GCN 89.63 82.96 84.15 83.33 86.52 87.85 - 86.30 84.07 72.89 GIN 88.52 80.96 84.22 81.70 84.22 84.22 - 83.11 82.96 65.56 GraphSAGE 87.85 81.26 83.41 82.81 85.19 74.00 - 82.81 75.63 48.89 TAGCN 88.07 81.19 84.37 83.04 82.52 87.85 - 84.96 82.67 69.56 GCN 89.70 83.19 83.56 83.19 85.33 87.11 - 85.93 80.89 69.93 Arxiv TF-IDF R-GCN 67.98 65.78 62.50 61.34 60.08 - 61.30 67.46 59.42 56.56 GIN 63.14 58.76 58.16 57.82 56.24 - 48.82 59.20 51.26 41.16 GraphSAGE 61.34 56.58 55.86 55.84 54.02 - 59.44 47.32 52.90 34.90 TAGCN 68.56 63.90 64.32 63.34 62.40 - 63.24 64.92 65.66 59.02 GCN 65.40 65.58 61.02 60.88 58.57 - 64.82 64.46 61.32 58.56 SBERT R-GCN 67.90 67.08 63.48 65.00 62.70 - 61.22 67.56 60.94 58.94 GIN 69.04 66.78 64.98 65.38 63.40 - 63.36 66.96 56.82 44.26 GraphSAGE 70.00 67.42 66.92 65.66 64.80 - 64.28 62.14 66.32 47.58 TAGCN 70.30 68.30 66.90 67.32 65.58 - 69.82 65.88 68.00 60.28 GCN 67.02 68.28 63.80 63.34 62.72 67.86 66.58 62.72 59.30 TAPE R-GCN 70.00 75.82 66.96 69.44 68.18 - - 69.20 66.54 65.22 GIN 77.68 77.06 78.10 78.04 78.48 - - 56.42 63.62 25.22 GraphSAGE 80.82 80.44 79.84 79.90 80.12 - - 52.70 80.12 31.44 TAGCN 80.48 81.40 79.40 79.16 79.34 - - 64.42 79.80 58.62 GCN 70.24 77.92 69.36 70.58 69.86 - - 69.22 68.46 66.14 Products TF-IDF R-GCN 86.00 80.70 83.28 81.54 81.58 85.28 82.08 81.84 81.56 70.84 GIN 85.28 79.78 82.58 81.62 81.16 81.62 68.42 75.90 75.18 53.30 GraphSAGE 83.94 78.18 81.42 80.78 79.36 80.02 80.90 70.14 71.02 50.06 TAGCN 85.94 78.72 82.90 82.42 79.50 85.32 83.40 83.16 82.68 74.14 GCN 86.48 82.12 84.28 82.28 82.98 85.38 83.92 81.20 81.90 69.04 SBERT R-GCN 87.38 82.98 86.34 84.48 84.16 86.92 80.84 86.02 84.66 79.06 GIN 86.08 81.54 84.28 83.06 82.86 84.02 83.60 84.24 80.40 71.18 GraphSAGE 87.08 82.76 85.74 84.64 84.14 83.46 81.38 80.72 73.48 58.60 TAGCN 88.08 80.40 86.42 84.82 82.30 87.60 86.34 86.72 85.26 80.28 GCN 87.26 83.66 86.20 84.18 84.26 86.86 85.66 86.36 84.04 77.58 TAPE R-GCN 89.54 89.58 89.22 88.86 89.96 89.38 - 87.42 88.56 80.52 GIN 88.64 88.80 88.58 88.02 88.88 87.48 - 82.26 86.82 69.12 GraphSAGE 90.22 90.70 90.10 89.86 90.48 90.16 - 81.06 89.58 66.28 TAGCN 89.08 88.74 88.58 88.30 88.40 89.06 - 83.84 88.62 79.98 GCN 89.44 89.80 88.96 88.96 89.72 89.32 - 86.44 88.56 75.74 6.2. Overall Performance 6.2.1. Attack Success Across Backbone Models in GNN-as-Reasoner Scenarios. BadGraph framework is highly flexible and can be universally applied to attack any type of target TAG backbone. We first evaluate the performance of BadGraph in a black-box setting across various models in GNN-as-Reasoner scenarios. To this end, we explore three node feature encoding methods with different levels of expressiveness: TF-IDF, SBERT, and TAPE. The results are shown in Table 1, we have the following observations: (1) Compared to existing attack baselines, BadGraph achieves state-of-the-art (SOTA) performance across all target models and datasets. These findings further highlight the effectiveness and universality of BadGraph in attacking TAG models. Notably, our method results in an accuracy drop of nearly 40% on Cora, 52% on OGBN-Arxiv, and around 30% on OGBN-Products. This performance drop is mainly due to the powerful adversarial perturbations generated by our LLM, which leverage rich graph-related knowledge to pinpoint and exploit the most vulnerable structures and texts. (2) Surprisingly, we find that models with richer node features tend to exhibit greater robustness. While traditional structure-based attacks are generally effective against shallow features like TF-IDF, they have minimal impact on models leveraging more expressive textual representations such as SBERT and TAPE, on OGBN-Arxiv, some attacks even lead to accuracy improvements. This is because these models effectively capture the semantic information of TAGs, enabling accurate predictions even when the structural information is compromised. (3) Single-modality attacks, whether structural or textual, are ineffective—our text-only and structure-only variants confirm this through significantly reduced performance, consistent with our cross-modal shortcut theory. Table 2. LLM-as-Reasoner Scenarios. Attack performance across two LLM backbones on three TAG datasets. Dataset Models Clean STACK PGD RND FLIP SGAttack WTGIA Our-text Our-struct BadGraph Cora DeepSeek-V3 71.85 68.14 72.96 65.92 64.07 67.03 63.70 25.55 67.03 17.03 Mistral-7B 43.70 42.96 53.33 42.59 47.03 37.40 21.48 21.11 38.51 16.29 Arxiv DeepSeek-V3 64.60 60.80 60.60 61.20 58.70 - 60.10 44.30 55.55 22.90 Mistral-7B 9.30 7.70 8.90 9.20 9.00 - 7.60 4.90 4.70 2.90 Products DeepSeek-V3 77.10 75.90 75.00 76.50 75.60 75.80 74.10 60.20 75.20 55.80 Mistral-7B 12.20 9.50 10.00 9.70 8.30 12.20 9.10 8.60 12.80 7.80 6.2.2. Attack Success Across Backbone Models in LLM-as-Reasoner Scenarios. To develop a more generalizable model, we evaluate the performance of BadGraph in LLM-as-Reasoner scenarios, where the graph structure and textual attributes are converted into prompts understandable by the LLM, and the LLM makes predictions based on its reasoning capabilities. The results are presented in Table 2. Additionally, we observed several interesting findings: (1) BadGraph consistently demonstrates strong destructive power against two target LLMs across all datasets, indicating its effectiveness in undermining the LLMs’ ability to comprehend graph patterns. Specifically, on the Cora dataset under the same perturbation budget, BadGraph reduces DeepSeek’s prediction accuracy by 76.3%, whereas the best-performing baseline, WTGIA, results in only an 11.3% drop. This significant degradation stems from BadGraph’s ability to uncover the underlying principles of how LLMs interpret graph structures—and to precisely disrupt them. (2) LLM-as-Reasoner models tend to be more vulnerable to text-based attacks while exhibiting greater resilience to structural perturbations. For instance, a text-only attack using BadGraph reduces DeepSeek’s prediction accuracy by 64%, whereas a structure-only attack leads to just a 6.3% drop. This disparity arises because LLMs primarily rely on textual information to infer graph patterns—a stark contrast to the GNN-as-Reasoner setting, where models place greater emphasis on structural semantics. Overall, irrespective of the underlying backbone, jointly attacking both text and structure consistently achieves the most impactful results. (a) WTGIA (b) BadGraph Figure 2. Edge-level homophily shift on the Cora dataset. Table 3. Accuracy and homophily changes of deepSeek-as-Reasoner on Arxiv under varying perturbation ratios. #\#Nodes Perturb. Ratio Acc Avg. Homo. (edge) Avg. Homo. (node) 0 0 64.6% 0.8184 0.4257 500 0.09% 23.4% 0.8183 0.4292 1000 0.17% 22.9% 0.8182 0.4317 1500 0.26% 22.6% 0.8181 0.4316 6.3. Merits of BadGraph 6.3.1. Stealthy, Localized Attacks with Homophily Stability Observation 1. BadGraph maintains global homophily stability. We evaluate the imperceptibility of BadGraph using edge-centric homophily metrics (Chen et al., 2022). As shown in Fig. 2, WTGIA causes pronounced shifts in homophily distributions, making it easily detectable by homophily-based defenses. In contrast, BadGraph introduces only subtle and localized distributional changes, confirming its stealthy and unnoticeable nature. This stability stems from semantically aligned, anchor-guided perturbations that jointly adjust topology and text while preserving the global structural context. Observation 2. BadGraph achieves high attack effectiveness without disrupting overall graph properties. As presented in Table 3, even when the perturbation budget increases (500 → 1500 edges), node- and edge-level homophily remain nearly unchanged, whereas target node accuracy drops sharply. This demonstrates that BadGraph performs tightly localized “edge rewriting,” where each deletion is paired with an addition, maintaining structural balance while creating semantic shortcuts. Although a small fraction of semantically important edges may be modified (≤0.26%≤ 0.26\%), these edits are context-aware and minimally invasive, preserving the global homophily distribution. 6.3.2. Affordable Inference Cost and High Destructiveness. Observation 1. BadGraph achieves efficient and low-cost attack inference. The total computational cost includes (1) the influencer retrieval module and (2) LLM API queries. The retriever has a training complexity of (2KNd2)O(2KNd^2), where K is the number of attention heads, N the number of nodes, and d the feature dimension. Unlike conventional LLM-based edge prediction approaches that require (N)O(N) evaluations per target node, our retrieval-then-reasoning selection reduces the cost to (1)O(1). Moreover, BadGraph executes entirely through API calls on CPU, with an average query cost of approximately $0.0009 per node—demonstrating its practicality and scalability for real-world black-box attack scenarios. Observation 2. BadGraph delivers strong representational disruption despite its lightweight cost. As illustrated in Fig. 3, the T-SNE visualization reveals that BadGraph induces significantly greater boundary distortion and class entanglement than WTGIA, implying a deeper perturbation of the latent representation space. This indicates that even under minimal resource consumption, BadGraph can generate substantial embedding shifts—achieving a rare balance between efficiency and destructiveness. 6.3.3. Robustness to Prompt Design and LLM Variants Observation 1. BadGraph remains robust to prompt variations, while cross-modal shortcut alignment serves as the key attack guarantee. As shown in Table 4, we evaluate multiple prompt phrasings for generating perturbations (e.g., rewording “Summarize why [node] is adjacent to…” as “Explain the likely reason for its connection to…”). BadGraph maintains stable attack performance, with accuracy fluctuations within 3.7%, indicating low sensitivity to surface-level linguistic changes. However, replacing the shared influencer node between textual and structural attacks leads to a sharp performance drop (up to 22.66%), demonstrating that the attack’s effectiveness stems from semantic alignment across modalities rather than prompt wording itself. Observation 2. BadGraph generalizes across different attacker LLMs. We further test BadGraph with diverse open-source LLMs (e.g., Qwen-Plus, LLaMA-4-17B), as reported in Table 5. Across all models, BadGraph consistently achieves strong attack effectiveness, while larger models (e.g., Qwen-Plus) produce slightly more precise and context-aware perturbations. These results confirm that BadGraph is requiring no model-specific tuning, and can flexibly leverage the reasoning capability of emerging LLMs—underscoring its scalability and plug-and-play design for future LLM-powered TAG attacks. (c) WTGIA (d) BadGraph Figure 3. T-SNE visualization illustrating embedding shifts caused by the attack on the Cora dataset. Table 4. Robustness of BadGraph under prompt variations on Cora. “Rephrasing” rewrites the prompt, and “Anchor Mis.” uses inconsistent influencers across modalities. Method R-GCN GCN GIN GraphSAGE TAGCN Clean 87.33 87.11 85.70 86.00 88.22 Anchor Mis. 71.63 63.93 71.04 62.59 77.11 Rephrasing 58.15 58.74 50.74 39.04 54.59 BadGraph 56.67 56.00 47.04 39.93 51.19 Table 5. Robustness of BadGraph under Different Attacker LLMs on the Cora Dataset. Attacker models: LLaMA-4-17B, Qwen-Plus, and DeepSeek-V3. Method GIN GraphSAGE SGCN TAGCN Qwen DeepSeek Clean 85.70 86.00 86.07 88.22 68.88 71.85 Ours-LLaMA 48.81 39.85 58.52 52.44 15.92 17.03 Ours-Qwen 48.70 39.56 55.78 55.19 17.03 19.25 Ours-DeepSeek 47.04 39.93 55.63 51.19 16.29 16.29 6.3.4. Potential for Interpretable Attack Patterns. To demonstrate the reasonableness and interpretability of the attacks generated by BadGraph, we present a case study using DeepSeek to illustrate the reasoning process behind structural attacks. Instead of directly crafting adversarial examples, we reformulate the attack as a harmful prompt generation task, leveraging the reasoning capabilities of LLMs to identify structural patterns and generate effective perturbations. Given a target node (e.g., A Non-linear Information Maximisation Algorithm that Performs Blind Separation), the LLM produces not only potential perturbations but also natural language justifications for each modification, revealing the semantic and structural rationale behind the attack. Step 1: Analysis of the Target Node and Its Neighboring Set Summary of Adjacency and Correlation: The neighboring nodes are adjacent to the target node due to shared themes in unsupervised learning, information maximization, and blind source separation. The most prominent factors guiding their strong correlation are: - Information Maximization: The target node and the first neighboring node explicitly focus on information-theoretic approaches for blind separation. - Unsupervised Learning: All neighboring nodes address unsupervised methods (competitive learning, feature extraction, or classification). - Blind Separation/Deconvolution: The first neighboring node directly extends the target node’s core problem (blind separation). Step 2: Most Relevant Node in the Neighboring Set [Node] "An information-maximisation approach to blind separation and blind deconvolution" Reason: This node is the most relevant because it: 1. Shares the identical problem domain (blind separation/deconvolution). 2. Builds on the same theoretical foundation (information maximization). 3. Likely cites the target node as prior work or a direct extension. Step 3: Exclusion of Least Relevant Node from Candidate List [Node, Reason for irrelevance] "Type Inheritance in Strongly Typed Genetic Programming" Reason: This paper discusses type systems in genetic programming, a niche topic far removed from the target node’s focus on information maximization and blind separation. The other candidates at least tangentially relate to optimization (closer to machine learning), but this one is purely about programming language design for GAs. 7. Conclusion In this paper, we propose BadGraph, a novel method that enables LLMs to generate universal perturbations targeting both node topology and textual semantics in TAGs, all in a black-box manner. We design a target influencer retrieval module that identifies candidate influencer nodes, providing attack evidence and facilitating the construction of cross-modal adversarial shortcuts. The resulting adversarial graph is backbone-agnostic and transfers effectively across diverse graph learning models. Guided by a homophily-preserving bound and a cross-modal shortcut theory, we explain why BadGraph achieves both high attack efficacy and stealthiness. Extensive experiments show that it substantially degrades GNN- and LLM-based TAG backbones while producing interpretable, hard-to-detect, and cost-efficient attacks. As the first LLM-driven TAG attacker, this work lays a simple yet effective foundation for future studies, including autonomous LLM agents for adaptive attacks. Acknowledgements.This work was supported in part by the Zhejiang Provincial Natural Science Foundation under Grant No. LQN26F020049, in part by the Zhejiang Province Key R&D Program Project under Grant No. 2025C01023, and in part by the National Natural Science Foundation of China under Grant Nos. 62372146, 62322203, and 62172052. References Z. Alom, T. G. B. Ngo, M. Kantarcioglu, and C. G. Akcora (2025) GOttack: universal adversarial attacks on graph neural networks via graph orbits learning. In The Thirteenth International Conference on Learning Representations, Cited by: §2.1. T. Ao, Y. Yu, Y. Wang, Y. Deng, Z. Guo, L. Pang, P. Wang, T. Chua, X. Zhang, and Z. Cai (2025) Lightprof: a lightweight reasoning framework for large language model on knowledge graph. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39, p. 23424–23432. Cited by: §2.2. A. Bojchevski and S. Günnemann (2019) Adversarial attacks on node embeddings via graph poisoning. In International conference on machine learning, p. 695–704. Cited by: 2nd item, §6.1.3. P. Chao, A. Robey, E. Dobriban, H. Hassani, G. J. Pappas, and E. Wong (2023) Jailbreaking black box large language models in twenty queries. arXiv preprint arXiv:2310.08419. Cited by: §2.2. R. Chen, T. Zhao, A. Jaiswal, N. Shah, and Z. Wang (2024a) Llaga: large language and graph assistant. arXiv preprint arXiv:2402.08170. Cited by: §1. Y. Chen, H. Yang, Y. Zhang, K. Ma, T. Liu, B. Han, and J. Cheng (2022) Understanding and improving graph injection attack by promoting unnoticeability. External Links: 2202.08057, Link Cited by: §5.1, §6.3.1. Z. Chen, H. Mao, H. Li, W. Jin, H. Wen, X. Wei, S. Wang, D. Yin, W. Fan, H. Liu, et al. (2024b) Exploring the potential of large language models (llms) in learning on graphs. ACM SIGKDD Explorations Newsletter 25 (2), p. 42–61. Cited by: §1, §6.1.2. J. Dai, Z. Xiong, and C. Cao (2024) A semantic backdoor attack against graph convolutional networks. Neurocomputing 600, p. 128133. Cited by: §2.1. J. Du, S. Zhang, G. Wu, J. M. Moura, and S. Kar (2017) Topology adaptive graph convolutional networks. arXiv preprint arXiv:1710.10370. Cited by: 4th item, §6.1.2. K. Guo, Z. Liu, Z. Chen, H. Wen, W. Jin, J. Tang, and Y. Chang (2024) Learning on graphs with large language models (llms): a deep dive into model robustness. arXiv preprint arXiv:2407.12068. Cited by: §1. Z. Guo, L. Xia, Y. Yu, T. Ao, and C. Huang (2025) LightRAG: simple and fast retrieval-augmented generation. External Links: 2410.05779, Link Cited by: §1. W. Hamilton, Z. Ying, and J. Leskovec (2017) Inductive representation learning on large graphs. Advances in neural information processing systems 30. Cited by: 3rd item, §6.1.2. X. He, X. Bresson, T. Laurent, A. Perold, Y. LeCun, and B. Hooi (2024) Harnessing explanations: llm-to-lm interpreter for enhanced text-attributed graph representation learning. In ICLR, Cited by: §1. Z. Hou, R. Feng, T. Derr, and X. Liu (2024) Robust graph neural networks via unbiased aggregation. Advances in Neural Information Processing Systems 37, p. 110097–110130. Cited by: 7th item, §B.1. W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec (2020) Open graph benchmark: datasets for machine learning on graphs. Advances in neural information processing systems 33, p. 22118–22133. Cited by: §A.1, §6.1.1. A. Q. Jiang, A. Sablayrolles, A. Roux, A. Mensch, B. Savary, C. Bamford, D. S. Chaplot, D. d. l. Casas, E. B. Hanna, F. Bressand, et al. (2024) Mixtral of experts. arXiv preprint arXiv:2401.04088. Cited by: 9th item, §A.2, §6.1.2. T. N. Kipf and M. Welling (2016) Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907. Cited by: 1st item, §1, §6.1.2. R. Lei, Y. Hu, Y. Ren, and Z. Wei (2024) Intruding with words: towards understanding graph injection attacks at the text level. arXiv preprint arXiv:2405.16405. Cited by: 7th item, §1, §2.2, §6.1.3. J. Li, M. Pang, Y. Dong, J. Jia, and B. Wang (2024) Graph neural network explanations are fragile. In Proceedings of the 41st International Conference on Machine Learning, p. 28551–28567. Cited by: §2.1. J. Li, T. Xie, L. Chen, F. Xie, X. He, and Z. Zheng (2023) Adversarial attack on large scale graph. IEEE Transactions on Knowledge & Data Engineering 35 (01), p. 82–95. Cited by: 6th item, §6.1.3. Y. Li, X. Zhang, L. Luo, H. Chang, Y. Ren, I. King, and J. Li (2025) G-refer: graph retrieval-augmented large language model for explainable recommendation. In Proceedings of the ACM on Web Conference 2025, p. 240–251. Cited by: §1. H. Liu, J. Feng, L. Kong, N. Liang, D. Tao, Y. Chen, and M. Zhang (2023) One for all: towards training one graph model for all classification tasks. arXiv preprint arXiv:2310.00149. Cited by: §1. J. Liu, C. Yang, Z. Lu, J. Chen, Y. Li, M. Zhang, T. Bai, Y. Fang, L. Sun, P. S. Yu, et al. (2025a) Graph foundation models: concepts, opportunities and challenges. IEEE Transactions on Pattern Analysis and Machine Intelligence. Cited by: §1. X. Liu, Y. Zhang, M. Wu, M. Yan, K. He, W. Yan, S. Pan, X. Ye, and D. Fan (2025b) Revisiting edge perturbation for graph neural network in graph data augmentation and attack. IEEE Transactions on Knowledge and Data Engineering. Cited by: §2.1. Y. Liu, R. Zhang, J. Guo, M. de Rijke, Y. Fan, and X. Cheng (2025c) Attack-in-the-chain: bootstrapping large language models for attacks against black-box neural ranking models. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39, p. 12229–12237. Cited by: §2.2. H. Lu, W. Liu, B. Zhang, B. Wang, K. Dong, B. Liu, J. Sun, T. Ren, Z. Li, H. Yang, et al. (2024) Deepseek-vl: towards real-world vision-language understanding. arXiv preprint arXiv:2403.05525. Cited by: 8th item, §A.2, §6.1.2. A. Ma, X. Wang, J. Li, C. Wang, T. Xiao, Y. Liu, H. Cheng, J. Wang, Y. Li, Y. Chang, et al. (2023) Single-cell biological network inference using a heterogeneous graph transformer. Nature Communications 14 (1), p. 964. Cited by: §1. J. Ma, S. Ding, and Q. Mei (2020) Towards more practical adversarial attacks on graph neural networks. Advances in neural information processing systems 33, p. 4756–4766. Cited by: §2.1. A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu (2018) Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, Cited by: 4th item, §6.1.3. A. K. McCallum, K. Nigam, J. Rennie, and K. Seymore (2000) Automating the construction of internet portals with machine learning. Information Retrieval 3, p. 127–163. Cited by: §A.1, §6.1.1. L. Ning, S. Wang, W. Fan, Q. Li, X. Xu, H. Chen, and F. Huang (2024) Cheatagent: attacking llm-empowered recommender systems via llm agent. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, p. 2284–2295. Cited by: §1, §2.2. [32] X. Qi, A. Panda, K. Lyu, X. Ma, S. Roy, A. Beirami, P. Mittal, and P. Henderson Safety alignment should be made more than just a few tokens deep. In The Thirteenth International Conference on Learning Representations, Cited by: §2.2. D. Sanmartin (2024) KG-rag: bridging the gap between knowledge and creativity. arXiv preprint arXiv:2405.12035. Cited by: §1. Y. Shang, Y. Zhang, J. Chen, D. Jin, and Y. Li (2023) Transferable structure-based adversarial attack of heterogeneous graph neural network. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, p. 2188–2197. Cited by: §1. Y. Sun, J. He, L. Cui, S. Lei, and C. Lu (2024) Exploring the deceptive power of llm-generated fake news: a study of real-world detection challenges. arXiv preprint arXiv:2403.18249. Cited by: §1, §2.2. H. Touvron, T. Lavril, G. Izacard, X. Martinet, M. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, F. Azhar, et al. (2023) Llama: open and efficient foundation language models. arXiv preprint arXiv:2302.13971. Cited by: §A.4. B. Wang and N. Z. Gong (2019) Attacking graph-based classification via manipulating the graph structure. In Proceedings of the 2019 ACM SIGSAC conference on computer and communications security, p. 2023–2040. Cited by: §2.1. B. Wang, Y. Li, and P. Zhou (2022) Bandits for structure perturbation-based black-box attacks to graph neural networks with theoretical guarantees. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, p. 13379–13387. Cited by: §2.1. B. Wang, M. Lin, T. Zhou, P. Zhou, A. Li, M. Pang, H. Li, and Y. Chen (2024a) Efficient, direct, and restricted black-box graph evasion attacks to any-layer graph neural networks via influence function. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining, p. 693–701. Cited by: §2.1. B. Wang, M. Pang, and Y. Dong (2023) Turning strengths into weaknesses: a certified robustness inspired attack framework against graph neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, p. 16394–16403. Cited by: §2.1. H. Wang, C. Xu, C. Shi, P. Zheng, S. Zhang, M. Cheng, and H. Chen (2024b) Unsupervised heterogeneous graph rewriting attack via node clustering. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, p. 3057–3068. Cited by: §1. Y. Wang, C. Tian, B. Hu, Y. Yu, Z. Liu, Z. Zhang, J. Zhou, L. Pang, and X. Wang (2024c) Can small language models be good reasoners for sequential recommendation?. In Proceedings of the ACM Web Conference 2024, p. 3876–3887. Cited by: §1, §2.2. F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger (2019) Simplifying graph convolutional networks. In International conference on machine learning, p. 6861–6871. Cited by: 5th item. J. Xu, Y. Sun, X. Jiang, Y. Wang, Y. Yang, C. Wang, and J. Lu (2012) Query-free black-box adversarial attacks on graphs. arXiv preprint arXiv. Cited by: 3rd item, §6.1.3. K. Xu, W. Hu, J. Leskovec, and S. Jegelka (2018) How powerful are graph neural networks?. arXiv preprint arXiv:1810.00826. Cited by: 2nd item, §6.1.2. X. Xu, K. Kong, N. Liu, L. Cui, D. Wang, J. Zhang, and M. Kankanhalli (2023) An llm can fool itself: a prompt-based adversarial attack. arXiv preprint arXiv:2310.13345. Cited by: §2.2. H. Yan, C. Li, R. Long, C. Yan, J. Zhao, W. Zhuang, J. Yin, P. Zhang, W. Han, H. Sun, et al. (2023) A comprehensive study on text-attributed graphs: benchmarking and rethinking. Advances in Neural Information Processing Systems 36, p. 17238–17264. Cited by: §1. H. Zhang, B. Wu, X. Yuan, S. Pan, H. Tong, and J. Pei (2022) Trustworthy graph neural networks: aspects, methods and trends. (en-US). Cited by: §2.1. K. Zhang, Q. Liu, H. Qian, B. Xiang, Q. Cui, J. Zhou, and E. Chen (2021a) Eatn: an efficient adaptive transfer network for aspect-level sentiment analysis. IEEE Transactions on Knowledge and Data Engineering 35 (1), p. 377–389. Cited by: §1. K. Zhang, H. Qian, Q. Cui, Q. Liu, L. Li, J. Zhou, J. Ma, and E. Chen (2021b) Multi-interactive attention network for fine-grained feature learning in ctr prediction. In Proceedings of the 14th ACM international conference on web search and data mining, p. 984–992. Cited by: §1. Z. Zhang, J. Jia, B. Wang, and N. Z. Gong (2021c) Backdoor attacks to graph neural networks. In Proceedings of the 26th ACM symposium on access control models and technologies, p. 15–26. Cited by: §2.1. Z. Zhang, X. Wang, H. Zhou, Y. Yu, M. Zhang, C. Yang, and C. Shi (2024) Can large language models improve the adversarial robustness of graph neural networks?. arXiv preprint arXiv:2408.08685. Cited by: §1. Q. Zheng, X. Zou, Y. Dong, Y. Cen, D. Yin, J. Xu, Y. Yang, and J. Tang (2021) Graph robustness benchmark: benchmarking the adversarial robustness of graph machine learning. arXiv preprint arXiv:2111.04314. Cited by: §A.1, §A.4, §6.1.4. D. Zhu, Z. Zhang, P. Cui, and W. Zhu (2019) Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, p. 1399–1407. Cited by: 6th item, §6.1.2. Y. Zhu, H. Shi, X. Wang, Y. Liu, Y. Wang, B. Peng, C. Hong, and S. Tang (2025) GraphCLIP: enhancing transferability in graph foundation models for text-attributed graphs. External Links: 2410.10329, Link Cited by: §1. X. Zou, Q. Zheng, Y. Dong, X. Guan, E. Kharlamov, J. Lu, and J. Tang (2021) Tdgia: effective injection attacks on graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, p. 2461–2471. Cited by: §A.4. D. Zügner, A. Akbarnejad, and S. Günnemann (2018) Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, p. 2847–2856. Cited by: 1st item, 5th item, §2.1, §6.1.3. Appendix A Details of Experimental Settings A.1. Datasets We conduct extensive experiments on three TAG datasets: Cora (McCallum et al., 2000), OGBN-Arxiv, and OGBN-Products (Hu et al., 2020). The dataset statistics are provided in Table 6, with the largest dataset containing 1,166,243 edges. We follow the data splitting scheme from (Zheng et al., 2021), using the full splits for each dataset to train the target model. For the attack settings, we use the medium split as target nodes in Cora. In OGBN-Arxiv, we randomly select 1000 nodes from the medium split as target nodes, and in OGBN-Products, we randomly select 1000 nodes from the hard split. To ensure consistency and simplicity, we use minimal textual descriptions for each node in the TAG. Specifically, for the Cora and OGBN-Arxiv datasets, we extract only the paper titles as input text. For the OGBN-Products dataset, we use the product name as the textual input; if the name is unavailable, we substitute it with the product description. Each experiment is conducted five times, and the average performance and standard deviation are reported. The sources of the datasets are detailed in the footnote111https://github.com/XiaoxinHe/TAPE. Table 6. Overview of dataset statistics. Dataset #Nodes #Edges #Classes Cora 2,708 5,429 7 Arxiv 169,343 1,166,243 40 Products (subset) 54,025 74,420 47 A.2. Target Backbones Mistral-7B (Jiang et al., 2024) and DeepSeek (Lu et al., 2024) are employed in a zero-shot manner to perform node classification based on textual descriptions and their 2-hop neighborhoods. • GCN (Kipf and Welling, 2016): GCN is a widely used class of graph neural networks grounded in spectral graph theory. • GIN (Xu et al., 2018): GIN maximizes the expressive power of GNNs by using injective aggregation functions to distinguish different graph structures. • GraphSAGE (Hamilton et al., 2017): GraphSAGE samples a fixed number of neighbors and aggregates their features through learnable functions, enabling inductive learning on large graphs. • TAGCN (Du et al., 2017): TAGCN leverages fixed-size learnable filters based on powers of the graph Laplacian to capture multi-hop neighborhood information efficiently in a single convolutional layer. • SGCN (Wu et al., 2019): SGCN simplifies GCN by merging multiple layers of linear transformations and nonlinear activations into a single neighborhood aggregation step. • R-GCN (Zhu et al., 2019): R-GCN represents nodes as Gaussian distributions to resist adversarial noise and uses attention to downweight high-variance nodes. • RUNG (Hou et al., 2024): RUNG employs edge reweighting to prune suspicious edges, thereby enhancing the model’s robustness against adversarial attacks. • DeepSeek (Lu et al., 2024): DeepSeek adopts a 671B-parameter MoE architecture with MLA and multi-token prediction, demonstrating strong performance on multilingual tasks. • Mistral (Jiang et al., 2024): Mistral is an open-source LLM that adopts Grouped-Query Attention and Sliding Window Attention architectures, offering excellent inference efficiency. A.3. Baselines • RND (Zügner et al., 2018): RND is a random attack strategy that only modifies the structure of the graph. • FLIP (Bojchevski and Günnemann, 2019): FLIP is a deterministic approach that first ranks all nodes in ascending order according to their degrees, then flips their edges from the lower degree nodes to higher degree nodes. • STACK (Xu et al., 2012): STACK leverages a universal graph filter to unify different graph learning models, using this approximation to perform optimization-based attacks. • PGD (Madry et al., 2018): PGD works by adjusting inputs in multiple iterative steps towards the direction that increases model loss, thereby generating adversarial samples. • NETTACK (Zügner et al., 2018): NETTACK proposes an efficient algorithm to address the discrete nature of graph data while perturbing both the graph structure and node features. • SGAttack (Li et al., 2023): SGAttack is an efficient, simplified gradient-based attack that performs multi-stage perturbations on target nodes using only a small subgraph. • WTGIA (Lei et al., 2024): WTGIA is a text-level injection attack, utilizing LLMs to convert the embedding information of the fake nodes into adversarial text. Table 7. Attack Results Under RUNG Defense on the Cora Dataset. Clean STACK PGD RND FLIP NETTACK SGAttack WTGIA BadGraph TF-IDF 86.81 79.56 82.00 80.89 78.00 86.07 87.56 87.26 62.44 SBERT 85.45 78.22 81.11 78.07 78.15 83.56 86.00 85.11 35.11 Table 8. Effectiveness of BadGraph under adversarial training on the Cora. Δ = Accuracyadv-trained−AccuracyvanillaAccuracy_adv-trained-Accuracy_vanilla. Method R-GCN GCN SGCN TAGCN Clean 86.30 85.19 87.78 87.04 BadGraph 72.59 75.19 75.19 75.56 Δ +1.70 +3.86 +3.93 +1.63 A.4. Implementation Details We employ GNNs as the graph encoder in all experiments. Specifically, GAT is used for Cora and Products, while GIN is applied to Arxiv, as defined in Eq. (1). For each target node, we retrieve k=5k=5 candidate influencer nodes that are semantically distant in the embedding space. The open-source DeepSeek-V3222https://github.com/deepseek-ai/DeepSeek-V3 model serves as the LLM-based attacker, with its API333https://api.deepseek.com generating both topological and textual perturbations. Throughout this paper, we use the shorthand notations: Qwen for Qwen-Plus, LLaMA for LLaMA-4-17B, and DeepSeek for DeepSeek-V3. We implement BadGraph in PyTorch444https://pytorch.org/. For target backbones we generally use the default hyperparameters from GRB (Zheng et al., 2021); when those defaults produced unreasonably low clean accuracies, we made justified adjustments to ensure fair and representative baselines. All attack methods—BadGraph and competitors—are evaluated under the same strict black-box setting. We implement WTGIA using the authors’ official code and adopt its best-performing variant (the TDGIA-perturbed graph after training) (Zou et al., 2021). Adversarial texts for injected fake nodes are generated by converting embeddings with LLaMA3-8B (Touvron et al., 2023). The number of injected nodes is 20, 166, and 166 for Cora, OGBN-Products, and OGBN-Arxiv, respectively. For consistency across attack settings, all other baselines use a unified configuration: Bag-of-Words (BoW) for node features, GCN as the surrogate model, and up to two edge perturbations per node. The perturbed graphs produced by these procedures are then evaluated on the same set of target models. Public implementations of the compared methods are available at the referenced repositories. Target backbones: • R-GCN, GCN, GIN, GraphSAGE, SGCN, TAGCN555https://github.com/thudm/grb. • RUNG666https://github.com/chris-hzc/RUNG. • LLM4RGNN777https://github.com/zhongjian-zhang/LLM4RGNN. Baselines: • WTGIA888https://github.com/Leirunlin/Text-level-Graph-Attack. • STACK, PGD, RND, FLIP999https://github.com/thudm/grb. • SGAttack, NETTACK101010https://github.com/DSE-MSU/DeepRobust. A.5. Computing Environment and Resources The experiments are conducted in a computing environment with the following specifications: • OS: Ubuntu 22.04.3 LTS (Linux kernel 5.15.0-124-generic) • CPU: Intel(R) Xeon(R) Platinum 8360Y CPU @ 2.40GHz • GPU: NVIDIA GeForce RTX 4090, 24GB Appendix B More Experimental Results B.1. Evaluating Effectiveness Under Defense Observation. BadGraph effectively breaks advanced defenses by exploiting cross-modal alignment vulnerabilities. We evaluate BadGraph against two strong defenses—RUNG (Hou et al., 2024) and adversarial training. As shown in Table 7, BadGraph reduces RUNG’s accuracy by over 50% under the SBERT encoding, revealing its strong adversarial potency even against robust models. This degradation stems from semantically aligned cross-modal perturbations that mislead RUNG’s edge reweighting mechanism, causing the model to overemphasize adversarial edges and aggregate corrupted information. Moreover, as shown in Table 8, BadGraph remains effective under adversarial training, demonstrating strong transferability and resilience to conventional defense strategies. Together, these results highlight that cross-modal, LLM-guided perturbations can bypass even graph defenses—empirically validating our theoretical claims on cross-modal synergy. Table 9. Attack performance with different encoders on the Cora dataset across various GNN encoder backbones. Encoder GIN GraphSAGE SGCN TAGCN DeepSeek Clean 85.70 86.00 86.07 88.22 71.85 GCN 55.44 54.07 58.63 55.59 21.11 R-GCN 46.96 38.52 57.04 54.37 19.59 GAT 47.04 39.93 55.63 51.19 17.03 (a) SBERT (b) TF-IDF Figure 4. Attack Success Rate on OGBN-Products for different target GNNs, evaluated on two settings: Medium (medium-degree nodes) and Hard (high-degree nodes). Table 10. GNN-as-Reasoner Scenarios. Comprehensive evaluation results (Average, 3-MAX, and Weighted) across all target backbones. Lower values indicate stronger attack effectiveness. "Clean" denotes unperturbed graphs, while Our-text and Our-struct represent text-only and structure-only variants, respectively. Best results are highlighted in bold. Dataset Emb. Metrics Clean STACK PGD RND FLIP SGAttack WTGIA Our-text Our-struct BadGraph Cora TF-IDF Average 86.19 73.14 78.51 74.07 74.19 82.38 84.95 82.60 78.90 67.52 3-MAX 86.91 73.93 79.28 74.91 75.01 85.46 86.49 84.79 80.47 72.17 Weighted 87.03 74.61 79.72 74.85 75.36 86.14 86.84 84.90 81.85 72.51 SBERT Average 86.74 76.57 80.32 76.93 76.58 83.53 85.28 77.01 77.02 51.07 3-MAX 87.56 77.75 80.67 78.07 77.26 87.14 86.72 80.35 80.15 56.10 Weighted 87.79 77.71 80.70 78.49 77.32 87.55 87.17 80.06 81.42 55.68 TAPE Average 88.51 81.99 83.47 82.93 84.69 84.25 - 84.60 81.09 66.20 3-MAX 89.28 82.84 84.25 83.33 85.68 87.60 - 85.73 83.23 71.06 Weighted 89.44 82.91 84.21 83.36 85.99 87.30 - 85.91 83.39 71.46 Arxiv TF-IDF Average 65.43 62.71 60.52 59.75 58.18 - 60.38 61.56 58.07 51.27 3-MAX 67.57 65.67 62.69 61.85 60.34 - 64.24 66.13 62.13 58.33 Weighted 67.87 65.30 63.32 62.36 61.21 - 64.09 66.30 63.53 57.79 SBERT Average 68.56 67.68 64.75 64.81 63.43 - 65.34 66.03 62.14 54.60 3-MAX 69.78 68.27 66.27 66.12 64.59 - 67.72 67.20 65.68 59.51 Weighted 69.91 68.19 66.46 66.60 65.01 - 68.60 67.25 66.55 59.25 TAPE Average 74.84 77.76 73.30 74.11 73.88 - - 63.58 69.72 51.00 3-MAX 79.66 79.92 79.11 79.03 79.31 - - 69.31 76.13 63.57 Weighted 79.59 80.51 78.60 78.74 78.88 - - 68.55 77.81 63.47 Products TF-IDF Average 85.66 79.60 82.95 81.83 80.79 83.44 78.67 79.21 78.63 64.72 3-MAX 86.27 80.87 83.60 82.35 81.91 85.33 83.13 82.67 82.05 71.97 Weighted 86.32 81.38 83.88 82.31 82.33 85.06 83.00 82.52 81.91 72.13 SBERT Average 87.22 82.30 85.86 84.28 83.55 85.35 81.42 85.08 81.35 73.97 3-MAX 87.64 83.13 86.32 84.65 84.19 87.13 85.20 86.49 84.65 78.97 Weighted 87.83 83.31 86.32 84.70 84.13 87.09 85.38 86.43 84.51 79.09 TAPE Average 89.31 89.52 88.85 88.59 89.45 88.81 - 84.75 87.86 75.27 3-MAX 89.73 90.03 89.43 89.23 90.05 89.62 - 87.12 88.92 80.16 Weighted 89.94 90.33 89.72 89.48 90.20 89.80 - 86.99 89.14 79.62 B.2. Influence of Graph Encoder Selection Observation 1. BadGraph exhibits strong and consistent attack performance across diverse graph encoders. We assess the impact of encoder choice by substituting the influencer retriever with different GNNs—GCN, R-GCN, and GAT. As shown in Table 9, BadGraph consistently causes over 27% accuracy degradation across all variants, demonstrating its robustness and flexibility. This adaptability shows that BadGraph can seamlessly integrate with any expressive encoder, making it a general plug-and-play attack framework for diverse graph learning backbones. Observation 2. Encoder expressiveness amplifies cross-model transferability. More expressive encoders (e.g., GAT) produce finer-grained relational embeddings, enabling more accurate influencer retrieval and directionally aligned perturbations. Consequently, BadGraph achieves stronger and more transferable attacks across both GNN- and LLM-based reasoners. These findings confirm that encoder expressiveness enhances both the performance and generalization of LLM-driven adversarial attacks, reinforcing BadGraph’s universality across architectures and modalities. B.3. Low-Degree Nodes Are More Vulnerable to Adversarial Perturbations Observation. Nodes with fewer neighbors exhibit significantly higher attack susceptibility. We analyze the relationship between node degree and adversarial vulnerability on the Products dataset under the GNN-as-Reasoner setting, comparing medium (low-degree) and hard (high-degree) splits. As shown in Fig. 4, the Attack Success Rate (ASR) is markedly higher for the medium split, indicating that low-degree nodes are more easily compromised by adversarial perturbations. These findings highlight the necessity for defense mechanisms that explicitly account for the heightened vulnerability of low-degree nodes in TAG security scenarios. B.4. Additional Experimental Results. Due to space limitations in the main paper, we omitted part of Table 1. Specifically, the detailed results for the three evaluation metrics—Average, 3-MAX, and Weighted—were excluded. Table 10 in this appendix provides the complete results across all datasets and evaluation metrics. Overall, BadGraph consistently achieves state-of-the-art performance, demonstrating strong effectiveness and generalizability under diverse settings.

Instant research discovery