SoftHist: Teaching Graph Injection Attackers to Camouflage with Memory

Graph Neural Networks (GNNs) have achieved notable success in a wide range of applications. However, their vulnerability to adversarial attacks, particularly graph injection attacks (GIAs), raises serious concerns for their deployment in security-sensitive domains. Existing GIA methods, despite their demonstrated effectiveness, face several inherent limitations. They typically require training surrogate models to approximate the victim model's behavior, which may lead to performance degradation when the surrogate mismatches the target model. Furthermore, the discrete nature of graph data poses challenges for generating effective adversarial features, often resulting in suboptimal solutions. Most critically, these methods show markedly reduced effectiveness when deployed against defended GNN models, limiting real-world applicability. To address these challenges, we introduce SoftHist, a novel gradient-free reinforcement learning framework for black-box graph injection attacks. Our approach incorporates a softened embedding mechanism to avoid suboptimal feature generation, ensuring stable and stealthy node injection. Moreover, we design a topology-aware edge sampler and a defense-aware policy learner with adaptive history reuse optimized for misclassification maximization. These innovations collectively balance attack effectiveness, stealthiness, and robustness against defensive measures. Extensive experiments on eight benchmark datasets demonstrate SoftHist's significant advantages in key scenarios: (1) On discrete-feature datasets like AMComputer, the misclassification rate is 10.34%~38.09% higher than baseline methods; (2) Against defensive models such as RGCN, it maintains 98.23% success rate, surpassing state-of-the-art methods by 12.36%.