We study the black-box attacks on graph neural networks (GNNs) under a novel
and realistic constraint: attackers have access to only a subset of nodes in
the network, and they can only attack a small number of them. A node selection
step is essential under this setup. We demonstrate that the structural
inductive biases of GNN models can be an effective source for this type of
attacks. Specifically, by exploiting the connection between the backward
propagation of GNNs and random walks, we show that the common gradient-based
white-box attacks can be generalized to the black-box setting via the
connection between the gradient and an importance score similar to PageRank. In
practice, we find attacks based on this importance score indeed increase the
classification loss by a large margin, but they fail to significantly increase
the mis-classification rate. Our theoretical and empirical analyses suggest
that there is a discrepancy between the loss and mis-classification rate, as
the latter presents a diminishing-return pattern when the number of attacked
nodes increases. Therefore, we propose a greedy procedure to correct the
importance score that takes into account of the diminishing-return pattern.
Experimental results show that the proposed procedure can significantly
increase the mis-classification rate of common GNNs on real-world data without
access to model parameters nor predictions.

研究黑盒攻击图神经网络中节点选择的问题，发现通过基于 PageRank 的重要度计算可提高分类误差率，提出一种基于贪心算法的修正方法能有效地解决被攻击节点数量与分类误差率之间的矛盾。