# Towards More Practical Adversarial Attacks on Graph Neural Networks

arXiv: https://arxiv.org/abs/2006.05057 · HTML: https://mlsanity.com/paper/2006.05057/

## Key facts

- Cited by 76 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2020.

## Built on by (most cited first, 30 of 76)

- [A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability](https://mlsanity.com/paper/2204.08570/) (2022)
- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (2021)
- [Model Stealing Attacks Against Inductive Graph Neural Networks](https://mlsanity.com/paper/2112.08331/) (2021)
- [Enhancing Self-supervised Video Representation Learning via Multi-level Feature Optimization](https://mlsanity.com/paper/2108.02183/) (2021)
- [Model Inversion Attacks against Graph Neural Networks](https://mlsanity.com/paper/2209.07807/) (2022)
- [How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implications](https://mlsanity.com/paper/2106.07767/) (2021)
- [Model-Agnostic Augmentation for Accurate Graph Classification](https://mlsanity.com/paper/2202.10107/) (2022)
- [Adversarial Attack on Graph Neural Networks as An Influence Maximization Problem](https://mlsanity.com/paper/2106.10785/) (2021)
- [Scalable Verification of GNN-based Job Schedulers](https://mlsanity.com/paper/2203.03153/) (2022)
- [Graph Neural Network Explanations are Fragile](https://mlsanity.com/paper/2406.03193/) (2024)
- [Jointly Attacking Graph Neural Network and its Explanations](https://mlsanity.com/paper/2108.03388/) (2021)
- [Verification-Aided Deep Ensemble Selection](https://mlsanity.com/paper/2202.03898/) (2022)
- [Graph Structural Attack by Perturbing Spectral Distance](https://mlsanity.com/paper/2111.00684/) (2021)
- [Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debias](https://mlsanity.com/paper/2304.00010/) (2023)
- [Verification-Guided Shielding for Deep Reinforcement Learning](https://mlsanity.com/paper/2406.06507/) (2024)
- [Adversarial Inter-Group Link Injection Degrades the Fairness of Graph Neural Networks](https://mlsanity.com/paper/2209.05957/) (2022)
- [Verifying Generalization in Deep Learning](https://mlsanity.com/paper/2302.05745/) (2023)
- [Safety in Graph Machine Learning: Threats and Safeguards](https://mlsanity.com/paper/2405.11034/) (2024)
- [Learning on Graphs with Large Language Models(LLMs): A Deep Dive into Model Robustness](https://mlsanity.com/paper/2407.12068/) (2024)
- [Adversarial Attack Framework on Graph Embedding Models with Limited Knowledge](https://mlsanity.com/paper/2105.12419/) (2021)
- [Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks](https://mlsanity.com/paper/2301.02039/) (2023)
- [Verifying message-passing neural networks via topology-based bounds tightening](https://mlsanity.com/paper/2402.13937/) (2024)
- [Bandits for Structure Perturbation-based Black-box Attacks to Graph Neural Networks with Theoretical Guarantees](https://mlsanity.com/paper/2205.03546/) (2022)
- [Fundamental Limits in Formal Verification of Message-Passing Neural Networks](https://mlsanity.com/paper/2206.05070/) (2022)
- [Spear and Shield: Adversarial Attacks and Defense Methods for Model-Based Link Prediction on Continuous-Time Dynamic Graphs](https://mlsanity.com/paper/2308.10779/) (2023)
- [Hierarchical Randomized Smoothing](https://mlsanity.com/paper/2310.16221/) (2023)
- [Coupling Graph Neural Networks with Fractional Order Continuous Dynamics: A Robustness Study](https://mlsanity.com/paper/2401.04331/) (2024)
- [GraphAttacker: A General Multi-Task GraphAttack Framework](https://mlsanity.com/paper/2101.06855/) (2021)
- [Revisiting Adversarial Attacks on Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/2208.06651/) (2022)
- [GDeR: Safeguarding Efficiency, Balancing, and Robustness via Prototypical Graph Pruning](https://mlsanity.com/paper/2410.13761/) (2024)

## Abstract (arXiv)

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.