Towards More Practical Adversarial Attacks on Graph Neural Networks
This work addresses practical security vulnerabilities in graph neural networks for applications like social networks or recommendation systems, but it is incremental as it builds on existing gradient-based attacks.
The paper tackles black-box adversarial attacks on graph neural networks under realistic constraints of limited node access, showing that exploiting structural inductive biases via a connection to random walks increases classification loss but not mis-classification rate due to diminishing returns, and proposes a greedy correction procedure that significantly boosts mis-classification rates on real-world data without model access.
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.