# GAIM: Attacking Graph Neural Networks via Adversarial Influence Maximization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 37 references that are in the map.
- First posted on arXiv 20 Aug 2024.

## Builds on (most cited first, 27 of 27)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples](https://mlsanity.com/paper/1605.07277/) (2016)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [Adversarial Attack and Defense on Graph Data: A Survey](https://mlsanity.com/paper/1812.10528/) (2018)
- [Adversarial Attacks on Node Embeddings via Graph Poisoning](https://mlsanity.com/paper/1809.01093/) (2018)
- [Towards More Practical Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2006.05057/) (2020)
- [A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Models](https://mlsanity.com/paper/1908.01297/) (2019)
- [Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studies](https://mlsanity.com/paper/2003.00653/) (2020)
- [Attacking Graph Convolutional Networks via Rewiring](https://mlsanity.com/paper/1906.03750/) (2019)
- [Adversarial Attack on Graph Neural Networks as An Influence Maximization Problem](https://mlsanity.com/paper/2106.10785/) (2021)
- [Graph Universal Adversarial Attacks: A Few Bad Actors Ruin Graph Learning Models](https://mlsanity.com/paper/2002.04784/) (2020)
- [Node Injection Attacks on Graphs via Reinforcement Learning](https://mlsanity.com/paper/1909.06543/) (2019)
- [Higher-order Weighted Graph Convolutional Networks](https://mlsanity.com/paper/1911.04129/) (2019)
- [Can One Embedding Fit All? A Multi-Interest Learning Paradigm Towards Improving User Interest Diversity Fairness](https://mlsanity.com/paper/2402.13495/) (2024)

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

- [Infusion: Shaping Model Behavior by Editing Training Data via Influence Functions](https://mlsanity.com/paper/2602.09987/) (2026)

## Abstract (arXiv)

Recent studies show that well-devised perturbations on graph structures or node features can mislead trained Graph Neural Network (GNN) models. However, these methods often overlook practical assumptions, over-rely on heuristics, or separate vital attack components. In response, we present GAIM, an integrated adversarial attack method conducted on a node feature basis while considering the strict black-box setting. Specifically, we define an adversarial influence function to theoretically assess the adversarial impact of node perturbations, thereby reframing the GNN attack problem into the adversarial influence maximization problem. In our approach, we unify the selection of the target node and the construction of feature perturbations into a single optimization problem, ensuring a unique and consistent feature perturbation for each target node. We leverage a surrogate model to transform this problem into a solvable linear programming task, streamlining the optimization process. Moreover, we extend our method to accommodate label-oriented attacks, broadening its applicability. Thorough evaluations on five benchmark datasets across three popular models underscore the effectiveness of our method in both untargeted and label-oriented targeted attacks. Through comprehensive analysis and ablation studies, we demonstrate the practical value and efficacy inherent to our design choices.