  Graph neural networks (GNNs) have achieved remarkable success in various
real-world applications. However, recent studies highlight the vulnerability of
GNNs to malicious perturbations. Previous adversaries primarily focus on graph
modifications or node injections to existing graphs, yielding promising results
but with notable limitations. Graph modification attack~(GMA) requires
manipulation of the original graph, which is often impractical, while graph
injection attack~(GIA) necessitates training a surrogate model in the black-box
setting, leading to significant performance degradation due to divergence
between the surrogate architecture and the actual victim model. Furthermore,
most methods concentrate on a single attack goal and lack a generalizable
adversary to develop distinct attack strategies for diverse goals, thus
limiting precise control over victim model behavior in real-world scenarios. To
address these issues, we present a gradient-free generalizable adversary that
injects a single malicious node to manipulate the classification result of a
target node in the black-box evasion setting. We propose Gradient-free
Generalizable Single Node Injection Attack, namely G$^2$-SNIA, a reinforcement
learning framework employing Proximal Policy Optimization. By directly querying
the victim model, G$^2$-SNIA learns patterns from exploration to achieve
diverse attack goals with extremely limited attack budgets. Through
comprehensive experiments over three acknowledged benchmark datasets and four
prominent GNNs in the most challenging and realistic scenario, we demonstrate
the superior performance of our proposed G$^2$-SNIA over the existing
state-of-the-art baselines. Moreover, by comparing G$^2$-SNIA with multiple
white-box evasion baselines, we confirm its capacity to generate solutions
comparable to those of the best adversaries.
