Adversarial Attacks on Link Prediction Algorithms Based on Graph Neural Networks

Wanyu Lin, Shengxiang Ji, Baochun Li

Abstract

Link prediction is one of the fundamental problems for graph- structured data. However, a number of applications of link predic- tion, such as predicting commercial ties or memberships within a criminal organization, are adversarial, with another party aiming to minimize its effectiveness by manipulating observed informa- tion about the graph. In this paper, we focus on the feasibility of mounting adversarial attacks against link prediction algorithms based on graph neural networks. We first propose a greedy heuris- tic that exploits incremental computation to find attacks against a state-of-the-art link prediction algorithm, called SEAL. We then design an efficient variant of this algorithm that incorporates the link formation mechanism and Υ-decaying heuristic theory to de- sign more effective adversarial attacks. We used real-world datasets and performed an extensive array of experiments to show that the performance of SEAL is negatively affected by a significant margin. More importantly, our experimental results have shown that our ad- versarial attacks mounted based on SEAL can be readily transferred to several existing link prediction heuristics in the literature.
BibTeX
@inproceedings{lin2020adversarial,
  author = {Wanyu Lin and Shengxiang Ji and Baochun Li},
  title = {{Adversarial Attacks on Link Prediction Algorithms Based on Graph Neural Networks}},
  booktitle = {AsiaCCS},
  year = {2020},
  doi = {10.1145/3320269.3384750},
}

Loading related content...

Figure