Graph neural networks (GNNs) have achieved state-of-the-art performance in
many graph-related tasks, e.g., node classification. However, recent works show
that GNNs are vulnerable to evasion attacks, i.e., an attacker can slightly
perturb the graph structure to fool GNN models. Existing evasion attacks to
GNNs have several key drawbacks: 1) they are limited to attack two-layer GNNs;
2) they are not efficient; or/and 3) they need to know GNN model parameters. We
address the above drawbacks in this paper and propose an influence-based
evasion attack against GNNs. Specifically, we first introduce two influence
functions, i.e., feature-label influence and label influence, that are defined
on GNNs and label propagation (LP), respectively. Then, we build a strong
connection between GNNs and LP in terms of influence. Next, we reformulate the
evasion attack against GNNs to be related to calculating label influence on LP,
which is applicable to multi-layer GNNs and does not need to know the GNN
model. We also propose an efficient algorithm to calculate label influence.
Finally, we evaluate our influence-based attack on three benchmark graph
datasets. Our experimental results show that, compared to state-of-the-art
attack, our attack can achieve comparable attack performance, but has a 5-50x
speedup when attacking two-layer GNNs. Moreover, our attack is effective to
attack multi-layer GNNs.

本研究提出了一种基于影响力的逃避攻击方法，用于攻击多层图神经网络，不需要知道其具体参数，在性能相当的情况下有 5-50 倍的速度提升。