Deep learning models for graphs have advanced the state of the art on many tasks. Despite their recent success, little is known about their robustness. We investigate training time attacks on graph neural networks for node classification that perturb the discrete graph structure.   Our core principle is to use meta-gradients to solve the bilevel problem underlying training-time attacks, essentially treating the graph as a hyperparameter to optimize. Our experiments show that small graph perturbations consistently lead to a strong decrease in performance for graph convolutional networks, and even transfer to unsupervised embeddings. Remarkably, the perturbations created by our algorithm can misguide the graph neural networks such that they perform worse than a simple baseline that ignores all relational information. Our attacks do not assume any knowledge about or access to the target classifiers. Graphs are a powerful representation that can model diverse data from virtually any domain, such as biology (protein interaction networks), chemistry (molecules), or social networks (Facebook). Not surprisingly, machine learning on graph data has a longstanding history, with tasks ranging from node classification, over community detection, to generative modeling.In this paper, we study node classification, which is an instance of semi-supervised classification: given a single (attributed) network and a subset of nodes whose class labels are known (e.g., the topic of a paper in a citation graph), the goal is to infer the classes of the unlabeled nodes. While there exist many classical approaches to node classification (London & Getoor, 2014; Chapelle et al., 2006) , recently deep learning on graphs has gained much attention BID7 Bojchevski & Günnemann, 2018a; BID2 BID11 Bojchevski et al., 2018; Klicpera et al., 2019) . Specifically, graph convolutional approaches (Kipf & Welling, 2017; BID12 have improved the state of the art in node classification.However, recent works have also shown that such approaches are vulnerable to adversarial attacks both at test time (evasion) as well as training time (poisoning attacks) BID18 Dai et al., 2018) . A core strength of models using graph convolution -exploiting the information in a node's neighborhood to improve classification -is also a major vulnerability: because of these propagation effects, an attacker can change a single node's prediction without even changing any of its attributes or edges. This is because the foundational assumption that all samples are independent of each other does not hold for node classification. Network effects such as homophily (London & Getoor, 2014) support the classification, while on the other hand they enable indirect adversarial attacks.So far, all existing attacks on node classification models are targeted, that is, aim to provoke misclassification of a specific single node, e.g. a person in a social network. In this work, we propose the first algorithm for poisoning attacks that is able to compromise the global node classification performance of a model. We show that even under restrictive attack settings and without access to the target classifier, our attacks can render it near-useless for use in production (i.e., on test data).Our approach is based on the principle of meta learning, which has traditionally been used for hyperparameter optimization BID4 , or, more recently, few-shot learning (Finn et al., 2017) . In essence, we turn the gradient-based optimization procedure of deep learning models upside down and treat the input data -the graph at hand -as a hyperparameter to learn. We propose an algorithm for training-time adversarial attacks on (attributed) graphs, focusing on the task of node classification. We use meta-gradients to solve the bilevel optimization problem underlying the challenging class of poisoning adversarial attacks. Our experiments show that attacks created using our meta-gradient approach consistently lead to a strong decrease in classification performance of graph convolutional models and even transfer to unsupervised models. Remarkably, even small perturbations to a graph based on our approach can lead to graph neural networks performing worse than a baseline ignoring all relational information. We further propose approximations of the metagradients that are less expensive to compute and, in many cases, have a similarly destructive impact on the training of node classification models. While we are able to show small statistical differences of adversarial and 'normal' edges, it is still an open question what makes the edges inserted/removed by our algorithm so destructive, which could then be used to detect or defend against attacks.
We use meta-gradients to attack the training procedure of deep neural networks for graphs. Studies the problem of learning a better poisoned graph parameters that can maximize the loss of a graph neural network.  An algorithm to alter graph structure by adding/deleting edges so as to degrade the global performance of node classification, and the idea to use meta-learning to solve the bilevel optimization problem.