  Graph Neural Networks (GNNs) have drawn significant attentions over the years
and been broadly applied to essential applications requiring solid robustness
or vigorous security standards, such as product recommendation and user
behavior modeling. Under these scenarios, exploiting GNN's vulnerabilities and
further downgrading its performance become extremely incentive for adversaries.
Previous attackers mainly focus on structural perturbations or node injections
to the existing graphs, guided by gradients from the surrogate models. Although
they deliver promising results, several limitations still exist. For the
structural perturbation attack, to launch a proposed attack, adversaries need
to manipulate the existing graph topology, which is impractical in most
circumstances. Whereas for the node injection attack, though being more
practical, current approaches require training surrogate models to simulate a
white-box setting, which results in significant performance downgrade when the
surrogate architecture diverges from the actual victim model. To bridge these
gaps, in this paper, we study the problem of black-box node injection attack,
without training a potentially misleading surrogate model. Specifically, we
model the node injection attack as a Markov decision process and propose
Gradient-free Graph Advantage Actor Critic, namely G2A2C, a reinforcement
learning framework in the fashion of advantage actor critic. By directly
querying the victim model, G2A2C learns to inject highly malicious nodes with
extremely limited attacking budgets, while maintaining a similar node feature
distribution. Through our comprehensive experiments over eight acknowledged
benchmark datasets with different characteristics, we demonstrate the superior
performance of our proposed G2A2C over the existing state-of-the-art attackers.
Source code is publicly available at: https://github.com/jumxglhf/G2A2C}.
