Node injection attack on Graph Neural Networks (GNNs) is an emerging and
practical attack scenario that the attacker injects malicious nodes rather than
modifying original nodes or edges to affect the performance of GNNs. However,
existing node injection attacks ignore extremely limited scenarios, namely the
injected nodes might be excessive such that they may be perceptible to the
target GNN. In this paper, we focus on an extremely limited scenario of single
node injection evasion attack, i.e., the attacker is only allowed to inject one
single node during the test phase to hurt GNN's performance. The discreteness
of network structure and the coupling effect between network structure and node
features bring great challenges to this extremely limited scenario. We first
propose an optimization-based method to explore the performance upper bound of
single node injection evasion attack. Experimental results show that 100%,
98.60%, and 94.98% nodes on three public datasets are successfully attacked
even when only injecting one node with one edge, confirming the feasibility of
single node injection evasion attack. However, such an optimization-based
method needs to be re-optimized for each attack, which is computationally
unbearable. To solve the dilemma, we further propose a Generalizable Node
Injection Attack model, namely G-NIA, to improve the attack efficiency while
ensuring the attack performance. Experiments are conducted across three
well-known GNNs. Our proposed G-NIA significantly outperforms state-of-the-art
baselines and is 500 times faster than the optimization-based method when
inferring.

该研究提出了优化方法和模型：一个针对单节点注入攻击的优化方案，以及一个通用的针对节点注入的模型 (G-NIA)，实验表明 G-NIA 模型在攻击效率和攻击性能两方面表现优异。