Graph Adversarial Attack via Rewiring

Yao Ma, Suhang Wang, Tyler Derr, Lingfei Wu, Jiliang Tang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

40 Scopus citations


Graph Neural Networks (GNNs) have demonstrated their powerful capability in learning representations for graph-structured data. Consequently, they have enhanced the performance of many graph-related tasks such as node classification and graph classification. However, it is evident from recent studies that GNNs are vulnerable to adversarial attacks. Their performance can be largely impaired by deliberately adding carefully created unnoticeable perturbations to the graph. Existing attacking methods often produce perturbation by adding/deleting a few edges, which might be noticeable even when the number of modified edges is small. In this paper, we propose a graph rewiring operation to perform the attack. It can affect the graph in a less noticeable way compared to existing operations such as adding/deleting edges. We then utilize deep reinforcement learning to learn the strategy to effectively perform the rewiring operations. Experiments on real-world graphs demonstrate the effectiveness of the proposed framework. To understand the proposed framework, we further analyze how its generated perturbation impacts the target model and the advantages of the rewiring operations. The implementation of the proposed framework is available at

Original languageEnglish (US)
Title of host publicationKDD 2021 - Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
PublisherAssociation for Computing Machinery
Number of pages9
ISBN (Electronic)9781450383325
StatePublished - Aug 14 2021
Event27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021 - Virtual, Online, Singapore
Duration: Aug 14 2021Aug 18 2021

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining


Conference27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2021
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems


  • adversarial attack
  • graph neural networks
  • rewiring


Dive into the research topics of 'Graph Adversarial Attack via Rewiring'. Together they form a unique fingerprint.

Cite this