← Back to Library

GRAPHTEXTACK: A Realistic Black-Box Node Injection Attack on LLM-Enhanced GNNs

Authors: Jiaji Ma, Puja Trivedi, Danai Koutra

Published: 2025-11-16

arXiv ID: 2511.12423v1

Added to Library: 2025-11-18 03:01 UTC

Red Teaming

📄 Abstract

Text-attributed graphs (TAGs), which combine structural and textual node information, are ubiquitous across many domains. Recent work integrates Large Language Models (LLMs) with Graph Neural Networks (GNNs) to jointly model semantics and structure, resulting in more general and expressive models that achieve state-of-the-art performance on TAG benchmarks. However, this integration introduces dual vulnerabilities: GNNs are sensitive to structural perturbations, while LLM-derived features are vulnerable to prompt injection and adversarial phrasing. While existing adversarial attacks largely perturb structure or text independently, we find that uni-modal attacks cause only modest degradation in LLM-enhanced GNNs. Moreover, many existing attacks assume unrealistic capabilities, such as white-box access or direct modification of graph data. To address these gaps, we propose GRAPHTEXTACK, the first black-box, multi-modal{, poisoning} node injection attack for LLM-enhanced GNNs. GRAPHTEXTACK injects nodes with carefully crafted structure and semantics to degrade model performance, operating under a realistic threat model without relying on model internals or surrogate models. To navigate the combinatorial, non-differentiable search space of connectivity and feature assignments, GRAPHTEXTACK introduces a novel evolutionary optimization framework with a multi-objective fitness function that balances local prediction disruption and global graph influence. Extensive experiments on five datasets and two state-of-the-art LLM-enhanced GNN models show that GRAPHTEXTACK significantly outperforms 12 strong baselines.

🔍 Key Points

  • Introduction of GRAPHTEXTACK, a black-box, multi-modal poisoning attack that injects nodes into LLM-enhanced GNNs, effectively exploiting vulnerabilities in both structure and semantics.
  • Proposed a novel evolutionary optimization framework to navigate the complex search space of node injection, combining both structural and semantic adaptations to enhance attack effectiveness.
  • Demonstrated superior attack performance on various node classification benchmarks compared to 12 strong baselines, showcasing the need for multi-modal approaches in adversarial settings.
  • Provided theoretical analysis of the search space complexity and the additive benefits of multi-modal attacks, confirming their effectiveness over isolated uni-modal attacks.

💡 Why This Paper Matters

The paper presents an essential advancement in understanding and exploiting the vulnerabilities of integrative models like LLM-enhanced GNNs. By developing GRAPHTEXTACK, it highlights the need for a multi-modal perspective in security assessments, underscoring the critical vulnerabilities that arise when combining language models with graph structures, thereby paving the way for more robust defenses.

🎯 Why It's Interesting for AI Security Researchers

This paper is significant for AI security researchers as it uncovers specific vulnerabilities in increasingly common hybrid models that integrate LLMs and GNNs. By addressing the practical attack models under realistic conditions, it informs both the research community and practitioners of the security implications of deploying these technologies in real-world applications, spurring necessary advancements in defenses against such sophisticated attacks.

📚 Read the Full Paper