Towards More Practical Adversarial Attacks on Graph Neural Networks

Abstract

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.

arXiv commentNeurIPS 2020, Code Link Update

References in corpus (12)

• Emergence of scaling in random networks
• Semi-Supervised Classification with Graph Convolutional Networks
• Neural Architecture Search with Reinforcement Learning
• Representation Learning on Graphs with Jumping Knowledge Networks
• Adversarial Attacks on Graph Neural Networks via Meta Learning
• Adversarial Attacks on Node Embeddings via Graph Poisoning
• Adversarial Attack on Graph Structured Data
• Fast Gradient Attack on Network Embedding
• Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective
• The Case for Bayesian Deep Learning
• Maximization of Approximately Submodular Functions
• Node Injection Attacks on Graphs via Reinforcement Learning

Cited by in corpus (2)

• A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability
• How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implications