Graph neural networks (GNNs) have seen tremendous success in recent years, leading to their widespread adoption in a variety of applications. However, recent studies have demonstrated that GNNs can be vulnerable to adversarial attacks. Adversarial attacks allow adversaries to manipulate GNNs by introducing small, seemingly harmless perturbations to the input data, which can lead to misclassification or unexpected behavior from the GNN. Such attacks can have drastic impacts on security and privacy, particularly in safety-critical or privacy-sensitive applications. Consequently, research into adversarial attacks on GNNs is becoming increasingly important, and we thus propose an adversarial attack framework that discovers continuous latent representations of graphs to which adversarial modifications are added, instead of modifying a benign graph itself.
1. Generating Attack with Surrogate Model
Figure 2: From "Adversarial Attacks on Graph Classification via Bayesian Optimisation"; a visualization of the attack generation procedure.
Generating Attack with Surrogate Model on Graphs is a method used to find the most effective attacks on graphs using machine learning algorithms. The main goal is to learn a surrogate model from the data of the graph, and then use the generated model to simulate attack scenarios and search for the most effective attack strategy. This technique can be especially useful for cyber-security applications, such as identifying potential weaknesses in networks or finding malicious pathways in a graph.
2. Generating Adversarial Example with WGAN
Figure 3: From "Generating Natural Adversarial Example"; A visualization of the Wasserstein GAN procedure.
This approach is a novel method for generating natural adversarial examples, which are inputs that can fool state-of-the-art machine learning models while being imperceptible to human observation. Its architecture is comprised of an inverter, which maps from the data space to the latent space, a generator, which is trained to be part of a Wasserstein GAN and maps from the latent space to the data space, and a search algorithm, which explores the latent space for representations of adversarial examples.
Figure 4: From "Generating Natural Adversarial Example"; A visualization of the Graph2Vec structure.
Graph2Vec is a machine learning method that embeds a graph of arbitrary size into Euclidean space. We intend to first pass graphs to Graph2Vec and then pass the resulting vectors to the inverter.
Inverter: Graph2Vec/GAM + MLP
1. New Training Procedure for GraphRNN
Originally, GraphRNN is trained by comparing the generated padded adjacency vector with the sequenced original adjacency matrix using binary cross entropy loss. This isn't ideal for the WGAN training procedure, where the generator needs to be trained by the discriminator's output, which is no longer an adjacency matrix.
For our new training process for the GraphRNN, we revert the output of node-level and edge-level RNN models to batches of generated adjacency matrices; then we pass these adjacency matrices into the discriminator network, whose output is used in our Wasserstein loss function. We will use this loss to update the node-level and edge-level RNN model parameters.
2. Observation on the three Losses
With our proposed WGAN training regime, we trained the generator, the discriminator, and the inverter, all in one training loop. We recorded the loss of each of the models every epoch.
We found that as the discriminator loss improves overtime, the generator loss and inverter loss quickly hits a threshold and cannot improve further beyond this point. This can be an indication that the new training regime isn't suitable for GraphRNN training, and the quality of our generated graphs is not good enough support the training of the discriminator and inverter.
1. Previous work and time constraint
There isn’t much research done in generating latent representations of adversarial examples, especially not for the task of attacking graph classifiers, so we had to implement our ideas from the ground up. Also, the time frame for this project is 10 weeks, which is very little time to fully develop this framework and run experiments.
2. GraphRNN output during training is difficult to interpret and process by the discriminator
The output of GraphRNN is a graph of almost arbitrary size. However, in practice, the GraphRNN implementation returned batched and packed versions of the original graph adjacency vector, which made every version of the discriminator fail to compute.
3. Lack of networkx integration in PyTorch/PyTorch Geometric
The procedure of computing high-quality graph features (e.g. clustering coefficient) is too complex for us to implement with solely PyTorch functions, so we relied on NetworkX functions to do these computations. This became an issue during the training of GraphRNN because NetworkX functions are incompatible with the way PyTorch computes gradients, which means that gradient descent cannot happen. We resorted to using a simple multi-layer perceptron as our discriminator, which takes as input flattened and padded adjacency matrices, but flattening and padding adjacency matrix loses structural information.
If we continue this research project, we want to do the following:
1. Improve implementation of GraphRNN
Due to a lack of time, we did not thoroughly investigate the GraphRNN implementation and treated the model as a black box. We encountered many issues related to loading the data, model training, and graph generation using the official implementation. As we were troubleshooting the model, we noticed that the implementation is incompatible with downstream processing of GraphRNN outputs. We would have liked more time to edit GraphRNN’s implementation to be more compatible with other tasks.
2. Use a graph classifier as our discriminator instead of a simple multi-layer perceptron
Currently, the discriminator is a simple MLP that takes in flattened and padded adjacency matrices. The discriminator is trained by the negative Wasserstein distance between the generated distribution and the real data distribution. However, because reshaping adjacency matrices caused a loss of structural information, we would have preferred to use a model that could process a graph without reshaping operations.
After evaluating the result of the current setup, we think a simple MLP can't take into account specific graph properties, and thus cannot accurately discern between the two distributions. We propose to substitute this MLP with a Graph Attention Machine (GAM) classifier, because GAM can utilize the Weisfeiler-Lehman kernel to capture graph features to discern between the real and the generated distributions. Ideally, this will provide high quality loss for the discriminator training and the generator training.