Towards Type-I Adversarial Attack on Graph Neural Networks

Despite the significant success of graph neural networks (GNNs), adversarial attacks can still deceive well-trained classifiers through small perturbations. In this paper, we propose a novel type of adversarial attack that targets classifiers using more substantial modifications. Specifically, we demonstrate that it is possible to significantly alter the one-hop subgraph of a node and the features associated with that node while maintaining its original label classification. This attack paradigm is fundamentally different from existing methods. Statistically, traditional adversarial attacks primarily increase Type II error, whereas our proposed attack is designed to exploit Type I error. We refer to these as Type II and Type I adversarial attacks, respectively. We argue that the success of such a Type I attack is closely linked to the Out-of-Distribution (OOD) Generalization problem. This means that the distribution of subgraphs in the training graph may not be representative of those in the test or adversarial graph. To address this, we introduce an OOD detector, which, when combined with cross-entropy loss and t-2 norm loss, serves as a guide for generating adversarial examples. Experimental results on three publicly available real-world datasets and across two popular graph neural network architectures demonstrate the effectiveness of our approach.