# Efficient, Direct, and Restricted Black-Box Graph Evasion Attacks to Any-Layer Graph Neural Networks via Influence Function

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

## Key facts

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

## Built on by (most cited first, 14 of 14)

- [Unnoticeable Backdoor Attacks on Graph Neural Networks](https://mlsanity.com/paper/2303.01263/) (2023)
- [Characterizing the Influence of Graph Elements](https://mlsanity.com/paper/2210.07441/) (2022)
- [Adversarial Attacks on Graph Classification via Bayesian Optimisation](https://mlsanity.com/paper/2111.02842/) (2021)
- [Task and Model Agnostic Adversarial Attack on Graph Neural Networks](https://mlsanity.com/paper/2112.13267/) (2021)
- [Certifiably Robust Graph Contrastive Learning](https://mlsanity.com/paper/2310.03312/) (2023)
- [Stealing Training Graphs from Graph Neural Networks](https://mlsanity.com/paper/2411.11197/) (2024)
- [Practicable Black-box Evasion Attacks on Link Prediction in Dynamic Graphs -- A Graph Sequential Embedding Method](https://mlsanity.com/paper/2412.13134/) (2024)
- [Watermarking Graph Neural Networks via Explanations for Ownership Protection](https://mlsanity.com/paper/2501.05614/) (2025)
- [Backdoor Attacks on Discrete Graph Diffusion Models](https://mlsanity.com/paper/2503.06340/) (2025)
- [Are You Using Reliable Graph Prompts? Trojan Prompt Attacks on Graph Neural Networks](https://mlsanity.com/paper/2410.13974/) (2024)
- [Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations](https://mlsanity.com/paper/2503.18503/) (2025)
- [AuditVotes: Elevating Provable Defense for GNNs with Efficient Augmentation and Conditional Smoothing](https://mlsanity.com/paper/2503.22998/) (2025)
- [Momentum Gradient-based Untargeted Attack on Hypergraph Neural Networks](https://mlsanity.com/paper/2310.15656/) (2023)
- [Can LLMs Fool Graph Learning? Exploring Universal Adversarial Attacks on Text-Attributed Graphs](https://mlsanity.com/paper/2603.21155/) (2026)

## Abstract (arXiv)

Graph neural network (GNN), the mainstream method to learn on graph data, is vulnerable to graph evasion attacks, where an attacker slightly perturbing the graph structure can fool trained GNN models. Existing work has at least one of the following drawbacks: 1) limited to directly attack two-layer GNNs; 2) inefficient; and 3) impractical, as they need to know full or part of GNN model parameters. We address the above drawbacks and propose an influence-based efficient, direct, and restricted black-box evasion attack to any-layer GNNs. Specifically, we first introduce two influence functions, i.e., feature-label influence and label influence, that are defined on GNNs and label propagation (LP), respectively. Then we observe that GNNs and LP are strongly connected in terms of our defined influences. Based on this, we can then reformulate the evasion attack to GNNs as calculating label influence on LP, which is inherently applicable to any-layer GNNs, while no need to know information about the internal GNN model. Finally, we propose an efficient algorithm to calculate label influence. Experimental results on various graph datasets show that, compared to state-of-the-art white-box attacks, our attack can achieve comparable attack performance, but has a 5-50x speedup when attacking two-layer GNNs. Moreover, our attack is effective to attack multi-layer GNNsfootnoteSource code and full version is in the link: urlhttps://github.com/ventr1c/InfAttack.