# Attacking Graph Convolutional Networks via Rewiring

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jun 2019.

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

- [Trustworthy AI: A Computational Perspective](https://mlsanity.com/paper/2107.06641/) (2021)
- [Graph Robustness Benchmark: Benchmarking the Adversarial Robustness of Graph Machine Learning](https://mlsanity.com/paper/2111.04314/) (2021)
- [A Hard Label Black-box Adversarial Attack Against Graph Neural Networks](https://mlsanity.com/paper/2108.09513/) (2021)
- [Unsupervised Graph Poisoning Attack via Contrastive Loss Back-propagation](https://mlsanity.com/paper/2201.07986/) (2022)
- [Reinforcement learning on graphs: A survey](https://mlsanity.com/paper/2204.06127/) (2022)
- [Let Graph be the Go Board: Gradient-free Node Injection Attack for Graph Neural Networks via Reinforcement Learning](https://mlsanity.com/paper/2211.10782/) (2022)
- [Jointly Attacking Graph Neural Network and its Explanations](https://mlsanity.com/paper/2108.03388/) (2021)
- [Graph-Fraudster: Adversarial Attacks on Graph Neural Network Based Vertical Federated Learning](https://mlsanity.com/paper/2110.06468/) (2021)
- [Robust Mid-Pass Filtering Graph Convolutional Networks](https://mlsanity.com/paper/2302.08048/) (2023)
- [Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debias](https://mlsanity.com/paper/2304.00010/) (2023)
- [Adversarial Inter-Group Link Injection Degrades the Fairness of Graph Neural Networks](https://mlsanity.com/paper/2209.05957/) (2022)
- [BeMap: Balanced Message Passing for Fair Graph Neural Network](https://mlsanity.com/paper/2306.04107/) (2023)
- [Learning on Graphs with Large Language Models(LLMs): A Deep Dive into Model Robustness](https://mlsanity.com/paper/2407.12068/) (2024)
- [Are Gradients on Graph Structure Reliable in Gray-box Attacks?](https://mlsanity.com/paper/2208.05514/) (2022)
- [Structack: Structure-based Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2107.11327/) (2021)
- [Minimum Topology Attacks for Graph Neural Networks](https://mlsanity.com/paper/2403.02723/) (2024)
- [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)
- [Surrogate Representation Learning with Isometric Mapping for Gray-box Graph Adversarial Attacks](https://mlsanity.com/paper/2110.10482/) (2021)
- [Reinforcement Learning For Data Poisoning on Graph Neural Networks](https://mlsanity.com/paper/2102.06800/) (2021)
- [Black-box Gradient Attack on Graph Neural Networks: Deeper Insights in Graph-based Attack and Defense](https://mlsanity.com/paper/2104.15061/) (2021)
- [Dynamic Network Reconfiguration for Entropy Maximization using Deep Reinforcement Learning](https://mlsanity.com/paper/2205.13578/) (2022)
- [Practicable Black-box Evasion Attacks on Link Prediction in Dynamic Graphs -- A Graph Sequential Embedding Method](https://mlsanity.com/paper/2412.13134/) (2024)
- [What Does the Gradient Tell When Attacking the Graph Structure](https://mlsanity.com/paper/2208.12815/) (2022)
- [Deterministic Certification of Graph Neural Networks against Graph Poisoning Attacks with Arbitrary Perturbations](https://mlsanity.com/paper/2503.18503/) (2025)
- [Adversarial Robustness of Probabilistic Network Embedding for Link Prediction](https://mlsanity.com/paper/2107.01936/) (2021)
- [Explainability-Based Adversarial Attack on Graphs Through Edge Perturbation](https://mlsanity.com/paper/2312.17301/) (2023)
- [GAIM: Attacking Graph Neural Networks via Adversarial Influence Maximization](https://mlsanity.com/paper/2408.10948/) (2024)
- [Black-box Node Injection Attack for Graph Neural Networks](https://mlsanity.com/paper/2202.09389/) (2022)
- [Multi-Instance Adversarial Attack on GNN-Based Malicious Domain Detection](https://mlsanity.com/paper/2308.11754/) (2023)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have boosted the performance of many graph related tasks such as node classification and graph classification. Recent researches show that graph neural networks are vulnerable to adversarial attacks, which deliberately add carefully created unnoticeable perturbation to the graph structure. The perturbation is usually created by adding/deleting a few edges, which might be noticeable even when the number of edges modified is small. In this paper, we propose a graph rewiring operation which affects the graph in a less noticeable way compared to adding/deleting edges. We then use reinforcement learning to learn the attack strategy based on the proposed rewiring operation. Experiments on real world graphs demonstrate the effectiveness of the proposed framework. To understand the proposed framework, we further analyze how its generated perturbation to the graph structure affects the output of the target model.